Characterizing Timing Yield for Functional Units During High Level Synthesis

In this project, our goal is to search for the methods to characterize the timing yield by efficient circuit graph analysis techniques (to be more specific, it is the critical path analysis techniques) instead of expensive SSTA techniques. We will evaluate the effectiveness of this approach by incorporating it into a timing analysis flow consisting of Synopsys tools.

In order to address the problem of process variations, statistical static timing analysis (SSTA) has been proposed and widely studied in recent years. Existing SSTA methods mainly focus on gate-level timing analysis. However, in the domain of high-level synthesis, statistical timing analysis has not been studied extensively as at the gate level. One of the reasons why this is the case is because it is difficult to accurately characterize performance yields during high-level behavioral synthesis. In most of the existing works [1,2], a piecewise linear approximation based approach is adopted. In this approach, the delays of the functional units in the behavioral model are expressed as a function of the process variations, such as the deviation of threshold voltages DV_th and the deviation of the gate length Dl,

T = a₀ + a₁DV_th + a₂Dl (1)

where T is the probabilistic delay of the functional unit due to the process variations. a₀ represents the nominal delay computed at the nominal values of the process variables. a₁ and a₂ are sensitivity values to the deviation of different process variables. The delays of individual functional units in the library are calculated by performing Monte Carlo analysis [1,2]. The yield of an individual functional unit is then calculated as the probability that the delay of that functional unit is less than the timing constraint, that is,

Yield (i) = Prob(T_i < T_c) (2)

Monte Carlo analysis and gate-level statistical timing analysis are slow for large functional units. Both will generate detailed timing distribution of individual functional unit. However, not all those information are used in the yield calculation during high-level synthesis. In fact, we only need to calculate the percentage of the delay distribution that meets the timing constraint as illustrated in Equation (2). Therefore, a more efficient characterization of the timing yields of functional units without performing gate-level statistical analysis is needed.

It has been recognized that the timing yield is in proportional to the longest path delay of the function unit. The functional unit will have higher probability to violate a tighter timing constraint. As the longest path delay constraint becomes tight, there will be more and more critical or asymptotic critical paths in the circuit. It is obvious that the probability of timing failure is proportional to the total number of the critical or asymptotic critical paths in the circuit. Therefore, it is a good heuristic to use the number of critical paths in the circuit to characterize the yield of that function unit. In this way, we avoid performing Monte Carlo simulation or propagating Probability Distribution Functions in the circuit, both of which are inefficient for large functional units.

There are several advantages of using critical path as a metric to characterize the yield. The algorithms for finding critical path or asymptotic critical path in a circuit have already been widely researched. There also exist commercial tools that could perform such analysis, such as PrimeTime from Synopsys. In high-level synthesis, the timing constraint of an individual functional unit may be optimized iteratively during scheduling and module selection. Within each iteration, the timing yield of the function unit should be recalculated. If we use Monte Carlo or statistical timing analysis, no information from the previous iteration can be used to speed up the computation. However, the distributions of the critical and asymptotic critical paths in the circuit have only small local changes after the timing constraint is updated.

References

[1] F. Wang, X. Wu, Y. Xie, Variability-Driven Module Selection with Joint Design Time Optimization and Post-Silicon Tuning, ASPDAC, 2007.

[2] W.-L. Hung, X. Wu, Y. Xie, Guaranteeing Performance Yield in High-level Synthesis, ICCAD, 2006.