Untangling twisted nets for bus routing

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

Abstract

Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

Original languageEnglish (US)
Title of host publication2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
Pages396-400
Number of pages5
DOIs
StatePublished - Dec 1 2007
Event2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, United States
Duration: Nov 4 2007Nov 8 2007

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Other

Other2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
CountryUnited States
CitySan Jose, CA
Period11/4/0711/8/07

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Cite this

Yan, T., & Wong, M. D. F. (2007). Untangling twisted nets for bus routing. In 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD (pp. 396-400). [4397297] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2007.4397297