Redundant-via enhanced maze routing for yield improvement

ABSTRACT

Redundant via insertion is a good solution to reduce the yield loss by via failure. However, the existing methods are all post-layout optimizations that insert redundant via after detailed routing. In this paper, we propose the first routing algorithm that considers feasibility of redundant via insertion in the detailed routing stage. Our routing problem is formulated as maze routing with redundant via constraints. The problem is transformed to a multiple constraint shortest path problem, and solved by Lagrangian relaxation technique. Experimental results show that our algorithm can find routing layout with much higher rate of redundant via than conventional maze routing.

REFERENCES

• 1: Louis K. Scheffer, Physical CAD changes to incorporate design for lithography and manufacturability, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.768-773, January 27-30, 2004, Yokohama, Japan
• 2: Guest Editors' Introduction: Design for Yield and Reliability, IEEE Design & Test, v.21 n.3, p.177-182, May 2004 [doi>10.1109/MDT.2004.12]
• 3: TSMC Symposium 2004.
• 4: G. A. Allan and A. J. Walto, "Automated redundant via placement for increased yield and reliability", Proc of SPIE, vol 3216, pp 114--125, 1997.
• 5: Hardy Kwok-Shing Leung, Advanced routing in changing technology landscape, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640027]
• 6: Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
• 7: Crosstalk-Constrained Maze Routing Based on Lagrangian Relaxation, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.628, October 12-15, 1997
• 8: Li-Da Huang , Martin D. F. Wong, Optical proximity correction (OPC): friendly maze routing, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996622]