research-article

Ordered escape routing based on Boolean satisfiability

Authors:

Martin D. F. WongAuthors Info & Claims

ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference

Pages 244 - 249

Published: 21 January 2008 Publication History

Abstract

Routing for high-speed boards is largely a time-consuming manual task today. In this work we consider the ordered escape routing problem which is a key problem in board-level routing. All existing approaches to this problem cannot guarantee to find a routing solution even if one exists. We present an algorithm to exactly solve this problem based on Boolean satisfiability. Experimental results on escape routing problems from industry show that our algorithm performs well.

References

[1]

V. P. Roychowdhury, J. Bruck, and T. Kailath, "Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays", IEEE trans. on Comp., 39(4): 480--489, April 1990.

Digital Library

[2]

Y. Birk, and J. B. Lotspiech, "On Finding Non-Intersecting Straightline Connections of Grid Points to the Boundary", J. of Algorithms, 13(4): 636--656, Dec. 1992.

[3]

W.-T. Chan, and F. Y. L. Chin, "Efficient Algorithms for Finding Maximum Number of Disjoint Paths in Grids", SODA, pp. 454--463, 1997.

Digital Library

[4]

J. W. Fang, I. J. Lin, P. H. Yuh, Y. W. Chang, and J. H. Wang, "A Routing Algorithm for Flip-Chip Design," Proc. of ICCAD, pp. 753--758, 2005.

Digital Library

[5]

Y. Tomioka, and A. Takahashi, "Monotonic Parallel and Orthogonal Routing for Single-Layer Ball Grid Array Packages," Proc. of ASP-DAC, pp.642--647, 2006

Digital Library

[6]

J. W. Fang, C. H. Hsu, and Y. W. Chang, "An Integeer Linear Programming Based Routing Algorithm for Flip-Chip Design", Proc. of DAC, pp. 606--611, 2007.

Digital Library

[7]

S. Devadas, "Optimal Layout Via Boolean Satisfiability," Proc. of ACM/IEEE ICCAD, pp. 294--297, 1989.

[8]

R. G. Wood, and R. A. Rutenbar, "FPGA Routing and Routability Estimation Via Boolean Satisfiability," IEEE Trans. VLSI Systems, pp. 222--231, June 1998.

Digital Library

[9]

Gi-Joon Nam, "An Exploration of Physical Design Problems Via Boolean Satisfiability (SAT)", Ph.D forum at DAC, 1999

[10]

T. Larrabee, "Eficient Generation of Test Patterns Using Boolean Satisfiabiliy", Ph.D. Dissertation, Department of Computer Science, Stanford University, STAN-CS-90-1302, February 1990.

Digital Library

[11]

T. Larrabee, "Test Pattern Generation Using Boolean Satisfiability", IEEE Trans. on CAD, 11(1):4C15, Jan 1992.

Digital Library

[12]

H. Konuk and T. Larrabee, "Explorations of Sequential ATPG Using Boolean Satisfiability", Proc. of the 11th IEEE VLSI Test Symposium, pp. 85--90, April 1993.

[13]

P. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Combinational Test Generation Using Satisfiability," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, pp. 1167C1176, 1996.

Digital Library

[14]

M. Velev, and R. Bryant, "Effective Use of Boolean Satisfiability Procedures in the Formal Verification of Superscalar and VLIW Microprocessors," Proc. of DAC, July 2001.

Digital Library

[15]

E. Goldberg, "Practical SAT Solving: Achievements, Problems and Opportunities", Algorithms for the SAT-problem Workshop, 2006

[16]

http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/

Cited By

Chen CLin DWei RLiu QZhu ZChen JTakahashi A(2023)Efficient Global Optimization for Large Scaled Ordered Escape RoutingProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567901(535-540)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567901
Liao ZDong SMohsenin TZhao WChen YMutlu O(2020)A Constraint-Driven Compact Model with Partition Strategy for Ordered Escape RoutingProceedings of the 2020 on Great Lakes Symposium on VLSI10.1145/3386263.3406942(393-398)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1145/3386263.3406942
Kang IPark DHan CCheng CHu S(2018)Fast and precise routability analysis with conditional design rulesProceedings of the 20th System Level Interconnect Prediction Workshop10.1145/3225209.3225210(1-8)Online publication date: 23-Jun-2018
https://dl.acm.org/doi/10.1145/3225209.3225210
Show More Cited By

Index Terms

Ordered escape routing based on Boolean satisfiability
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Hardware validation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Machine Learning Based Acceleration Method for Ordered Escape Routing
GLSVLSI '21: Proceedings of the 2021 Great Lakes Symposium on VLSI

Escape routing, especially ordered escape routing, is a critical design stage for both printed circuit boards (PCBs) and integrated fan-out (InFO) wafer-level chip-scale packages. Previous works formulate ordered escape routing as boolean satisfiability (...
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiability

We present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSAT_CNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Backjumping for quantified Boolean logic satisfiability

The implementation of effective reasoning tools for deciding the satisfiability of Quantified Boolean Formulas (QBFs) is an important research issue in Artificial Intelligence. Many decision procedures have been proposed in the last few years, most of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference

January 2008

812 pages

ISBN:9781424419227

General Chair:
Chong-Min Kyung,
Program Chairs:
Kiyoung Choi,
Soonhoi Ha

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEEK: The Institute of Electronics Engineers of Korea

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 21 January 2008

Check for updates

Qualifiers

Research-article

Conference

ASPDAC '08

Sponsor:

SIGDA
IEEK

ASPDAC '08: Asia and South Pacific Design Automation Conference

January 21 - 24, 2008

Seoul, Korea

Acceptance Rates

ASP-DAC '08 Paper Acceptance Rate 122 of 350 submissions, 35%;

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
227
Total Downloads

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

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen CLin DWei RLiu QZhu ZChen JTakahashi A(2023)Efficient Global Optimization for Large Scaled Ordered Escape RoutingProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567901(535-540)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567901
Liao ZDong SMohsenin TZhao WChen YMutlu O(2020)A Constraint-Driven Compact Model with Partition Strategy for Ordered Escape RoutingProceedings of the 2020 on Great Lakes Symposium on VLSI10.1145/3386263.3406942(393-398)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1145/3386263.3406942
Kang IPark DHan CCheng CHu S(2018)Fast and precise routability analysis with conditional design rulesProceedings of the 20th System Level Interconnect Prediction Workshop10.1145/3225209.3225210(1-8)Online publication date: 23-Jun-2018
https://dl.acm.org/doi/10.1145/3225209.3225210
Jiao FDong S(2018)Ordered Escape Routing with Consideration of Differential Pair and BlockageACM Transactions on Design Automation of Electronic Systems10.1145/318578323:4(1-26)Online publication date: 9-May-2018
https://dl.acm.org/doi/10.1145/3185783
Ahmadinejad AZarrabi-Zadeh H(2017)Finding Maximum Disjoint Set of Boundary Rectangles With Application to PCB RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.258576136:3(412-420)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2585761
Yan J(2015)Length-constrained escape routing of differential pairsIntegration, the VLSI Journal10.1016/j.vlsi.2014.07.00648:C(158-169)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2014.07.006
Yan TWu PMa QWong MScheffer LPhillips JHu A(2010)On the escape routing of differential pairsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133559(614-620)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133559
Yan TWong MScheffer LPhillips JHu A(2010)Recent research development in PCB layoutProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133514(398-403)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133514
Kohira YTakahashi ALin Y(2010)CAFE routerProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899782(281-286)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1899721.1899782
Kong HMa QYan TWong MSapatnekar S(2010)An optimal algorithm for finding disjoint rectangles and its application to PCB routingProceedings of the 47th Design Automation Conference10.1145/1837274.1837326(212-217)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1837274.1837326
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