Page 334 - DSP Integrated Circuits

7.6 Scheduling Algorithms 319

Figure 7.46 Processor schedule for three consecutive intervals

overlap in Figure 7.46. Note also that operations are folded due to the cyclic index-
ing of the multiplier processor space.
The schedule is both rate optimal and processor optimal since three multipli-
ers and one adder are used. The multipliers have a utilization of 10/12 ~ 83%.

The processor schedule can be found by a depth-first search for valid cyclo-
static schedules in the processor-time space with an iteration period equal to the
iteration period bound and number of processors equal to the processor bound.
Only solutions that are processor optimal are considered.
This approach consists of the following steps:
1. Determine the iteration period bound.
2. Depth-first search in the discrete space of
(a) Valid processor optimal and iteration period optimal schedules.
(b) Valid cyclo-static processor assignments.
The same method can be used to find non-rate optimal solutions. In such cases
either the number of processors or the iteration period should be chosen. Cyclo-
static scheduling is nonheuristic since it includes a search of the whole solution
space. The search has a worst-case exponential complexity due to the NP-com-
pleteness of the scheduling problem. However, the size of real problems makes the
solution space reasonably small.
Cyclo-static processor and rate optimal solutions exist for all recursive shift-
invariant signal-flow graphs. The existence of solutions meeting other combina-
tions of optimality criteria may not exist, and are problem dependent. Further,
cyclo-static solutions can be found for a subset of the optimality criteria: processor
optimality, rate optimality, and delay optimality.