Post-Routing Redundant Via Insertion and Line End Extension with Via Density Consideration
- 1 November 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10923152,p. 633-640
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 resultsKeywords
This publication has 13 references indexed in Scilit:
- Yield-preferred via insertion based on novel geotopological technology2006
- Post-routing redundant via insertion for yield/reliability improvement2006
- Redundant-via enhanced maze routing for yield improvement2005
- DFM: linking design and manufacturing2005
- Physical CAD changes to incorporate design for lithography and manufacturability2005
- Embedded tutorial I2005
- Targeted Layout Modifications for Semiconductor Yield/Reliability EnhancementIEEE Transactions on Semiconductor Manufacturing, 2004
- Guest Editors' Introduction: Design for Yield and ReliabilityIEEE Design & Test of Computers, 2004
- Fixing antenna problem by dynamic diode dropping and jumper insertion2002
- The R*-tree: an efficient and robust access method for points and rectangles1990