Paper Info
Title
Simultaneous escape routing and layer assignment for dense PCBs
Abstract
As die sizes are shrinking, and circuit complexities are increasing, the PCB routing problem becomes more and more challenging. Traditional routing algorithms can not handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. In this paper, we propose a problem decomposition that distinguishes routing within dense components from routing in the intermediate area. In particular, we propose an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. For this, we model the problem as a longest path with forbidden pairs (LPFP) problem, and propose two algorithms for it. The first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. The second is a randomized algorithm that has good scalability characteristics for large circuits. Then we use these algorithms to assign the maximal subset of planar nets to each layer, and then distribute the remaining nets at the end. We demonstrate the effectiveness of these algorithms through experiments on industrial circuits.
Year
DOI
Venue
2004
10.1109/ICCAD.2004.1382689
ICCAD
Keywords
Field
DocType
circuit complexity,network routing,printed circuit design,randomised algorithms,PCB routing problem,dense PCB,exact polynomial-time algorithm,industrial circuits,layer assignment,longest path with forbidden pairs problem,maximal planar routing solution,maximal subset,planar nets,randomized algorithm,simultaneous escape routing
Equal-cost multi-path routing,Multipath routing,Link-state routing protocol,Dynamic Source Routing,Path vector protocol,Static routing,Computer science,Parallel computing,Destination-Sequenced Distance Vector routing,Real-time computing,Routing (electronic design automation),Distributed computing
Conference
ISBN
Citations 
PageRank 
0-7803-8702-3
14
1.02
References 
Authors
7
2
Name
Order
Citations
PageRank
Muhammet Mustafa Ozdal131323.18
Martin D. F. Wong23525363.70