research-article

A parallel integer programming approach to global routing

Authors:

Tai-Hsuan Wu,

Azadeh Davoodi,

Jeffrey T. LinderothAuthors Info & Claims

DAC '10: Proceedings of the 47th Design Automation Conference

Pages 194 - 199

https://doi.org/10.1145/1837274.1837323

Published: 13 June 2010 Publication History

Get Access

Abstract

We propose a parallel global routing algorithm that concurrently processes routing subproblems corresponding to rectangular subregions covering the chip area. The algorithm uses at it core an existing integer programming (IP) formulation---both for routing each subproblem and for connecting them. Concurrent processing of the routing subproblems is desirable for effective parallelization. However, achieving no (or low) overflow global routing solutions without strong, coordinated algorithmic control is difficult. Our algorithm addresses this challenge via a patching phase that uses IP to connect partial routing solutions. Patching provides feedback to each routing subproblem in order to avoid overflow, later when attempting to connect them. The end result is a flexible and highly scalable distributed algorithm for global routing. The method is able to accept as input target runtimes for its various phases and produce high-quality solution within these limits. Computational results show that for a target runtime of 75 minutes, running on a computational grid of few hundred CPUs with 2GB memory, the algorithm generates higher quality solutions than competing methods in the open literature.

References

[1]

Y.-J. Chang, et al. NTHU-route 2.0: A fast and stable global router. ICCAD, 2008.

Digital Library

Google Scholar

[2]

H.-Y. Chen, et al. High-performance global routing with fast overflow reduction. ASPDAC, 2009.

Digital Library

Google Scholar

[3]

M. Cho, et al. Boxrouter 2.0: architecture and implementation of a hybrid and robust global router. ICCAD, 2007.

Digital Library

Google Scholar

[4]

C. Chu, et al. Flute: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design. TCAD, 27(1), 2008.

Digital Library

Google Scholar

[5]

J. Desrosiers, et al. A primer in column generation. In Column Generation, chapter 1. Springer, 2005.

Crossref

Google Scholar

[6]

J. T. Linderoth. Topics in Parallel Integer Optimization. PhD thesis, Georgia Institute of Technology, 1998.

Digital Library

Google Scholar

[7]

J. A. Roy, et al. High-performance routing at the nanometer scale. ICCAD, 2007.

Digital Library

Google Scholar

[8]

T.-H. Wu, et al. GRIP: Scalable 3D global routing using integer programming. DAC, 2009.

Digital Library

Google Scholar

[9]

Y. Xu, et al. Computational experience with a software framework for parallel integer programming. INFORMS Journal on Computing, 23:383--397, 2009.

Digital Library

Google Scholar

[10]

Y. Xu, et al. Fastroute 4.0: global router with efficient via minimization. ASPDAC, 2009.

Digital Library

Google Scholar

Cited By

View all

Liu SPu YLiao PWu HZhang RChen ZLv WLin YYu B(2023)FastGR: Global Routing on CPU–GPU With Heterogeneous Task Graph SchedulerIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321766842:7(2317-2330)Online publication date: Jul-2023
https://doi.org/10.1109/TCAD.2022.3217668
He JAgarwal UYang YManohar RPingali K(2022)SPRoute 2.0: A detailed-routability-driven deterministic parallel global router with soft capacity2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC52403.2022.9712557(586-591)Online publication date: 17-Jan-2022
https://doi.org/10.1109/ASP-DAC52403.2022.9712557
Agarwalla MSarma MSarma K(2021)A High Performance Global Routing Algorithm on Julia Parallel Computing PlatformWSEAS TRANSACTIONS ON COMPUTER RESEARCH10.37394/232018.2021.9.129(103-108)Online publication date: 10-Aug-2021
https://doi.org/10.37394/232018.2021.9.12
Show More Cited By

Index Terms

A parallel integer programming approach to global routing
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Integer Linear Programming Models for Global Routing

Modern integrated circuit design involves the layout of circuits consisting of millions of switching elements or transistors. Due to the sheer complexity of the problem, optimizing the connectivity between transistors is very difficult. The circuit ...
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

In this paper, we consider problem (P) of minimizing a quadratic function q(x)=xtQx+ctx of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective ...
An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '10: Proceedings of the 47th Design Automation Conference

June 2010

1036 pages

ISBN:9781450300025

DOI:10.1145/1837274

General Chair:
Sachin Sapatnekar
Univ. of Minnesota, Minneapolis, MN

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations

Conference

DAC '10

Sponsor:

EDAC
SIGDA

DAC '10: The 47th Annual Design Automation Conference 2010

June 13 - 18, 2010

California, Anaheim

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
257
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu SPu YLiao PWu HZhang RChen ZLv WLin YYu B(2023)FastGR: Global Routing on CPU–GPU With Heterogeneous Task Graph SchedulerIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321766842:7(2317-2330)Online publication date: Jul-2023
https://doi.org/10.1109/TCAD.2022.3217668
He JAgarwal UYang YManohar RPingali K(2022)SPRoute 2.0: A detailed-routability-driven deterministic parallel global router with soft capacity2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC52403.2022.9712557(586-591)Online publication date: 17-Jan-2022
https://doi.org/10.1109/ASP-DAC52403.2022.9712557
Agarwalla MSarma MSarma K(2021)A High Performance Global Routing Algorithm on Julia Parallel Computing PlatformWSEAS TRANSACTIONS ON COMPUTER RESEARCH10.37394/232018.2021.9.129(103-108)Online publication date: 10-Aug-2021
https://doi.org/10.37394/232018.2021.9.12
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
Agarwalla MSarma MSarma K(2019)Implementation of a Modified Global Routing Algorithm on a High-throughput Parallel Environment2019 2nd International Conference on Innovations in Electronics, Signal Processing and Communication (IESC)10.1109/IESPC.2019.8902369(273-278)Online publication date: Mar-2019
https://doi.org/10.1109/IESPC.2019.8902369
He JBurtscher MManohar RPingali K(2019)SPRoute: A Scalable Parallel Negotiation-based Global Router2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD45719.2019.8942105(1-8)Online publication date: Nov-2019
https://doi.org/10.1109/ICCAD45719.2019.8942105
Tumelero DBontorin GReis R(2015)Overhead for independent net approach for Global Routing2015 IEEE 6th Latin American Symposium on Circuits & Systems (LASCAS)10.1109/LASCAS.2015.7250454(1-4)Online publication date: Feb-2015
https://doi.org/10.1109/LASCAS.2015.7250454
Liu WPeng ZWang TChang Y(2014)A resource-level parallel approach for global-routing-based routing congestion estimation and a method to quantify estimation accuracyProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691445(389-396)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691445
Wei YSze CViswanathan NLi ZAlpert CReddy LHuber ATellez GKeller DSapatnekar S(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
https://dl.acm.org/doi/10.1145/2566663
Han YAncajas DChakraborty KRoy S(2014)Exploring High-Throughput Computing Paradigm for Global RoutingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2012.223448922:1(155-167)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1109/TVLSI.2012.2234489
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Integer Linear Programming Models for Global Routing

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

An efficient compact quadratic convex reformulation for general integer quadratic programs