Reactive process networks

ABSTRACT

Data flow process networks are a good model of computation for streaming multimedia applications incorporating audio, video and/or graphics streams. Process networks are concurrent processes communicating streams of data through FIFO channels. They can be executed efficiently and determinately on multiprocessor platforms. However, such stream processing applications are becoming more dynamic, often requiring run-time reconfigurations. Moreover, stream processing is not always an application on its own, but may be a component of a larger application. This application, e.g. a game application, may be control oriented and event driven; events may interact with the streaming component and (re)configure it.In order to capture the interaction between reactive and streaming components as well as reconfiguration in dynamic stream processing, we introduce in this paper a formal, operational and compositional semantics of so-called reactive process networks. This operational semantics can serve as the basis for programming models that allow the programming of streaming components interacting with reactive system components and their reconfigurations. It also supports the construction of analysis and synthesis tools for dynamic streaming multimedia applications. It allows the integration of reactive behaviour in process networks as general as Kahn process networks, but it is also suitable for more restricted and efficient classes of process networks.

REFERENCES

• 1: T. Basten and J. Hoogerbrugge. Efficient execution of process networks. In A. Chalmers, M. Mirmehdi, and H. Muller, editors, Proc. of Communicating Process Architectures 2001, Bristol, UK, September 2001, pages 1--14. IOS Press, 2001.
• 2: B. Bhattacharya and S. Bhattacharyya. Parameterized dataflow modeling for DSP systems. IEEE Transactions on Signal Processing, 49(10):2408--2421, October 2001.
• 3: Shuvra S. Bhattacharyya , Praveen K. Murthy , Edward A. Lee, Synthesis of Embedded Software from Synchronous Dataflow Specifications, Journal of VLSI Signal Processing Systems, v.21 n.2, p.151-166, June 1999 [doi>10.1023/A:1008052406396]
• 4: J. Dean Brock , William B. Ackerman, Scenarios: A Model of Non-Determinate Computation, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.252-259, April 19-25, 1981
• 5: A. A. Faustini, An Operational Semantics for Pure Dataflow, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.212-224, July 12-16, 1982
• 6: M. Geilen and T. Basten. Requirements on the execution of Kahn process networks. In P. Degano, editor, Proc. of the 12th European Symposium on Programming, ESOP 2003, Warsaw, Poland, April 7-11, 2003. LNCS Vol.2618. Springer Verlag, Berlin, 2003.
• 7: A. Girault, B. Lee, and E. Lee. Hierarchical finite state machines with multiple concurrency models. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 18(6):742--760, June 1999.
• 8: M. Goel. Process networks in Ptolemy II. Technical Memorandum UCB/ERL No. M98/69, University of California, EECS Dept., Berkeley, CA, December 1998.
• 9: G. Kahn. The semantics of a simple language for parallel programming. In J. Rosenfeld, editor, Information Processing 74: Proc. of the IFIP Congress 74, Stockholm, Sweden, August 1974, pages 471--475. North-Holland, Amsterdam, Netherlands, 1974.
• 10: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 11: Bilung Lee , Edward A. Lee, Specification and design of reactive systems, 2000
• 12: E. Lee. Overview of the Ptolemy project. Technical Memorandum UCB/ERL No. M01/11, University of California, EECS Dept., Berkeley, CA, March 2001.
• 13: E. Lee and D. Messerschmitt. Synchronous data flow. IEEE Proceedings, 75(9):1235--1245, Sept. 1987.
• 14: Nancy Lynch , Eugene W. Stark, A proof of the Kahn principle for input/output automata, Information and Computation, v.82 n.1, p.81-92, July 1989 [doi>10.1016/0890-5401(89)90066-7]
• 15: A. Martin. The probe: An addition to communication primitives. Information Processing Letters, 20(3):125--130, 1985.
• 16: S. Neuendorffer and E. A. Lee. Hierarchical reconfiguration of dataflow models. In Proc. Second ACM-IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2004). IEEE Computer Society Press, 2004. to appear.
• 17: Thomas Martyn Parks, Bounded scheduling of process networks, University of California at Berkeley, Berkeley, CA, 1996
• 18: Karsten Strehl , Lothar Thiele , Matthias Gries , Dirk Ziegenbein , Rolf Ernst , Jürgen Teich, FunState—an internal design representation for codesign, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.4, p.524-544, Aug. 2001 [doi>10.1109/92.931229]
• 19: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Languages, Theory

Keywords:
media processing, multiprocessor systems, operational semantics, process networks, reactive systems, signal processing