Specification of Control Flow in Ptolemy

Researchers: Bilung Lee
Wan-Teh Chang
Advisor:Edward A. Lee

Real-time signal processing systems typically consist of control and signal processing subsystems. The control subsystems are responsible for the proper sequencing of signal processing operations and switching among multiple operating modes in response to user commands or events. The signal processing subsystems perform the numerical operations. Their algorithms can be specified compactly with dataflow graphs using Ptolemy's dataflow domains. We will extend the Ptolemy environment to enable the specification of control subsystems.

The finite-state machine (FSM) is an intuitive computational model for specifying control flow. In large systems, however, the control functionality can become so complex that the flat, sequential FSM model becomes impractical. Hierarchical state machine models such as Statecharts [1] and specialized synchronous programming languages such as Esterel [2] extend the basic FSM model with hierarchy and concurrency in order to handle the complexity of large controllers.

The goal of this project is to introduce control flow capabilities based on hierarchical state machines into Ptolemy, and to understand formally the interaction semantics between the hierarchical state machines and Ptolemy's dataflow domains. We have created a preliminary implementation of this mixed model in Ptolemy. Systems can be built by hierarchically nesting FSMs and concurrency models. The synchronous dataflow model is particularly attractive because when it is combined hiearchically with FSMs, the combination is far more expressive than either SDF or FSMs alone, yet the resulting system remains finite state, so verification, synthesis, and optimization problems all remain decidable. The next step is to add the capability to generate code from such systems.

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

D. Harel, "Statecharts: A Visual Formalism for Complex Systems," Science of Computer Programming, vol. 8, pp. 231-274, 1987.
G. Berry and G. Gonthier, "The Esterel Synchronous Programming Language: Design, Semantics, Implementation," Science of Computer Programming, vol. 19, no. 2, pp. 87-152, 1992.