Title :
Prim-Dijkstra tradeoffs for improved performance-driven routing tree design
Author :
Alpert, C.J. ; Hu, T.C. ; Huang, J.H. ; Kahng, A.B. ; Karger, D.
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fDate :
7/1/1995 12:00:00 AM
Abstract :
Analysis of Elmore delay in distributed RC tree structures shows the influence of both tree cost and tree radius on signal delay in VLSI interconnects. We give new and efficient interconnection tree constructions that smoothly combine the minimum cost and the minimum radius objectives, by combining respectively optimal algorithms due to Prim (1957) and Dijkstra (1959). Previous “shallow-light” techniques are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Timing simulations for a range of IC and MCM interconnect technologies show that our wirelength savings yield reduced signal delays when compared to shallow-light or standard minimum spanning tree and Steiner tree routing
Keywords :
VLSI; circuit layout CAD; delays; integrated circuit interconnections; integrated circuit layout; multichip modules; network routing; trees (mathematics); Elmore delay; IC interconnect technologies; IC layout; MCM interconnect technologies; Prim-Dijkstra tradeoffs; VLSI interconnects; cost-radius tradeoffs; distributed RC tree structures; interconnection tree constructions; minimum cost objective; minimum radius objective; optimal algorithms; performance-driven routing tree design; signal delay; timing simulations; tree cost; tree radius; wirelength savings; Capacitance; Computer science; Costs; Delay; Integrated circuit interconnections; Routing; Signal analysis; Signal design; Tree graphs; USA Councils;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on