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

Hyewon Choi, Bernd Burgstaller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationParallel and Distributed Computing 2013 - Proceedings of the Eleventh Australasian Symposium on Parallel and Distributed Computing, AusPDC 2013
PublisherAustralian Computer Society
Number of pages8
ISBN (Print)9781921770258
Publication statusPublished - 2013
Event11th Australasian Symposium on Parallel and Distributed Computing, AusPDC 2013 - Adelaide, Australia
Duration: 2013 Jan 292013 Feb 1

Publication series

NameConferences in Research and Practice in Information Technology Series
ISSN (Print)1445-1336


Other11th Australasian Symposium on Parallel and Distributed Computing, AusPDC 2013

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Software


Dive into the research topics of 'Non-blocking parallel subset construction on shared-memory multicore architectures'. Together they form a unique fingerprint.

Cite this