Page 314 - DSP Integrated Circuits

7.5 Scheduling Formulations 299

Figure 7.18 K circularly concatenated computation graphs

Each computation graph represents the operations and the shimming and
equalizing delays within one sample interval. The delay elements in the critical
loop are replaced by new delay elements, representing a delay of T' = K T. If the
required sample rate is lower than the iteration period bound, an appropriated
amount of equalizing delay must be inserted into each loop so that their lengths
equal a multiple of the desired sample period. It may help to imagine the
computation graphs drawn on a cylinder of circumference equal to the
scheduling period (which is a multiple of the sample period, as was discussed in
Chapter 6).
This problem formulation forces the schedule to be periodic—i.e., the length of
the schedule is proportional to K. Unfortunately, it is not possible to determine the
best choice of Kin the general case. In order to attain the minimum sample period,
it is necessary to perform cyclic scheduling of the operations belonging to several
sample successive intervals if
Q The computation time for a PE is longer than T mi n or
Q The critical loop(s) contains more than one delay element.
Generally, the critical loop should be at least as long as the longest execution
time for any of the PEs in the loop. For bit-serial arithmetic, the execution times of
the processing elements are normally longer than the minimum sample period.
The minimum sample period, using an unlimited amount of resources, is
achieved for K = NICP- A more interesting case is to obtain T mi n when using a min-
imum number of resources. This is achieved if only one CP exists, and a proper
scheduling is done, with

where m = integer. In order to find the actual resource minimum the best sched-
ules, with minimum resources, must be found for all reasonable values of m. Typi-
cal values for m are in the range 1 to 10.
If several CPs exist, the scheduling shall instead be done for