DocumentCode :
786869
Title :
Multidimensional synchronous dataflow
Author :
Murthy, Praveen K. ; Lee, Edward A.
Author_Institution :
Fujitsu Labs of America, Sunnyvale, CA, USA
Volume :
50
Issue :
8
fYear :
2002
fDate :
8/1/2002 12:00:00 AM
Firstpage :
2064
Lastpage :
2079
Abstract :
Signal flow graphs with dataflow semantics have been used in signal processing system simulation, algorithm development, and real-time system design. Dataflow semantics implicitly expose function parallelism by imposing only a partial ordering constraint on the execution of functions. One particular form of dataflow called synchronous dataflow (SDF) has been quite popular in programming environments for digital signal processing (DSP) since it has strong formal properties and is ideally suited for expressing multirate DSP algorithms. However, SDF and other dataflow models use first-in first-out (FIFO) queues on the communication channels and are thus ideally suited only for one-dimensional (1-D) signal processing algorithms. While multidimensional systems can also be expressed by collapsing arrays into 1-D streams, such modeling is often awkward and can obscure potential data parallelism that might be present. SDF can be generalized to multiple dimensions; this model is called multidimensional synchronous dataflow (MDSDF). This paper presents MDSDF and shows how MDSDF can be efficiently used to model a variety of multidimensional DSP systems, as well as other types of systems that are not modeled elegantly in SDF. However, MDSDF generalizes the FIFO queues used in SDF to arrays and, thus, is capable only of expressing systems sampled on rectangular lattices. This paper also presents a generalization of MDSDF that is capable of handling arbitrary sampling lattices and lattice-changing operations such as nonrectangular decimation and interpolation. An example of a practical system is given to show the usefulness of this model. The key challenge in generalizing the MDSDF model is preserving static schedulability, which eliminates the overhead associated with dynamic scheduling, and preserving a model where data parallelism, as well as functional parallelism, is fully explicit
Keywords :
data flow computing; data flow graphs; interpolation; multidimensional signal processing; queueing theory; signal sampling; FIFO queues; algorithm development; communication channels; data parallelism; dataflow semantics; digital signal processing; first-in first-out queues; functional parallelism; graphical programming model; interpolation; lattice-changing operations; multidimensional DSP systems; multidimensional synchronous dataflow; multirate DSP algorithms; nonrectangular decimation; partial ordering constraint; programming environments; real-time system design; rectangular lattices; sampling lattices; signal flow graphs; signal processing system simulation; static scheduling; Communication channels; Digital signal processing; Dynamic scheduling; Flow graphs; Lattices; Multidimensional signal processing; Multidimensional systems; Programming environments; Real time systems; Signal processing algorithms;
fLanguage :
English
Journal_Title :
Signal Processing, IEEE Transactions on
Publisher :
ieee
ISSN :
1053-587X
Type :
jour
DOI :
10.1109/TSP.2002.800830
Filename :
1018801
Link To Document :
بازگشت