optimization. This deficiency ultimately leads to a lower
manufacturing yield and decreased circuit robustness, and
results in designs that are sub-optimal in terms of silicon area
or power consumption. A new design strategy is needed to
seamlessly describe these variations and provide chip designers with accurate performance and robustness metrics.
2. BAcKGRounD
Validating the correctness of timing behavior is a paramount
task of design flow. For large digital systems, this is performed
using static timing analysis (STA). In contrast to dynamic
timing simulations which trace circuit response for specific
inputs, static timing analysis ensures correct timing of synchronous digital circuits in an input-independent manner.
5
Virtually all current digital computing systems (such as
microprocessors) are synchronous: all events are coordinated by a clock signal. A synchronous circuit is timing-correct if the signal computed by the combinational circuit
is captured at the memory element, e.g., a flip-flop, on every
latching edge of the clock signal (see Figure 2). The signal
must arrive at the destination flip-flop by the time the latching clock edge arrives. The arrival time at the destination
flip-flop is given by the path with the longest delay through
the combinational circuit. Note that the clock signal arrival
times vary from one memory element to another, and a complete timing analysis involves a simultaneous treatment of
clock and data networks.
To carry out the timing checks, the circuit is represented
by a graph with a vertex for each gate input/output and for the
primary circuit inputs/outputs. A directed edge connects two
vertices if the signal transition on the former causes a signal
transition on the latter. Thus, the graph contains an edge for a
transition between each possible input and output of the gate
and for every interconnect segment. A virtual source node
connected to all primary inputs is added to the graph, along
with a virtual sink node connected to all primary outputs.
Definition: A timing graph G = {V, E, ns, nf} is a directed graph
having exactly one source node ns and one sink node nf,
where V is a set of vertices and E is a set of edges. The weight
associated with an edge corresponds to either the gate delay
or interconnect delay.
An example of a simple circuit and its timing graph is
shown in Figure 3. The timing graph is, or can be made, acyclic, thus the final data structure is a directed acyclic graph
figure 2. A combinational circuit with source and destination
flip-flops.
Combinational Block
Q1
Q2
critical path, 5 logic levels
Clock
96 communIcATIons of The Acm | auGust 2009 | Vol. 52 | no. 8
(DAG). The basic job of static timing analysis is to determine
the maximum delay between the source and the sink node of
the timing graph; this is the focus of the present article. STA
is effective because it relies on algorithms with runtimes
that grow only linearly with circuit size. For DAGs, computing the maximum propagation time can be performed using
a graph traversal following a topological order completed
in O(|V| + |E|) time, where |V| and |E| denote the numbers
of vertices and edges in the timing graph. In this method,
the maximum arrival time to a given node is recorded and
propagated, where the arrival time is the maximum time to
propagate to a node through any path.
Traditional STA deals with the variability of process parameters deterministically by using the worst- and best-case corner strategy, in which edge delays are set to their maximum
or minimum timing values that are possible as a result of
process variation. This strategy fails for several reasons.
First, corner-based deterministic STA produces increasingly
conservative timing estimates, since it assumes that all edges
behave in a correlated manner. This is reasonable only in the
absence of intra-chip variability, which actually increases
with scaling.
13 Furthermore, the probability of simultaneously having the process values corresponding to the corners
shrinks with the growing dimensionality of the process space.
Second, the computational cost of running a corner-based
deterministic analysis becomes prohibitive since the number of corner cases to be checked grows exponentially with
the number of varying process parameters. Third, because it
is difficult to properly identify the corner conditions in the
presence of intra-chip variation, deterministic timing analysis cannot always guarantee conservative results.
3. ReLATeD WoRK
To overcome the limitations of deterministic timing, statistical static timing analysis (SSTA) has been proposed as
an alternate way to accurately estimate circuit delay. SSTA
models gate and interconnect delays as random rather
than deterministic values and relies on fully probabilistic
approaches to handle timing variability.
Definition: A timing graph G in which the ith edge weight di
is random is called a probabilistic timing graph. A path pi
figure 3. (a) Gate schematic of a simple circuit and (b) its timing
graph.
A
D
H
B
C
EF
J
G
I
A
D
ns
nf
B
H
E
F
J
C
G