Tech Note

Title:               Task Graph Architecture
Date:              March 5, 2003
Written by:     Peter C. Bosch
Number:        TN-001
Version:         0.1

The SOM infrastructure includes a mechanism for representing task-based workflow items in a Directed Acyclic Graph (DAG). This document describes the general architecture of this mechanism, called the Task Graph Architecture, or TGA.

A simulation may require modeling a series of related activities such as a schedule. That schedule consists of many tasks that must be performed, each perhaps requiring time and resources for completion, and each also perhaps requiring other tasks be done simultaneously, before or after them. The SOM simulation engine models this construct through, at the lowest level, a Directed Acyclic Graph object model. Above that level is a Task-oriented object model that conceptually specializes vertices into milestones[1], and specializes edges into tasks and ligatures. A task has a start and a finish milestone, and enables a custom activity, and a ligature serves as an edge to clarify a relationship between two tasks, using their start and/or finish milestones. A task graph is executed by finding one or more of its leading vertices (those with no predecessor edge), and triggering them. As they trigger their downstream edges, and those edges trigger their downstream vertices, etc, tasks in the graph each executed in a sequence that honors the dependencies and relationships reflected in the structure of the graph.

We will first discuss basic task relationships, then more advanced relationships such as childhood and vertex synchronicity, and then we will discuss a mechanism called a GraphContext that allows tasks to be stateless and to have multiple simultaneous processes and their results tracking through a given task graph at the same time. In a nod to the actually useful, we will discuss in basic terms, two ways that a modeler could use the TGA to implement a workflow item, and therefore, a network of them. Finally, we will discuss the API for starting a task graph.

Basic Task Relationships

tasks and ligatures

Figure 1 Tasks and Ligatures

Figure 1 shows the symbology that we will use to represents a task and a ligature. A task has a start and finish vertex and implies some action occurring on its edge. In traditional DAG algorithms, (some of which are provided to the TGA through the …graphs.analysis namespace) these actions can be used to imply cost, in terms of time, material or other criteria.

 In  Figure 2 below, we show several of the basic relationships between tasks.

basic task-to-task relationships

Figure 2 Basic Task-to-Task Relationships

In a predecessor/successor relationship, Task B is not permitted to commence until Task A has completed. In the bottom left sub-diagram, we describe the costart and cofinish relationships. Each may stand alone, and in both cases, Task A is considered the “master” task. In the costart relationship, Task B may not start until Task A has started. In the cofinish relationship, Task B may not complete until Task A has completed.  The handoff relationship, at the bottom right, describes a situation wherein task A may not signify itself to be complete until Task B has begun.

Advanced Task Relationships

Two additional relationships are modeled in the Task Graph architecture, those of tasks having children, and of synchronicity between vertices.

A child task Tc is a child to a parent task Tp, if it is a part of a subgraph that is slaved as a costart to Tp, and Tp is slaved as a cofinish to that subgraph. Tc must also be known to Tp as a child task through Tp’s API. Figure 3, below, demonstrates several levels of hierarchy in a task graph containing parents and children. Note that one task in a child task network (Task 7) can be a parent to another task subgraph.

Semantically, a network of child tasks can be considered to be a detailed implementation of the higher-level task that the parent task represents. An example of such a relationship might be a task, “Bake Muffins”, being executed as a part of a larger “Bakery” task graph, but having, itself, a child task network that includes making batter, filling muffin tins, using an oven, and extracting the muffins from the tins.


Task Graph Demonstrating Tasks With Children

Figure 3 A Task Graph Demonstrating Tasks With Children

A second advanced relationship that is supported in the Task Graph architecture is that of synchronicity between vertices. A costart relationship implies that one task cannot start until another has started, but that does not infer that it will start at the same time, only that it will start at an equal or greater time. The TGA includes a class called VertexSynchronizer that is illustrated in Figure 4 below. With this construct, we ensure that regardless of the time consumed by Task0 and Task 1 separately, the prevertices of Task 3 and Task 4 will fire at the same clock time as the other.

vertex synchronizer

Figure 4 VertexSynchronizer


The train of execution, as mentioned before, traverses the graph from its start (all vertices with no predecessors) to its finish (all vertices with no successors). While a task (or user class derived from the Task class) could maintain information about the current execution instance such as oven temperature or number of kilograms of muffin batter, this would prevent using the task graph construct for more than one batch of muffins at a time, for example. We would need to clone the task graph once for each batch of muffins. In a large manufacturing operation, this would incur prohibitive performance cost.

We therefore extract all state in a graph’s execution to a dictionary called a GraphContext, which is passed from vertex to edge to subsequent vertex, thereby making its way through the graph – always held by the task or tasks currently executing. This is the bucket into which all information about the current execution train is held. It is advisable to partition these data into their largest possible chunks, and then using known structures in those chunks. When grouping tasks with a Unit, we define a UnitContext that is held as an entry in the GraphContext (keyed on the unit itself) and provides type-safe access to the unit, the assigned equipment, and other unit-related data constructs. In this approach, each task can be used as a key to retrieve a data structure peculiar to that task.

When starting a new batch, or execution train through a task graph, a new GraphContext is created and assigned to that execution train.

Creating a Meaningful Task Graph

In order to model a specific recipe or sequence of networked tasks, you will need to either (a) derive from Task and provide meaningful logic, or hook into events fired by the base level task class. The mechanism we have used is to derive SOMTask from the Task class, and accommodate validity checks and snapshotting (SOM-specific but still specific-task independent requirements) in that SOMTask class. Then the SOMOperation class derives from SOMTask, and provides a mechanism for acquiring resources, performing transfers into the equipment on which the operation works, performing temperature control, transfers out, and resource relinquishment. Each of these adds an event to the set of events already supported by the TGA.

Tech Note TN-003 discusses the events fired by the Task class, the SOMTask and the SOMOperation classes..

Running A Task Graph

A task graph is run by finding all of its vertices that have no predecessors, and calling those vertices’ FireVertex(IDictionary graphContext) method with, perhaps, a new Hashtable as the graphContext. Alternatively, the graph’s edges can be added as children to a parent task, and that parent task’s Start() method could be called. This will locate all of the relevant start vertices and fire them automatically, starting the cascade through the task graph.

[1] A Task class is derived from Edge, but there is no Milestone class, as there was no functionality needed in the concept of a milestone that was not already provided through the Vertex class.