Redundant Via Insertion under Timing Constraint

Chi-Wen Pan and Yu-Min Lee
Institute of Communication Engineering, National Chiao-Tung University, Taiwan


Redundant via insertion is a useful technique to alleviate the yield loss and elevate the reliability of VLSI designs. While extra visa are inserted into the design, the electronic properties of designed circuit will be altered, and the circuit timing will 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 in average, and 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.