Heterogeneous Simulation—Mixing Discrete-Event Models with Dataflow

Journal of VLSI signal processing systems for signal, image and video technology - 1997
Wan-Teh Chang1, Soonhoi Ha2, Edward A. Lee1
1EECS Dept., U.C. Berkeley, USA
2Department of Computer Engineering, Seoul National University, Korea

Tóm tắt

This paper relates to system-level design of signal processing systems, which are often heterogeneous in implementation technologies and design styles. The heterogeneous approach, by combining small, specialized models of computation, achieves generality and also lends itself to automatic synthesis and formal verification. Key to the heterogeneous approach is to define interaction semantics that resolve the ambiguities when different models of computation are brought together. For this purpose, we introduce a tagged signal model as a formal framework within which the models of computation can be precisely described and unambiguously differentiated, and their interactions can be understood. In this paper, we will focus on the interaction between dataflow models, which have partially ordered events, and discrete-event models, with their notion of time that usually defines a total order of events. A variety of interaction semantics, mainly in handling the different notions of time in the two models, are explored to illustrate the subtleties involved. An implementation based on the Ptolemy system from U.C. Berkeley is described and critiqued.

Từ khóa


Tài liệu tham khảo

D. Harel, “Statecharts: A visual formalism for complex systems,” Sci. Comput. Program, Vol. 8, pp. 231-274, 1987.

M. von der Beeck, “A comparison of statecharts variants,” in Proc. of Formal Techniques in Real Time and Fault Tolerant Systems, LNCS863, pp. 128-148, Sprinter-Verlag, Berlin, 1994.

J.T. Buck, S. Ha, E.A. Lee, and D.G. Messerschmitt, “Ptolemy: A framework for simulating and prototyping heterogeneous systems,” Int. Journal of Computer Simulation, special issue on ”Simulation software development,” Vol. 4, pp. 155-182, April, 1994. (http://ptolemy.eecs.berkeley.edu/papers/JEurSim).

A. Benveniste and G. Berry, “The synchronous approach to reactive and real-time systems,” Proceedings of the IEEE, Vol. 79, No. 9, pp. 1270-1282, 1991.

F. Boussinot and R. De Simone, “The ESTEREL language,” Proceedings of the IEEE, Vol. 79, No. 9, Sept. 1991.

A. Benveniste and P. Le Guernic, “Hybrid dynamical systems theory and the SIGNAL language,” IEEE Tr. on Automatic Control, Vol. 35, No. 5, pp. 525-546, May 1990.

N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud, “The synchronous data flow programming language LUSTRE,” Proceedings of the IEEE, Vol. 79, No. 9, pp. 1305-1319, 1991.

E.A. Lee and T.M. Parks, “Dataflow process networks,” Proceedings of the IEEE, May 1995. (http://ptolemy.eecs.berkeley. edu/papers/processNets).

A.M. Turing, “Computability and ?-definability,” J. Symbolic Logic, Vol. 2, pp. 153-163, 1937.

E.L. Post, “Formal reductions of the general combinatorial decision problem,” Am. J. Math., Vol. 65, pp. 197-215, 1943.

A. Church, The Calculi of Lambda-Conversion, Princeton University Press, Princeton, NJ, 1941.

D. Harel, H. Lachover, A. Naamad, A. Pnueli, M. Politi, R. Sherman, A. Shtull-Trauring, and M. Trakhtenbrot, “STATEMATE: A working environment for the development of complex reactive systems,” IEEE Trans. on Software Engineering, Vol. 16, No. 4, April 1990.

J.L. Pino, S. Ha, E.A. Lee, and J.T. Buck, “Software synthesis for DSP using Ptolemy,” Journal on VLSI Signal Processing, Vol. 9, No. 1, pp. 7-21, Jan. 1995. (http://ptolemy.eecs.berkeley.edu/ papers/jvsp_codegen).

S. Ritz, M. Pankert, and H. Meyr, “High level software synthesis for signal processing systems,” in Proc. of the Int. Conf. on Application Specific Array Processors, IEEE Computer Society Press, Aug. 1992.

P. Zepter and T. Grötker, “Abstract multirate dynamic dataflow graph specification for high throughput communication link ASICs,” IEEE VLSI DSP Workshop, The Netherlands, 1993.

A, Kalavade, “System level codesign of mixed hardware-software systems,” Tech. Report UCB/ERL 95/88, Ph.D. Dissertation, Dept. of EECS, University of California, Berkeley, CA 94720, Sept. 1995.

A. Kalavade and E.A. Lee, “A hardware/software codesign methodology for DSP applications,” IEEE Design and Test, Vol. 10, No. 3, pp. 16-28, Sept. 1993.

J. Rasure and C.S. Williams, “An integrated visual language and software development environment,” Journal of Visual Languages and Computing, Vol. 2, pp. 217-246, 1991.

J.B. Dennis, “First version data flow procedure language,” Technical Memo MAC TM61, May, 1975, MIT Laboratory for Computer Science.

G. Kahn, “The semantics of a simple language for parallel programming,” Proc. of the IFIP Congress 74, North-Holland Publishing Co., 1974.

R.M. Karp and R.E. Miller, “Properties of a model for parallel computations: Determinacy, termination, queueing,” SIAM Journal, Vol. 14, pp. 1390-1411, Nov. 1966.

E.A. Lee and D.G. Messerschmitt, “Synchronous data flow,” IEEE Proceedings, Sept. 1987.

R. Lauwereins, P. Wauters, M. Adé, and J.A. Peperstraete, “Geometric parallelism and cyclo-static dataflow in GRAPE-II,” Proc. 5th Int.Workshop on Rapid System Prototyping, Grenoble, France, June, 1994.

G. Bilsen, M. Engels, R. Lauwereins, and J.A. Peperstraete, ”Static scheduling of multi-rate and cyclo-static DSP applications,” Proc. 1994 Workshop on VLSI Signal Processing, IEEE Press, 1994.

D.J. Kaplan et al., “Processing graph method specification version 1.0,” Unpublished Memorandum, The Naval Research Laboratory, Washington, D.C., Dec. 11, 1987.

R. Jagannathan, “Parallel execution of GLU programs,” presented at 2nd International Workshop on Dataflow Computing, Hamilton Island, Queensland, Australia, May 1992.

W.B. Ackerman, “Data flow languages,” Computer, Vol. 15, No. 2, Feb. 1982.

N. Carriero and D. Gelernter, “Linda in context,” Comm. of the ACM, Vol. 32, No. 4, pp. 444-458, April 1989.

F. Commoner and A.W. Holt, “Marked directed graphs,” Journal of Computer and System Sciences, Vol. 5, pp. 511-523, 1971.

P.A. Suhler, J. Biswas, K.M. Korner, and J.C. Browne, “TDFL: A task-level dataflow language,” J. on Parallel and Distributed Systems, Vol. 9, No. 2, June 1990.

J.T. Buck, “Scheduling dynamic dataflow graphs with bounded memory using the token flow model,” Tech. Report UCB/ERL 93/69, Ph.D. Dissertation, Dept. of EECS, University of California, Berkeley, CA 94720, 1993.

C. Ellingson and R.J. Kulpinski, “Dissemination of system-time,” IEEE Trans. on Communications, Vol. Com-23, No. 5, pp. 605-624, May, 1973.

L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Communications of the ACM, Vol. 21, No. 7, July, 1978.

D.G. Messerschmitt, “Synchronization in digital system design,” IEEE Journal on Selected Areas in Communications, Vol. 8, No. 8, pp. 1404-1419, Oct. 1990.

W.T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins University Press, Baltimore, Maryland, 1992.

C. Cassandras, Discrete Event Systems, Modeling and Performance Analysis, Irwin, Homewood, IL, 1993.

H. Hsieh, L. Lavagno, and A. Sangiovanni-Vincentelli, “Embedded system codesign: Synthesis and verification,” presented at NATO-ASI Workshop on Hardware/Software Codesign, Lake Como, June 1995.

D. Verkest, K. Van Rompaey, I. Bolsens, and H. De Man, “POPE-A design environment for heterogeneous hardware/software systems,” to appear, Design Automation for Embedded Systems, 1996.

E.A. Lee, “Consistency in dataflow graphs,” IEEE Transactions on Parallel and Distributed Systems, Vol. 2, No. 2, April 1991.

J. Bier, P. Lapsley, E. A. Lee, and F. Weller, “DSP design tools and methodologies,” Technical Report, Berkeley Design Technology, 39355 California St., Suite 206, Fremont, CA 94538, 1995.

A.V. Oppenheim and R.W. Schafer, Discrete-Time Signal Processing, Englewood Cliffs, NJ, 1989.

Thông tin
Thông tin xuất bản

Journal of VLSI signal processing systems for signal, image and video technology

Thông tin tác giả