Title: Generalized Multidimensional Synchronous Dataflow
Students: Praveen K. Murthy
Advisor: Edward A. Lee
Sponsors: ARPA and the US Air Force (under the RASSP program, contract
F33615-93-C-1317)
Synchronous Dataflow (SDF) [1] is a model that has proven effective for
expressing a large class of one-dimensional multirate signal processing
systems. In the SDF model, a system is represented by a graph in which
the nodes represent computations and arcs represent precedences. Each
node produces and consumes a fixed number of samples and these numbers
are known at compile time. Hence, at compile time, we can construct
efficient, static schedules for SDF graphs.
Multidimensional SDF (MDSDF), a natural extension of SDF [2], allows
multidimensional multirate signal processing systems to be expressed
in a natural and efficient way, and retains the desirable properties of
SDF such as the ability to determine static schedules at compile time.
However, MDSDF allows only rectangular sampling geometries to be expressed
and does not express systems that use, for example, hexagonal sampling.
Non-rectangularly sampled systems are more efficient for certain types of
signals in that they allow the sampling density to be lower than an
equivalent rectangularly sampled system. Thus, it is of interest to
determine models for expressing such systems that can be used in
environments for rapid prototyping such as Ptolemy.
In this project, we are investigating other models of dataflow that allow
static scheduling at compile time but also allow systems with arbitrary
sampling lattices to be expressed. One such model that appears to be
promising, based on some preliminary results, is the cyclo-static dataflow
model [3]. In cyclostatic dataflow, actors are permitted to have a
number of firing phases. In each phase, an actor can produce and consume
a different number of samples. However, since there are only a finite
number of phases for each actor, we can still determine static schedules
for the graph. Even though the model reported in [3] was developed
with the aim of reducing buffer-memory requirements for unidimensional
SDF graphs, an extension of the cyclostatic model to multiple dimensions
appears to be powerful enough to allow non-rectangularly sampled systems
to be expressed formally.
[1] E. A. Lee, "Static Scheduling of Synchronous Dataflow Programs for
Digital Signal Processing," IEEE Trans. on Computers, Jan. 1987.
[2] E. A. Lee, "Multidimensional Streams Rooted in Dataflow", Proceedings
of the IFIP Working Conference on Architectures and Compilation
Techniques for Fine and Medium Grain Parallelism, Jan. 20-22,
1993, Orlando, FL.
[3] G. Bilsen, M. Engels, R. Lauwereins, J. Peperstraete, "Static Scheduling
of Multi-rate Cyclo-static DSP applications," IEEE workshop on VLSI
Signal Processing, Oct. 26-28, 1994.