Design Automation Conference Announces Best Paper Award Winners

The 44th Design Automation Conference (DAC), the electronic design automation (EDA) industry’s prestigious annual forum, awarded Best Paper honors to two noteworthy technical papers presented at this year’s conference. “Interdependent Latch Setup/Hold Time Characterization via Euler-Newton Curve Tracing on State-Transition Equations,” provides a breakthrough solution to a longstanding problem with timing closure. “Period Optimization for Hard Real-time Distributed Automotive Systems,” presents a new solution to the mapping problem for distributed automotive systems. The Best Paper awards were announced at DAC on June 8 before the Thursday keynote.

“Both of this year’s winning papers include outstanding research with tremendous impact for electronics design, and they are the result of highly productive interactions between academia and industry,” said Steve Levitan, general chair, 44th DAC. “DAC continues to be the premier venue for presenting the latest research in the field of electronic design.”

The winning paper titled “Interdependent Latch Setup/Hold Time Characterization via Euler-Newton Curve Tracing on State-Transition Equations,” by Shweta Srivastava, Univ. of Minnesota, Minneapolis, Minn., and her advisor, Jaijeet Roychowdhury, addresses a long-existing problem in timing closure for microprocessors: latch characterization. Identifying the performance characteristics of latches, specifically the set-up and hold times, has long been a time consuming process. Jaijeet Roychowdhury was aware of the problem before, but it wasn’t until 2006, during a meeting with Chirayu Amin at Intel’s strategic CAD labs in Oregon, that he discussed the problem and the need for a solution that achieves speedups without sacrificing any accuracy, prompting Roychowdhury to take another approach.

In some initial research, presented earlier this year at DATE, Roychowdhury’s team demonstrated the basic approach, an alternative to the widely used binary search technique, which resulted in a factor of up to 10X speed increase, shortening the time required for calculating the set up or hold time from three months to a couple of weeks.

The next breakthrough came when the team applied some previously little known research in a new way: the existence of multiple set up and hold time delays for each latch. Previously, characterizing one pair of setup and hold times typically took many months for a cell library. Therefore in the event of timing closure problems, designers were required to change the latch, inevitably making other design sacrifices as a result. Knowing that for each latch any number of valid pairs exist which can be used for timing closure and analysis, Srivastava and Roychowdhury developed a new method for identifying them more quickly.

The paper provides this method for doing the required computation in a smarter way, allowing a 20X increase for typical small latches and as a result, allowing designers greater choice and flexibility. The paper has already received strong interest from many EDA tool providers and microprocessor manufacturers.

This research is also unique in that it adapted well-known techniques in mixed-signal and RF simulation (homotopy and shooting) to a digital design problem, thanks to Roychowdhury’s group’s prior experience with analog, RF and mixed-signal CAD.

Roychowdhury calls Srivastava “one of the brightest students he’s ever had” in six years as a professor and eight years at Bell Labs working with student interns. The DAC best paper award announcement came just as Srivastava was preparing to leave for her wedding. Due to flight delays, Roychowdhury was able to reach her at the airport, and Srivastava returned to DAC for the award presentation.

The second winning paper, “Period Optimization for Hard Real-time Distributed Automotive Systems,” was written by Abhijit Davare and Qi Zhu, University of California, Berkeley; Marco Di Natale, General Motors Corp.; Claudio Pinello, Cadence Design Systems, Inc. and Sri Kanajan, General Motors Corp. with advisor Alberto Sangiovanni-Vincentelli, University of California, Berkeley. The paper, which tied to the automotive theme of this year’s conference, looks at the mapping problem for distributed automotive systems, which is particularly relevant for the design of active safety applications such as electronic stability control and parallel parking assist.

These applications are deployed on architectures with multiple electronic control units (ECUs) interconnected by buses. Designers need to determine how to assign the activation periods for tasks executed on ECUs and messages transmitted on buses such that end-to-end latencies and other constraints are met. Until now, this problem has required a time-consuming manual process. The method outlined in the paper automates the period assignment stage within mapping. The approach is scalable, allowing realistic industrial problems to be solved within a few minutes. It is also flexible, in that designers can add system-specific constraints if desired.

Alberto Sangiovanni-Vincentelli, advisor to Abhijit Davare and Qi Zhu at Berkeley, was instrumental in setting up the collaboration with General Motors and Cadence, and hosted Marco Di Natale from General Motors in Berkeley. Di Natale posed the problem and provided a deep understanding of the prior work in the area. Davare and Zhu developed the approach with help from Pinello and Kanajan. The paper reports two industrial-strength case studies, including an experimental vehicle system obtained from the collaboration with General Motors, which further strengthened the winning paper.

Best Paper Selection Process
Of the 161 papers presented at the 44th DAC, 15 papers were nominated by the technical subcommittees for consideration for Best Paper, six in the front-end and nine in the back-end. A special best paper selection committee comprised of seven distinguished individuals in the EDA community across faculty, industry and geographies, reviewed the nominated papers. They visited the best paper presentations at the conference, and in a closed meeting on Wednesday afternoon selected a best paper in the front-end and a best paper in the back-end category.

About DAC
The Design Automation Conference (DAC) is the premier educational and networking event for Electronic Design Automation (EDA) and silicon solutions. More than 9,000 designers, developers, researchers, academics and managers from leading electronics companies and universities from around the world attend. DAC features close to 60 technical sessions covering the latest research on design methodologies and technologies, EDA tool developments and trends selected by a diverse committee of electronic design experts. A highlight is its Exhibition and Suite area with approximately 250 of the leading and emerging EDA, silicon and IP providers.