Specification of Control Flow in Ptolemy

Researchers: Xiaojun Liu
Advisor:Edward A. Lee
Most modern systems include control logic for the proper sequencing of computational tasks, and for switching and coordinating between different operating modes. 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.

Hierarchical concurrent FSMs (HCFSMs) increase the usefulness of FSMs by extending them with structuring and communication mechanisms. However, most formalisms that support HCFSMs, such as Statecharts and its variants, tightly integrate the concurrency semantics with the FSM semantics. Based on the Ptolemy philosophy of hierarchical composition of heterogeneous models of computation, the *charts formalism [1] allows embedding hierarchical FSMs within various concurrency models, in particular continuous time, dataflow, discrete event and synchronous/reactive models. In this heterogeneous model, the semantics of FSM, concurrency and hierarchy are naturally supported. Our scheme decouples the FSM from the concurrency models, enabling selection of the most appropriate concurrency model for the problem at hand.

An FSM domain has been developed in Ptolemy II and is integrated with the CT, DE, SDF, and Giotto domains. We are currently working on integrating the FSM domain with process-based domains such as CSP and PN. We will also investigate what formal verification methods can be applied to the *charts formalism.

[1]
A. Girault, B. Lee, and E. A. Lee, "Hierarchical Finite State Machines with Multiple Concurrency Models," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 6, pp.742-760, 1999.
[2]
John Davis II, et al., "Ptolemy II - Heterogeneous Concurrent Modeling and Design in Java," Memorandum UCB/ERL M99/40, Electronics Research Laboratory, University of California, Berkeley, CA 94720, July 1999.

Last updated 11/18/02