research-article

Sidewinder: a scalable ILP-based router

Authors:

Igor L. MarkovAuthors Info & Claims

SLIP '08: Proceedings of the 2008 international workshop on System level interconnect prediction

Pages 73 - 80

https://doi.org/10.1145/1353610.1353625

Published: 05 April 2008 Publication History

Abstract

We propose Sidewinder, a new global router that combines pattern routing and maze routing in a novel, incremental, ILP formulation. It is the first flat ILP-based approach scalable enough to consider over 10⁴ GCells at once. Moreover, it also can be used as a component in previously proposed multi-level and progressive ILP schemes. Sidewinder is particularly good at finding routes with minimal via count, which can improve yield in sub-90nm technologies. Other innovations in our work include an ILP construction based on a dynamically-updated congestion map and the use ofC-shape routes to alleviate local congestion and improve routability. On well-known benchmarks, Sidewinder improves routed wirelength and reduces via count by over 6% compared to ILP-based BoxRouter 1.0 and 35.8% compared to DLM-based FGR 1.0. This easy-to-implement methodology is extensible to detail routing of ASICs as well as FPGAs where it can account for complex design rules and models.

References

[1]

C. Albrecht, "Global Routing by New Approximations for Multicommodity Flow," IEEE TCAD 20(5), pp. 622--632, 2001.

Digital Library

[2]

M. Burstein and R. Pelavin, "Hierarchical Wire Routing,", IEEE TCAD 2(4), pp. 223--234, 1983.

Digital Library

[3]

M. Cho and D. Z. Pan, "BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP," In Proc. DAC, pp. 373--378, 2006.

Digital Library

[4]

M. Cho, H. Xiang, R. Puri and D. Z. Pan, "Wire Density Driven Global Routing for CMP Variation and Timing," In Proc. ICCAD, pp. 487--492, 2006.

Digital Library

[5]

C. C. N. Chu and Y.-C.Wong, "Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design," In Proc. ISPD, pp. 28--35, 2005.

Digital Library

[6]

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Section 24.3: Dijkstra's algorithm, pp. 595--601.

Digital Library

[7]

R. Hadsell and P. H. Madden, "Improved Global Routing through Congestion Estimation," In DAC, pp. 28--34, 2003.

Digital Library

[8]

J. Hu and S. S. Sapatnekar, "A Survey on Multi-net Global Routing for Integrated Circuits," Integration, the VLSI Journal 31(1), pp. 1--49, 2001.

[9]

ILOG CPLEX: High-performance software for mathematical programming and optimization. http://www.ilog.com/products/cplex

[10]

ISPD 1998 Global Routing benchmark suite. http://www.ece.ucsb.edu/~kastner/labyrinth

[11]

ISPD 2007 Global Routing Contest and benchmark suite. http://www.ispd.cc/ispd07_contest.html

[12]

R. Karp, "Complexity of computer computations", In Reducibility Among Combinatorial Problems, New York: Plenum, 1972.

[13]

R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh, "Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling," IEEE TCAD 21(7), pp. 777--790, 2002.

Digital Library

[14]

G. Nam, F. Aloul, K. Sakallah and R. Rutenbar, "A comparative study of two Boolean formulations of FPGA detailed routing constraints", In Proc. ISPD, pp. 222--227, 2001.

Digital Library

[15]

M. Pan and C. Chu, "FastRoute: A Step to Integrate Global Routing into Placement," In Proc. ICCAD, pp. 464--471, 2006.

Digital Library

[16]

M. Pan and C. Chu, "FastRoute 2.0: A High-quality and Efficient Global Router," In Proc. ASP-DAC, pp. 250--255, 2007.

Digital Library

[17]

J. Roy and I. Markov, "High-performance Routing at the Nanometer Scale," In Proc. ICCAD, 2007.

Digital Library

[18]

TSMC: Silicon Success http://www.tsmc.com/download/enliterature/html-newsletter/September03/InDepth/index.html.

[19]

J. Westra, C. Bartels and P. Groeneveld, "Probabilistic Congestion Prediction," In Proc. ISPD, pp. 204--209, 2004.

Digital Library

[20]

H. Xu, R. Rutenbar and K. Sakallah, "sub-SAT: A Formulation for Relaxed Boolean Satisfiability with Applications in Routing," In Proc. ISPD, pp. 182--187, 2002.

Digital Library

Cited By

Liu GZhu YZhuang ZPei ZGan MHuang XGuo W(2024)A Robust Multilayer X-Architecture Global Routing System Based on Particle Swarm OptimizationIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2024.340796054:9(5627-5640)Online publication date: Sep-2024
https://doi.org/10.1109/TSMC.2024.3407960
Jiang JYao PZhu W(2024)Detailed-Routability-Driven Global Routing with Lagrangian-Based Rip-Up and Rerouting2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617528(363-368)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617528
Siddiqi USait S(2024)A Deterministic Concurrent-Routing Algorithm to Improve Wire Selection in FPGA Routing2024 9th International Conference on Integrated Circuits, Design, and Verification (ICDV)10.1109/ICDV61346.2024.10616485(160-165)Online publication date: 6-Jun-2024
https://doi.org/10.1109/ICDV61346.2024.10616485
Show More Cited By

Index Terms

Sidewinder: a scalable ILP-based router
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design

Recommendations

BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability

In this article, we present BoxRouter 2.0, and discuss 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 a ...
XGRouter: high-quality global router in X-architecture with particle swarm optimization

This paper presents a high-quality very large scale integration (VLSI) global router in X-architecture, called XGRouter, that heavily relies on integer linear programming (ILP) techniques, partition strategy and particle swarm optimization (PSO). A new ...
Area-I/O flip-chip routing for chip-package co-design considering signal skews

The area-input/output (I/O) flip-chip package provides a high chip-density solution to the demand of more I/Os in very large scale integration designs; it can achieve smaller package size, shorter wirelength, and better signal and power integrity. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SLIP '08: Proceedings of the 2008 international workshop on System level interconnect prediction

April 2008

104 pages

ISBN:9781595939180

DOI:10.1145/1353610

General Chair:
Ion Mandoiu
University of Connecticut, USA
,
Program Chair:
Andrew Kennings
University of Waterloo, Canada

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 April 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SLIP08

Sponsor:

SLIP08: International Workshop on System Level Interconnect Prediction

April 5 - 8, 2008

Newcastle, United Kingdom

Acceptance Rates

Overall Acceptance Rate 6 of 8 submissions, 75%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
222
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu GZhu YZhuang ZPei ZGan MHuang XGuo W(2024)A Robust Multilayer X-Architecture Global Routing System Based on Particle Swarm OptimizationIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2024.340796054:9(5627-5640)Online publication date: Sep-2024
https://doi.org/10.1109/TSMC.2024.3407960
Jiang JYao PZhu W(2024)Detailed-Routability-Driven Global Routing with Lagrangian-Based Rip-Up and Rerouting2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617528(363-368)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617528
Siddiqi USait S(2024)A Deterministic Concurrent-Routing Algorithm to Improve Wire Selection in FPGA Routing2024 9th International Conference on Integrated Circuits, Design, and Verification (ICDV)10.1109/ICDV61346.2024.10616485(160-165)Online publication date: 6-Jun-2024
https://doi.org/10.1109/ICDV61346.2024.10616485
Qi ZHu SPeng QYou HHan CZhu Z(2024)A High Performance Detailed Router Based on Integer Programming with Adaptive Route Guides2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC58780.2024.10473934(975-980)Online publication date: 22-Jan-2024
https://doi.org/10.1109/ASP-DAC58780.2024.10473934
Yao PZhang PZhu W(2023)Pathfinding Model and Lagrangian-Based Global Routing2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247969(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247969
Liu JYoung E(2023)EDGE: Efficient DAG-based Global Routing Engine2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247702(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247702
Kundu SRoy SMukherjee S(2022)Congestion-Aware Rectilinear Steiner Tree Construction Using PB-SATJournal of Circuits, Systems and Computers10.1142/S021812662250165131:09Online publication date: 5-Mar-2022
https://doi.org/10.1142/S0218126622501651
Zapletina MZheleznikov D(2022)The Acceleration Techniques for the Modified Pathfinder Routing Algorithm on an Island-Style FPGA2022 Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus)10.1109/ElConRus54750.2022.9755536(920-923)Online publication date: 25-Jan-2022
https://doi.org/10.1109/ElConRus54750.2022.9755536
Kahng ALienig JMarkov IHu JKahng ALienig JMarkov IHu J(2022)Global RoutingVLSI Physical Design: From Graph Partitioning to Timing Closure10.1007/978-3-030-96415-3_5(131-169)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-030-96415-3_5
Tang HLiu GChen XXiong N(2020)A Survey on Steiner Tree Construction and Global Routing for VLSI DesignIEEE Access10.1109/ACCESS.2020.29861388(68593-68622)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2986138
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents