Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal

Hongliang Chang, Sachin S. Sapatnekar · 2003

We present an efficient statistical timing analysis algorithm that predicts the probability distribution of the circuit delay while incorporating the effects of spatial correlations of intra-die parameter variations, using a method based on principal component analysis. The method uses a PERT-like circuit graph traversal, and has a run-time that is linear in the number of gates and interconnects, as well as the number of grid partitions used to model spatial correlations. On average, the mean and standard deviation values computed by our method have errors of and, respectively, in comparison with a Monte Carlo simulation. delays), as explained in Section 2. Moreover, any strictly pathbased method will eventually be faced with an explosion in the number of critical paths. We propose an algorithm for statistical STA that computes the distribution of circuit delay while considering correlations due to path reconvergence as well as spatial correlations. We model the circuit delay as a correlated multivariate normal distribution, considering both gate and wire delay variations. The complexity of the algorithm is, which is linear in the number of gates and interconnects, and also linear in the number of grids that are used to model the variational regions. In other words, the cost is, at worst, times the cost of a deterministic STA. 1.

Cited by 527 works. doi:10.5555/996070.1009954

Authors

References