Decidable Dataflow Models for Signal Processing: Synchronous Dataflow and Its Extensions - Signal Processing Systems - page 1071

2.3.1 Scheduling Techniques for Single Processor Implementations

The main objective for a single processor implementation is to minimize the mem-
ory requirement, considering both the code and the buffer size. Since the problem
of finding a schedule with minimum buffer requirement for an acyclic graph is
NP-complete, various heuristic approaches have been proposed. Since a single
appearance schedule guarantees the minimum code size for inline code generation,
a group of researchers have focused on finding a single appearance schedule that
minimizes the buffer size. Bhattacharyya et al. developed two heuristics: APGAN
and RPMC, to find an SA-schedule that minimizes the buffer requirements [ 3 ] .
Ritz et al. used an ILP formulation to find a flat single appearance schedule that
minimizes the buffer size [ 19 ] considering buffer sharing. Since a flat SA-schedule
usually requires more data buffer than a nested SA-schedule, it is not evident which
approach is better between these two approaches.
Another group of researches tries to minimize only the buffer size. Ade et al.
presented an algorithm to determine the smallest possible buffer size for arbitrary
SDF applications [ 1 ] . Though their work is mainly targeted for mapping an
SDF application onto a Field Programmable Gate Array (FPGA) in the GRAPE
environment, the computed lower bound on the buffer requirement is applicable to
software synthesis. Govindarajan et al. [ 7 ] developed a rate optimal compile time
schedule, which minimizes the buffer requirement by using linear programming
formulation. Since the resultant schedule will not be an SA-schedule in general, a
function coding style should be used to minimize the code size in the generated
code.
No previous work exists that considers all design factors such as coding styles,
buffer sharing, and code sharing. In spite of extensive prior research efforts, finding
an optimal schedule that minimizes the total memory requirement still remains an
open problem, even for single processor implementation.

2.3.2 Scheduling Techniques for Multiprocessor Implementations

A key scheduling objective for multiprocessor implementation is to reduce the
execution length or to maximize the throughput of a given SDF graph. While there
are numerous techniques developed for multiprocessor scheduling, they usually
assume a single rate dataflow graph where each node is executed only once in a
single iteration. And they primarily focus on exploiting the functional parallelism
of an application to minimize the length of the schedule, called makespan .In
stream-based applications, however, maximizing the throughput is more important
than minimizing the schedule length. Pipelining is a popular way of improving
the throughput of a dataflow graph. For example Hoang et al. have proposed a
pipelined mapping/scheduling technique based on a list scheduling heuristic [ 8 ] .
They maximize the throughput of a homogeneous dataflow graph on a homogeneous
multi-processor architecture.