Redundant via insertion with wire spreading capability

Redundant via insertion is a widely recommended technique to enhance the via yield and reliability. In this work, the post-routing redundant via insertion problem is transformed to a mixed bipartite-conflict graph matching problem, and an efficient minimum weighted matching algorithm is developed to solve the matching problem. The developed method not only inserts redundant vias for alive vias but also protects dead vias by utilizing the wire spreading capability - that's to say, wire segments are spread into the empty space, then, redundant vias can be inserted for dead vias to further enhance the via yield. Experimental results show that the redundant via insertion rate for alive vias can be over 99.86% on average. With only 0.104% wirelength overhead on average, the developed wire spreading technique can achieve an average redundant via insertion rate for alive dead vias of 95.61 %, and the dead via protection rate can be 21.96% on average.