Optimal bus sequencing for escape routing in dense PCBs

Hui Kong, Tan Yan, Martin D.F. Wong, Muhammet Mustafa Ozdal

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

Abstract

The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for high-end boards. Existing algorithms for escape routing, an important step in PCB routing, are net-centric. Directly applying these algorithms will result in mixing nets of different buses together. But in practice, it is preferred to bundle together nets in a bus. Thus the bus-centric escape routing problem can be naturally divided into two subproblems: (1) finding a subset of buses that can be routed on the same layer without net mixings and crossings, which we refer to as the bus sequencing problem, and (2) finding the escape routing solutions for each chosen bus, which can be solved by a netcentric escape router. In this paper, we solve the bus sequencing problem. We introduce a new optimization problem called the Longest Common Interval Sequence (LCIS) problem and model the bus sequencing problem as an LCIS problem. By using dynamic programming and balanced search tree data structure, we present an LCIS algorithm which can find an optimal solution in O(n log n) time. We also show that O(n log n) is a lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.

Original languageEnglish (US)
Title of host publication2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
Pages390-395
Number of pages6
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

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Optimal bus sequencing for escape routing in dense PCBs'. Together they form a unique fingerprint.

  • Cite this

    Kong, H., Yan, T., Wong, M. D. F., & Ozdal, M. M. (2007). Optimal bus sequencing for escape routing in dense PCBs. In 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD (pp. 390-395). [4397296] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2007.4397296