Ptolemy II Domain Compatibility

Below we describe some of the issues and include a chart that describes what combinations should work.

Contents

Composing Models of Computation in Kepler/Ptolemy II

Antoon Goderis, Christopher Brooks, Ilkay Altintas, Edward A. Lee, Carole Goble. Composing Different Models of Computation in Kepler and Ptolemy II, 2007 Proceedings, International Conference on Computational Science (ICCS), May, 2007.

Although prior work has offered formalisms for comparing MoCs, e.g. [Lee & S.V. 98], MoC compositions have not been well treated. To address the void, we develop a classification of valid MoC combinations in Kepler/Ptolemy II.

In the Kepler environment, opaque composite actors can be put into workflows with a different type of director, thereby combining different models of computation in one workflow. The choice of director determines whether a given actor can be put on the inside or outside of other actors.

To determine which combinations are possible, we need to know two things about a director:

1. What properties it assumes of the actors under its control, and
2. What properties it exports via the opaque composite actor in which it is placed.

If a director’s exported properties match those assumed by another director, then it can be used within that other director. Otherwise, it cannot. If the SDF director exports properties that match those assumed by the PN director, then the SDF can be used inside PN. The properties in question can be formulated in terms of actor abstract semantics.

Actor Abstract Semantics

All models of computation in Kepler and Ptolemy II share a common abstraction that we call the actor abstract semantics.

Actors and directors are instances of Java classes that implement the Executable interface, which defines action methods. The action methods include two distinct initialization methods:

1. preinitialize(). invoked prior any static analysis performed on the workflow (such as static scheduling, type inference, checking for deadlock, etc.).

2. initialize(). invoked to initialize an actor or director to its initial conditions. This is invoked after all static analysis has been performed, but it can also be invoked during execution to reinitialize an actor.

The action methods also include three distinct execution methods that are invoked in sequence repeatedly during an execution of the workflow:

3. prefire(): invoked to check whether an actor is ready to fire (for example, an actor may return false if there are not enough input data tokens).

4. fire(). In this method, the actor should read input tokens from input ports and write tokens to output ports, but it should not change its state. That is, if the fire() method is invoked repeatedly with the same input tokens, then the resulting output tokens should be the same.

5. postfire(). In this method, the actor can read input tokens and update its state.

Finally, there is a finalization method:

6. wrapup(). This method is invoked for each actor just prior to finishing execution of a workflow.

All of the methods are required to be finite (they must eventually return).

The method definitions specify a contract, but not all actors obey this contract. Any actor that strictly conforms to this contract is said to be domain polymorphic, and the actor may be used by any director that operates on actors (which is all the directors above except FSM, which operates on states).

Actors that do not obey the contract are more specialized, and may only work with specific directors. They are not domain polymorphic (strictly obeying the actor abstract semantics) and come in two flavors. The first flavor obeys a looser version of the abstract semantics where the fire() method provides no assurance that the state of the actor is unchanged. The second is still looser in that it that also provides no assurance that any of these methods is finite.

Based on these three levels of obeyance to actor abstract semantics, we can now classify the directors.

Abstract semantics assumed by a director of the actors under its control

The PN director only assumes the loosest of these abstract semantics. It does not require that any method be finite because it invokes all of these methods, in order, in a thread that belongs entirely to the actors. If an actor chooses to run forever in the preinitialize() method, that does not create any problems for the director. The director will happily let it run. Dataflow directors require that actors conform with the loose actor semantics, where all methods are finite. But they do not require that actors leave the state unchanged in the fire() method. CT requires that actors obey the strictest form of the semantics. The director iteratively fires actors until some condition is satisfied. The strict actor semantics ensures that the answers will always be the same given the same inputs. FSM requires loose actor semantics. A firing of an FSM in Ptolemy II consists of a firing of the refinement of the current state (if there is one), followed by evaluation of the guards and a state transition. Clearly, the firing of the refinement must be finite for this to be useful.

Abstract semantics exported by a director via the actor in which it is placed

A director also implements the Executable interface. If a director conforms to the strict actor semantics, then any opaque composite actor containing that director also conforms to the contract. Such a director can be used safely within opaque composite actors that use any of the directors. None ot the directors conforms to the strict actor semantics in the current version of Ptolemy II (version 6.0). The undiscussed SR director does however and in principle CT and DE can be made to conform. Currently these and the dataflow directors all conform to the looser version of the abstract semantics, but still guarantee that all methods return after finite time. PN only conforms to the loosest version, providing no guarantees about methods ever returning. The FSM director exports whatever the state refinements export.

Director compatibility

We classify directors according to two criteria. They require that the actors they control are either strict, looser, or loosest, depending on whether they must conform with the strictest, looser, or loosest form of abstract semantics. They similarly export either strict, looser, or loosest. Ideally, any director should export the same version of the contract it assumes or a stricter version, but this is not the case in currently.

The current status of the directors is given in Table 1. The rule applied to determine director compatibility is that exported abstract semantics should be stricter or equal to required abstract semantics. The table is on-line (http://www.mygrid.org.uk/wiki/Papers/IccsPaper2007) and will evolve over time. Where available, the on-line version links each entry to example actors.

Discussion of PN, Dataflow and FSM Directors

A key question may arise at this point. If actors can be made domain polymorphic by conforming to the strict actor semantics, then why not design all directors to conform? In some cases, the semantics of the MoC precludes this. In other cases, it would simply be too costly. We examine some of these cases.

PN. The PN director is apparently the least restrictive in the actors it can manage, but also the least useful in an opaque composite actor. The reason for this is very fundamental. If the PN director were to define a finite fire() method, what should that method do? Each of the actors under its control is executing in its own thread of control. How much execution should be performed? One possible answer is "as little as possible," but this would result in nondeterminate execution. If two actors have threads that are able to perform computation, which should be allowed to perform computation? The only other obvious answer is "as much as possible." This can be made determinate, but typical PN workflows can execute forever if given the opportunity. Hence, "as much as possible" turns out to be an infinite amount. Sometimes it is finite, in that a PN model may deadlock after a finite computation. However, PN is sufficiently expressive that determining whether a workflow deadlocks is equivalent to solving the famous halting problem in computation. Hence, whether a workflow deadlocks is undecidable [Buck 93].

When a workflow has potential to be reused inside others, PN should be avoided and, if possible, replaced by a more reusable director.

DDF. DDF is as expressive as PN, and hence potentially suffers from the same limitation. However, DDF has an advantage. It assumes that all actors under its control have finite firings. Thus, it is relatively easy for the designer of a workflow to specify how many firings of the component actors constitute a single firing of the enclosing opaque composite actor. The DDF director assumes a simple default if these numbers are not given by the workflow designer: one firing of a DDF opaque composite actor constitutes at most one firing of each component actor. The actor is fired if possible, and not fired if not, given the available input data. This yields a simple, finite, and determinate notion of a finite firing for the director to export.

SDF. SDF is still simpler in that it is not as expressive as PN, and there is a simple unique finite firing that is natural and easy to define [Lee & Messerschmitt 87]. However, for both DDF and SDF, it is difficult to define a fire() of an opaque composite actor that does not update the state of the workflow because data values stored on buffers change during the firing of the component actors. In order for SDF and DDF to export the strict actor semantics, they would have to backtrack or restore the state of these buffers on repeated invocations of the fire() method. While this is doable in principle, it might be sufficiently computationally expensive that it is not worth it. A promising technique, however, that could make it computationally attractive is the lightweight backtracking mechanism developed in [Feng & Lee 06].

FSM. A particularly interesting case is FSM and modal models. Modal models always use opaque composite actors as state refinements, and these must at a minimum have finite firings to be useful (given the semantics of an FSM in Ptolemy II discussed before). Hence, it does not make sense to use PN inside the refinement of a state. But any other of the directors described above can be used in a Modal Model.

Expanded Domain Compatibility Graph

Click on the + or - to see examples that work and don't work.

Note that not all combinations make semantic sense.

The rules are

Loose goes into Loose
Loose goes inside Strict
Strict goes inside Strict

DE inside SDF

1. Stick with SDF inside SDF, don't use VariableDelay. You could get a similar effect to VariableDelay by explicitly modeling presence or absence using, for example, a boolean.
2. Use DE at the top level. Some care would be needed to make sure that SDF subsystems that exepected to fire once per day are in fact provided with input tokens once per day (e.g., using PeriodicSampler).
3. Use DE within SDF, but ensure that the DE model never needs to do anything except at multiples of the period. This solution is fragile because it will be vulnerable to quantization errors in the time variable.

Last updated $Id$