Ptolemy II Domains

The Algebraic model of computation includes a director that solves algebraic loops.

As of August, 2014, this model of computation is under active development and should be seen as a work in progress.

The Cellular Automata (CA) model of computation uses the number of neighbors of a cell to determine if the cell lives or dies at the next iteration.

The CA domain was created by Zach Ezzell.

Resources

The component interaction (CI) domain models systems that blend data-driven and demand-driven styles of computation. As an example, the interaction between a web server and a browser is mostly demand-driven. When the user clicks on a link in the browser, it pulls the corresponding page from the web server. A stock-quote service can use a data-driven style of computation. The server generates events when stock prices change. The data drive the clients to update their displayed information. Such push/pull interaction between a data producer and consumer is common in distributed systems, and has been included in middleware services, most notably in the CORBA event service. These services motivated the design of this domain to study the interaction models in distributed systems, such as stock-quote services, traffic or weather information systems. Other applications include database systems, file systems, and the Click modular router.

An actor in a CI model can be active, which means it possesses its own thread of execution. For example, an interrupt source of an embedded system can be modeled as an active source actor. Such a source generates events asynchronously with respect to the software execution on the embedded processor. CI models can be used to simulate and study how the embedded software handles the asynchronous events, such as external interrupts and asynchronous I/O.

References

The Continuous Time Model of Computation defines a semantics used for continuous-time simulations. Continuous Time models consist of Actors that have continuous time signals as their inputs and outputs, and may have a state that changes over time advancement. These actors are connected by relations denoting particular signals. At a sequence of time increments, the values of all signals are determined using a continuous time solving algorithm. If a given precision cannot be accomplished, finer time increments are used adaptively.

The domain models systems with continuous dynamics, including for example analog circuits and mechanical systems, but also cleanly supports discrete events, modal behaviors, and signals that mix continuous-time behaviors with discrete events. Models for continuous dynamics are equivalent to linear or nonlinear integral equations. A sophisticated numerical solver for these equations is integrated with the director. The clean semantics of the Continuous domain enables its integration in hierarchical heterogeneous models that use the Synchronous/Reactive (SR) and Discrete Event (DE) domains. Arbitrary hierarchical mixtures of these domains are supported, although if SR is at the top level, then the period parameter of the director must be used so that time advances. Domain interactions are documented in Lee and Zheng, 2007.

The clean semantics of the Continuous domain enables its integration in hierarchical heterogeneous models that use the Synchronous/Reactive (SR) and Discrete Event (DE) domains. Arbitrary hierarchical mixtures of these domains are supported, although if SR is at the top level, then the period parameter of the director must be used so that time advances. Domain interactions are documented in Goderis et al.

References

The Communicating Sequential Processes (CSP) domain in Ptolemy II models a system as a network of processes communicating with messages through unidirectional channels. If a process is ready to send a message, it blocks until the receiving process is ready to accept it. Similarly if a process is ready to accept a message, it blocks until the sending process is ready to send it. Thus the communication between processes is rendezvous based as both the reading and writing processes block until the other side is ready to communicate. This model of computation is non-deterministic as a process can be blocked waiting to send or receive on any number of channels. It is also highly concurrent due to the nature of the model.

The model of computation used in the CSP domain is based on the CSP model first proposed by Hoare[2] in 1978. In this model, a system is modeled as a network of processes communicating via messages along unidirectional channels. This is the only way processes can communicate as there is no shared state. The transfer of message between processes is via rendezvous, which means both the sending and receiving of a messages from a channel are blocking: i.e. the sending or receiving process stalls until the message is transferred. Some of the notation used here is borrowed from Andrews' book on concurrent programming [1], which refers to rendezvous-based message passing as synchronous message passing.

Applications for the CSP domain include resource management and high level system modeling early in the design cycle. Resource management is often required when modeling embedded systems, and to further support this, a notion of time has been added to the model of computation used in the domain. This differentiates our CSP model from those more commonly encountered, which do not typically have any notion of time, although several versions of timed CSP have been proposed[3]. It might thus be more accurate to refer to the domain using our model of computation as the "Timed CSP" domain, but since the domain can be used with and without time, it is simply referred to as the CSP domain.

References

The DDE domain's use of time serves as the point of divergence in the respective designs of DDE and PN. Time progress is communicated between actors by passing tokens that have time stamps associated with them. In a network of DDE actors each actor has a local notion of time. To facilitate this local notion of time, actors in a DDE model adhere to the following constraints.

• Successive tokens emitted from any actor's output port must have a time stamp that is greater than or equal to that of previous tokens.
• An actor can consume a token on an input port (P1) only if the other input ports of that actor have pending tokens with time stamps greater than or equal to that of P1.
• If an actor has two or more input ports with pending time stamps that are identical, then a local input port prioritization rule must be invoked to determine the ordering of these simultaneous tokens.

We are approaching the DDE model of computation as the intersection between dataflow and discrete event semantics. This allows us to study DDE semantics from two different perspectives. In particular, we can benefit from denotational semantics that are based on metric spaces (the Banach oriented DE approach) or posets (the Tarskian oriented dataflow approach). Matthews offers a partial metric topology which incorporates both of these mathematical tools.

The DDE domain is an experimental domain, the code has not been reviewed, and the interfaces are likely to change.

1. Misra, Jayadev, "Distributed Discrete Event Simulation," ACM Computing Surveys, vol. 18, no. 1, March 1986, pp 39-65.
2. Fujimoto, Richard M., "Parallel Discrete Event Simulation," Communications of the ACM, vol. 33, no. 10, October 1990, pp 30-53.
3. Matthews, S. G., "Partial Metric Topology," General Topology and Applications, Proceedings of the 8th Summer Conference, Queen's College (1992), Annals of the New York Academy of Science, vol. 728, pp 183-197.

The Dynamic Dataflow (DDF) domain is a superset of the Synchronous Dataflow (SDF) and Boolean dataflow (BDF) domains. In the SDF domain, an actor consumes and produces a fixed number of tokens per firing. This static information makes possible compile-time scheduling. In the DDF domain, an actor could change the production and consumption rates after each firing. The scheduler makes no attempt to construct a compile-time schedule, neither does it attempt to statically answer questions about deadlock and boundedness, which are fundamentally undecidable. Instead, each actor has a set of sequential firing rules (patterns) and can be fired if one of them is satisfied, i.e., one particular firing pattern forms a prefix of sequences of unconsumed tokens at input ports. The scheduler dynamically schedules the firing of actors according to some criteria. The canonical actors in the DDF domain include Select and Switch, which consume or produce tokens on different channels based on the token received from the control port.

References

The Discrete Event (DE) Model of Computation defines a semantics for a network of Actors that produce discrete events, and whose executions are triggered by discrete events. A discrete event is a value with a time associated with it that is global on the level of the model. Each event also has, as a destination, an associated input port on an Actor. This destination is determined by a relation connecting to this input port the output port, or model input, from which the event is produced, or enters the model, respectively.

When an event exist in the model, at a particular time, with an input port on an Actor as its destination, this Actor must respond to the event at the associated time. This response may be to produce no output. However, if output events are produced, the time associated with these events must be equal to or later than that of its inputs. This constraint ensures weak causality.

Furthermore, for the currently implemented form of the Discrete Event MoC in Ptolemy II, in a model every dependency cycle along the reaction to and production of events must have at least one Actor that produces events strictly later in associated time than those of its inputs. In more recent conceptions of these semantics this restriction is lifted to a strictly broader monotonicity condition.

This MoC is a Synchronous one, since at the time associated with every event in the model, associated with the relation connected to its destination, each relation can be determined uniquely to either have a single event associated with that same time, or have no event at that time, in which case the output of the Actor or model input connected to such a relation is said to produce absent. In other words, like the Synchronous Reactive model, at each Reaction event a unique value, including absent, can be determined at each relation.

DE models are extensively used in simulation of networks, queueing systems, and digital circuits.

References

Semantics and Theory

The Discrete Time (DT) domain is a timed extension of the Synchronous Dataflow (SDF) domain. Like SDF, it has static scheduling of the dataflow graph model. Likewise, DT requires that the rates on the ports of all actors be known beforehand and fixed. DT handles feedback systems in the same way that SDF does, but with additional constraints on initial tokens.

Because of the inherent concurrency occurring within SDF dataflow graph models, there are two notions of time in DT -- global time and local time. Global time increases steadily as execution progresses. Moreover, global time increments by fixed discrete chunks of time based on the value of the period parameter. On the other hand, local time applies to each of the actors in the model. All the actors have distinct local times as an iteration proceeds. The local time of an actor during an iteration depends on the global time, period, firing count, port rates, and the schedule. These local times obey the following constraint:

The exact way that local time increments during an iteration is described in detail in the DTReceiver documentation.

The DT domain is an experimental domain, the code has not been reviewed, and the interfaces are likely to change.

References

Giotto is a domain designed by Christoph Meyer Kirsch to realize the semantics of the Giotto language, designed by Tom Henzinger, Ben Horowitz, and Christoph Meyer Kirsch. The semantics is a particular flavor of a synchronous model. Each component executes a specified number of times per iteration. The number of times it executes is called its frequency, and it defaults to one. The frequency can be specified to be something other than one by simply adding a parameter to the component named frequency, and then giving it a value different from one.

A particular feature of Giotto semantics is that the arcs connecting components are updated with a new value at well-defined points in the execution, irrespective of their execution time. If the frequency of the actor producing the data for the arc is one, then the value is updated only between iterations. Thus, each arc begins empty (having no value present), and acquires a value at the end of the first iteration.

If a component has frequency greater than one, then its output arcs are updated more than once per iteration. Suppose the frequency is two. Then its output arcs will be updated twice per iteration, but only the final update will be visible to components with frequency one (and only on the next iteration). If a component with frequency two is a destination of one of its outputs, then that component will see each update, but only in its next invocation. Thus, the second invocation of the destination in the iteration will see the value produced by the first invocation of the source in the iteration.

Giotto imposes the additional constraint that the frequencies of all components in a model bear harmonic relationships with one another. This means, for example, that frequencies of 2 and 3 cannot coexist in the same model. Frequencies 2 and 4 or 3 and 6 can, however, coexist.

The Giotto domain is highly preliminary, and the example models are not particularly interesting. Watch this space for more interesting examples.

References

Java3D

The Heterochronous Dataflow (HDF) domain, created by Ye Zhou, is an extension of the Synchronous Dataflow (SDF) domain. In SDF, the set of port rates (called rate signatures) of an actor are constant. In HDF, however, rate signatures are allowed to change between iterations of the HDF schedule. The change of rate signatures can be modeled by state transitions of a modal model, in which each state refinement infers a set of rate signatures. Within each state, the HDF model behaves like an SDF model.

References

A Modal Model is a finite set of Actors (other models), all having the same set of inputs and outputs, associated each with states in a finite state machine. For any given state, the associated Actor is known as a Refinement of this state. During each firing of this Modal Model the refinements associated with the current state in the state machine fires. Subsequently, the evaluation of guards in the state machine determines which state, if any, to transition to, thereby determining the next refinement to fire.

The modal domain replaces the fsm domain.

References

This domain implements the basic Petri Net model where Places and Transitions form a bipartite graph and enabled Transitions can fire randomly. It also allows Transitions to be replaced by any other Actors in Ptolemy. It implements two forms of Hierarchical and compositional Petri nets. The first form of hierarchical and compositional Petri net semantics comes from the fact that a Transition can contain a sub-Petri-net which is invisible to the director of the container of the Transition. The second form of hierarchical and compositional Petri net semantics comes from a new Actor called PetriNetActor which is a collection of Places and Transitions, and those Places and Transitions are visible to the director of the container of the PetriNetActor. The users can choose which form of models to use, and/or mix them together.

The basic Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called Places and Transitions, where arcs are either from a Place to a Transition or from a Transition to a Place. In graphical representation, Places are drawn as circles, Transitions as bars or boxes. Arcs are labeled with their weights (positive integers). Labels of unity weight are usually omitted. Multiple arcs can exist between a Place and a Transition. A marking assigns to each Place p an nonnegative integer k, we say that p is marked with k tokens. at the next iteration.

References

To model hardware and embedded applications, a highly concurrent model of computation is required. The PN domain in Ptolemy II presents a mechanism to model concurrency using the Kahn process networks model of computation [1]. The process networks model of computation has a dataflow flavor to it. This makes it well suited to modeling embedded dataflow applications and hardware architectures.

In Ptolemy II, an implementation of the Kahn-MacQueen [2] semantics is provided. This is the bounded memory execution as proposed by T. Parks [3].

The following are the most important features of the operational semantics of PN as proposed by Kahn and MacQueen:

• This is a network of sequential processes.
• The processes do not share memory. Instead they communicate with each other only through unidirectional FIFO channels.
• Communication between processes is asynchronous.
• Processes block on a read from a FIFO channel if the channel is empty but can write to a channel whenever they want to.

The above features make the execution of the network deterministic. The implementation in Ptolemy II is based on Java threads and synchronizing monitors.

In addition to the above features, the PN domain has been extended to support a notion of global time. Time advances for a PN process either when the process is blocked on a read from some channel or when is explicitly waiting for time to advance. This is based primarily on Pamela [4].

PN has been further extended to support dynamic changes to a graph. In case of timed-PN these changes are completely deterministic, while in case of untimed-PN, the changes could be non-deterministic and can depend on the schedule of the underlying java threads.

References

The Ptera (Ptolemy Event Relation Actor) domain is a discrete-event model of computation. A model in Ptera is represented with a graph of nodes and edges, where nodes represent events and directed edges between events represent scheduling relation. One or more events can be selected as initial events, which are scheduled at model time 0.0. When an event is fired, it possibly performs certain actions, and if there are outgoing edges from that event, the events at the end points of those edges are scheduled after non-negative delays. One or more events can also be selected as final events. The firing of final events causes the event queue to be emptied after their actions are performed, and therefore no more events can be processed.

The Ptera domain supports a different kind of modal models called PteraModalModels, compared to modal models using FSMs (Finite State Machines) as the control. A PteraModalModel uses Ptera at the top level, and each event is refined into a sub-model. The refinements can use Ptera and any other Ptolemy models of computation.

A Ptera model is timed. Although it should work in many domains, the DE (Discrete-Event) domain or Ptera domain itself are recommended. When embedded in those domains, the scheduling of the Ptera model is delegated to the container by calling the fireAt() function of its director.

There are many useful additional features for Ptera, such as canceling edges and parameters. A canceling edge, denoted by a dotted line, cancels a previously scheduled event instead of scheduling a new one. If the pointed to event has multiple instances in the event queue, then the first instance is cancelled. Events may also have parameters, and the actual values for those parameters are specified by the expressions on the edges that schedule them. Those expressions are evaluated at run-time. The events may refer to the values of those parameters in their actions by parameter names.

References

Pthales is a multidimensional dataflow model of computation implemented in the heterogeneous modeling environment Ptolemy II. Pthales is based on Array-OL.

References

In the Rendezvous domain in Ptolemy II, each actor executes in its own thread of control, and communication between actors is by rendezvous. If an actor is ready to send a message, it blocks until the receiving actor is ready to receive it. Similarly if an actor is ready to receive a message, it blocks until the sending actor is ready to send it.

This domain supports both conditional and multi-way rendezvous. In conditional rendezvous, an actor is willing to rendezvous with any one of several other actors. In multiway rendezvous, an actor requires rendezvous with multiple other actors at the same time. When using conditional rendezvous, the choice of which rendezvous occurs is nondeterministic, in general.

The model of computation is based on the CSP model first proposed by Hoare[1] in 1978. Rendezvous-based communication is also known as synchronous message passing, but we avoid this term to avoid confusion with the SR (synchronous/reactive) domain.

References

The Software Cost Reduction (SCR) model of computation is a implementation of SCR. SCR "was created to help developers build specifications with greater assurance that the requirements will be complete, and the resulting software error-free."

The Ptolemy II SCR model of computation is an incomplete prototype.

References

Synchronous dataflow (SDF) is a special case of dataflow where the flow of control is sufficiently regular to be completely predictable at compile time. An SDF model is an interconnection of actors whose firings are enabled by fixed, pre-specified numbers of tokens on each of their inputs. Moreover, when an actor fires, it produces a fixed, pre-specified number of tokens on each of its outputs. The fact that these numbers are fixed makes it possible for a scheduler to determine the firing sequence at the time the model is initialized. Thus, SDF models are quite efficient, in that there is no multithreading needed, and run-time overhead consists only of a very simple dispatcher that implements the pre-computed schedule.

References

In the synchronous/reactive (SR) model of computation , the arcs represent data values that are aligned with global clock ticks. Thus, they are discrete signals, but unlike discrete time, a signal need not have a value at every clock tick. The entities represent relations between input and output values at each tick, and are usually partial functions with certain technical restrictions to ensure determinacy. Examples of languages that use the SR model of computation include Esterel, Signal, Lustre, and Argos.

SR models are excellent for applications with concurrent and complex control logic. Because of the tight synchronization, safety-critical real-time applications are a good match. However, also because of the tight synchronization, some applications are overspecified in the SR model, limiting the implementation alternatives. Moreover, in most realizations, modularity is compromised by the need to seek a global fixed point at each clock tick.

References

The timed multitasking (TM) domain, created by Jie Liu, offers a model of computation based on priority-driven multitasking, as common in real-time operating systems (RTOSs), but with more deterministic behavior. In TM, actors (conceptually) execute as concurrent threads in reaction to inputs. The domain provides an event dispatcher, which maintains a prioritized event queue. The execution of an actor is triggered by the event dispatcher by invoking first its prefire() method. The actor may begin execution of a concurrent thread at this time. Some time later, the dispatcher will invoke the fire() and postfire() methods of the actor (unless prefire() returns false).

The amount of time that elapses between the invocation of prefire() and fire() depends on the declared executionTime and priority of the actor (or more specifically, of the port of the port receiving the triggering event). The domain assumes there is a single resource, the CPU, shared by the execution of all actors. At one particular time, only one of the actors can get the resource and execute. Execution of one actor may be preempted by another eligible actor with a higher priority input event. If an actor is not preempted, then the amount of time that elapses between prefire() and fire() equals the declared. executionTime. If it is preempted, then it equals the sum of the executionTime and the execution times of the actors that preempt it. The model of computation is more deterministic than the usual priority-driven multitasking because the actor produces outputs (in its fire() method) only after it has been assured access to the CPU for its declared executionTime. In this domain, the model time may be synchronized to real time or not.

References

Modeling of wireless sensor networks requires sophisticated modeling of communication channels, sensor channels, ad-hoc networking protocols, localization strategies, media access control protocols, energy consumption in sensor nodes, etc. This modeling framework is designed to support a component-based construction of such models. It is intended to enable the research community to share models of disjoint aspects of the sensor nets problem and to build models that include sophisticated elements from several aspects.

References