Civil Engineering Reference
In-Depth Information
path branches out from the node on that has the smallest
branch_slack
for
the edge for some successor node of This path is identical to up
to some node after which the remaining nodes are obtained by identifying
the first successor node in the graph until the sink is reached. Once this path
is identified, the
branch
-
slack
values on the branch points on this path are used
to compute the delays for the corresponding candidate path delays, and these
are added to the ordered list.
In general, once the most critical paths have been identified, the
most critical path is computed by choosing the longest delay path on the ordered
list. The branch points off this path are then used to update the ordered list.
For efficiency, the ordered list is maintained as a heap [CLR90].
Example
:The graph listed in Figure 5.9 shows a DAG on which the most
critical paths are to be found. The first step is to find the values of the
max
-
delay
-
to
-
sink
and
branch
-
slack
throughout the graph; these are shown in
the figure using the same scheme as in Figure 5.8. A trace of the execution
that shows the computation of the five most critical paths is shown below.
Critical
path #
1
2
3
4
5
Path
Delay
Available branch point
[
branch_slack,
path delay]
A[1,12], B[1,12], C[2,11], F[3,10]
B[1,11], E[2,10], C[2,10], F[3,9]
A[1,11], C[2,10]
A[1,10], B[1,10], F[3,8]
E[2,9], C[2,9]
Branch point
used (path #)
ABFCD
AEBFCD
ABCD
ABFCGD
AEBCD
13
12
12
11
11
A[1,12] (1)
B[1,12] (1)
C[2,11] (1)
B[1,11] (2)
The first path that is identified is the most critical path, ABFCD, with a
delay of 13. The available branch points and the delays on the next most
critical paths using each of those branch points may be calculated using the
corresponding branch slacks as shown, and arranged in the heap in order of
the delay. The next critical path is found by taking the largest delay path off
the heap. Of the two choices of branch points A and B, A is chosen if it is
arranged on the heap before B, leading the the second most critical path. The
procedure continues: up to the fourth most critical path, all paths are derived
from the most critical path. However, observe that the fifth-most critical path
corresponds to the branch slack along B on the second-most critical path.
5.5 SUMMARY
In this chapter, we have developed the material from the earlier chapters to
present techniques that find the delay of a combinational block. The critical
path method for delay computation was first presented, followed by a discussion
on false paths and timing analysis in the presence of false paths.
