On using SAT to ordered escape problems
Authors:
- 1 January 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21536961,p. 594-599
Abstract
Routing for high-speed boards is largely a time-consuming manual task today. The ordered escape routing problem is one of the key problems in board-level routing, and Boolean satisfiability (SAT) based approach [1] is the only solution to this problem so far. In this paper, we first solve the major deficiency of the original SAT formulation so that the escape problem is completely resolved. Then we propose two techniques to extend SAT approach for large-scale problems. Experimental results on industrial benchmarks show that our methods perform well in terms of both speed and routability.Keywords
This publication has 6 references indexed in Scilit:
- A Network-Flow-Based RDL Routing Algorithmz for Flip-Chip DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007
- An Integer Linear Programming Based Routing Algorithm for Flip-Chip DesignProceedings of the 39th conference on Design automation - DAC '02, 2007
- Monotonic parallel and orthogonal routing for single-layer ball grid array packages2006
- Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in GridsJournal of Algorithms, 2000
- On finding non-intersecting straightline connections of grid points to the boundaryJournal of Algorithms, 1992
- Efficient algorithms for reconfiguration in VLSI/WSI arraysIEEE Transactions on Computers, 1990