UC San Diego Team Wins International Routing Contest
|Professor Andrew B. Kahng (seated) with Ph.D. students Lutong Wang and Bangqi Xu.|
La Jolla, Calif., April 11, 2018 -- Team TritonRoute from the University of California San Diego won the 2018 Initial Detailed Routing Contest at the 22nd ACM International Symposium on Physical Design (ISPD), held March 25 to 28, 2018 in Monterey, Calif. ISPD is the premier forum for exchange of ideas and presentation of research on topics related to the physical design of very large-scale integrated circuits.
The TritonRoute team consisted of Lutong Wang, a fourth-year Ph.D. student and Bangqi Xu, a third-year Ph.D. student, both from the Department of Electrical and Computer Engineering. Both Wang and Xu are members of the UCSD VLSI CAD Lab, advised by Professor Andrew B. Kahng.
The annual ISPD contest, established in 2005, challenges teams from around the world to advance the state of the art in semiconductor design. Past topics have included global and detailed placement, clock tree synthesis, global routing and gate sizing.
For the first time, the focus was on initial detailed routing this year. As noted by the contest lead organizer, detailed routing is a “dead-or-alive” critical topic for electronic design automation tools that enable IC (integrated circuit) designs at the 7nm, 5nm and forthcoming 3nm technology nodes. However, know-how in detailed routing is highly sensitive, and there have been very few works about detailed routing in the open literature. The 2018 contest was sponsored by Cadence Design Systems, Inc. A record 33 initial team registrations were received from nine different countries or regions. After a four-month period of development, alpha submission, and beta submission, 10 final projects were submitted when the contest closed March 11.
“The experience was like jumping into a pool and learning how to swim. I had not written a routing tool before but wanted to take up the challenge,” said Xu.
“With just two of us, we needed to carefully work backward from the deadline, the evaluation metric, and the bar for submission that our advisor had set,” added Wang. ” So, we focused on developing several core optimizers that could be applied repeatedly to construct and polish a routing solution in a robust way. While other teams seem to have used traditional maze routing and rip-up-and-reroute strategies, a key piece of our router sets up and solves an integer program.”
The detailed routing contest evaluated the quality of contestants’ solutions using one universal evaluation metric. The metric considers key aspects of routing quality, including wirelength, via count, #opens, area of shorts and various design rule violations. Results were scaled by factors that penalized non-determinism and excessive runtime. (A non-deterministic router produces different results in different runs. Runtime is the wall clock time from the beginning to the end of the execution of the submitted binary code program. The contest also established a hard memory limit, and any run that exceeded the limit was considered a failure.)
According to the contest results announced March 27 (see the organizers’ presentation at the symposium website for details), UC San Diego’s TritonRoute team took first place, along with a cash prize, by achieving the best metric value on eight out of the 10 benchmarks used in the contest. TritonRoute also achieved the best overall routing quality. Other than UC San Diego, the top-five winners in the 2018 ISPD Initial Detailed Routing Contest were the Chinese University of Hong Kong; a joint entry by National Tsing Hua University and Fuzhou University; Universidade Federal do Rio Grande do Sul; and National Chiao Tung University.
Students from the UCSD VLSI CAD Lab won the very first ISPD contest in 2005. The last time UC San Diego participated in the ISPD contest, two students from the UCSD VLSI CAD lab teamed up with Michigan and won in 2013 (article).
“These contests are very time-consuming -- and so my lab usually avoids them -- but they are also great learning and training experiences for students in the field,” said Professor Kahng. “Lutong and Bangqi worked really well together, and they certainly learned a lot during these past months. In my view, there is some advantage from having had past experiences with ISPD contests, and from frequently testing our work in close interactions with industry. Other students in the lab contributed by developing scaled test cases and regression scripts, helping to profile memory usage, discussing difficult corner cases, and so on. So, this success in many ways draws on the entire lab and its history.”