Page 344 - DSP Integrated Circuits

7.8 Resource Allocation 329

values. Usually, the largest number of concurrent processes determines the num-
ber of resources required. In fact, both the resource allocation and assignment
steps are usually simple one-to-one mappings where each process can be bounded
to a free resource. However, as will be shown in Example 7.8, more resources than
there are concurrent processes are required in some cases. This fact makes it diffi-
cult to evaluate the cost function to be minimized by the scheduling.

EXAMPLE 7.8
Consider the periodic algorithm whose schedule is
shown in Figure 7.63. The iteration period is
assumed to be 3. Obviously, there are at most two
concurrent operations. Show that three PEs are
required.
Figure 7.64 shows the same schedule folded
modulo(3). Still, there are at the most two concur-
rent operations. Now, let each row represent a PE.
Obviously, it is not enough to use only two PEs,
since a process that is folded modulo(3) must be Figure 7.63 Schedule
continued on the same row in the diagram, i.e.,
continued in the same PE. It is illustrative here to draw the schedule on the cir-
cumference of a cylinder. In this case it is not possible to find a schedule that uses
fewer than three PEs assuming that the schedule is nonpreemptive. A possible PE
assignment with three PEs is shown in Figure 7.65.
me total amount 01 storage required can be deter-
mined from the lifetime table. Obviously, the largest num-
ber of concurrent storage processes is a lower bound of the
storage requirement. In practice, it is important early in
the design process to determine the number of logical
memories required. This number equals the largest num-
ber of simultaneous memory transactions. The logical
memories may in a low-speed application be implemented
by a single physical memory, while in high-speed applica-
Figure 7.64 Folded
tions several physical memories must be used.
We stress that scheduling the processes is a crucial schedule
design step, since it determines the number of PEs, mem-
ories, and communication channels required.

Figure 7.65 PE schedule for two consecutive sample periods