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 proceedingpeer-review

24 Citations (Scopus)

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
Title of host publicationProceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007
PublisherIEEE
Pages390-395
Number of pages6
ISBN (Print)9781424413812
DOIs
Publication statusPublished - 4 Nov 2007
Event2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007 - DoubleTree Hotel, San Jose, United States
Duration: 4 Nov 20078 Nov 2007
https://ieeexplore.ieee.org/xpl/conhome/4397222/proceeding (Conference proceedings)

Publication series

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

Conference

Conference2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007
Country/TerritoryUnited States
CitySan Jose
Period4/11/078/11/07
Internet address

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