Specification of Control Flow in Ptolemy


Researchers: Bilung Lee
Advisor:Edward A. Lee
Sponsor:

The complexity of systems today continues to grow rapidly. One major source of complexity arises from concurrency, and various models of computation have been explored to deal with it. However, concurrency is not the only major source of complexity. Increasingly intricate control also adds more difficulty and attracts more attention for designers.

Control functionality is needed for the proper sequencing of the computation tasks, switching and coordinating between different operation modes, etc. Finite state machines (FSMs) have long been used to specify control flow for control-dominated problems. In large systems, however, the control functionality can become so complex that the flat, sequential FSM model becomes impractical.

In this project, we add hierarchy and heterogeneity to the FSM. This allows the FSM to be hierarchically combined with various concurrency models, in particular dataflow [2], discrete events [3] and synchronous/reactive [4] models. In this heterogeneous model, the semantics of FSM, concurrency and hierarchy are naturally supported. Unlike most formalisms that combine FSMs with concurrency models, such as Statecharts [1] and its variants, our scheme decouples the FSM from the concurrency models, enabling selection of the most appropriate concurrency model for the problem at hand.

The proposed idea has been under implementation in the Ptolemy software environment. We have created a preliminary implementation of this mixed model in Ptolemy. Systems can be built by hierarchically nesting FSMs and concurrency models.

Some possible applications include the simulation and rapid prototyping of software systems such as telecommunications control software, and the embedded signal processing systems.

[1]
D. Harel, "Statecharts: A Visual Formalism for Complex Systems," Science of Computer Programming, vol. 8, pp. 231-274, 1987.
[2]
J. B. Dennis, "First Version Data Flow Procedure Language", Technical Memo MAC TM61, May, 1975, MIT Laboratory for Computer Science.
[3]
C. Cassandras, "Discrete Event Systems, Modeling and Performance Analysis," Irwin, Homewood IL, 1993.
[4]
A. Benveniste and G. Berry, "The Synchronous Approach to Reactive and Real-Time Systems," Proceedings of the IEEE, Vol. 79, No. 9, 1991, pp. 1270-1282.