Tech Note

Title:               TaskGraph Synchronization & Remapping
Date:              June 6, 2003
Written by:     Peter Bosch
Number:        TN-009
Version:         0.1

The Modeler works with the concept of at least two types of models, process models and plant models. A plant model is created from a process model, with new tasks added as children to the existing tasks in the process model. The types of tasks are determined as a result of user-provided data and preexistent maps of operations to operation steps. This tech note describes the features that support this requirement, including vertex synchronizers, yielding and joining. We then walk through a scenario that was developed by way of providing a specification, and finally offer some suggestions on how these features can affect PERT analysis.

Task Graph

As a reminder, simulations are built from plant, process and product specifications. (Plant specs are resource pools, process specs are recipes, and product specs are material types.) The process portion of a simulation is built up as a directed graph consisting of vertices and edges, where vertices represent synchronization points and edges represent tasks running from one vertex to another. A task graph has a single root task, which represents the overall goal of the graph. A given task may have child tasks that represent sub-steps that are executed toward the completion of the parent task. These children may, themselves, have child tasks. An illustrative example is provided in Figure 1, below.

task graph for making oatmeal

Figure 1: Task Graph for Making Oatmeal

Vertex Synchronizer

Simple TaskGraph construction with edges, vertices and ligatures can be used to ensure that one task does not begin before another, end after another, etc (see Figure 2 below). These constructs, however, depict a one way relationship – one vertex cannot fire until after another, but it may end up firing long after the other.

 remapping scenario, after

Figure 2 : Simple Task Graph Relationships

In order to ensure that two vertices fire simultaneously[1], the developer must use a Vertex Synchronizer. A Vertex Synchronizer ensures that among a set of vertices, none will fire until all are ready to fire, and at that precise simulation clock time, all of the vertices in the set will fire, in a specified order. This is useful, for example, when a material handoff is being performed and there is no buffering capability. Both the sending and the receiving operations must be running for the transfer to occur, and if either is not ready, the transfer must wait.

hypothetical transfer process

Figure 3: Hypothetical Transfer Process

In Figure 3 above, preparatory activities, some unrelated to each other, must all be complete in order for a transfer to take place. The Vertex Synchronizer will ensure that neither of its vertices fires until all preparatory activities are complete. Then, it will fire first the Transfer event, and then the receive event, at the same clock time, but in that order.

Yielding

Yielding, available through the Edge.Yield(IExecutive exec) method, suspends execution of the current task until all other tasks scheduled at the same priority and for the current time have had a chance to execute, at which time the original task continues from the line of code following the Yield call. This is useful when a task needs to permit its surroundings to evolve in order to complete its efforts.

Joining

Joining, available through the Edge.Join(IExecutive exec, Edge otherEdge) method, suspends execution of the current edge until the otherEdge has completed.

A Note on Yield And Join

Both Yield and Join entail suspension of execution of the current edge. This is useful if the aggregate state being managed by the edge is considerable in complexity – that is, if it would take significant time and effort to “pack it up” into a state object, schedule a callback that re-provided that state object, and terminate the thread, then a suspension is often a better option. Suspension of execution is not possible if the event is being run on the executive’s dispatcher thread, since it would suspend execution of the executive itself. Therefore, if the event being serviced is being serviced as a synchronous event, the call will fail with an exception.

In addition to the inadvisability of suspending the executive’s dispatch thread, Yield and Join operations, if used, impose dynamic dependencies on the flow through a task graph. PERT analysis relies on evaluation of the static form of the task graph, and therefore, errors may be introduced into the PERT analysis by the use of Join and Yield operations. It is best, if it can be done, to represent join and yield operations as simple task graph relationships. Sometimes, though, as in dynamic (run-time) graph reconfiguration, this is not possible. In this case, the developer will want to ensure that PERT data are not extracted from a run that employed dynamic Join and Yield operations.

Since they are a part of the static structure of the graph, Vertex Synchronizers are accounted for, in PERT analysis.

How Does Remapping Work?

Remapping is the process of adding detail to a task graph. This can be done dynamically during validation. See Figure 4 below for an example of a task graph that is to be remapped. We have a recipe that consists of two units, each of which has three operations underneath it. The pre-vertices of the second tasks under each unit are synchronized, ensuring that these edges’ service commences at the same time. We desire, in Remapping, to add operation steps under each of the operations. The difficulty arises in the remapping of operations 1_2 and 2_2, since they will both have to be remapped, and then a connection established (which creates a vertex synchronizer) between pairs of the operation steps.

remapping scenario, before

Figure 4: Remapping Scenario, Before

This means that there will need to be three actions involved in the remapping, namely, (1) create children of 1_2, (2) create children of 2_2, and (3) create mappings between the children.

Remapping occurs during the handling of the event fired when the edge starts. Operation 1_1 and 1_2 create their children on their receipt of this event, and as they have no relationships to anyone but their parent, this is sufficient for their creation.

After an edge creates its children, since it’s own execution implies that its PreVertex has already fired, and therefore only the PostEdges that were known to the PreVertex at that time were scheduled for execution, it may want to ensure that these children are given a chance to execute on the current run. It can do this by calling Edge.ScheduleForImmediateCommencement(IDictionary graphContext).

Operation1_2, in its handler, knows (or can find out) enough about its own state to determine what children it needs to create for itself, so it creates them. The presence of the vertex synchronizer on the PreVertices of operations 1_2 and 2_2 ensure that both are running at the current time. So operation 1_2 yields after it creates its children, allowing operation 2_2 to create its children. Operation 2_2 has just created receiving operation steps, so it knows that they will need to be connected to by someone else, and therefore, operation 2_2 yields. This allows operation 1_1 to continue from the place where it had previously yielded, and its next activity is to make the required connections, and thereby to establish the three new vertex synchronizers.

 

Figure 5: Remapping Scenario, After

The connection (and therefore the vertex synchronizer) may be left in place on the PreVertex if it is expected that the parent operations will need to remap again (recall the importance of the two edges being begun at the same time, in order for the Yield operation to have the desired result), or it may be removed for higher fidelity timing (though this may not be an issue with MAI. If it becomes an issue, we recommend that immediately prior to a validation run in which remapping is anticipated, the vertex synchronizer be reestablished.

See Listing 1 below for an example. OnValSim_1_2 is the event handler for the validation or simulation of Operation 1_2, and the same naming pattern applies for the other methods shown. Technically, it would probably be better to place remapping only in a validation handler…

remapping code example

Listing 1: Remapping Code Example



[1] Note that ‘simultaneously’ infers ‘at the same simulation clock time’, not ‘in concurrent threads.’