research-article

The efficient solution of integer programs for hierarchical global routing

Authors:

J. Heisterman,

T. LengauerAuthors Info & Claims

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 10, Issue 6

Pages 748 - 753

https://doi.org/10.1109/43.137503

Published: 01 November 2006 Publication History

Abstract

Hierarchical methods for global routing are addressed. These methods break down the integer program that formulates the routing problem into small integer programs. These programs are solved exactly by using integer programming methods. Then the exact solutions of the small integer programs are pieced together to form an approximate solution of the original routing problem. The structure of the small integer programs is investigated. A greedy preprocessing method is proposed that, in effect, preroutes easily routable nets and reduces the remaining integer program to a fraction of the size in some cases, and eliminates it altogether in other cases. This yields a substantial reduction of the time required to solve the small integer programs

Cited By

View all

Xiong JHe L(2007)Full-chip multilevel routing for power and signal integrityIntegration, the VLSI Journal10.1016/j.vlsi.2005.11.00140:3(226-234)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1016/j.vlsi.2005.11.001
Chen TChang YTang T(2005)Multilevel full-chip gridless routing considering optical proximity correctionProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120930(1160-1163)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120930
Cong JXie MZhang YPileggi LKuehlmann A(2002)An enhanced multilevel routing systemProceedings of the 2002 IEEE/ACM international conference on Computer-aided design10.1145/774572.774580(51-58)Online publication date: 10-Nov-2002
https://dl.acm.org/doi/10.1145/774572.774580
Show More Cited By

The efficient solution of integer programs for hierarchical global routing
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization

Recommendations

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 ...
Extending the QCR method to general mixed-integer programs

Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with ...
Global solution of nonlinear mixed-integer bilevel programs

An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475---513, 2008). The algorithm relies on a convergent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Volume 10, Issue 6

November 2006

140 pages

ISSN:0278-0070

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 November 2006

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xiong JHe L(2007)Full-chip multilevel routing for power and signal integrityIntegration, the VLSI Journal10.1016/j.vlsi.2005.11.00140:3(226-234)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1016/j.vlsi.2005.11.001
Chen TChang YTang T(2005)Multilevel full-chip gridless routing considering optical proximity correctionProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120930(1160-1163)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120930
Cong JXie MZhang YPileggi LKuehlmann A(2002)An enhanced multilevel routing systemProceedings of the 2002 IEEE/ACM international conference on Computer-aided design10.1145/774572.774580(51-58)Online publication date: 10-Nov-2002
https://dl.acm.org/doi/10.1145/774572.774580
Lin SChang YPileggi LKuehlmann A(2002)A novel framework for multilevel routing considering routability and performanceProceedings of the 2002 IEEE/ACM international conference on Computer-aided design10.1145/774572.774579(44-50)Online publication date: 10-Nov-2002
https://dl.acm.org/doi/10.1145/774572.774579
Cong JFang JZhang YErnst R(2001)Multilevel approach to full-chip gridless routingProceedings of the 2001 IEEE/ACM international conference on Computer-aided design10.5555/603095.603178(396-403)Online publication date: 4-Nov-2001
https://dl.acm.org/doi/10.5555/603095.603178
Raman SSapatnekar SAlpert CWiesel MHill D(2000)Datapath routing based on a decongestion metricProceedings of the 2000 international symposium on Physical design10.1145/332357.332387(122-127)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/332357.332387
Liu LSechen C(1997)Multi-layer chip-level global routing using an efficient graph-based Steiner tree heuristicProceedings of the 1997 European conference on Design and Test10.5555/787260.787682Online publication date: 17-Mar-1997
https://dl.acm.org/doi/10.5555/787260.787682
Park T(1996)A Parallel Algorithm for Global Routing Using an Associative ProcessorJournal of Parallel and Distributed Computing10.1006/jpdc.1996.012838:1(51-62)Online publication date: 10-Oct-1996
https://dl.acm.org/doi/10.1006/jpdc.1996.0128
Hayashi MTsukiyama S(1995)A hybrid hierarchical approach for multi-layer global routingProceedings of the 1995 European conference on Design and Test10.5555/787258.787482Online publication date: 6-Mar-1995
https://dl.acm.org/doi/10.5555/787258.787482

Abstract

Cited By

Recommendations

An efficient compact quadratic convex reformulation for general integer quadratic programs

Extending the QCR method to general mixed-integer programs

Global solution of nonlinear mixed-integer bilevel programs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations