1996 Research Summaries for the Ptolemy Project

Specification of Control Flow in Ptolemy


Researchers:Wan-Teh Chang and Bilung Lee
Advisors:Edward A. Lee and David G. Messerschmitt
Sponsors:(SRC) 95-DC-324-016 and the Ptolemy project

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 implemented a preliminary graphical entry tool for state transition diagrams using Tcl/Tk. One major objective over the next year is to achieve a better understanding of the role of concurrency and communication in hierarchical finite-state-machine models like those used in Statecharts and at least 22 variants [3]. This understanding will be used to develop a methodology for hierarchically mixing FSM models with dataflow and discrete-event models. A second objective will be to develop formal methods capable of mixing control-oriented FSMs with numeric-oriented dataflow graphs. If we restrict ourselves to the synchronous dataflow subset of dataflow, then the combined model will not be Turing complete, and therefore many questions involved in synthesis and verification remain decidable. Unlike many non-Turing-complete models of computation, however, this combined model will be quite rich, capable of fully describing many complete embedded 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.

  1. D. Harel, "Statecharts: A Visual Formalism for Complex Systems," Science of Computer Programming, vol. 8, pp. 231-274, 1987.
  2. 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.
  3. M. von der Beeck, "A Comparison of Statecharts Variants," Proc. of Formal Techniques in Real-Time and Fault-Tolerant Systems (FTRTFT '94), Lecture Notes in Computer Science, vol. 863, Springer-Verlag, pp. 128-148, 1994.

Send comments to Wan-teh Chang at wtc@eecs.berkeley.edu.