Tech Note

Title: Procedure Function Chart Validation
Date: July 22, 2010
Written by: Peter C. Bosch
Number: TN-022
Version: 0.1

Note Highpoint Libraries include Procedure Function Chart (PFC) constructs that are used for control system recipe generation and a dynamic execution engine.

Procedure function charts are a graph-oriented means for describing an execution scheme with activities (or Steps) occurring before, after and concurrently-to other steps. As parallelism, loops and branches are supported in this format, it is possible to describe a PFC that could result in uncontrolled impact on execution (see figure 1,) or perpetual deadlock (see figure 2,) unless measures are taken to control the combination of transitions, steps and links.

Unstable graph - token generator

Figure 1 : Unstable - Token Generator

Deadlock graph configuration

 

Figure 2 : Unstable - Deadlock

These measures can follow either of two approaches - either controlling the creation of the network such that it can only be valid, or of performing validation of the network after creation to determine whether it is valid.

We describe an algorithm that, with a couple of simple assumptions, achieves the latter, enabling static analysis of a PFC to determine if the graph will run properly (i.e. without instabilities.)

Algorithmic Approach

We use tokens in a hierarchical relationship and assigned to elements in the PFC to represent meta-execution sequences. By "meta-execution sequences," we mean that a token represents one possible execution path through a node to which it is assigned. Thus, when a series divergence is encountered, since (and on the assumption that) only one path may be taken in any single case, all branches get the same token. Similarly, when a parallel divergence is encountered, since all paths are taken, each gets a new token, a child of the token that was assigned to the transition that created the divergence. On a convergence, the inbound tokens are coalesced. In the case of a parallel convergence, a parent or one sibling token may be assigned to the convergence transition, and in the case of a serial convergence, one of the inbound tokens is assigned to the convergence step.

After completely traversing the graph and assigning tokens to elements, a static analysis of the tokens allows us to make an assessment of its validity.

Token And PFCElement Characteristics

A token has an OriginElement, which is the PfcElement to which it was first attached.

A token has a Generation, which is how many descents there are from the root token to itself.

A token has an ActivePathCount, which represents how many copies of that token are currently being used by elements either executing, or waiting in the execution list. A token that has its ActivePathCount decremented to zero is said to have been deactivated, and when/if it is reincremented to 1, it has been reactivated.

A PfcElement has a collection each of PredecessorNodes and SuccessorNodes, which are the PfcSteps (for a PfcTransition) or PfcTransitions (for a PfcStep) that precede or follow it.

A PfcElement has a property called the GraphOrdinal, which is an integer, computed to indicate its minimum path distance from the start element in the PFC. This property is used, among other things, to detect when a link represents a rejoining of a path to a previously-traversed path (i.e. the rejoint of a loopback.)

 

Algorithm Dynamics

An execution list is created for impending PFC elements. The process starts with the creation of a token for, and assignation of it to, the initial element of the PFC, and the initial enqueueing of that element into the execution list. Execution occurs by sorting the list, then taking the next impending node and processing its token, and adding the node's successors, if they have not yet been run, to the list. This process is repeated until all PFC elements have been processed.

Sorting, which determines the next element to process, is done such that parallel convergences are done after all other elements, elements whose tokens have the largest generation (i.e. are deepest in the graph) are done first, and when both of the preceding have been taken into account, elements with lower GraphOrdinal values are done first. This ensures that the front representing next-to-run elements advances until nothing but parallel convergences can be processed, and then, that the deepest convergences are processed in a repeatable order.

Element Processing Scenarios

Initial Element

The initial element of the PFC gets a token denoted as "Token 0," which serves as the root token of the entire graph.

Passthrough Element

Any element that is followed by only one element passes its token directly to that element.

Serial Divergence

Any step that is followed by more than one transition passes its token to all of those transitions, incrementing its ActivePathCount by N-1, where N is the number of successors.

Serial Convergence

The first time a transition that represents a serial convergence is dequeued for processing, its token is passed on to its successor. For subsequent dequeueings, (it will be enqueued once by each of its predecessors) no further processing is performed, but the ActivePathCount is decremented. This ensures that the path through a serial convergence is followed only once, and ensures that as a path is terminated into a serial convergence, its count remains correct. After a convergence, it does not matter, for the purposes of static analysis, which path the token arrived on.

Parallel Divergence

Any transition that is followed by more than one step is host to a parallel divergence. When that transition is processed, it has one child of its token created for, and attached to, each outbound successor element as that element is enqueued. Finally, its token's ActivePathCount is decremented to represent that the parent token is now hibernated, and will not awaken until all of its children are no longer active. It may thus be deactivated. See Parallel Convergence for details.

 

Parallel Convergence

The parallel convergence is the most complex of the processing scenarios. Unlike a serial convergence, a parallel convergence is not processed until all of its predecessors have completed. This ensures that Fundamentally, when a convergence happens, we want to close out as many of the incoming paths as possible. If it is a convergence of all of the sibling paths that diverged at one point, those siblings are all deactivated (ActivePathCount decremented to zero), and the parent token is reactivated. In effect, the parent's path, which was suspended is resumed. See Figure 3 for an illustration. If the convergence involves a subset of the sibling paths, then one path is nominated to carry forth, and all but that one are decremented/deactivated. See Figure 4 for an illustration.

In the case where the converging paths did not come from the same divergence, their tokens are still decremented, but the challenge is to identify the right token to assign to the convergence transition. We identify the youngest (closest) common ancestor to all incoming tokens, and if all of that ancestor's successor paths are closed by this transition, the ancestor's token is assigned to this transition. See XXXXXX for an example. The token belonging to that divergence transition is incremented and assigned to the convergence transition.

parallel divergence not completed

Figure 3 : Parallel Divergence Completed

parallel divergence not completed

Figure 4 : Parallel Divergence Not Completed

 

Terminal Element

The terminal element will be the last PfcElement processed, and its token is already assigned when it is dequeued. Since it has no SuccessorNodes, no successors are enqueued, and processing terminates.

Post-Assignment Assessment

Parallel Convergences

Parallel convergences are not analyzed individually, but instead,

Serial Convergences

Terminal Element


flip-flopFuture Research

Several new research areas are of interest.

1.) Using a two dimensional tree hierarchy for tokens where children in one dimension represent concurrent paths, and in the other dimension represent alternate paths. We feel this could simplify the parallel convergence closure algorithm, and possibly address the second research area.

2.) We feel that the alternate path closure evaluation (do all incoming branches share the same token?) excludes some valid graph constructs (although they are not constructs that can be created in any application currently using our libraries). See the PFC segment to the right.

This needs to be addressed.

3.) We would like to shift the emphasis of the analysis to links from elements. Links would host a token, but also have a role which, by the Duality rule, can only be "Passthrough," "Parallel Divergence," "Parallel Convergence," "Serial Divergence" or "Serial Convergence" with no link holding more than one of these roles.