Non-blocking parallel subset construction on shared-memory multicore architectures

We discuss ways to effectively parallelize the sub- set construction algorithm, which is used to con- vert non-deterministic finite automata (NFAs) to deterministic finite automata (DFAs). This con- version is at the heart of string pattern match- ing based on regular expressions and thus has many applications in text processing, compilers, scripting languages and web browsers, security and more recently also with DNA sequence analysis. We discuss sources of parallelism in the sequen- tial algorithm and their profitability on shared- memory multicore architectures. Our NFA and DFA data-structures are designed to improve scal- ability and keep communication and synchroniza- tion overhead to a minimum. We present three dif- ferent ways for synchronization; the performance of our non-blocking synchronization based on a compare-and-swap (CAS) primitive compares fa- vorably to a lock-based approach. We consider structural NFA properties and their relationship to scalability on highly-parallel multicore architec- tures. We demonstrate the efficiency of our paral- lel subset construction algorithm through several benchmarks run on a 4-CPU (40 cores) node of the Intel Manycore Testing Lab. Achieved speedups are up to a factor of 32x with 40 cores.