1993 IEEE International Symposium on Circuits and Systems · 2002 · 67 citations · 15 references
EngineeringComputer EngineeringComputer ScienceCircuit TheoryComputer NetworksInterconnection NetworksInterconnect DesignNetwork-on-chip DesignRoutingRouting AlgorithmsRouting ArchitectureShortest Path AlgorithmsDijkstra's AlgorithmGlobal RoutingInterconnect RoutingMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ConstructionMultichip ModulesShortest Path TreesWirelength Optimization
Motivated by analysis of distributed RC delay in routing trees, a new tree construction is proposed for performance-driven global routing which directly trades off between Prim's minimum spanning tree algorithm and Dijkstra's shortest path tree algorithm. This direct combination of two objective functions and their corresponding optimal algorithms contrasts with the more indirect 'shallow-light' methods. The authors' method achieves routing trees which satisfy a given routing tree radius bound while using less wire than previous methods. Detailed simulations show that these wirelength savings translate into significantly improved delay over standard MST routing in both IC and multichip module (MCM) interconnect technologies.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
15
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Chip Layout Optimization Using Critical Path Weighting
A.E. Dunlop, Vishwani D. Agrawal, D.N. Deutsch et al. · Design Automation Conference · 1984 · 148 citations