skip to main content
10.5555/1326073.1326176acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
research-article

BoxRouter 2.0: architecture and implementation of a hybrid and robust global router

Published: 05 November 2007 Publication History

Abstract

In this paper, we present BoxRouter 2.0, a hybrid and robust global router with discussion on its architecture and implementation. As high performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose BoxRouter 2.0 which has strong ability to improve routability and minimize the number of vias with blockages, while minimizing wirelength. BoxRouter 2.0 is improved over [1], but can perform multi-layer routing with 2D global routing and layer assignment. Our 2D global routing is equipped with two ideas: robust negotiation-based A* search for routing stability, and topology-aware wire ripup for flexibility. After 2D global routing, 2D-to-3D mapping is done by the layer assignment which is powered by progressive via/blockage-aware integer linear programming. Experimental results show that BoxRouter 2.0 has better routability with comparable wirelength than other routers on ISPD07 benchmark, and it can complete (no overflow) ISPD98 benchmark for the first time in the literature with the shortest wirelength.

References

[1]
M. Cho and D. Z. Pan, "BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP," in Proc. Design Automation Conf., July 2006.
[2]
International Technology Roadmap for Semiconductors (ITRS), 2006.
[3]
J. Cong, "Challenges and opportunities for design innovations in nanometer technologies," in SRC Design Science Concept Papers, 1997.
[4]
R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, "An Exact Algorithm for Coupling-Free Routing," in Proc. Int. Symp. on Physical Design, Apr 2001.
[5]
D. Wu, J. Hu, and R. Mahapatra, "Coupling Aware Timing Optimization and Antenna Avoidance in Layer Assignment," in Proc. Int. Symp. on Physical Design, Apr 2005.
[6]
J. Hu and S. Sapatnekar, "A Survey On Multi-net Global Routing for Integrated Circuits," Integration, the VLSI Journal, vol. 31, no. 1, pp. 1--49, 2002.
[7]
J. Hu and S. Sapatnekar, "A Timing-Constrained Algorithm for Simultaneous Global Routing of Multiple Nets," in Proc. Int. Conf. on Computer Aided Design, Nov 2000.
[8]
J. Westra, P. Groeneveld, T. Yan, and P. H. Madden, "Global Routing: Metrics, Benchmarks, and Tools," in IEEE DATC Electronic Design Process, Apr 2005.
[9]
T. Kutzschebauch and L. Stok, "Congestion aware layout driven logic synthesis," in Proc. Int. Conf. on Computer Aided Design, Nov 2001.
[10]
H. Wenting, Y. Hong, H. Xianlong, C. Y. W. Weimin, G. J. Gu, and W. Kao, "A new congestion-driven placement algorithm based on cell inflation," in Proc. Asia and South Pacific Design Automation Conf., Jan 2001.
[11]
U. Brenner and A. Rohe, "An Effective Congestion-Driven Placement Framework," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, 2003.
[12]
M. Burstein and R. Pelavin, "Hierarchical Wire Routing," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 2, no. 4, pp. 223--234, Oct 1983.
[13]
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, vol. 21, no. 7, pp. 777--790, July 2002.
[14]
R. T. Hadsell and P. H. Madden, "Improved Global Routing through Congestion Estimation," in Proc. Design Automation Conf., Jun 2003.
[15]
C. Albrecht, "Global Routing by New Approximation Algorithms for Multicommodity Flow," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 5, pp. 622--632, May 2001.
[16]
M. Pan and C. Chu, "FastRoute: A Step to Integrate Global Routing into Placement," in Proc. Int. Conf. on Computer Aided Design, Nov 2006.
[17]
M. Pan and C. Chu, "FastRoute 2.0: A High-quality and Efficient Global Router," in Proc. Asia and South Pacific Design Automation Conf., Jan 2007.
[18]
Z. Cao, T. Jing, J. Xiong, Y. Hu, L. He, and X. Hong, "DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm," in Proc. Asia and South Pacific Design Automation Conf., Jan 2007.
[19]
R. Kay and R. A. Rutenbar, "Wire packing: A strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution," in Proc. Int. Symp. on Physical Design, 2000.
[20]
D. Wu, J. Hu, R. Mahapatra, and M. Zhao, "Layer assignment for crosstalk risk minimization," in Proc. Asia and South Pacific Design Automation Conf., Jan 2004.
[21]
M. Cho, H. Xiang, R. Puri, and D. Z. Pan, "Wire Density Driven Global Routing for CMP Variation and Timing," in Proc. Int. Conf. on Computer Aided Design, Nov 2006.
[22]
D. Wu, J. Hu, and R. Mahapatra, "Antenna avoidance in layer assignment," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, 2006.
[23]
G. Xu, L. Huang, D. Z. Pan, and D. F. Wong, "Redundant-Via Enhanced Maze Routing for Yield Improvement," in Proc. Asia and South Pacific Design Automation Conf., Jan 2005.
[24]
K.-Y. Lee and T.-C. Wang, "Post-Routing Redundant Via Insertion for Yield/Reliability Improvement," in Proc. Asia and South Pacific Design Automation Conf., Jan 2006.
[25]
http://www.ispd.cc/ispd07_contest.html.
[26]
J. Westra, C. Bartels, and P. Groeneveld, "Probabilistic Congestion Prediction," in Proc. Int. Symp. on Physical Design, Apr 2004.
[27]
J. Westra, C. Bartels, and P. Groeneveld, "Is Probabilistic Congestion Estimation Worthwhile?" in Proc. System-Level Interconnect Prediction, Apr 2005.
[28]
L. McMurchie and C. Ebeling, "PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs," in ACM Symposium on FPGAs, Feb 1995.
[29]
K. C. Chang and H. C. Du, "Layer assignment problem for three-layer routing," IEEE Trans. on Computers, vol. 37, 1988.
[30]
C.-C. Chang and J. Cong, "An efficient approach to multilayer layer assignment with an application to via minimization," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, 1999.
[31]
K. Ahn and S. Sahni, "Constrained via minimization," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, 1993.
[32]
N. Naclerio, S. Masuda, and K. Nakajima, "The via minimization problem is NP-complete," IEEE Trans. on Computers, vol. 38, 1989.
[33]
C. C. N. Chu, "FLUTE: Fast Lookup Table Based Wirelength Estimation Technique," in Proc. Int. Conf. on Computer Aided Design, Nov 2004.
[34]
http://www.ece.ucsb.edu/~kastner/labyrinth/.
[35]
http://www.diku.dk/geosteiner/.

Cited By

View all
  • (2019)Toward an Open-Source Digital FlowProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3326334(1-4)Online publication date: 2-Jun-2019
  • (2014)Techniques for scalable and effective routability evaluationACM Transactions on Design Automation of Electronic Systems10.1145/256666319:2(1-37)Online publication date: 28-Mar-2014
  • (2013)CATALYSTProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485728(1873-1878)Online publication date: 18-Mar-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design
November 2007
933 pages
ISBN:1424413826
  • General Chair:
  • Georges Gielen

Sponsors

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

  • Research-article

Conference

ICCAD07
Sponsor:

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;
Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Toward an Open-Source Digital FlowProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3326334(1-4)Online publication date: 2-Jun-2019
  • (2014)Techniques for scalable and effective routability evaluationACM Transactions on Design Automation of Electronic Systems10.1145/256666319:2(1-37)Online publication date: 28-Mar-2014
  • (2013)CATALYSTProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485728(1873-1878)Online publication date: 18-Mar-2013
  • (2013)A routing algorithm for graphene nanoribbon circuitACM Transactions on Design Automation of Electronic Systems10.1145/250505618:4(1-18)Online publication date: 25-Oct-2013
  • (2013)Delay-driven layer assignment in global routing under multi-tier interconnect structureProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451942(101-107)Online publication date: 24-Mar-2013
  • (2012)FastRouteVLSI Design10.1155/2012/6083622012(14-14)Online publication date: 1-Jan-2012
  • (2012)GLAREProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228499(768-773)Online publication date: 3-Jun-2012
  • (2012)GDRouterProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228469(597-602)Online publication date: 3-Jun-2012
  • (2012)Guiding a physical design closure system to produce easier-to-route designs with more predictable timingProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228442(465-470)Online publication date: 3-Jun-2012
  • (2012)Optimizing the antenna area and separators in layer assignment of multi-layer global routingProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160946(137-144)Online publication date: 25-Mar-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media