Symbolic Methods for Accurate Timing Analysis

November 2, 2005
2:50 pm - 4:00 pm
Halligan 111


Successful analysis of high-speed integrated circuits requires accurate delay computation. A number of delay models have been developed; however, none can claim to be truly robust in the face of large channel-connected regions with input ``exclusivity'' constraints. A good circuit-level delay model should 1) consider input exclusivity constraints; 2) handle a wide range of circuit structures; and 3) have a robust underlying framework that can be applied independent of the actual device model. In this talk, I will present a symbolic timing analysis tool that aims to address these three goals. We use Algebraic Decision Diagrams (ADDs) to estimate delay within a channel-connected region (CCR) as a function of its inputs while easily handling Boolean input constraints. The effectiveness of our approach is demonstrated on circuits from industry. Our delay estimates are within 10% of SPICE for over 90% of the circuits we simulated. This difference can translate into significant savings in manpower by avoiding the need to verify many unrealizable worst-case conditions with other, more costly, simulation techniques. I will also touch on ongoing research in our group that builds on this notion of obtaining accurate delay estimates by including logic, or data dependent information, in the timing analysis. Our approach is to determine the true critical path through a circuit by unrolling a network as a function of time and posing the circuit delay as a satisfiability problem.