Paper Info
Title
A provably good algorithm for high performance bus routing
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.
Year
DOI
Venue
2004
10.1109/ICCAD.2004.1382690
ICCAD
Keywords
Field
DocType
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
Multipath routing,Link-state routing protocol,Equal-cost multi-path routing,Dynamic Source Routing,Static routing,Computer science,Enhanced Interior Gateway Routing Protocol,Destination-Sequenced Distance Vector routing,Algorithm,Real-time computing,Distance-vector routing protocol
Conference
ISBN
Citations 
PageRank 
0-7803-8702-3
8
0.82
References 
Authors
12
2
Name
Order
Citations
PageRank
Muhammet Mustafa Ozdal131323.18
Martin D. F. Wong23525363.70