Comparing Models of Computation

Professor Edward A. Lee
Dept. of Electrical Engineering and Computer Science
UC Berkeley

September 5, 1996
Hogan Room, 531 Cory Hall
4:00-5:00 p.m.

Abstract:

Design automation depends on the high-level modeling and specification of systems. Such modeling and specification often uses innovative and sometimes domain-specific languages. A rich and interesting variety of languages with different semantic properties have been developed. These languages are often more abstract than the established conventional languages into which they are frequently compiled.

A major impediment to further progress in such abstract modeling and specification of systems is the confusion that arises from different usage of common terms. Terms like "synchronous", "discrete event", "dataflow", and "process" are used in different communities to mean significantly different things. These terms attempt to describe the model of computation underlying a language, but by being imprecise and overused, they often do more to cause confusion than to illuminate. This talk addresses one approach to this problem, giving a formalism that will enable description and differentiation of models of computation. To be sufficiently precise, this language is a mathematical one, although the mathematics is not much more sophisticated than basic set theory. It is denotational rather than operational, meaning that it declares relationships rather than describing procedures. It is also incomplete, in that it focuses on certain properties of models of computation, namely their concurrency and communication, and ignores other aspects.

We define precisely "process", "signal", and "event", and give a framework for identifying the essential properties of discrete-event systems, dataflow, rendezvous-based systems, and process networks. This is based on unambiguous definitions of timed systems and synchrony. In brief, concurrent processes are described in very general terms 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. A system is "determinate" if given the constraints imposed by the inputs there is exactly one or exactly zero behaviors. 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 work presented is a collaboration between Alberto Sangiovanni-Vincentelli and Edward A. Lee, both of U.C. Berkeley. The talk will be given by Edward A. Lee.