82. improved prim-dijkstra tradeoffs for high performance vlsi routing

Department: Computer Science & Engineering
Research Institute Affiliation: Graduate Program in Computational Science, Mathematics, and Engineering (CSME)
Faculty Advisor(s): Andrew B. Kahng

Primary Student
Name: Sriram Venkatesh
Email: srvenkat@ucsd.edu
Phone: 858-822-5003
Grad Year: 2018

Student Collaborators
Sriram Venkatesh, srvenkat@eng.ucsd.edu

The Prim-Dijkstra (PD) tradeoff was first proposed for integrated-circuit routing over 20 years ago. Since then, this approach has been used to construct high-performance routing trees in leading semiconductor design methodologies and electronic design automation tools. The PD construction brings together the conflicting objectives of minimum tree wirelength (WL) and minimum tree radius, by blending the Prim and Dijkstra spanning tree constructions. However, PD constructions can show suboptimality in the form of highly detoured paths from the source to the sinks. This is especially harmful in recent technology nodes, where wire delays can dominate overall timing delays. In this work, we improve the original PD construction by "repairing" tree edges to simultaneously recover WL and detouring. We also provide an algorithm to recover detour and WL in Steiner trees that are created from the PD spanning tree constructions. Our improved algorithms achieve reduced signal delays for both spanning and Steiner tree constructions, across a wide range of practical instance sizes.

Industry Application Area(s)
Electronics/Photonics | Semiconductor | Software, Analytics

Related Links:

  1. http://vlsicad.ucsd.edu/Publications/Journals/j18.pdf

« Back to Posters or Search Results