Page 258 - DSP Integrated Circuits

6.6 Computation Graphs 243

6.6 COMPUTATION GRAPHS

It is convenient to describe the computational properties of an algorithm with a
computation graph that combines the information contained in the signal-flow
graph with the corresponding precedence graph for the operations. The
computation graph will be used in Chapter 7 as the basis for scheduling the
operations. Further, the storage and communication requirements can be derived
from the computation graph. In this graph, the signal-flow graph in precedence
form remains essentially intact, but the branches representing the arithmetic
operations are also assigned appropriate execution times. Branches with delay
elements are mapped to branches with delay. As will be discussed in the following
sections, additional branches with different types of delay must often be inserted
to obtain consistent timing properties in the computation graph. These delays
will determine the amount of physical storage required to implement the
algorithm.

6.6.1 Critical Path

By assigning proper execution times to the operations, represented by the
branches in the precedence graph, we obtain the computation graph. The longest
(time) directed path in the computation graph is called the critical path (CP) and
its execution time is denoted TCP- Several equally long critical paths may exist. For
example, there are two critical paths in the computation graph shown in Figuure.
6.25. The first CP starts at node v\(n) and goes through nodes u±, 11%, 113, UQ, uj,
and y(n) while the second CP begins at node v<i(ri) and goes through nodes u§, u%,
us,UQ,UT,andy(n).
Note that the critical path will not necessarily determine the shortest time in
which the algorithm can be computed since it represents only the precedence
between operations within a sample interval and neglects intersample interval
precedences. The minimum sample period is determined by the recursive loops in
the algorithm (see section 6.6.4). The critical path may in some cases, therefore, be
longer than the minimum sample period. Later, in section 6.8.2, we will discuss
methods of breaking the critical path into smaller pieces so that the maximum
sample rate can be achieved.

6.6.2 Equalizing Delay
Assume that an algorithm shall be executed with a sample period T and the time
taken for the arithmetic operations in the critical path is TCP, where TCP < T. Then
additional delay, which is here called equalizing delay, has to be introduced into all
branches that cross an arbitrary vertical cut in the computation graph, as
illustrated in Example 6.4. This delay accounts for the time difference between a
path and the length of the sample interval. The required duration of equalizing
delay in each such branch is

The amount of equalizing delay, which usually corresponds to physical stor-
age, can be minimized by proper scheduling of the operations, which will be fur-
ther discussed in Chapter 7.