TY - GEN

T1 - Optimal bus sequencing for escape routing in dense PCBs

AU - Kong, Hui

AU - Yan, Tan

AU - Wong, Martin D.F.

AU - Ozdal, Muhammet Mustafa

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=50249107944&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=50249107944&partnerID=8YFLogxK

U2 - 10.1109/ICCAD.2007.4397296

DO - 10.1109/ICCAD.2007.4397296

M3 - Conference contribution

AN - SCOPUS:50249107944

SN - 1424413826

SN - 9781424413829

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

SP - 390

EP - 395

BT - 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD

T2 - 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD

Y2 - 4 November 2007 through 8 November 2007

ER -