Statistical Timing Analysis of Combinational Logic Circuits

Horng Fei Jyu, Sharad Malik, Srinivas Devadas, Kurt W. Keutzer

Research output: Contribution to journalArticlepeer-review

67 Scopus citations


An important problem in high performance circuit design is to predict the percentage of fabricated circuits that will achieve a certain performance level (or clock speed). Accurate and efficient means of answering this question have not been developed thus far. In this paper, we develop efficient methods to compute an exact probability distribution of the delay of a combinational circuit, given probability distributions for the gate and wire delays. The derived distribution can give the probability that a combinational circuit will achieve a certain performance, across the possible range. This information can then be used to predict the expected performance of the entire circuit. The techniques presented in this paper target fast analysis as well as reduced memory requirements. We define the notion of a correct approximation, based on convex inequality, which never overestimates the percentage of circuits that will achieve any given performance. We show that given the assumption that all the topologically longest paths are responsible for the delay, our computation technique provides a correct probabilistic measure in the sense given above. Nevertheless, false paths in a circuit may result in needlessly pessimistic probability distributions. We give methods to identify and to ignore false paths in our probabilistic analysis, so as to obtain correct and less pessimistic answers to the performance prediction question. Some practical results are given for a number of benchmark combinational circuits.

Original languageEnglish (US)
Pages (from-to)126-137
Number of pages12
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number2
StatePublished - Jun 1993

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Statistical Timing Analysis of Combinational Logic Circuits'. Together they form a unique fingerprint.

Cite this