Civil Engineering Reference
In-Depth Information
time at
is max(2, 1) + 1 = 3. At the end of this step, both
and
are
ready for processing and are added to the queue.
Step 7
Gate is scheduled, and its rise and fall arrival times are calculated,
respectively, as max(1, 5) + 3 = 8 and max(2, 3) + 2 = 5.
Step 8
Gate is now processed, and its rise and fall arrival times are found
to be max(5, 2) + 2 = 7 and max(3, 4) + 2 = 6, respectively. This sets the
stage for adding gate to the queue.
Step 9
Gate is scheduled, and its rise and fall arrival times are max(5, 6) +
1 = 7 and max(8, 7) + 3 = 11, respectively. The queue is now empty and the
algorithm terminates.
The worst-case delay for the entire block is therefore max(7, 11) = 11 units.
5.2.2 Critical paths, required times, and slacks
The
critical path,
defined as the path between an input and an output with
the maximum delay, can now easily be found by using a traceback method.
We begin with the block whose output is the primary output with the latest
arrival time: this is the last block on the critical path. Next, the latest arriving
input to this block is identified, and the block that causes this transition is the
preceding block on the critical path. The process is repeated recursively until
a primary input is reached.
In the example, we begin with Gate at the output, whose falling transition
corresponds to the maximum delay. This transition is caused by the rising
transition at the output of gate which must therefore precede on the
critical path. Similarly, the transition at is effected by the faling transition
at the output of and so on. By continuing this process, the critical path
from the input to the output is identified as being caused by a falling transition
at either input or and then progressing as follows: rising
A useful concept is the notion of the
required time
,
R
, at a node in the
circuit. If a circuit is provided with a set of arrival time constraints at each
output node, then on the completion of the CPM traversal, one may check
whether those constraints are met or not. If they are not met, it is useful to
know which parts of the circuit should be sped up and how, and if they are, it
may be possible to save design resources by resynthesizing the circuit to slow
it down. In either case, the required time at each node in the circuit provides
useful information. At any node in the circuit, if the arrival time exceeds the
required time, then the path that this node lies on must be sped up.
The computation of the required time proceeds as follows. At each primary
output, the rise/fall required times are set according to the specifications pro-
vided to the circuit. Next, a backward topological traversal is carried out,
processing each gate when the required times at all of its fanouts are known.
In essence, this is equivalent to performing a CPM traversal with
