On using SAT to ordered escape problems

Lijuan Luo, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

24 Citations (Scopus)

Abstract

Routing for high-speed boards is largely a time- consuming manual task today. The ordered escape routing problem is one of the key problems in board-level routing, and Boolean Satisfiability (SAT) based approach [1] is the only solution to this problem so far. In this paper, we first solve the major deficiency of the original SAT formulation so that the escape problem is completely resolved. Then we propose two techniques to extend SAT approach for large-scale problems. Experimental results on industrial benchmarks show that our methods perform well in terms of both speed and routability.

Original languageEnglish
Title of host publicationProceedings of the 14th Asia and South Pacific Design Automation Conference, ASP-DAC 2009
PublisherIEEE
Pages594-599
Number of pages6
ISBN (Print)9781424427482
DOIs
Publication statusPublished - 21 Jan 2009
Event14th Asia and South Pacific Design Automation Conference, ASP-DAC 2009 - Pacifico Yokohama, Yokohama, Japan
Duration: 19 Jan 200922 Jan 2009
https://www.aspdac.com/aspdac2009/ (Conference website)
https://www.aspdac.com/aspdac2009/pdf/finalprog09printnosign.pdf (Conference program )
https://ieeexplore.ieee.org/xpl/conhome/4781528/proceeding (Conference proceedings)

Publication series

NameProceedings of The Asia and South Pacific Design Automation Conference, ASP-DAC
ISSN (Print)2153-6961
ISSN (Electronic)2153-697X

Conference

Conference14th Asia and South Pacific Design Automation Conference, ASP-DAC 2009
Country/TerritoryJapan
CityYokohama
Period19/01/0922/01/09
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this