The VLSI design productivity crisis, that is, the fact that the number of available transistors grows much faster than the ability to design them meaningfully, has become the greatest threat to the growth of semiconductor industry. Silicon complexity, which refers to the impact of previously ignorable physical phenomena, is at the center of this crisis. Based on our beliefs that the only effective way to improve productivity is to maintain design complexity at a manageable level, and that formal methods are the right techniques for complexity control, the objective of this research is to improve design productivity by applying formal methods to silicon complexity problems such as inductive/capacitive couplings and process variabilities.

The research develops methodology, models, and algorithms to handle silicon complexity through the application of formal methods. By treating timing analysis as extracting semantics of a circuit, a timing analysis system is developed that handles both inductive and capacitive coupling delay variations. The system develops and uses a range of inductive coupling models with different accuracy and complexity. Based on that, timing macromodels for coupling delays are created for library characterization and IP specification. Clock scheduling and retiming algorithms are developed to separate signal switching times for coupling delay optimization. Signal switching time information is also explored in routing and placement to minimize coupling between sensitive wires. For process variability, statistical models are developed and combined into the timing analysis system to compute the statistical performance of a circuit, and stochastic optimization is used to optimize the statistical performance. The integrated education activities aim at two aspects of computer engineering education: 1) educating students in formal methods, especially their applications to nanometer VLSI design, thus bringing needed mathematical rigor into the discipline; 2) introducing students to silicon complexity and its impacts on VLSI design so that they are equipped with necessary background for modern high performance VLSI design.

National Science Foundation (NSF)
Division of Computer and Communication Foundations (CCF)
Application #
Program Officer
Sankar Basu
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
Northwestern University at Chicago
United States
Zip Code