Provably good performance-driven global routing
- 1 June 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 11 (6) , 739-752
- https://doi.org/10.1109/43.137519
Abstract
The authors propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree formulation. The authors first present several heuristics with good performance, based on an analog of Prim's minimum spanning tree construction. Next, they give an algorithm which simultaneously minimizes both routing cost and the longest interconnection path, so that both are bounded by small constant factors away from optimal. They also show that geometry helps in routing: in the Manhattan plane, the total wire length for Steiner routing improves to 3/2*(1+(1/ epsilon )) times the optimal Steiner tree cost, while in the Euclidean plane, the total cost is further reduced to (2/ square root 3)*(1+(1/ epsilon )) times optimal. The method generalizes to the case where varying wire length bounds are prescribed for different source-sink paths. Extensive simulations confirm that this approach works well.Keywords
This publication has 18 references indexed in Scilit:
- Timing driven placementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A fast algorithm for performance-driven placementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Timing driven placement using complete path delaysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A new algorithm for standard cell global routingIntegration, 1992
- Performance-driven constructive placementPublished by Association for Computing Machinery (ACM) ,1990
- Performance-driven placement of cell based IC'sPublished by Association for Computing Machinery (ACM) ,1989
- Bounded diameter minimum spanning trees and related problemsPublished by Association for Computing Machinery (ACM) ,1989
- Chip Layout Optimization Using Critical Path WeightingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- A fast algorithm for Steiner treesActa Informatica, 1981
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976