A provably good algorithm for high performance bus routing
- 22 February 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 830-837
Abstract
As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools can not successfully handle these constraints any more. We focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. An effective approach to solve this problem is to allocate extra routing resources around short nets during routing; and use those resources for length extension afterwards. We first propose a provably optimal algorithm for routing nets with min-area max-length constraints. Then, we extend this algorithm to the case where minimum constraints are given as exact length bounds. We also prove that this algorithm is optimal within a constant factor. Both algorithms proposed are also shown to be scalable for large circuits, since the respective time complexities are O(A) and O(A log A), where A is the area of the intermediate region between chips.Keywords
This publication has 12 references indexed in Scilit:
- Algorithmic study of single-layer bus routing for high-speed boardsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- Length-matching routing for high-speed printed circuit boards2003
- A timing-driven global router for custom chip design2002
- Optimal river routing with crosstalk constraintsACM Transactions on Design Automation of Electronic Systems, 1998
- VPR: a new packing, placement and routing tool for FPGA research1997
- Placement and routing tools for the Triptych FPGAIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1995
- Provably good performance-driven global routingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- Chip Layout Optimization Using Critical Path Weighting1984
- River Routing: Methodology and Analysis1983
- On routing two-point nets across a channel1982