Efficient and optimal post-layout double-cut via insertion by network relaxation and min-cost maximum flow

As VLSI design complexity is continuously increasing, the yield loss due to via failure becomes more significant. Adding a redundant via adjacent to each single via is a well-known and highly recommended method to reduce yield loss due to via failure. In this paper, we develop a network-flow-based algorithm in post-layout stage for the redundant via insertion problem. With our novel and efficient approach, we can obtain optimal redundant via insertion solution in improving the manufacturing yield, with minimal fixup if necessary. Moreover, our approach is parallel-processing-friendly and effective in ECO incremental solution due to the nature of network-flow models.