Abstract
Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we studied the problem of simultaneous double via insertion and wire bending (DVI/WB) in a postrouting stage, where a single via can have at most one redundant via inserted next to it. Aside from this, we are allowed to bend existing signal wires for enhancing the insertion rate of double vias. The primary goal of the DVI/WB problem is to insert as many double vias as possible; the secondary objective is to minimize the amount of layout perturbation. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We proposed algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. We also proposed a zero-one integer linear program (01 ILP)-based approach to solve the mWMIS problem. Moreover, we studied the problem of DVI/WB with the consideration of via density and extended our 01 ILP-based approach to solve it. Experimental results show that our approaches can improve the insertion rate by up to 6.34% at the expense of up to 1.29% wirelength increase when compared with the state-of-the-art double via insertion methods that do not consider wire bending. Moreover, when compared with an existing method that considers wire bending, our DVI/WB approach can insert 2% more double vias and produce 32% less wirelength increase rate on average. © 2010 IEEE.