A dynamic dataflow model suitable for efficient mixed hardware and software implementations of DSP applications

ABSTRACT

This paper presents an analytical model for the behavior of dataflow graphs with data-dependent control flow and discusses its suitability to the generation of efficient software and hardware implementations of digital signal processing (DSP) applications. In the model, the number of tokens produced or consumed by each actor is given as a symbolic function of the Boolean values in the system; in addition, it may vary cyclically to permit more memory-efficient multirate implementations. The model can be used to extend the ability of block-diagram-oriented systems for DSP design, such as Ptolemy [1], to produce efficient hardware and software implementations; this permits the hardware-software codesign techniques of [2] to be efficiently targeted at a wider class of problems, those involving some asynchronous behavior, for example.

REFERENCES

• 1: J. Buck, S. Ha, E. A. Lee, D. G. Messerschmitt, "Ptolemy: a Framework for Simulating and Prototyping Heterogeneous Systems", International Journal of Computer Simulation, Vol. 4, pp. 155--182, 1994.
• 2: Asawaree Kalavade , Edward A. Lee, A Hardware-Software Codesign Methodology for DSP Applications, IEEE Design & Test, v.10 n.3, p.16-28, July 1993 [doi>10.1109/54.232469]
• 3: M. Chiodo et al., "A Formal Specification Model for Hardware/Software Codesign," Proc. International Workshop on Hardware-Software Co-Design, Cambridge, Mass., October 1993.
• 4: F. Boussinot, R. De Simone, "The ESTEREL Language," Proceedings of the IEEE, Vol. 79, No. 9, September 1991.
• 5: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 6: A. Benveniste and P. Le Guernic, "Hybrid Dynamical Systems Theory and the SIGNAL Language," IEEE Trans. on Automatic Control, pp. 535--546, May, 1990.
• 7: N. Halbwachs, P. Caspi, P. Raymond, D. Pilaud, "The Synchronous Data Flow Programming Language LUSTRE," Proceedings of the IEEE, Vol. 79, No. 9, 1991, pp. 1305--1319.
• 8: P. N. Hilfinger, "A High-Level Language and Silicon Compiler for Digital Signal Processing," Proc. Custom Integrated Circuits Conf., IEEE Computer Society Press, pp. 213--216, 1985.
• 9: E. A. Lee, D. G. Messerschmitt, "Synchronous Dataflow," Proceedings of the IEEE, September 1987.
• 10: B. Dennis, "First Version of a Dataflow Procedure Language," MIT/LCS/TM-61, Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge MA 02139, 1975.
• 11: H. Printz, "Automatic Mapping of Large Signal Processing Systems to a Parallel Machine," Memorandum CMU-CS-91-101, School of Computer Science, Carnegie-Mellon University, May 1991.
• 12: W. H. Ho, E. A. Lee, D. G. Messerschmitt, "High Level Dataflow Programming for Digital Signal Processing," VLSI Signal Processing Ill, IEEE Press 1988.
• 13: S. Ritz, M. Pankert, H. Meyr, "High Level Software Synthesis for Signal Processing Systems", Proceedings of the International Conference on Application Specific Array Processors, Berkeley, CA, August, 1992.
• 14: H. De Man, J. Rabaey, P. Six, L. Claesen, "CATHEDRALII: a silicon compiler for digital signal processing," IEEE Design and Test Magazine, pp. 13--25, Dec. 1986.
• 15: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 16: J. T. Buck and E. A. Lee, "Scheduling Dynamic Dataflow Graphs With Bounded Memory Using the Token Flow Model," Proc. of ICASSP '93, 1993.
• 17: Joseph Tobin Buck , Edward A. Lee, Scheduling dynamic dataflow graphs with bounded memory using the token flow model, 1993
• 18: E. A. Lee, Consistency in Dataflow Graphs, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.223-235, April 1991 [doi>10.1109/71.89067]
• 19: G. Bilsen, M. Engels, R. Lauwereins, J. A. Peperstraete, "Static Scheduling of Multi-rate and Cyclo-static DSP-applications," Proc. IEEE Workshop on VLSI Signal Processing, to appear, 1994.
• 20: G. R. Gao, R. Govindarajan, P. Panangaden, "Well-Behaved Programs for DSP Computation," Proc. ICASSP 1992, San Francisco, California, March 1992.
• 21: Shuvra S. Bhattacharyya , Joseph T Buck , Soonhoi Ha , Edward A. Lee, Generating Compact Code From Dataflow Specifications of, University of California at Berkeley, Berkeley, CA, 1993
• 22: Gilbert Christopher Sih, Multiprocessor scheduling to account for interprocessor communication, University of California at Berkeley, Berkeley, CA, 1992
• 23: Soonhoi Ha, Compile-time scheduling of dataflow program graphs with dynamic constructs, University of California at Berkeley, Berkeley, CA, 1992
• 24: P. D. Hoang and J. M. Rabaey, "Scheduling of DSP Programs Onto Multiprocessors for Maximum Throughput," IEEE Trans. Signal Processing, pp. 2225--2235, June 1993.