A New Strategy for Simultaneous Escape Based on Boundary Routing
Authors:
- 17 January 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 30 (2) , 205-214
Abstract
Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.Keywords
This publication has 11 references indexed in Scilit:
- A correct network flow model for escape routing2009
- Simultaneous Escape-Routing Algorithms for Via Minimization of High-Speed BoardsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007
- A Network-Flow-Based RDL Routing Algorithmz for Flip-Chip DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007
- Layer minimization of escape routing in area array packaging2006 IEEE/ACM International Conference on Computer Aided Design, 2006
- Simultaneous escape routing and layer assignment for dense PCBs2005
- Innovative Circuit Board Level Routing Designs for BGA PackagesIEEE Transactions on Advanced Packaging, 2004
- Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in GridsJournal of Algorithms, 2000
- Via design rule consideration in multilayer maze routing algorithmsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000
- Optimal printed wiring board design for high I/O density chip size packagesCircuit World, 1999
- PathFinder1995