A Speculative Parallel DFA Membership Test for Multicore, SIMD and Cloud Computing Environments
The authors present techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Their method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. They partition the input string into chunks, match chunks in parallel, and combine the matching results. Their parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, their speculation is failure-free, i.e., sequential semantics are maintained, and speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, their matching operation is fully vectorized.