BoxRouter: a new global router based on box expansion and progressive ILP

ABSTRACT

In this paper, we propose a new global router, BoxRouter, powered by the concept of box expansion and progressive integer linear programming (ILP). BoxRouter first uses a simple PreRouting strategy which can predict and capture the most congested regions with high fidelity compared to the final routing. Based on progressive box expansion initiated from the most congested region, BoxRouting is performed with progressive ILP and adaptive maze routing. It is followed by an effective PostRouting step which reroutes without rip-up to obtain smooth tradeoff between wirelength and routability. Our experimental results show that BoxRouter significantly outperforms the state-of-the-art published global routers, e.g., 79% better routability than [1(with similar wirelength and 2x speedup), 4.2% less wirelength and 16x speedup than [2](with similar routability). Given the fundamental importance of routing, such dramatic improvement shall sparkle renewed interests in routing which plays a key role in nanometer design and manufacturing closure.

REFERENCES

• 1: 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]
• 2: C. Albrecht. Global Routing by New Approximation Algorithms for Multicommodity Flow. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 20, May 2001.
• 3: M. Burstein and R. Pelavin. Hierarchial Global Wiring for Custom Chip Design. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2(4), Oct 1983.
• 4: C. Chu, FLUTE: fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.696-701, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382665]
• 5: J. Cong. Challenges and opportunities for design innovations in nanometer technologies. In SRC Design Science Concept Papers, 1997.
• 6: T. E. Gbondo-Tugbawa. Chip-Scale Modeling of Pattern Dependencies in Copper Chemical Mechanical Polishing Process. In Ph.D. Thesis, Massachusetts Institute of Technology, 2002.
• 7: http://vlsicad.cs.binghamton.edu/.
• 8: http://www.diku.dk/geosteiner/.
• 9: http://www.ece.ucsb.edu/$sim$kastner/labyrinth/.
• 10: http://www.gnu.org/software/glpk/glpk.html/.
• 11: Jiang Hu , Sachin S. Sapatnekar, A timing-constrained algorithm for simultaneous global routing of multiple nets, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: J. Hu and S. Sapatnekar. A Survey On Multi-net Global Routing for Integrated Circuits. Integration, the VLSI Journal, 31, 2002.
• 13: 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]
• 14: Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639942]
• 15: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, An exact algorithm for coupling-free routing, Proceedings of the 2001 international symposium on Physical design, p.10-15, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369711]
• 16: R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh. Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 21, July 2002.
• 17: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 18: Joydeep Mitra , Peng Yu , David Z. Pan, RADAR: RET-aware detailed routing using fast lithography simulations, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065678]
• 19: Chiu-wing Sham , Evangeline F. Y. Young, Congestion prediction in early stages, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA [doi>10.1145/1053355.1053376]
• 20: R. Tian, D. F. Wong, and R. Boone. Model-Based Dummy Feature Placement for Oxide Chemical-Mechanical Polishing Manufacturability. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 20, 2001.
• 21: Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
• 22: Jurjen Westra , Chris Bartels , Patrick Groeneveld, Probabilistic congestion prediction, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981110]
• 23: Jurjen Westra , Patrick Groeneveld, Is probabilistic congestion estimation worthwhile?, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA [doi>10.1145/1053355.1053377]
• 24: J. Westra, P. Groeneveld, T. Yan, and P. H. Madden. Global Routing: Metrics, Benchmarks, and Tools. In IEEE DATC Electronic Design Process, April 2005.
• 25: Di Wu , Jiang Hu , Rabi Mahapatra, Coupling aware timing optimization and antenna avoidance in layer assignment, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055144]
• 26: Gang Xu , Li-Da Huang , David Z. Pan , Martin D. F. Wong, Redundant-via enhanced maze routing for yield improvement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120927]
• 27: http://openeda.si2.org.
• 28: http://www.cerc.utexas.edu/utda.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
VLSI, congestion, global routing