Abstract
This paper quantifies the approximation error when results obtained by Clark (Oper. Res., vol. 9, p. 145, 1961) are employed to compute the maximum (max) of Gaussian random variables, which is a fundamental operation in statistical timing. We show that a finite lookup table can be used to store these errors. Based on the error computations, approaches to different orderings for pairwise max operations on a set of Gaussians are proposed. Experimental results show accuracy improvements in the computation of the max of multiple Gaussians, in comparison to the traditional approach. In addition, we present an approach to compute the tightness probabilities of Gaussian random variables with dynamic runtime-accuracy tradeoff options. We replace required numerical computations for their estimations by closed form expressions based on Taylor series expansion that involve table lookup and a few fundamental arithmetic operations. Experimental results demonstrate an average speedup of 2× using our approach for computing the maximum of two Gaussians, in comparison to the traditional approach, without any accuracy penalty.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1522-1533 |
| Number of pages | 12 |
| Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
| Volume | 26 |
| Issue number | 8 |
| DOIs | |
| State | Published - Aug 2007 |
Funding
Manuscript received January 25, 2006; revised May 22, 2006 and September 20, 2006. This work was supported in part by the National Science Foundation under Grant CCR-0238484. This paper was presented in part at the Proceedings International Symposium on Quality Electronic Design, pp. 306–311, 2006. This paper was recommended by Associate Editor V. Bertacco.
Keywords
- Computer-aided design (CAD)
- Gaussian approximation
- Statistical timing
- Very large-scale integration (VLSI)
ASJC Scopus subject areas
- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering