IEEE TRANSACTIONS ON COMPUTER AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS VOL 17 NO 12 DECEMBER 1998 1217 A Framework for Comparing Models of Computation Edward A Lee Fellow IEEE and Alberto Sangiovanni Vincentelli Fellow IEEE Abstract We give a denotational framework a meta model within which certain properties of models of computation can be compared It describes concurrent processes in general terms as sets of possible behaviors A process is determinate if given the constraints imposed by the inputs there are exactly one or exactly zero behaviors Compositions of processes are processes with behaviors in the intersection of the behaviors of the component processes 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 processes have only synchronous signals as behaviors Strict causality in timed tag systems and continuity in untimed tag 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 I INTRODUCTION A MAJOR impediment to further progress in modeling and specification of concurrent systems is the confusion that arises from different usage of common terms Terms like synchronous discrete event dataflow signal and process are used in different communities to mean significantly different things To address this problem we give a formalism that will enable description abstraction and differentiation of models of computation It is not intended as a grand unifying model of computation but rather as a meta model within which certain properties of the models of computation can be studied To be sufficiently precise this language is a mathematical one It is denotational in the sense of Scott and Strachey 38 rather than operational to avoid associating the semantics of a model of computation with an execution policy In many denotational semantics the denotation of a program fragment is a partial function or a relation on the state This approach does not model concurrency well 40 where the notion of a single global state may not be well defined In our approach the denotation of a process is a partial function or a relation on signals and hence we can model concurrency well Manuscript received February 20 1997 revised March 12 1998 This work was supported in part by the Defense Advanced Research Projects Agency under the Ptolemy project in part by the State of California under the 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 DaimlerBenz and SGS Thomson This paper was recommended by Associate Editor D Dill The authors are with the Department of Electrical Engineering and Computer 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 a framework for identifying the essential properties of discreteevent systems dataflow rendezvous based systems Petri nets and process networks Our definitions of these terms sometimes conflict with common usage in some communities and even with our own prior usage in certain cases We have made every attempt to maintain the spirit of that usage with which we are familiar but have discovered that terms are used in contradictory ways sometimes even within a community Maintaining consistency with all prior usage is impossible without going to the unacceptable extreme of abandoning the use of these terms altogether Our objectives overlap somewhat with prior efforts to provide mathematical models for concurrent systems such as communicating sequential processes CSP 19 calculus of communicating systems CCS 29 event structures 41 action structures 30 and interaction categories 1 and previous efforts to formally compare models of computation 37 42 We do not have a good answer for the question do we really need yet another meta model for concurrent systems except perhaps that our objectives are somewhat different and result in a model that has some elements in common with other 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 a single interaction mechanism such as rendezvous and show how other interaction mechanisms can be described in terms of it We assume no particular interaction mechanism and show how to use the framework to describe and compare a number of interaction mechanisms including rendezvous We devote most of our attention however to interaction mechanisms in practical use for designing electronic systems such as discreteevent rendezvous and dataflow The latter two are aligned with the atomicity and precedence constraints interaction patterns of Agha s actors model 2 but we add the discreteevent model because of our interest in physical modeling of digital electronic systems The prior frameworks closest to ours Abramsky s interaction categories 1 and Winskell s event structures 41 have been presented as categorical concepts We avoid category theory here because it does not appear to be necessary for our more limited objectives and because we wish to make the concepts more accessible to a wider audience But it would be wrong to not acknowledge the influence We limit the mathematics to sets posets relations and functions Section II generically develops the notion of tagged signals systems and composition of systems Section III illustrates some tag systems for various models of computation Section IV shows how tag systems can model time and causality an essential property of concurrent models of computation 0278 0070 98 10 00 1998 IEEE 1218 IEEE TRANSACTIONS ON COMPUTER AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS VOL 17 NO 12 DECEMBER 1998 II THE TAGGED SIGNAL MODEL A Signals and a set of tags we define Given a set of values i e an event has a an event to be a member of tag and a value We will use tags to model time precedence relationships
View Full Document
Unlocking...