MathSciDoc: An Archive for Mathematician ∫

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

No keywords uploaded!