DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21536961,p. 256-261
Abstract
This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30x runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing.Keywords
This publication has 9 references indexed in Scilit:
- Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design2005
- FLUTE: fast lookup table based wirelength estimation technique2005
- SSTT: Efficient local search for GSI global routingJournal of Computer Science and Technology, 2003
- Creating and exploiting flexibility in rectilinear steiner treesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003
- Pattern routing: use and theory for increasing predictability and avoiding couplingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002
- Provably good global routing by a new approximation algorithm for multicommodity flow2000
- A global router with a theoretical bound on the optimal solutionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- Global routing based on Steiner min-max treesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966