Recent EECS alumni Myung-Chul Kim (PhD EE '12) and Jin Hu (PhD CSE '12) have won first place at the ICCAD 2012 place-and-route competition. The competition was held in August and September, but the results were revealed, after thorough evaluation by IBM Researchers, on November 6, 2012 at the IEEE/ACM International Conference on Computer-Aided Design in San Jose, CA.
Every modern digital circuit requires significant physical optimization, such as finding the locations of circuit elements (placement) and defining wire configurations (routing). Otherwise, long interconnects would make the chip impractically slow. Such optimization is beyond the reach of individual architects and chip designers due to its combinatorial complexity and is performed by sophisticated CAD software. To this end, placement and routing have traditionally been implemented as separate steps. However, it has been noted that such separable chip-design methodologies can be vastly improved by informing the placement process about the routability of resulting layout, and as a consequence, combining placement and routing into a joint optimization is an active area of research in Electronic Design Automation. The ICCAD place-and-route competition was one of three competitions held under the ICCAD 2012 contest and sponsored by IEEE Council on Electronic Design Automation and Taiwan's Ministry of Education. 56 teams from all over the world participated in the contest, and Michigan placed first. Second place went to a team from the Chinese University of Hong Kong, and third place went to the National Taiwan University.
The Michigan team fully leveraged their doctoral research performed under the guidance of Prof. Igor Markov. Dr. Kim's dissertation was on multiobjective algorithms for VLSI placement (defended in August 2012), and Dr. Hu's was on high-performance routing algorithms (defended in October 2012). During his doctoral research, Dr. Kim developed a placement algorithm called "SimPL," which in the contest was guided by the global router developed by Dr. Hu. The resulting software was called "SimPLR," which also stands for "Simultaneous PLacement and Routing." Making this combination effective, fast and reliable required several breakthroughs on the placer and the router side, as well as significant innovation on the interface between these two optimizations that are traditionally viewed as stand-alone.
Contest entries were evaluated on a series of hidden benchmarks derived from semiconductor products under development at IBM. According to the results announced at ICCAD 2012, SimPLR produced high-quality layouts for integrated circuits with several million independently-placeable objects, and did so significantly faster than other top competitors. To accomplish this feat, the Michigan researchers not only improved their place-and-route algorithms, but also leveraged instruction-level (SIMD) and thread-level parallelism by dynamically dividing computation between four threads running on the same system. After their graduation, Drs. Kim and Hu are joining IBM in Texas and New York, respectively.
Posted: November 16, 2012