The research group focuses on the development of tools and techniques for attacking a wide range of NP-complete problems. The goal is to find optimal solutions when possible. In principle, NP-complete problems can require exponential amounts of time to solve; in practice, many instances are either small enough for brute force, or contain internal structure that can be exploited.
We are developing a hybrid problem solving approach, combining dynamic programming, branch-and-price ILP, and parallel compute resources.
The research focus has been motivated by the emergence of multi-core processors (which should not be viewed as a positive development.) There is a recent opinion article that illustrates the challenge; this grew out of the "Keep the Faith" debate at ICCAD.
Director: Prof. Patrick H. Madden
Graduate students: Satoshi Ono, Ed Mattison, Jason Gallia, James Simone, Gowrishankar Sivanathan, Will Rotach.
Undergraduates: Greg Stoddard, Alex Jasperson, Dave Lundgren, Oray Tan, Ayca Yucel.
Collaborators: Prof. Purush Damodaran.
Below are links to the most relevant papers; a more complete list (including papers from when the group focus was primarily on design automation) is here.
- November 2007: ICCAD Can We Still Keep the Faith? SCDsource story on this debate. At the SIGDA Member Meeting at ICCAD, there is a videotaped talk by Dr. Amdahl, as well as a tape of the debate following the talk. 2007 is the 40th anniversary of Amdahl's Law; a copy of the original paper has been recreated by Guihai Chen.
- April 2007: EDP Forty Years of Amdahl's Law (The Sky is Falling). Slides.
- April 2006: EDP On the Marketing of Multicore. Slides.
- April 2005: EDP Supersized VLSI: A Recipe for Disaster. Slides.
- January 2005: ASPDAC Optimal Placement by Branch-and-Price
Our tools are not yet publicly available