YetiSim Blog

Not so long ago, I wrote a blog about the fact that I am separating the YetiSim state machine architecture into a generic component for contribution to the TBB project. I have no idea whether or not this component will be accepted by TBB officially, however others may find it useful so I am blogging about my design as I go. I use the term state machine to describe the construct I am building, but this is misleading. In August 2007, I started the research that lead to the YetiSim state machine construct, however it has evolved into something more sophisticated and without a proper name. Let’s start from the beginning and illustrate the initial motivations for the construct and what it does for us now.

I first looked toward TBB as a platform independent C++ threading library which could be used as the foundation of a simulation framework. Initially I was searching for a method to save and restore the stack, hence emulating coroutines for simulation. I was disappointed to learn that not only does TBB not provide any such low-level method, the usage of such methods is actually discouraged. After much thought, I realized that I could implement a state machine to provide the functionality which I required. The state machine would consist of start, final, error, fork, join and state nodes. I’ll give a brief description of the intended role of each node.

• Start Node: This is where execution of the state machine always begins, only one is permitted per state machine.
• Final Node: The normal end of an execution pathway, multiple nodes are permitted in a single state machine.
• Error Node: The abnormal termination of an execution pathway, the entire state machine will be terminated as a result. This node is used as a form of assertion.
• Fork Node: Splits a single execution pathway into multiple for potential parallel execution. Each pathway is executed independently of the others.
• Join Node: Merges multiple execution pathways back into one.
• State Node: Executes a C++ function or class member.

Each node has a corresponding symbol which I will not include here. These node types are based off state machine nodes found within UML. The nodes are joined by transitions which are either guarded or unguarded. The basic motivation is that an unguarded transition is always taken, whereas whether or not to proceed along a guarded transition is determined at runtime. Already I have omitted a critical detail, execution of the state machine proceeds literally. I will describe execution next.

When a state machine is executed, a pointer is created which points to the single start node within the state machine. Execution logic determines how execution proceeds by evaluating transitions and following them accordingly. Each node has a special meaning, and execution logic must take this into account while traversing the state machine. When a fork node is encountered, multiple pointers are created which might traverse the state machine in parallel. Similarly, join nodes indicate that multiple execution pathways should be tied together before execution proceeds. The join node will wait patiently for each execution pathway that can reach the join node to do so, and proceeds after that point.

In my opinion, the execution of a state machine will not have a significant runtime cost. The execution of a state machine provides a functionality that replaces the requirement for coroutines within simulation, since a transition might indicate that execution should not proceed until the simulation clock has been advanced by a certain amount. Similarly transitions might indicate probabilities, providing a functionality like that of a Markov chain. Since the logic of the state machine is dictated by the connections of nodes, they may be altered arbitrarily and potentially at runtime. This permits a highly dynamic programming environment with minimal additional cost. Keep in mind that saving and restoring the runtime stack would also have a significant runtime cost, and might require operating system calls. The state machine construct does not require any such calls, and should execute faster.

Earlier I described the name state machine to be misleading. This is because each state node may embed any logic, and not just represent a particular state. This construct is thus a superset of a state machine. Execution may proceed in many possible manners. Furthermore this state machine is easier to maintain than state machines implemented with switch logic. The adjustment of state machine logic does not have a high cost here, because only the representation of the state machine must be altered. A good design which incorporates the state machine concept will not require a reimplementation of existing code, rather just adjustment of transitions.

This construct is highly useful for simulations, but equally useful in other contexts. For example, this state machine might be highly useful for controlling parallel I/O when TBB itself supports it. It might also be the foundation for such an I/O library. Each state node might be labeled as computationally or I/O constrained and TBB could then manage the low-level details to ensure efficient execution with these hints. It also provides a simple interface to the TBB scheduler, and might permit designers to exploit parallelism in constructs that otherwise might be more complex. In fact, complex logic could be dissected into smaller chunks with this construct and represented easily as a system of nodes and transitions. This allows close inspection of the logic, and discussion with others to ensure that the system designed and requirements match properly. It is not difficult to construct a graphviz representation of the state machine, so it is fairly simple to inspect this logic visually to ensure proper execution.

I realize that programming languages and the computer execution itself may be considered to be a state machine. This is certainly true at a theoretical level, however adjustments to logic generally require a recompilation of source code. The state machine construct I propose has an easier method of dynamic adjustment. The state machine construct provides something like lego blocks, and thus allows users to assemble the pieces in any way they see fit.

Finally a theoretical discussion. The state machine construct I propose is deterministic. Although it appears similar to a Finite State Automaton (FSA), it is not. This state machine is capable of computation within its nodes, and has more node types than a FSA as well. The two are related, but are not identical.