Civil Engineering Reference
In-Depth Information
primary output at the end of that path. Therefore, finding the maximum delay
through a combinational block is a vital subtask, and we will address this issue
in this section. Alternatively, a combinational block that is to be treated as
a black box must be characterized in terms of its delays from each input to
each output; this is a vital problem in, for example, when the analysis involves
hierarchically defined blocks with such timing abstractions. For level-clocked
circuits, the timing relations are more complex, but the machinery developed
in this section will nevertheless be useful. A detailed discussion on the analysis
of sequential circuits based on combinational block delays will be presented in
Chapter 7.
Delay calculation for a combinational logic block
5.2.1
In this section, we will present techniques that are used for the static timing
analysis of digital combinational circuits. The word “static” alludes to the
fact that this timing analysis is carried out in an input-independent manner,
and purports to find the worst-case delay of the circuit over all possible input
combinations. The computational efficiency of such an approach has resulted
in its widespread use, even though it has some limitations that we will describe
in Section 5.3.
A method that is commonly referred to as PERT (Program Evaluation and
Review Technique) is popularly used in static timing analysis. In fact, this is a
misnomer, and the so-called PERT method discussed in most of the literature
on timing analysis refers to the CPM (Critical Path Method) that is widely
used in project management
2
. The CPM procedure is now an integral part
of most fast algorithms for circuit delay calculation, and in this topic we will
endeavor to use the correct terminology.
Before proceeding, it is worth pointing out that while CPM-based methods
are the dominantly in use today, other methods for traversing circuit graphs
have been used by various timing analyzers: for example, depth-first techniques
have been presented in [Jou87b].
The algorithm, applied to a timing graph
G =
(
V
,
E
), can be summarized
by the pseudocode shown in Figure 5.2. The procedure is best illustrated by
means of a simple example. Consider the circuit in Figure 5.3, which shows an
interconnection of blocks. Each of these blocks could be as simple as a logic
gate or could be a more complex combinational block, and is characterized by
the delay from each input pin to each output pin. For simplicity, this example
will assume that for each block, the delay from any input to the output is
identical. Moreover, we will assume that each block is an inverting logic gate
such as a NAND or a NOR, as shown by the “bubble” at the output. The
two numbers, inside each gate represent the delay corresponding to the
delay of the output rising transition, and that of the output fall transition,
respectively. We assume that all primary inputs are available at time zero,
so that the numbers “0/0” against each primary input represent the worst-case
rise and fall arrival times, respectively, at each of these nodes. The critical path
method proceeds from the primary inputs to the primary outputs in topological
