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
( orshansky@cerc.utexas.edu), 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 wang@mentor.com),
Mentor Graphics, taipei, taiwan.