In this paper, we formulate a problem of simultaneous redundant via insertion and line end extension for via yield optimization. Our problem is more general than previous works in the sense that more than one type of line end extension is considered and the objective function to be optimized directly accounts for via yield. We present a zero-one integer linear program based approach, that is equipped with two speedup techniques, to solve the addressed problem optimally. In addition, we describe how to modify our approach to exactly solve a previous work. Extensive experimental results are shown to demonstrate the effectiveness and efficiency of our approaches.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we studied the problem ofsimultaneous 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 (0–1 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 0–1 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.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double via insertion with wire bending (DVI/WB) in a post-routing 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 goal of DVI/WB is to primarily insert as many double vias as possible and to minimize the amount of layout perturbation as the secondary objective. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We propose algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. Moreover, we also propose a zero-one integer linear program (0-1 ILP) based approach to solve mWMIS. Experimental results show that our approach can improve the insertion rate by up to 5.58% at the expense of up to 0.37% wirelengh increase when compared with a state-of-the-art double via insertion method that does not consider wire bending.