CSE: Parallel finite state machines with convergence set enumeration

Finite State Machines (FSMs) are known to be “embarrassingly sequential” because the next state depends on the current state and input symbol. Enumerative FSMs break the data dependencies by cutting the input symbols into segments and processing all segments in parallel. With unknown starting state (except the first segment), each segment needs to calculate the state transitions, i.e., state state, for all states, each one called an enumeration path. The current software and hardware implementations suffer from two drawbacks: 1) large amount of state state computation overhead for the enumeration paths; and 2) the optimizations are restricted by the need to correctly perform state state and only achieve limited improvements. This paper proposes CSE, a Convergence Set based Enumeration based parallel FSM, to address these drawbacks. PDF