Using SAT to ordered escape problems

Lijuan Luo, Martin D.F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 (US)
Title of host publicationProceedings of the ASP-DAC 2009
Subtitle of host publicationAsia and South Pacific Design Automation Conference 2009
Pages594-599
Number of pages6
DOIs
Publication statusPublished - Apr 20 2009
EventAsia and South Pacific Design Automation Conference 2009, ASP-DAC 2009 - Yokohama, Japan
Duration: Jan 19 2009Jan 22 2009

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

OtherAsia and South Pacific Design Automation Conference 2009, ASP-DAC 2009
CountryJapan
CityYokohama
Period1/19/091/22/09

ASJC Scopus subject areas

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

Cite this

Luo, L., & Wong, M. D. F. (2009). Using SAT to ordered escape problems. In Proceedings of the ASP-DAC 2009: Asia and South Pacific Design Automation Conference 2009 (pp. 594-599). [4796545] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2009.4796545