100%" bgcolor=white>
Statistical Static Timing Analysis with Conditional Linear MAX/MIN Approximation and Extended Canonical Timing Model
ZHANG et al.: SSTA WITH CORRELATIONS
1
Statistical Static Timing Analysis with
Conditional Linear MAX/MIN Approximation
and Extended Canonical Timing Model
Lizheng Zhang, Student Member, IEEE, Weijen Chen, Student Member, IEEE,
Yuhen Hu, Fellow, IEEE, Charlie, Chung-ping Chen, Member, IEEE,
Abstract
An efcient and accurate statistical static timing analysis (SSTA) algorithm is reported in this work which
features (a) a conditional linear approximation method of the MAX/MIN timing operator, (b) an extended canonical
representation of correlated timing variables, and (c) a variation pruning method that facilitates intelligent trade-off
between simulation time and accuracy of simulation result. A special design focus of the proposed algorithm is on the
propagation of the statistical correlation among timing variables through the nonlinear circuit elements. The proposed
algorithm distinguishes itself from existing block based SSTA algorithms in that it not only deals with correlations
due to dependence on global variation factors, but also correlations due to signal propagation path reconvergence.
Tested with ISCAS benchmark suites, the proposed algorithm has demonstrated very satisfactory performance in
terms of both accuracy and running time. Compared with Monte Carlo based statistical timing simulation, the output
probability distribution got from the proposed algorithm is within
1.5% estimation error while a 350 times speed-up
is achieved over a circuit with 5355 gates.
I. I
NTRODUCTION
The timing performance of deep-submicron micro-architecture will be dominated by several factors. IC manufac-
turing process parameter variations will cause device and circuit parameters to deviate from their designed value.
Low supply voltage for low-power applications will reduce noise margin, causing increased timing delay variations.
Due to dense integration and non-ideal on-chip power dissipation, rising temperature of substrate may lead to hot
spot, causing excessive timing variations. Classical worst case timing analysis produces timing predictions that are
often too pessimistic and grossly conservative. On the other hand, statistical static timing analysis (SSTA) that
characterizes timing delays as statistical random variables offers a better approach for more accurate and realistic
timing prediction.
Existing SSTA methods can be categorized into two distinct approaches: path based SSTA [1][4] and block
based SSTA [5][10]. The path based SSTA seeks to estimate timing statistically on selected critical paths. However,
the task of selecting a subset of paths whose time constraints are statistically critical has a worst-case computation
February 7, 2005
DRAFT ZHANG et al.: SSTA WITH CORRELATIONS
2
complexity that grows exponentially with respect to the circuit size. Hence the path based SSTA is not easily
scalable to handle realistic circuits.
The block based SSTA, on the other hand, champions the notion of progressive computation. Specically, by
treating every gate/wire as a timing block, the SSTA is performed block by block in the forward direction in the
circuit timing graph without looking back to the path history. As such, the computation complexity of block based
SSTA would grow linearly with respect to the circuit size. However, to realize the full benet of block based SSTA,
one must address a challenging issue that timing variables in a circuit could be correlated due to either global
variations( [6], [7], [10]) or path reconvergence ( [5], [9]). As illustrated in the left hand side of Figure 1, global
correlation refers to the statistical correlation among timing variables in the circuit due to global variations such as
inter- or intra-die spatial correlations, same gate type correlations, temperature or supply voltage uctuations, etc.
Path correlation, on the other hand, is caused by the phenomenon of path reconvergence, that is, timing variables
in the circuit can share a common subset of gate/wire blocks along their path histories. (Figure 1)
The importance of the path correlation comes from the fact that each gate/wire block in the circuit will have some
local variations which are independent to the rest of the circuit. These local variations will propagate towards the
circuit output and cause additional correlations due to the phenomenon of path reconvergence. Furthermore, these
correlations caused by sharing local variations, cannot be correctly captured by any algorithm that deals with global
variations only. So for clarity, the term path correlation used here and after specically refers to the correlation
caused by the local variations of the common path history.
X
Y
Z
g
(a) X, Y and Z depend on g
p
X
Y
(b) X and Y depend on p
Fig. 1: Global Correlations (left) and Path Correlation(right)
Several solutions have been proposed to deal with either of these two types of correlations. In [6], [7], [10], the
dependence on global variations is explicitly represented using a canonical timing model. However, these approaches
did not take into account the path correlations. In [9], a method based on common block detection is introduced
to deal with the path correlations. However, this method does not address the issue of dependence on global
variations. To the best of our knowledge, there is no existing method that has dealt with both types of correlations
simultaneously. We present a novel block based SSTA algorithm in this paper that is designed to consider both
global correlations and path correlations: We develop a novel method to conditionally approximate the MAX/MIN operator by a linear mixing operator.
February 7, 2005
DRAFT ZHANG et al.: SSTA WITH CORRELATIONS
3
Using the pre-computed skewness, we are able to determine the linearity of the MAX/MIN operator analytically.
The linear approximation is then applied only when MAX/MIN behaves linear. When MAX/MIN is signicantly
non-linear, the MAX/MIN evaluation is postponed with a form of Max Tuple. We extend the commonly used canonical timing model to be able to represent all possible correlations, including
the path correlations, between timing variables in the circuit. We further explore the sparse structure of the
extended canonical representations of the timing variable and dynamically drop the non-signicant terms so
as to curtail the amount of storage and computation required for implementations.
Since min
(X, Y ) = max(X, Y ), in the interests of brevity, in the rest of this paper, we will only discuss
the MAX operator, with the understanding that the same results can be easily adapted to the MIN operator.
The rest of the paper is organized as following: In section II, previous block based SSTA methods are reviewed
briey; Section III discusses the non-linearity of the MAX operator and our conditional linear approximation method;
Section IV describes the extended canonical timing model and the proposed SSTA algorithm with the technique to
reduce computation complexity. Section V presents a real implementation of of our algorithm in C/C++ and the
testing results with benchmark circuits; Section VI gives the conclusions.
II. A B
RIEF
R
EVIEW OF
C
URRENT
SSTA A
LGORITHMS
For the purpose of timing analysis, the circuit is modeled as a directed acyclic graph(DAG), called a timing
graph, where timing blocks are used to represent the gate/wires in the circuit. Signals propagating through these
blocks will add block delays into their arrival times. Block delays and arrival times are both called timing variables
of the circuit. The history or path history of an arrival time is then dened as the set of block delays through which
the signal ever passes.
A. Timing Variable Propagation
In statistical timing analysis, a timing variable is modeled as a random variable that is characterized by its
distribution of probability density function(p.d.f.) or equivalently, cumulative distribution function(c.d.f.). The goal
of statistical timing analysis is to estimate the distribution of the arrival time in the circuits given the distributions of
each block delay in the circuit. To accrue the over all timing delay distribution, the timing delay random variables
will be joined through two basic operators [5]: ADD
: When an input arrival time X propagates through a block delay Y , the output arrival time will be
Z
= X + Y M AX
: When two arrival times X and Y merge in a block, a new arrival time Z
= max(X, Y ) will be
formulated before the block delay is added.
In the ADD operation, if both X and Y are Gaussian random variables, then Z
= X +Y will also be a G