Communications of the ACM
Home/Magazine Archive/August 2009 (Vol. 52, No. 8)/Technical Perspective: Where the Chips May Fall/Full Text
Research highlights
Technical Perspective: Where the Chips May Fall
Circuit speed, or timing, is one of the most crucial specifications on the performance of an integrated circuit. Since on-chip delays depend on the values of process parameters that drive transistor and wire characteristics, timing has traditionally been evaluated at several "corners," corresponding to process parameter settings that could result in nominal, best-case, or worst-case delays. The traditional approach to circuit design has been to build chips that work correctly at these extreme-case process corners, thereby guard-banding them against process variations.
This corner-based approach has been the mainstay of timing analysis for decades, but is on a collision course with the Moore's Law trend that doubles the number of transistors on a chip every 1824 months. This doubling has primarily been achieved by making transistor widths and heights smaller by a factor of about 1/
2, and appropriately scaling the wires, in each technology generation (as a result, the area of a chip is halved and twice the number of devices can fit in the same area). However, the characteristics of these smaller devices are more difficult to control: for instance, the fabrication process introduces variations in the physical dimensions of devices and wires; at tiny geometries, the dopant atoms within a transistor can no longer be considered uniformly distributed; and so on.
While some of these variations are predictable and can be incorporated relatively easily into conventional timing analysis, others must be modeled as uncorrelated or correlated random variations. If all of these random variations on a die were perfectly correlated, they could be evaluated at a worst-case or best-case corner, in accordance with traditional practice. However, the critical difference in nanometer technologies is the scale of these variations has shrunk, and even devices on the same die may behave very differently. This implies that some gates may become faster, and some slower, resulting in the possibility of cancellations of some variations. In this setting, using appropriate extreme-case process corners that ignore such cancellations will certainly produce functional circuits, but the guard-banding margin may be excessively conservative.
Why is this an important problem in practice? Excessive conservatism is likely to mean that circuit optimization will make most circuits much faster than they need to beat the cost of increased power. Consequently, a chip may be unable to simultaneously meet the stringent set of delay and power specifications imposed upon it. On the other hand, insufficiently conservative margins may imply that a large number of manufactured chips will fail to meet specifications, resulting in yield losses that could sink a product, or even a company. Thus, getting it just right, and being able to predict the timing yield well, has a notable impact on the bottom line.
Enter the science of probability and statistical design. The rich history of this area certainly provides a springboard for solving the problem noted here. After all, since delays are a function of process parameters, which can be treated as random variables, statistical delay computation should be a simple matter of finding the distribution of a function of random variables. However, the problem is significantly more complex and involves numerous intricacies: any solution must scale to solve large-sized circuit blocks with millions of gates; correlations between variations, and between path delays, must be handled; simple closed-forms for these functions of random variables do not exist, even if the random variables are assumed to follow a standard distribution; altering the mind-set of a designer to think of a delay as a probability, rather than a deterministic number, is a major cultural change; and so on.
The chief idea of the paper is to use bounding techniques to capture the probability distribution of the circuit delay.
The challenge of developing fast and practical solutions has led to a substantial amount of research in this area the past few years, with elegant theory being applied to solve intensely practical problems.
The following paper by Orshansky and Wang is an excellent sample of the clever ideas being applied in this field. The chief idea of the paper is to use bounding techniques to capture the probability distribution of the circuit delay. This work leverages Slepian's inequality, a classical result in probability theory, that allows a correlated normally distributed function to be bounded, and brings in the idea of stochastic majorization, which enables a partial ordering to be established on stochastic inequalities. This approach is applied to find the cumulative distribution function (CDF) of the maximum delay of a set of paths, and applied to standard benchmark circuits.
The authors illustrate that on these circuits, the lower and upper bound are extremely close, and accurately match a Monte Carlo based evaluation of the CDF, at a fraction of the computational cost. In doing so, they clearly demonstrate how a set of classical results can be beautifully adapted and applied to solve a very practical engineering problem.
©2009 ACM 0001-0782/09/0800 $10.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
No entries found