Statistical Analysis and Optimization of Digital Systems

Support: My students and I gratelfully acknowledge the following agencies for their generous support:

• National Science Foundation

• Science Foundation Arizona SFAz-SBC

• NSF S/IUCRC Center for Low Power Electronics

Motivation: The lack of process uniformity in the semiconductor manufacturing has caused variability to become a major cause of concern for nanometer scale CMOS design. The variations are caused by either global effects such as mask imperfections and lens aberration, or local effects such as layout pattern variations. These variations result in a significant amount of spread in the performance as well as leakage of the manufactured circuits. The effect of variations on circuit leakage current is much more pronounced compared to their effect on the delay. The variations can cause up to 30% variations in the circuit delay and up to 20X variations in the leakage current. Due to this, a large number of chips with significantly large leakage have to be discarded, thus resulting in a considerable yield loss.

The timely and cost effective design of a multi-million device VLSI circuit has been possible due to our ability to accurately estimate its delay and power consumption, prior to manufacture. As IC components continue to be miniaturized to atomic scales, the number of parameters that have appreciable variation, the relative magnitude of the variation and the sensitivity of the circuit delay and leakage to the variations have all increased substantially. Such variations translate to loss of predictability in the performance, power consumption and reliability of integrated circuits. Inter-die (between die) variations are generally easier to model and analyze. This is because a given parameter such as transistor length is perturbed by the same amount or each component on the die. Thus, if the number of parameters that vary between chips is small, then circuit delay and power consumption can be computed at several process corners. This approach is no longer feasible.

The number of parameters that have appreciable variation, the relative magnitude of the variation and the sensitivity of the circuit delay and leakage to the variations have all increased substantially. Moreover, with a significant increase in intra-die variations it is no longer accurate to assume that the variation in some parameter p can be represented as one random variable ∆p across the chip. Each gate i might have associated with it a distinct random variable ∆pi, potentially giving rise to a very large number of random variables. In addition, spatial correlations have to be taken into account. Therefore, the traditional approach of performing static timing analysis (STA) or full chip leakage analysis at all process corners is not feasible since the number of process corners would be enormous. Furthermore, requiring a design to be feasible at all process corners can introduce significant pessimism in the design.

Our research led to a new unified framework for statistical static timing analysis (SSTA) and statistical leakage analysis (SLA) while accounting for intra-die variations. These methods have advanced the state-of-the-art of statistical circuit analysis in several ways.

1. Delay, signal arrival times, gate leakage, interconnect response, etc., are all modeled as second order spatial stochastic processes in an infinite dimensional Hilbert space. Using the corre- lation function as the inner product, we developed a (multi-variate) quadratic orthogonal polynomial (QOP) representation for the delays, signal arrival times and log of sub-threshold and gate leakage in terms of the underlying random physical parameters. The canonical rep- resentation is mean-square optimal for the underlying probability space, and accommodates random variables with different densities. Orthogonality makes it possible to compute the coefficients of the expansion independent of each other.

2. The same representation framework was used to include variations in the setup and hold times of flip-flops and clock arrival times (clock skew) for analyzing sequential networks.

3. His also developed an efficient method to propagate the QOP representations of arrival times through the network. This results in the same representation of the delay of each output of the circuit in terms of all the random variables associated with the chip. Propagation of the polynomials through the network requires computing integrals in many dimensions. He developed an efficient and accurate approximation for computing the integrals and derive an upper bound on the error introduced in the approximation.

4. He also showed that the full chip leakage can be estimated using the same methodology. The leakage of each gate is added using an efficient sum operation, that preserves the exponential canonical form of the leakage, to obtain the total leakage of the circuit. This is done using the same approximation technique proposed for computation of multi-dimensional integrals for propagating max of arrival times in SSTA.

5. The proposed approach is shown to be far superior to linear models in terms of accuracy, and two orders of magnitude faster than Monte Carlo but with negligible error in the computation of the mean, standard deviation and empirical probability density function of circuit delay and leakage.

Publications:

• A. Goel, S. Vrudhula, F. Taraporevala, and P. Ghanta, “Statistical timing models for large macro cells and ip blocks considering process variations,” IEEE Transactions on Semiconductor Manufacturing, vol. 22, no. 1, pp. 3–11, 2009.

• A. Goel, S. Vrudhula, F. Taraporevala, and P. Ghanta, “A methodology for characterization of large macro cells and IP blocks considering process variations,” in Proceedings of the International Symposium on Quality Electronic Design (ISQED), (San Jose, CA), 17-19 March 2008. (Best Paper Award).

• S. Bhardwaj and S. Vrudhula, “Leakage minimization of digital circuits using gate sizing in the presence of process variations,” IEEE Transactions on Computer Aided Design, vol. 27, pp. 445–455, March 2008.

• S. Bhardwaj, S. Vrudhula, and A. Goel, “A unified approach to full chip statistical timing and leakage analysis of nanoscale circuits considering intra-die variations,” IEEE Transactions on Computer-Aided Design, vol. 27, no. 10, pp. 1812–1825, 2008.

• S. Bhardwaj and S. Vrudhula, “Multiattribute optimization with application to leakage delay trade-offs using utility theory,” Journal of Low Power Electronics (JOLPE), vol. 4, pp. 68–80, 2008.

• S. Bhardwaj, W. Wang, R. Vattikonda, K. Cao, and S. Vrudhula, “A scable model for predicting the effect of NBTI for reliable design,” IET Circuits, Devices and Systems, vol. 2, pp. 361–371, Aug. 2008.

• P. Ghanta and S. Vrudhula, “Analysis of power supply noise in the presence of process variations,” IEEE Design & Test of Computers, vol. 24, pp. 256–266, June 2007.

• S. Vrudhula, J. Wang, and P. Ghanta, “Hermite polynomial based interconnect analysis in the presence of process variations,” IEEE Transactions on Computer Aided Design, vol. 25, no. 10, pp. 2001–20011, 2006.

• P. Ghanta and S. Vrudhula, “Variational interconnect delay metrics for statistical timing analysis,” in Proceedings of the IEEE International Symposium on Quality Electronic Design (ISQED), (San Jose CA), March 2006.

• S. Bhardwaj, K. Cao, and S. Vrudhula, “Statistical leakage minimization of digital circuits using gate sizing, gate length biasing and threshold voltage minimization,” Journal of Low Power Electronics (JOLPE), vol. 2, no. 2, pp. 240–250, 2006.

• S. Bhardwaj, S. Vrudhula, and D. Blaauw, “Probability distribution of signal arrival times using bayesian networks,” IEEE Transactions on Computer Aided Design, vol. 24, pp. 1784–1794, November 2005.

• A. Goel, S. Bhardwaj, P. Ghanta, and S. Vrudhula, “Computation of joint timing yield for sequential networks considering process varia- tions,” in Proceedings of the International Workshop on Power, Tim- ing, Modeling, Optimization and Simulation (PATMOS), (Goteborg, Sweden), 3-5 September 2007.

• S. Bhardwaj, P. Ghanta, and S. Vrudhula, “A fast and accurate approach for full chip leakage analysis of nano-scale circuits considering intra-die correlations,” in International Conference on VLSI Deisgn, (Bangalore, India), January 2007.

• S. Bhardwaj, P. Ghanta, and S. Vrudhula, “A framework for statistical timing analysis using non-linear delay and slew models,” in Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD), (San Jose, CA), November 2006.

• S. Bhardwaj, S. Vrudhula, P. Ghanta, and K. Cao, “Modeling of intra-die process variations for accurate analysis and optimization of nano- scale circuits,” in Proceedings of the IEEE Design Automation Con- ference (DAC), (San Francisco, CA), July 2006.

• P. Ghanta, S. Vrudhula, S. Bhardwaj, and R. Panda, “Stochastic variational analysis of large power grids considering intra-die correlations,” in Proceedings of the IEEE Design Automation Conference (DAC), (San Francisco, CA), July 2006.

• S. Bhardwaj, S. Vrudhula, and Y. Cao, “Lotus: Leakage optimization under timing uncertainty for standard-cell designs,” in Proceedings of the IEEE International Symposium on Quality Electronic Design (ISQED), (San Jose CA), March 2006.

• S. Bhardwaj, Y. Cao, and S. Vrudhula, “Statistical leakage minimization through joint selection of gate sizes, gate lengths and threshold voltage,” in Proceedings of the Asia and South Pacific Design Automa- tion Conference, (Yokohama City, Japan), January 2006.

• S. Bhardwaj and S. Vrudhula, “Formalizing designer’s preferences for multi-attribute optimization with applications to leakage-delay trade- offs” in Proceedings of the IEEE International Conference on Com- puter Aided Design (ICCAD), pp. 713–718, November 2005.

• S. Bhardwaj and S. Vrudhula, “Leakage minimization of nanoscale circuits in the presence of systemaic and random variations,” in Proceedings of the IEEE Design Automation Conference (DAC), pp. 541–546, June 2005.

• P. Ghanta, S. Vrudhula, R. Panda, and J. Wang, “Stochastic power grid analysis considering process variations,” in Proceedings of the De- sign Automation and Test in Europe Conference (DATE), pp. 964–969, 2005.

• P. Ghanta, S. Bhardwaj, and S. Vrudhula, “Variational analysis of interconnects and power grids considering process variations,” in Proceedings of the ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, pp. 14–19, 2005.

• K. Agarwal, D. Sylvester, D. Blaauw, F. Liu, S. Vrudhula, and S. Nassif, “Variational delay metrics for interconnect timing analysis,” in Proceedings of the IEEE Design Automation Conference (DAC), pp. 381–388, 2004.

• J. Wang, P. Ghanta, and S. Vrudhula, “Stochastic analysis of interconnect performance in the presence of process variations,” in Proceedings of the IEEE International Conference on Computer Aided Design (IC- CAD), pp. 880–886, November 2004.

• S. Bhardwaj, S. Vrudhula, and D. Blaauw, “TAU : Timing analysis under uncertainity”, in Proceedings of the IEEE International Con- ference on Computer Aided Design (ICCAD), pp. 615–620, November 2003.

• A. Agarwal, D. Blaauw, V. Zolotov, and S. Vrudhula, “Computation and refinement of statistical bounds on circuit delay,” in Proceedings of the IEEE Design Automation Conference (DAC), pp. 348–353, June 2003.

• A. Agarwal, D. Blaauw, V. Zolotov, and S. Vrudhula, “Statistical timing analysis using bounds,” in Proceedings of the Design Automation and Test in Europe Conference (DATE), pp. 62–67, March 2003.

• A. Agarwal, D. Blaauw, V. Zolotov, and S. Vrudhula, “Statistical timing analysis using bounds and selective enumeration,” in Proceedings of the ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, pp. 25–31, December 2002.

• S. Bhardwaj, S. Vrudhula, and D. Blaauw, “Estimation of signal arrival times in the presence of delay noise,” in Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD), pp. 418–422, November 2002.