Abstract
Redundant via insertion and line end extension employed in the post-routing stage are two well known and highly recommended techniques 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 first study the problem of redundant via insertion, and present two methods to accelerate a state-of-the-art approach (which is based on a maximum independent set (MIS) formulation) to solve it. We then consider the problem of simultaneous redundant via insertion and line end extension. We formulate the problem as a maximum weighted independent set (MWIS) problem and modify the accelerated MIS-based approach to solve it. Lastly, we investigate the problem of simultaneous redundant via insertion and line end extension 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 the MWIS-based approach to find the set of regions which violate the maximum via density rule after performing simultaneous redundant via insertion and line end extension. 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 superiorities of our approaches are all demonstrated through promising experimental results. Copyright 2006 ACM.