Finite State Machines
←Older revision | Newer revision→
Computation represented as a finite state machine (FSM) is described by an interconnected set of states. The state machine can be described by the tuple [tuple here]. Σ is the set of possible inputs, Γ is the set of possible outputs, S is a non-empty set of states, s0 ε S is the initial state, δ: Σ × S →S is a state transition function which determines the next state based on the current inputs and state, and ω: Σ × S → Γ is an output function based on the current inputs and state:
State machines may have parallelism in the computation of their state transitions. Some state machines can decompose into multiple simultaneously active state machines. Their combined states and outputs functionally mimic the original state machine. The state machines may interact for transitions requiring some communication overhead. Each state machine is ideally simpler than the original making state transitions and output calculations simpler for each and capable of being done in parallel. Consider a state machine that shares registers among states. Each bit can potentially compute its next state value in parallel with other bits.
FSMs are naturally expressed in code as a case statement. Each case represents a different state and the switch statement evaluates the current state and the input conditions. The general form of implementing a FSM on a uniprocessor takes the following form. Each ƒ may produce output and must compute a single next state based solely on the input states (.i.e ƒ must not contain any state of its own). Each time through the case statement represents another state transition.
Parallelism in FSMs is often difficult to utilize. Since there is only one state active at any one time, only one thread of execution is naturally capable of executing it. However, opportunities can come from either decomposition or composition with other finite FSMs. Since decomposed FSMs can have more than one active state, they may be implemented by multiple processing elements. A processing element would calculate its FSM's next state based on the original inputs, its current state, and outputs from other state machines it is interacting with. Decomposition ideally creates smaller simpler state machines dividing the next state and output computation across processing elements. Parallelism exploited must justify the communication overhead introduced.
Original text by Will Plishker.