Title :
Redundant via insertion under timing constraints
Author :
Pan, Chi-Wen ; Lee, Yu-Min
Author_Institution :
Nat. Chiao Tung Univ., Hsinchu, Taiwan
Abstract :
Redundant via insertion is a useful technique to alleviate the yield loss and elevate the reliability of VLSI designs. While extra vias are inserted into the design, the electronic properties of designed circuit might be altered, and the circuit timing might be changed and needs to be efficiently re-analyzed. Therefore, a fast timing (incremental timing) analyzer is required to assistant the redundant via insertion procedure. This work develops an efficient redundant via insertion method under timing constraints. Firstly, an effectively incremental circuit timing analysis method is developed, and the redundant via insertion task is transformed into a mixed bipartite-conflict graph matching problem. Then, the insertion problem is solved by a timing-driven minimum weighted matching algorithm. The experimental results show that the developed algorithm can achieve 3.2% extra insertion rates over the method without considering timing effects, which all redundant vias would be removed if the timing of that net does not meet the timing requirements, in average. In addition, the developed incremental timing analysis mechanism can speed up the runtime of redundant via insertion procedure under timing constraints by over 34 times in average.
Keywords :
VLSI; integrated circuit design; integrated circuit reliability; integrated circuit yield; redundancy; VLSI design reliability; designed circuit; electronic property; extra insertion rates; fast timing; incremental circuit timing analysis method; incremental timing analysis mechanism; incremental timing analyzer; mixed bipartite-conflict graph matching problem; redundant via insertion; timing constraints; timing effects; timing-driven minimum weighted matching algorithm; yield loss; Algorithm design and analysis; Capacitance; Delay; Resistance; Routing; Wire;
Conference_Titel :
Quality Electronic Design (ISQED), 2011 12th International Symposium on
Conference_Location :
Santa Clara, CA
Print_ISBN :
978-1-61284-913-3
DOI :
10.1109/ISQED.2011.5770794