Wisconsin Alumni Research Foundation

Information Technology
Information Technology
Rapid Statistical Timing Analysis of Integrated Circuits to Test and Enhance New Circuit Designs
WARF: P06157US

Inventors: Lizheng Zhang, Chung-Ping Chen, Yu Hen Hu

The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing software for statistical timing analysis of integrated latch-based circuits with feedback loops.
All digital devices, from computers to stopwatches, contain circuits composed of numerous electrical components.  Most circuits are designed to allow for some flexibility in signal timing because of irregularities in the circuit components introduced during fabrication and operation.  However, a circuit will fail to operate properly when error in the timing exceeds a certain threshold.  Statistical timing analysis (STA) is used to determine the functionality of a circuit by measuring the delays between signals.  The delays then can be summed to determine if the error in timing is within the acceptable limit, and if the circuit will function properly.

Traditional methods of STA, such as Monte Carlo simulations, require costly and time-consuming large scale computations to analyze the many different timing arrangements that a circuit may accrue.  The computational limitations are amplified in the analysis of very large scale integrated (VLSI) circuits, which contain 100,000 to 1 million electronic components per circuit, because of self-dependent components.  A transparent latch with a feedback loop is a type of self-dependent logic gate; in other words, its input is determined by its own output.  Self-dependent circuit components require numerous iterations for accurate STA because of the cyclic nature of the signal produced.  The correlation between timing variables also must be taken into account for optimal performance of the algorithm.

UW-Madison researchers previously developed a method of accounting for timing variable correlations from global variation and path reconvergence in STA (see WARF reference number P04377US).  Using the canonical timing model, the correlations are accounted for by modeling timing variables as a weighted linear combination of independent variables.  A variation vector of weights is used to represent the correlations for global variation and path reconvergence, treating both simultaneously and systematically.  This method is faster and more efficient than traditional methods.
The Invention
UW-Madison researchers have developed a new algorithm for STA of VLSI latch-based circuits with feedback loops.  This algorithm expands upon previous developments in timing variable correlation by incorporating analysis of transparent latches and feedback loops.  The algorithm also overcomes the cost and time limitations of traditional methods.  When compared to the Monte Carlo method, considered the gold standard of computational simulation, the new method is 303 times faster and has an average error of only 1.1 percent. 

The increase in computational speeds makes STA of VLSI circuits faster and less expensive.  The increase occurs because the iterations used to determine the average timing results converge more quickly.  This new method of STA will enhance the development and testing of new circuit designs, accelerating the VLSI circuit industry and reducing the cost of digital technologies.
  • Testing of new circuit designs to determine functional yield
Key Benefits
  • Reduces computational time of STA for circuits having transparent latches with feedback loops
  • Reduces cost of digital circuit manufacturing
Stage of Development
The new algorithm was compared to the Monte Carlo simulation and found to be 303 times faster with an error of 1.1 percent on average.
Additional Information
For More Information About the Inventors
Related Intellectual Property
  • Zhang L., Chen W., Hu Y. and Chen C.C. 2006. Statistical Static Timing Analysis with Conditional Linear MAX/MIN Approximation and Extended Canonical Timing Model. IEEE Trans. Comput. Aided. Des. Integrated Circ. Syst. 25, 1183-1191.
  • Zhang L., Tsai J., Chen W., Hu Y. and Chen C. C. 2006. Convergence-Provable Statistical Timing Analysis with Level-Sensitive Latches and Feedback Loops. Proc. 2006 Conf. Asia S. Pac. Des. Autom. 941-946.
For current licensing status, please contact Emily Bauer at [javascript protected email address] or 608-960-9842