PUBLICATIONS of the DSP DESIGN GROUP and the PTOLEMY PROJECT
Comparing Models of Computation
by Edward A. Lee and Alberto Sangiovanni-Vincentelli
to appear: Proc. of ICCAD, San Jose, CA, Nov. 10-14, 1996.
We give a denotational framework (a "meta model")
within which certain properties of models of computation
can be understood and compared. It describes concurrent
processes as sets of possible behaviors. Compositions of
processes are given as intersections of their behaviors.
The interaction between processes is through signals,
which are collections of events. Each event is a value-tag
pair, where the tags can come from a partially ordered or
totally ordered set. Timed models are where the set of tags
is totally ordered. Synchronous events share the same tag,
and synchronous signals contain events with the same set
of tags. Synchronous systems contain synchronous signals.
Strict causality (in timed systems) and continuity (in
untimed systems) ensure determinacy under certain technical
conditions. The framework is used to compare certain
essential features of various models of computation,
including Kahn process networks, dataflow, sequential
processes, concurrent sequential processes with rendezvous,
Petri nets, and discrete-event systems.
Send comments to Edward A. Lee at firstname.lastname@example.org.