PRIM-DIJKSTRA TRADEOFFS FOR IMPROVED PERFORMANCE-DRIVEN ROUTING TREE DESIGN

Analysis of Elmore delay in distributed RC tree structures shows the i nfluence of both tree cost and tree radius on signal delay in VLSI int erconnects. We give new and efficient interconnection tree constructio ns that smoothly combine the minimum cost and the minimum radius objec tives, by combining respectively optimal algorithms due to Prim and Di jkstra. Previous ''shallow-light'' techniques [2], [3], [8], [13] are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Timing simulations for a ran ge of IC and MCM interconnect technologies show that our wirelength sa vings yield reduced signal delays when compared to shallow-light or st andard minimum spanning tree and Steiner tree routing.