Algorithms for simultaneous escape routing and Layer assignment of dense PCBs
Authors:
- M.D.F. WongMWM.D.F. Wong
- 30 May 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 25 (8) , 1510-1522
Abstract
As die sizes are shrinking, and circuit complexities are increasing, the printed circuit board routing problem becomes more and more challenging. Traditional routing algorithms cannot handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. This paper proposes a problem decomposition that distinguishes routing under dense components from routing in the intermediate area. In particular, it proposes 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, the problem is modeled as a longest path with forbidden pairs problem, and two algorithms are proposed 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, these algorithms are used to assign the maximal subset of planar nets to each layer, and then the remaining nets are distributed at the end. This paper demonstrates the effectiveness of these algorithms through experiments on industrial circuits.Keywords
This publication has 12 references indexed in Scilit:
- A provably good algorithm for high performance bus routing2005
- A two-layer bus routing algorithm for high-speed boards2004
- First- and second-level packaging of the z990 processor cageIBM Journal of Research and Development, 2004
- Length-matching routing for high-speed printed circuit boards2003
- An algorithm for simultaneous pin assignment and routing2002
- Land grid array sockets for server applicationsIBM Journal of Research and Development, 2002
- First- and second-level packaging for the IBM eServer z900IBM Journal of Research and Development, 2002
- On the k-layer planar subset and topological via minimization problemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- An Approach to Topological Pin AssignmentIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1984
- Pin assignment in automated printed circuit board design1972