DocumentCode :
2353534
Title :
A provably good algorithm for high performance bus routing
Author :
Ozdal, Muhammet Mustafa ; Wong, Martin D E
Author_Institution :
Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
fYear :
2004
fDate :
7-11 Nov. 2004
Firstpage :
830
Lastpage :
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 :
circuit optimisation; computational complexity; minimax techniques; network routing; system buses; timing; clock frequencies; exact length bounds; extra routing resource allocation; high-performance bus routing; min-area max-length constraints; net routing; optimal algorithm; single-layer bus routing; time complexities; timing requirements; Application software; Circuits; Clocks; Computer industry; Computer science; Frequency; Resource management; Routing; Timing; Wires;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Aided Design, 2004. ICCAD-2004. IEEE/ACM International Conference on
ISSN :
1092-3152
Print_ISBN :
0-7803-8702-3
Type :
conf
DOI :
10.1109/ICCAD.2004.1382690
Filename :
1382690
Link To Document :
بازگشت