Archer: a history-driven global routing algorithm

ABSTRACT

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of-the-art global routers. It is known that concurrent global routing algorithms are typically too expensive to be applied on today's large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR) based algorithms are susceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of congestion histories. We also focus on the problem of how to enable a smooth trade-off between seemingly conflicting objectives of overflow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation based bounded-length min-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments show that Archer obtains congestion-free solutions for all circuits in the standard ISPD98 benchmarks, which is the best result published so far. Furthermore, it produces better results than the best results reported in the ISPD-07 Global Routing Contest in terms of routability. Compared to FastRoute [18, 19], which is the state-of-the-art RNR-based global routing algorithm, Archer improves routability by 30%, and reduces the wirelengths by 32% on the average on ISPD07 benchmarks.

REFERENCES

• 1: Christoph Albrecht, Provably good global routing by a new approximation algorithm for multicommodity flow, Proceedings of the 2000 international symposium on Physical design, p.19-25, May 2000, San Diego, California, United States [doi>10.1145/332357.332368]
• 2: L. Behjat and A. Vanneli. Steiner tree construction based on congestion for the global routing problem. In Proc of IEEE Int'l Workshop on System on Chip for Real-Time Applications, pages 28--31, 2003.
• 3: C. Chiang, M. Sarrafzadeh, and C. Wong. Global routing based on steiner min-max trees. IEEE Transactions on Computer Aided Design, 9(12):1318--1325, 1990.
• 4: Minsik Cho , David Z. Pan, BoxRouter: a new global router based on box expansion and progressive ILP, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147009]
• 5: Chris Chu , Yiu-Chung Wong, Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055145]
• 6: M. L. Fisher. The lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1--18, 1981.
• 7: A. M. Geoffrion. Lagrangian relaxation and its uses in integer programming. Mathematical Programming, 2:82--114, 1974.
• 8: Raia T. Hadsell , Patrick H. Madden, Improved global routing through congestion estimation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775842]
• 9: M. Hanan. On steiner's problem with rectilinear distance. SIAM Journal of Applied Mathematics, 14:255--265, 1966.
• 10: M. H. Held, P. Wolfe, and H. D. Crowder. Validation of sub-gradient optimization. Mathematical Programming, 6(1):62--88, 1974.
• 11: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Predictable routing, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: S. Lee and M. D. F. Wong. Timing-driven routing for FP-GAs based on lagrangian relaxation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 506--510, 2003.
• 13: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 14: Dirk Müller, Optimizing yield in global routing, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233598]
• 15: G.-J. Nam. ISPD 2007 Global Routing Contest, 2007.
• 16: M. M. Ozdal and M. D. F. Wong. A length-matching routing algorithm for high-performance printed circuit boards. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 25:2784--2794, 2006.
• 17: Muhammet Mustafa Ozdal , Martin D. F. Wong, Length-Matching Routing for High-Speed Printed Circuit Boards, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.394, November 09-13, 2003 [doi>10.1109/ICCAD.2003.92]
• 18: Min Pan , Chris Chu, FastRoute: a step to integrate global routing into placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233596]
• 19: Min Pan , C. Chu, FastRoute 2.0: A High-quality and Efficient Global Router, Proceedings of the 2007 conference on Asia South Pacific design automation, p.250-255, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357994]