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 |
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.