Page 307 - DSP Integrated Circuits

292 Chapter 7 DSP System Design

7.4 SCHEDULING

So much to schedule, so little time.

Scheduling operations is a common problem that appears in a variety of set-
tings—for example, operating systems, real-time systems, and distributed-par-
allel computer systems. A process is an arbitrarily large, or small, computational
task, and is therefore a more general concept than a simple operation. A process
that is allowed to be halted while it is executed and continued in another PE, or
in the same PE at a later stage, is called a preemptive process, in contrast to the
opposite, a nonpreemptive process. A preemptive process can be split into smaller
processes. Processes to be scheduled are characterized by their start or release
time, duration, or deadline, and they may arrive at random time instances or
periodically. Hard real-time processes are processes for which the deadline must
be met.
If all processes are known in advance, it is possible to perform scheduling
before run time, yielding a static schedule that will not change. Static schedules
need only be done once. Conversely, a dynamic schedule must be used whenever
the process characteristics are not completely known. Scheduling must therefore
be done dynamically at run time by a scheduler that runs concurrently with the
program. The use of dynamic schedulers may cause a significant overhead since
most scheduling problems are NP-complete. Fortunately, most DSP algorithms are
amenable to static scheduling. In fact, for such algorithms it is possible to synthe-
size optimal architectures.
The processes shall be mapped according to the schedule onto a hardware
structure. Due to the complexity of the problem, the scheduling, resource alloca-
tion, and assignment are usually separated into distinct problems. Resource allo-
cation involves the allocation of physical resources such as PEs, memories, and
communication channels. Assignment involves the selection of a particular
resource to perform a given function.
The following five criteria of optimality are commonly used for static scheduling.

Q Sample period optimal
Q Delay optimal
Q Resource optimal
Q Processor optimal
Q Memory optimal

A schedule is sample period optimal or rate optimal if it has a sample period
equal to the iteration period bound.
A schedule is delay optimal (latency) if it has a delay from input to output
equal to the delay bound. The delay bound is the shortest possible delay from
input to output of the algorithm.
A resource optimal schedule yields a minimum amount of resources for given
performance constraint, e.g., sample rate and/or latency. It is interesting to note
that general-purpose computing corresponds to a resource limited scheduling prob-
lem while real-time processing, including most DSP applications, corresponds to a
resource adequate scheduling problem.