Generalized Multidimensional Synchronous Dataflow

Multidimensional SDF (MDSDF) [1], 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 and does not allow systems that use, for example, hexagonal sampling to be expressed. 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 and simulation such as Ptolemy.

We have developed a generalization of MDSDF to allow modeling of systems that have arbitrary sampling lattices and arbitrary, non-rectangular decimators and interpolators [3]. The generalization is based on associating a "support matrix" with each arc in the graph; this matrix is, in some sense, a dual of the basis matrix for the sampling lattice of the signal on that arc. The general model can also be scheduled statically, although there are many interesting optimization issues to be solved.

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. P. K. Murthy and E. A. Lee, "An Extension of Multidimensional Synchronous Dataflow to Handle Arbitrary Sampling Lattices," UCB Tech. Memorandum UCB/ERL M95/59, Electronics Research Lab., UC Berkeley, CA 94720, March, 20 1995