DoI: 10.1145/1536616.1536640
Technical Perspective
Where the chips may fall
By sachin s. sapatnekar
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 18–24 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 be—at 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
The chief idea
of the paper is
to use bounding
techniques to
capture the
probability
distribution of
the circuit delay.
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 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.
Sachin S. Sapatnekar ( sachin@umn.edu) is a professor of
electrical and Computer engineering at the university of
Minnesota, Minneapolis, Mn.
