Two University of California San Diego graduate students from the departments of Computer Science and Engineering and Electrical and Computer Engineering were awarded the Best Paper Award and a $1000 prize this week at the 2018 International Symposium on Physical Design in Monterey, California. Now in its 22nd year, ISPD is the premier forum for research related to the physical design of integrated circuits.
Sriram Venkatesh, a second-year CSE M.S. (CE) student, and Kwangsoo Han, a fifth-year ECE Ph.D. student, won the award for their paper titled “Prim-Dijkstra Revisited: Achieving Superior Timing-driven Routing Trees.” The paper presents an improvement over what’s known as Prim-Dijkstra (PD), a balance of two algorithms that efficiently trades off between shortest-path and minimum-wirelength routing trees that propagate signals in integrated circuits. PD was first proposed for use in integrated-circuit design 25 years ago, and is now integrated into nearly all leading semiconductor design methodologies and electronic design automation tools.
For all its strengths, PD is limited in terms of serving signals that are extremely timing-critical, even as they arise in extremely low-power devices such as those designed for the mobile Internet of Things. The original PD construction’s tradeoff can lead to both wirelength (WL) and source-sink pathlength (PL) being suboptimal.
Venkatesh and Han -- who are advised by CSE and ECE Professor Andrew B. Kahng -- were able to demonstrate that their new method, which they call PD-II, shows marked improvement over PD in wiring capacitance, thus minimizing power requirements while reducing delay.
Their approach essentially “repairs” the routing tree by simultaneously reducing both WL and PL, at virtually zero additional runtime cost. By way of comparison, PD-II outperforms a state-of-the-art academic tool known as SALT by 36.46 percent PL improvement with similar WL on average, for 20K networks with more than 32 terminals. This advantage makes it theoretically possible to create faster, low-power chips -- an essential component for market-leading products.
“It's not often that one can propose a method, see it used in the real world for 25 years but then get a bit long in the tooth, and have the chance to make non-trivial improvements that give it a new life," remarked Prof. Kahng. "To do this with multiple generations of students has been very rewarding."
The work is a joint project between UC San Diego and Cadence Design Systems, Inc. To read the paper, visit: http://vlsicad.ucsd.edu/Publications/Conferences/355/c355.pdf. To download a slideshow of the students’ presentation of the paper, visit http://www.ispd.cc/?page=program