Abstract
Redundant via insertion employed in the postrouting stage is a well known and highly recommended technique to reduce yield loss due to via failure. However, if the amount of inserted redundant vias is not well controlled, it could violate via density rules and adversely worsen the yield and reliability of the design. In this paper, we investigate the problem of redundant via insertion subject to the maximum via density rule, and present a two-stage approach for it. In the first stage, we ignore the maximum via density rule, and enhance a state-of-the-art approach (which is based on a maximum independent set (MIS) formulation) to find the set of regions which violate the maximum via density rule after performing redundant via insertion. In the second stage, excess redundant vias are removed from those violating regions such that after the removal, the maximum via density rule is met while the total amount of redundant vias removed is minimized. This density-aware redundant via removal problem is formulated as a set of zero-one integer linear programming (0- 1 ILP) problems each of which can be solved independently without sacrificing the optimality. The superiority of our approach is demonstrated through promising experimental results.