The Semantics of Discrete Event Systems

Researchers: John S. Davis II
Advisor:Edward A. Lee
Sponsor:
Discrete event (DE) systems play a critical role in the modeling of communication networks, embedded processors and manufacturing systems. A key feature of the DE model of computation is the incorporation of a complex network of interacting modules that communicate via tokens of time-stamped data. Sequences of tokens passed between DE modules form signals. With the use of the Cantor distance, this space of signals can be interpreted as a metric space. A practical application of the metric space interpretation is that constraints on the kind of causality that the DE modules observe impacts how the corresponding DE simulation progresses. As an example, VHDL or Verilog simulators (which are closely related to the DE system of modeling) have well-defined semantics depending on the causality constraints. Unfortunately, the causality constraints are unnecessarily stringent and lead to difficulties for the programmer of a simulation.

The standard denotational semantic approach as developed by Scott and Strachey focuses not on a metric space of signals but a complete partial order (CPO) of signals. Accordingly, the notion of monotonicity and continuity are used to guarantee well-definedness. This denotational approach has been applied to the Kahn dataflow model of computation in particular. Dataflow is a popular modeling paradigm for signal processors and other systems that are amenable to a functional style. A disadvantage of dataflow modeling is that there is no explicit notion of time, a characteristic that is critical for certain applications.

I am considering a hybrid model of computation that blends dataflow with discrete event modeling. I am studying this both within a theoretical framework and as a software implementation. Theoretically I am working towards the relaxation of some of the DE causality constraints given that the modules are monotonic/continuous. The key mathematical tool I am using towards this goal is Matthews' notion of a partial metric space. From an implementation standpoint, I am implementing an "ordered dataflow" domain within the Ptolemy II software environment. Ptolemy II, the Java-based reincarnation of C++ Ptolemy, is a system level modeling tool. A key advantage of an ordered dataflow system as compared to standard discrete event systems is the possibility for concurrent, multi-threaded processing (in the sense of Misra).

Last updated 03/22/99