Paper Info
Title
Length-Matching Routing for High-Speed Printed Circuit Boards
Abstract
As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. So, 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 the literature that ensures that minimum length constraints are also satisfied. In this paper, we propose a novel algorithm that effectively incorporates the min-max length constraints into the routing problem. Our approach is to use a Lagrangian relaxation framework to allocate extra routing resources around nets simultaneously during routing them. We also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Our 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. Our experiments demonstrate that this algorithm is effective even in the cases where length constraints are tight, and the layout is dense.
Year
DOI
Venue
2003
10.1109/ICCAD.2003.92
Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design
Keywords
Field
DocType
printed circuit board,graph theory,lagrangian relaxation,printed circuits,resource allocation,network routing,satisfiability
Mathematical optimization,Multipath routing,Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Destination-Sequenced Distance Vector routing,Routing (electronic design automation),Routing Information Protocol
Conference
ISBN
Citations 
PageRank 
1-58113-762-1
20
1.68
References 
Authors
9
2
Name
Order
Citations
PageRank
Muhammet Mustafa Ozdal131323.18
Martin D. F. Wong23525363.70