figure 6. A comparison between the node-based algorithm and our bounding strategy for a balanced tree circuit.

1.0

0.9

0.8

Cumulative Probability

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0

3200 3400 4000

Node-based Upper Bound Monte-Carlo Lower Bound

Balanced tree depth = 8

3600 3800 Delay (ps)

4200

benchmarks, the root-mean-square difference between the exact distribution and the bounds is 1. 7–4.5% for the lower bound and 0. 9–6.2% for the upper bound. Figure 5 illustrates that accurately accounting for edge delay correlations is crucial when predicting the shape of the cdf. The edge delay correlation changes with the ratio of the variance of inter-chip to intra-chip components. For example, the span of the low-correlation case is smaller than the high-correlation case. Our algorithm is more accurate than node-based approximation methods when processing balanced timing graphs with equal path mean delays and delay variances. In Figure 6, we compare the cumulative distribution functions generated by the node-based algorithm using the procedure of Visweswariah et al. 17 against the proposed approach. The cdfs are generated for a balanced tree circuit with depth of 8. An equal breakdown of total variation into inter-chip and intra-chip variability terms was used. Note that the approximate cdf may be noticeably different from the true one, but the bounds accurately contain the true cdf.

The implementation is very efficient even though the algorithm runtime is quadratic in the number of deterministically longest paths. The C++ implementation ran on a single-core machine with a 3.0GHz CPU and 1GB memory and took less than 4 seconds for the largest circuit in the ISCAS ‘ 85 benchmark suite (3874 nodes). When evaluated at a fixed number of extracted paths, there is a close-to-linear growth in algorithm runtime as a function of circuit size.

5. concLusIon

We have presented a new statistical timing analysis algorithm for digital integrated circuits. Instead of approximating the cdf of a circuit, we use majorization theory to compute a tight bound for the delay cdf. The equicoordinate random vectors are used to bound the exact cumulative

100 communIcATIons of The Acm | auGust 2009 | Vol. 52 | no. 8

distribution function, which facilitates the numerical evaluation of the probability.

Acknowledgments

We thank Ashish K. Singh for his help with the simulations, and Sachin Sapatnekar for his feedback on the article. The work has been partially supported by the NSF Career grant CCF-0347403.

1. agar wal, a., zolotov, V., blaauw, D.t. statistical timing analysis using bounds and selective enumeration. IEEE Trans. Comp. Aided Des. Integr. Circuits Syst. 22, 9 (2003), 1243–1260.

2. bernstein, k., frank, D. J., Gattiker, a.e., haensch, W., Ji, b.l., nassif, s.r., nowak, e.J., Pearson, D.J., rohrer, n.J. high-performance CMos variability in the 65-nm regime and beyond. IBM J. Res. Dev. 50, 4 (2006), 433–449.

3. Chang, h., sapatnekar, s.s. statistical timing analysis considering spatial correlations using a single Pert-like traversal. In Proceedings of the International Conference on Computer-Aided Design (san Jose, Ca, 2003).

4. Clark, C.e. the greatest of a finite set of random variables. Oper. Res. 9, 2 (1961), 85–91.

5. hassoun, s., sasao, t. Logic Synthesis and Verification. kluwer academic Publishers, new york, 2002.

6. hitchcock, r.b. timing verification and the timing analysis program. In Proceedings of the 19th Conference on Design Automation (Piscataway, nJ, 1982).

7. Jacobs, e.t.a.f., berkelaar, M.r.C.M. Gate sizing using a statistical delay model. In Proceedings of the Conference on Design, Automation and Test in Europe (Paris, france, 2000).

8. Jess, J.a.G., kalafala, k., naidu, s.r., otten, r.h.J.M., Visweswariah, C. statistical timing for parametric yield prediction of digital integrated circuits. In Proceedings of the 40th Conference on Design Automation (anaheim, Ca, 2003).

9. Jyu, h.f., Malik, s., Devadas, s., keutzer, k. W. statistical timing analysis of combinational logic circuits. IEEE Trans. VLSI Syst. 1, 2 (1993), 126–137.

References

Michael Orshansky ( [e-mail]), Department of eCe, university of texas, austin.

10. Marshall, a. W., olkin, I. Inequalities: Theory of Majorization and Its Applications. academic Press, new york, 1979.

11. Moretti G. Clk Design automation introduces amber fx analyzer, EDA Design Line. retrieved on May 22, 2009, http://www.edadesignline.com/.

12. nadas, a. Probabilistic Pert. IBM J. Res. Dev. 23, 3 (1979), 339–347.

13. orshansky, M., nassif, s., boning, D. Design for Manufacturability and Statistical Design: A Constructive Approach. springer, new york, 2008.

14. ramalingam, a., nam, G., singh, a.k., orshansky, M., nassif, s.r., Pan, D.z. an accurate sparse matrix based framework for statistical static timing analysis. In Proceedings of the International Conference on Computer-Aided Design (san Jose, California, 2006).

15. robillard, P., trahan M. the completion time of Pert networks. Oper. Res. 25, 1 (1977), 15–29.

16. tong, y.l. Probability Inequalities in Multivariate Distributions. academic Press, new york, 1980.

17. Visweswariah, C., ravindran, k., kalafala, k., Walker, s.G., narayan, s. first-order incremental block-based statistical timing analysis. In Proceedings of the 41st Conference on Design Automation (san Diego, Ca, 2004).

18. Wang, W.s., orshansky, M. Path-based statistical timing analysis handling arbitrary delay correlations: theory and implementation. IEEE Trans. Comp. Aided Des. Integr. Circuits Syst. 25, 12 (2006), 2976–2988.

19. yen, s.h., Du, D.h., Ghanta, s. efficient algorithms for extracting the k most critical paths in timing analysis. In Proceedings of the 26th Conference on Design Automation (las Vegas, nV, 1989).

Wei-Shen Wang (wei-shen [e-mail]), Mentor Graphics, taipei, taiwan.