Page 328 - DSP Integrated Circuits

7.6 Scheduling Algorithms 313

7.6 SCHEDULING ALGORITHMS

Scheduling algorithms are basically combinatorial optimization techniques. They
search the solution space for a solution with favorable properties. Combinatorial
optimization methods can be characterized as
Q Heuristic methods
- Constructive methods
- Iterative methods
Q Nonheuristic methods

Heuristic methods use a set of rules that limit the search in the solution space
in order to shorten the required search time. This is often necessary since most
scheduling problems have been shown to be NP-complete. A drawback of heuristic
methods is that they may get stuck in local optima. Conversely, nonheuristic
methods will find the optimal solution, but they will, in general, require excessive
run times since they traverse the whole solution space. Exhaustive searches can
be made effectively by depth-first or breadth-first approaches [3].
Constructive methods construct a solution whereas iterative methods produce
better solutions iteratively from older ones. Constructive methods can be used to
find an initial solution for an iterative method. Both these types of methods
traverse only a part of the solution space and yield suboptimal solutions.
The following optimization techniques are commonly used for scheduling:

U ASAP (as soon as possible) and ALAP (as late as possible) scheduling
Q Earliest deadline and slack time scheduling
Q Linear programming methods
Q Critical path list scheduling
Q Force-directed scheduling
Q Cyclo-static scheduling
Q Simulated annealing
Q Genetic algorithms

7.6.1 ASAP and ALAP Scheduling
Many real-life projects start with an ASAP schedule
but are completed according to an ALAP schedule.
Ragnar Arvidsson, Ericsson Radar Electronics

ASAP (as soon as possible) scheduling [8, 14, 17], simply schedules operations as
soon as possible. A computation can be performed as soon as all of its inputs are
available—i.e., all predecessors have been performed. The aim is to obtain the
shortest possible execution time without considering resource requirements. Fig-
ure 7.40 shows an example of an ASAP schedule.
ALAP (as late as possible) is a method similar to ASAP. Figure 7.41 shows
an example of an ALAP schedule. In ALAP the operations are scheduled as late
as possible. ASAP and ALAP scheduling are often used to determine the time
range in which the operations can be scheduled. This range is often referred to
as life-span.