IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 12, DECEMBER 1998 1217A Framework for Comparing Models of ComputationEdward A. Lee, Fellow, IEEE, and Alberto Sangiovanni-Vincentelli, Fellow, IEEEAbstract—We give a denotational framework (a “meta model”)within which certain properties of models of computation can becompared. It describes concurrent processes in general terms assets of possible behaviors. A process is determinate if, given theconstraints imposed by the inputs, there are exactly one or exactlyzero behaviors. Compositions of processes are processes withbehaviors in the intersection of the behaviors of the componentprocesses. 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 totallyordered set. Timed models are where the set of tags is totallyordered. Synchronous events share the same tag, and synchronoussignals contain events with the same set of tags. Synchronousprocesses have only synchronous signals as behaviors. Strictcausality (in timed tag systems) and continuity (in untimed tagsystems) ensure determinacy under certain technical conditions.The framework is used to compare certain essential features ofvarious models of computation, including Kahn process networks,dataflow, sequential processes, concurrent sequential processeswith rendezvous, Petri nets, and discrete-event systems.I. INTRODUCTIONAMAJOR impediment to further progress in modelingand specification of concurrent systems is the confusionthat arises from different usage of common terms. Termslike “synchronous,” “discrete event,” “dataflow,” “signal,”and “process” are used in different communities to meansignificantly different things. To address this problem, wegive a formalism that will enable description, abstraction, anddifferentiation of models of computation. It is not intendedas a “grand unifying model of computation” but rather as a“meta model” within which certain properties of the modelsof computation can be studied. To be sufficiently precise, thislanguage is a mathematical one. It is denotational, in thesense of Scott and Strachey [38], rather than operational, toavoid associating the semantics of a model of computationwith an execution policy. In many denotational semantics,the denotation of a program fragment is a partial functionor a relation on the state. This approach does not modelconcurrency well [40], where the notion of a single globalstate may not be well defined. In our approach, the denotationof a process is a partial function or a relation on signals, andhence we can model concurrency well.Manuscript received February 20, 1997; revised March 12, 1998. Thiswork was supported in part by the Defense Advanced Research ProjectsAgency under the Ptolemy project, in part by the State of California underthe MICRO program, and in part by the following: Cadence Design Systems,Hewlett Packard, Hitachi, Hughes Space and Communications, NEC, Philips,the Italian National Research Council, Magneti-Marelli, Rockwell, Daimler-Benz, and SGS-Thomson. This paper was recommended by Associate EditorD. Dill.The authors are with the Department of Electrical Engineering and Com-puter Science, University of California, Berkeley, CA 94720 USA.Publisher Item Identifier S 0278-0070(98)09367-1.We define precisely a process, signal, and event, and give aframework for identifying the essential properties of discrete-event systems, dataflow, rendezvous-based systems, Petri nets,and process networks. Our definitions of these terms some-times conflict with common usage in some communities, andeven with our own prior usage in certain cases. We have madeevery attempt to maintain the spirit of that usage with whichwe are familiar, but have discovered that terms are used incontradictory ways (sometimes even within a community).Maintaining consistency with all prior usage is impossiblewithout going to the unacceptable extreme of abandoning theuse of these terms altogether.Our objectives overlap somewhat with prior efforts toprovide mathematical models for concurrent systems, suchas communicating sequential processes (CSP) [19], calculusof communicating systems (CCS) [29], event structures [41],action structures [30], and interaction categories [1], and pre-vious efforts to formally compare models of computation [37],[42]. We do not have a good answer for the question “do wereally need yet another meta model for concurrent systems?”except perhaps that our objectives are somewhat different andresult in a model that has some elements in common withother models, but overall appears to be somewhat simpler.It is more descriptive of concurrency models (more “meta”)than some process calculi, which might for example assume asingle interaction mechanism, such as rendezvous, and showhow other interaction mechanisms can be described in terms ofit. We assume no particular interaction mechanism, and showhow to use the framework to describe and compare a numberof interaction mechanisms (including rendezvous). We devotemost of our attention, however, to interaction mechanisms inpractical use for designing electronic systems, such as discrete-event, rendezvous, and dataflow. The latter two are alignedwith the “atomicity” and “precedence constraints” interactionpatterns of Agha’s actors model [2], but we add the discrete-event model because of our interest in physical modeling ofdigital electronic systems.The prior frameworks closest to ours, Abramsky’s interac-tion categories [1] and Winskell’s event structures [41], havebeen presented as categorical concepts. We avoid categorytheory here because it does not appear to be necessary forour more limited objectives, and because we wish to make theconcepts more accessible to a wider audience. But it wouldbe wrong to not acknowledge the influence. We limit themathematics to sets, posets, relations, and functions.Section II generically develops the notion of tagged sig-nals, systems, and composition of systems. Section III illus-trates some tag systems for various models of computation.Section IV shows how tag systems can model time and causal-ity, an essential property of concurrent models of computation.0278–0070/98$10.00 1998 IEEE1218 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 12, DECEMBER 1998II. THE TAGGED SIGNAL
View Full Document
Unlocking...