DocumentCode :
799224
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
Volume :
14
Issue :
7
fYear :
1995
fDate :
7/1/1995 12:00:00 AM
Firstpage :
890
Lastpage :
896
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;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/43.391737
Filename :
391737
Link To Document :
بازگشت