Statistical Analysis of Circuit
Timing Using Majorization
by Michael Orshansky and Wei-Shen Wang
Future miniaturization of silicon transistors following
Moore’s Law may be in jeopardy as it becomes harder to
precisely define the behavior and shape of nanoscale transistors. One fundamental challenge is overcoming the variability in key integrated circuit parameters. In this paper, we
discuss the development of electronic design automation
tools that predict the impact of process variability on circuit
behavior, with particular emphasis on verifying timing correctness. We present a new analytical technique for solving
the central mathematical challenge of the statistical formulation of timing analysis which is the computation of the circuit delay distribution when delays of circuit elements are
correlated. Our approach derives the bounds for the exact
distribution using the theory of stochastic majorization.
Across the 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.
A notable feature of silicon microelectronics at the nanometer scale is the increasing variability of key parameters
affecting the performance of integrated circuits. This stems
from the dramatic reduction in the size of transistors and
on-chip wires, and is due to both technology-specific challenges and the fundamentals of nanoscale electronics. For
example, one technology-specific challenge is the lack of a
cost-effective replacement for using 193 nm light during the
lithographic process, which yields poor fidelity when patterning transistors with a 20 nm length.
The more fundamental challenge is overcoming intrinsic
randomness when manipulating materials on atomic scale.
This randomness is, for example, manifested in threshold
voltage variation, roughness of the transistor gate edge, and
variation in the thickness of the dielectric transistor layer.2
For example, the threshold voltage separating the on and off
states of the transistor is controlled by adding dopant (
non-silicon) atoms inside the transistor. Placing dopant atoms
into a silicon crystal (see Figure 1) is essentially a random
process, hence the number and location of atoms that end
up in the channel of each transistor is likewise random. This
leads to significant variation in the threshold voltage and
many of the key electrical properties of the transistor.
Process parameters can be distinguished by the spatial scales on which they cause variability to appear, such
as wafer-to-wafer, inter-chip, and intra-chip variability.
Historically, intra-chip variability has been small but has
grown due to the impact of technology-specific challenges
in photolithography and wire fabrication, as well as the
increased intrinsic randomness described above. Another
important distinction is systematic versus random variability patterns. Systematic variation patterns are due to well-understood physical behaviors and thus can be modeled for
a given chip layout and process. For example, the proximity of transistors to each other leads to a strong systematic
effect on their gate lengths. Random variation sources, such
as threshold voltage variation due to dopants, can only be
described through stochastic modeling.
The variability in semiconductor process parameters
translates to circuit-level uncertainty in timing performance
and power consumption. The timing uncertainty is added to
the uncertainty from the operating environment of circuit
components, such as their temperature and supply voltage.
The two sources of uncertainty, however, must be treated differently during the design process. Because a manufactured
chip must operate properly under all operating conditions,
environmental uncertainty is dealt with by using worst-case
methods. The timing uncertainty due to process parameter
variation can be dealt with statistically, since a small fraction of chips are allowed to fail their timing requirements
and discarded during manufacturing.
Increased process variability presents challenges to IC
design flows based on deterministic circuit analysis and
Figure 1. Distribution of dopant atoms in a transistor with the length
of 50 nm. The number and location of atoms determine the key
electrical properties. (Reprinted from Bernstein et al.2 © IBM, 2006.)
z position (mm)
x position (mm)
A previous version of this article appeared in IEEE
Transactions on Computer-Aided Design of Integrated
Circuits and Systems (2006).
AUGUST 2009 | VOL.52 | NO.8 | COMMUNICATIONS OF THE ACM