TY - JOUR
T1 - Algorithmic study of single-layer bus routing for high-speed boards
AU - Ozdal, Muhammet Mustafa
AU - Wong, M. D. F.
N1 - Funding Information:
Manuscript received October 7, 2004. This work was supported in part by the National Science Foundation under Grant CCR-0306244 and by an IBM Faculty Partnership Award. The preliminary version of this paper has been presented in IEEE/ACM ICCAD in November 2004. This paper was recommended by Associate Editor T. Yoshimura.
PY - 2006/3
Y1 - 2006/3
N2 - As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints anymore. In this paper, the authors 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. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are 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.
AB - As the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools cannot successfully handle these constraints anymore. In this paper, the authors 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. First, a provably optimal algorithm for routing nets with minimum-area maximum-length constraints is proposed. Then, this algorithm is extended to the case where minimum constraints are given as exact length bounds, and it is also proven that this algorithm is near-optimal. Both algorithms proposed are 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.
KW - Algorithms
KW - Design automation
KW - Physical design
KW - Routing
UR - http://www.scopus.com/inward/record.url?scp=33244484416&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2005.853685
DO - 10.1109/TCAD.2005.853685
M3 - Journal article
AN - SCOPUS:33244484416
SN - 0278-0070
VL - 25
SP - 490
EP - 503
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 3
ER -