Abstract | ||
---|---|---|
The increasing clock frequencies in high-end industrial circuits bring new routing challenges that cannot be handled by traditional algorithms. An important design automation problem for high-speed boards today is routing nets within tight minimum and maximum length bounds. In this article, we propose an algorithm for routing bus structures between components on two layers such that all length constraints are satisfied. This algorithm handles length extension simultaneously during the actual routing process so that maximum resource utilization is achieved during length extension. Our approach here is to process one track at a time, and choose the best subset of nets to be routed on each track. The algorithm we propose for single-track routing is guaranteed to find the optimal subset of nets together with the optimal solution with length extension on one track. The experimental comparison with a recently proposed technique shows the effectiveness of this algorithm both in terms of solution quality and run-time. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1145/1124713.1124726 | ACM Trans. Design Autom. Electr. Syst. |
Keywords | Field | DocType |
new routing challenge,high-speed printed circuit board,min-max length constraints,traditional algorithm,best subset,length extension,single-track routing,high-speed,bus routing,maximum resource utilization,length constraint,optimal solution,maximum length bound,actual routing process,pcb,two-layer bus routing,resource utilization,printed circuit board,satisfiability,design automation | Multipath routing,Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Parallel computing,Destination-Sequenced Distance Vector routing,Real-time computing,Routing (electronic design automation),Routing Information Protocol | Journal |
Volume | Issue | ISSN |
11 | 1 | 1084-4309 |
Citations | PageRank | References |
7 | 0.67 | 15 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Muhammet Mustafa Ozdal | 1 | 313 | 23.18 |
Martin D. F. Wong | 2 | 3525 | 363.70 |