Two CS student teams advance to the final round of ICCAD 2013 Competition

Two teams of computer science undergraduate students have placed highly in the competitive ICCAD 2013 CAD Contest. Team CADa046, “Boulders and Dust,” composed of undergrads Daniel MacLennan, Peter Xie, and recent alumnus Andrew Segavac, placed third in competition for the Technology Mapping for Macro Blocks topic. Team CADa047, “Placeholder,” composed of undergraduates Spencer Kim and Joseph Lee, placed fifth in the Detailed Placement and Legalization topic. Both teams were advised by Prof. Igor Markov.

A total of 87 teams worldwide, predominantly consisting of graduate students, competed in the contest’s three topic areas. Only about one in four teams advanced to the final round. The competition was held from April through August of this year, but the results of the final round were revealed, after thorough evaluation by IBM Researchers, on November 19, 2013 at the IEEE/ACM International Conference on Computer-Aided Design in San Jose, CA. Finalist teams were asked to prepare videos, which were played at the conference. Links to the official videos from the U-M teams are below.

Boulders and Dust

Team Boulders and Dust competed in Technology Mapping for Macro Blocks (“boulders”), where students developed algorithms to identify subcircuits of various types in a large circuit and substitute some of them with a small set of given modules. The contest encouraged logic optimization, which was particularly impactful for “dust logic” connecting macro blocks. Students were asked to develop software that would automatically analyze circuits and given module libraries, perform optimized substitutions, and produce the resulting circuit. Logic equivalence checking against the initial circuit was performed using industry-standard tools provided to contestants by Cadence Design Systems.

The team performed a literature search and reviewed existing software, but realized that most prior work did not suit their needs. The students implemented a Verilog parser, an object-oriented graph database to keep track of digital circuits, a logic normalizer, and search routines for several circuit types. After a careful study of available circuit benchmarks, they devised a priority-based substitution strategy that was both scalable and effective in practice.

The contest problem turned out to be so complex that not all planned algorithms were implemented and debugged by the deadline, but the implemented solution performed well on most benchmarks. It was exciting to hear from contest organizers that the team advanced to the final round of the contest, and also unexpected given that most competing teams consist of graduate students whose research is related to the contest problem. The U-M undergraduate students had to rely on their fundamentals, including algorithms and data structures, as well as software skills.

Placeholder

Team Placeholder competed in Detailed Placement and Legalization, where a given circuit had to be physically rearranged by relocating its standard cells, so as to relieve regions with excessive density and reduce the total length of interconnect between standard cells, while observing maximum displacement constraints.

The students chose to base their contest entry on existing software, which they modified in several ways. First, they made sure that all constraints could be satisfied. Then they improved the quality of results produced on competition benchmarks. After careful runtime profiling, they found ways to speed up the software and eventually prepared a multi-threaded version of the placer that processed different parts of the chip in parallel.

In the course of the contest, the students developed an extensive system for running batched simulations, collecting results, preparing tables and visualizing key trends. Every simulation run automatically produced a new web page with a summary of results, where any unusual numbers would be highlighted. With such infrastructure, steady progress was assured through many weeks. The U-M undergraduate students were excited to advance to the final round of the competition, especially since most competitors were graduate students working on placement.