TY - JOUR
T1 - A length-matching routing algorithm for high-performance printed circuit boards
AU - Ozdal, Muhammet Mustafa
AU - Wong, Martin D. F.
N1 - Funding Information:
Manuscript received March 24, 2006. This work was supported in part by the National Science Foundation under Grants CCR-0306244 and in part by an IBM Faculty Partnership Award. This paper was recommended by Associate Editor S. Sapatnekar.
PY - 2006/12
Y1 - 2006/12
N2 - As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. Therefore, it becomes important to route the nets within tight minimum and maximum length bounds. Although the problem of routing nets to satisfy maximum length constraints is a well-studied problem, there exists no sophisticated algorithm in literature that ensures that minimum length constraints are also satisfied. In this paper, the authors propose a novel algorithm that effectively incorporates the min-max length constraints into the routing problem. The approach is to use a Lagrangian-relaxation (LR) framework to allocate extra routing resources around nets simultaneously during routing them. The authors also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Their routing algorithm automatically prioritizes resource allocation for shorter nets and length minimization for longer nets so that all nets can satisfy their min-max length constraints. This paper demonstrates that this algorithm is effective even in the cases where length constraints are tight, and the spacing between adjacent nets is small.
AB - As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. Therefore, it becomes important to route the nets within tight minimum and maximum length bounds. Although the problem of routing nets to satisfy maximum length constraints is a well-studied problem, there exists no sophisticated algorithm in literature that ensures that minimum length constraints are also satisfied. In this paper, the authors propose a novel algorithm that effectively incorporates the min-max length constraints into the routing problem. The approach is to use a Lagrangian-relaxation (LR) framework to allocate extra routing resources around nets simultaneously during routing them. The authors also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Their routing algorithm automatically prioritizes resource allocation for shorter nets and length minimization for longer nets so that all nets can satisfy their min-max length constraints. This paper demonstrates that this algorithm is effective even in the cases where length constraints are tight, and the spacing between adjacent nets is small.
KW - Algorithms
KW - Lagrangian relaxation
KW - Printed circuit board (PCB)
KW - Routing
KW - Very large scale integration (VLSI)
UR - http://www.scopus.com/inward/record.url?scp=33845635280&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2006.882584
DO - 10.1109/TCAD.2006.882584
M3 - Journal article
AN - SCOPUS:33845635280
SN - 0278-0070
VL - 25
SP - 2784
EP - 2793
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 - 12
ER -