Page 330 - DSP Integrated Circuits

7.6 Scheduling Algorithms 315

requires that the execution of the process may be preempted. This method has
proven to be execution-time-optimal for a single processor.
The slack time algorithm [11] resembles the earliest deadline algorithm. In
each time slot, it schedules the process whose slack time is least. Slack time is the
time from the present to the deadline minus the remaining processing time of a
process. It is equivalent to shimming delay. This method has been proven to give
solutions that are better than or equally as good as solutions obtained using the
earliest deadline algorithm in cases where more than one processor is used.

7.6.3 Linear Programming

The scheduling problem is a combinatorial problem that can be solved by integer
linear programming (LP) methods [1, 13]. These methods (for example, the sim-
plex method and the interior point methods) find the optimal value of a linear cost
function while satisfying a large set of constraints. The precedence relations for
the operations to be scheduled represent a set of inequalities in the form of nonfea-
sible time intervals. Using linear programming methods, the optimal solution can
be obtained. Problems with a few thousand constraints and several thousand vari-
ables can be tackled on a small PC while workstations can often handle problems
with variables in the tens of thousands or even greater. However, very large prob-
lems with many operations might be intractable due to NP-completeness of the
scheduling problem and the cost function being limited to a linear function. Linear
programming methods are nonheuristic.
Integer LP models are ones where the answers may not take fractional values.
This is a very much harder problem than ordinary LP.

7.6.4 Critical Path List Scheduling
Critical path list scheduling [6—7, 14], is related to ASAP scheduling. It is one
method in the class of list scheduling methods. The first step in list scheduling
methods is to form an ordered list of operations to be performed. Secondly, the
operations are picked one by one from this list and assigned to a free resource
(PE). In critical path list scheduling, the list is formed by finding the critical paths
in the DAG of the algorithm. Operations are ordered according to path length from
the start nodes in the DAG. The method takes into account the fact that operations
on the time critical path must be given a higher priority than others. In order to
achieve as short an execution time as possible, not necessarily equal to the mini-
mum sample period, operations on the critical path must be scheduled first. Criti-
cal path list scheduling is a constructive and heuristic method that leads to
optimal schedules if the precedence graph is a tree and all processing times are
equal. Other forms of list scheduling methods are obtained by using different heu-
ristics for scheduling the operations that do not belong to the critical paths.

7.6.5 Force-Directed Scheduling

The force-directed scheduling method attempts to distribute the operations in
time so that the resources required are minimized under a fixed execution time
constraint [18, 19].