A denotational framework for comparing models of computationAbstractMain characteristicsSIGNALS 1SIGNALS 2: Characteristics & notationsPROCESSESComposing processes 1Composing processes 2: projectionsInputs and outputsDeterminacyTags systemsTimed models of computationFlavors of timed modelsMetric timeContinuous timeDiscrete eventDiscrete events simulatorsSynchronous and discrete-time systemsSequential systemsUntimed models of computationRendezvous of sequential processesKahn process networksDataflowPetri NetsHeterogeneous systemsThe Role of Tags in composition of processesDiscrete event systemsMonotonicity and continuity in Kahn process networksA denotational framework for comparing models of computationDaniele GasperiniAbstractAim: compare different model of computation and their certain essential featuresHow: use a denotational frameworkMain characteristicsDenotational rather than operationalMathematical approachMain actors:–Processes–Signals–EventsTagged signal modelSIGNALS 1Event e = tag : value–Set of values V–Set of tags TTags: model time, precedence relationships, synchronization pointsValues: represent operands and result of computationSignal s = set of events = subset of T x Ve є T x VSIGNALS 2: Characteristics & notationsFunctional signals–e1= (t, v1) є s and e2= (t, v2) є s then v1 = v2S = the set of all signalsSN = collection/tuple of N signalsλ = empty signal (no events)Λ = collection/tuple of N empty signals–λ є S and Λ є SN = bottom : absence of valuePROCESSESP = process : subset of SN for some Ns = behavior of a process–s є SN and s є P→ P = set of behaviors• Composing processes• Inputs and outputs• DeterminacyGiven M processes in SN a process Q composed of these processesis given by:Where P is the collection of processesComposing processes 1P = set of behaviors sComposing = P1 x P2 x … PnPPiiPQMiSPNi 1,Composing processes 2: projections)s,,(s )(by S ontoS )s,,(s s of )( projection thedefine andNi1 range in the indices ofset orderedanbe)i,,(iILetm1iiImNN1Im1ssProcess P = set of behaviors s s' (s) π whereP s exists theresuch that s'set (P)πIIInputs and outputs)(S B is inputs possible all ofSet behaviors acceptable ofset total theis P A such that S A constraint imposed externallyan is S process a Input toNNN).'()( that followsit )'()( whereP s' and P severy for ifO) (I, respect to with functional is P processA ssssOOIIPI (size m) O (size n)))(()( P,s allfor such that SS :F mapping valuedsingle a is ThereonmsFsIDeterminacyA process is determinate if for any input A є B it has exactly one behavioror exactly no behaviors. Otherwise is nondeterminate.functional + functional = functional → preserveFunctional + source processes with exacly one behavior = functional → preserveDepends on the tag system and the processTags systemsThe central role of a tag system is to establish ordering among events.specificationimplementations1 s2 s3 …s1 s2 s3 …i.e. timeOrdering relation among events properties:reflective transitive antisymmetricOrdering of tagsOrdering of eventsTimed models of computationThe set of tags T is a totally ordered setTag = timestampFlavors of timed modelsMetric timeContinuous timeDiscrete eventDiscrete event simulatorsSynchronous and discrete-time systemsSequential systemsMetric timeT totally orderedT Abelian group–closed to addition–zero–for every t є T there is another element -t є T such that t + (-t) = 0–T has a metricDirectly modeling physical systemsContinuous timeT totally orderedT is a continuumT(s) = T for each signal s in any tuple s that satisfies the systemDiscrete eventT totally orderedThe set of tags must be a discrete subset of TThe set of tags must be order isomorphicThe timestamps that appear in any behavior can be enumerated inchronological order.Many simulators (most digital circuit simulators)Discrete events simulatorsSame characteristics of discrete eventEvents explicitly include timestampThe simulator operates by keeping a list of events sorted by timestampDelta time (affects semantic and ensure strict causality)Synchronous and discrete-time systemsTwo events are synchronous if they have the same tagTwo signals are synchronous if all events in one signal are synchronous with an event in the other signal and vice versaA process is synchronous if every signal in any behavior of the process is synchronous with every other signal in the behaviorSequential systemsSingle signal sThe set of tags in the signal are totally orderedUntimed models of computationTags are partially orderedPartial order is present in many models of computations because denotes–Causality–SynchronizationRendezvous of sequential processesSequential processes reach a particular point at which they must verify that another process has reached a corresponding point before proceedingCommunicating sequential processes andthe calculus of communicating systemsT(e1) = T(e2) = T(e3)s1s3s2Kahn process networksProcesses communicate via channels, which are one-way unbounded FIFO queues with a single reader and a single writer.FIFO T(s) is totally ordered for each signal sImposes an ordering on the eventsBe Σ(s) denote the sequence of values in sTwo signals s and s’ sequence equivalent Σ(s) = Σ(s’) A process is sequence functional if given a set of equivalent tuples of inputsignals all possible outputs are sequence equivalentSequence determinacyDataflowSpecial case of Kahn process networksA dataflow process is a Kahn process that is also sequentialSelf loop signal is called firing signals’s’’sPe’consumed by ei + 1ei ≤ e’ ≤ ei + 1e’’produced by eiei ≤ e’’ ≤ ei + 1Petri NetsSimilar to dataflowEvents within signals need not be ordereds2s1f: s2 → s1 such that f(e) < e for all e є s2A firing (an event in s2) has a corresponding token(an event in s1) with a smaller tagHeterogeneous systemsV divided into subsets → carry the notion of data typesT divided → separately model parts of heterogeneous system (continuous time, discrete event and dataflow subsystems)The Role of Tags in composition of processesAim: connect tagged signal model to well-known results in semanticsTwo cases:–Discrete
View Full Document
Unlocking...