Statistical Timing Analysis of Combinational Logic Circuits

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.