Shared Memory Implementations of Synchronous Dataflow Specifications Using Lifetime Analysis Techniques

View/ Open
Date
1999-06-08Author
Murthy, Praveen K.
Bhattacharyya, Shuvra S.
Metadata
Show full item recordAbstract
There has been a proliferation of block-diagram environments for
specifying and prototyping DSP systems. These include tools from
academia like Ptolemy [6], and commercial tools like SPW from Cadence
Design Systems, and Cossap from Synopsys. The block diagram languages
used in these environments are usually based on dataflow semantics
because various subsets of dataflow have proven to be good matches
for expressing and modeling signal processing systems. In particular,
synchronous dataflow (SDF)[14] has been found to be a particularly good
match for expressing multirate signal processing systems [5].
One of the key problems that arises during synthesis from an SDF
specification is scheduling. Past work on scheduling [3] from SDF has
focused on optimization of program memory and buffer memory. However,
in [3], no attempt was made for overlaying or sharing buffers. In this
paper, we formally tackle the problem of generating optimally compact
schedules for SDF graphs, that also attempt to minimize buffering mem-
ory under the assumption that buffers will be shared. This will result in
schedules whose data memory usage is drastically lower than methods in
the past have achieved. The method we use is that of lifetime analysis;
we develop a model for buffer lifetimes in SDF graphs, and develop
scheduling algorithms that attempt to generate schedules that minimize
the maximum number of live tokens under the particular buffer lifetime
model. We develop several efficient algorithms for extracting the relevant
lifetimes from the SDF schedule. We then use the firstfit heuristic for
packing arrays efficiently into memory. We report extensive experimental
results on applying these techniques to several practical SDF systems,
and show improvements that average 50% over previous techniques, with
some systems exhibiting upto an 83% improvement over previous techniques.
Also cross-referenced as UMIACS-TR-99-32