Scaling out Speculative Execution of FiniteState Machines with Parallel Merge Finite State Machine (FSM) is a key component in many important applications, such as Huffman decoding, regular expression matching, and HTML tokenization. Due to its inherent dependency and unpredictable memory access, FSM computations are considered to be extremely difficult to parallelize. As such, significant research efforts have been made to accelerate FSM computations. Although they achieve promising performance results on multicore machines, these methods are not scalable for emerging manycore architectures such as GPUs.NWe analyzed the bottleneck of achieving scalability on GPUs is the sequential merge inherent to these methods. However, different from simple reduction loops, parallelization of FSM computations typically incorporates runtime check and reexecution, which may significantly affect performance. Based on these observations, our parallel merge implementations select efficient runtime check implementations and avoids unnecessary reexecutions. Further, based on GPU architectural features, we develop optimization techniques to further improve performance.NWe evaluate our parallel merge implementations on a set of representative algorithms. Experimental results show that our parallel merge implementation is several times more efficient than sequential merge implementations and achieves linear scalability on different GPUs.NYang XiaThe Ohio State UniversityPeng

Pipelined Parallel Finite Automata Evaluation Finite automata are key compute models in modern computational theory and important building blocks for digital logic used for regular expression and protocol parsing, filtering, and control. Finite automata evaluation would seem to be a sequential operation, since we need to complete the evaluation of one state to know the next state in which to evaluate the logic. Nonetheless, parallel theory provides strategies for parallel finite automata evaluation. We show how to exploit this parallel evaluation strategy in practice on todayu0027s high capacity FPGAs, including a novel formulation for spatially pipelined evaluation. For nondeterministic finite automata (NFA) with S states, we can evaluate N inputs in a single cycle with O(N * S2) BRAMs and O(N*S3) LUTs. This allows us, for example, to consume 64 inputs on a 16 state NFA in a single cycle on the Xilinx XZCU9EGffvb11562i SoC FPGA, achieving 47 GBs (377 Gbs) single stream throughput for 8b inputs. For a 40 Gbs network link, we can support 28 state NFAs.