Page 331 - DSP Integrated Circuits

316 Chapter? DSP System Design

The first step in force-directed
scheduling is to perform an ASAP and
an ALAP schedule on a fully specified
signal-flow graph. This will give the
earliest and latest times for all
operations and their execution time
frames. Each operation is given a
probability to be assigned eventually to
a time slot in its execution time frame
as shown in Figure 7.42. The
probabilities for each time slot are
added into a distribution graph, (DG),
one for each type of operation, as shown
in Figure 7.43.
Now, forces are associated with the
restriction of the original time frame for
operations [to, t-\] and [t a, tfr] where t a > to
and tb < t\ are calculated using the
Figure 7.42 Uti ot multiplication
formula and addition

where DG(i) is the value of the distribution graph for that type of operation in
time slot i. For an assignment to a single time slot, k, Equation (7.5) reduces to

This force is associated
with the cost of assigning an
operation to time slot k. How-
ever, assigning an operation
will have an influence on the
time frames of adjacent oper-
ations. Therefore indirect
forces representing the cost
of the assignment will
restrict the time frames of
other operations. This calcu-
lation is done according to
Equation (7.6). The total
force (self force plus indirect
forces) is used to guide the
scheduling. Scheduling is
done by assigning the opera-
tions one at a time while
always choosing the opera- Figure 7.43 Execution time frames and associated
tion with the least total force. probabilities