@inproceedings{1eb6235501554634822935a5384c07d2,
title = "GPGPU DFA membership tests",
abstract = "Pattern matching is often implemented on the CPU to-day using deterministic finite automata (DFAs). We present methods to efficiently parallelize the DFA membership test on general-purpose graphics processing units (GPGPUs). Our partitioning scheme builds on the work of Holub and Stekr [1]. Our implementations utilize the OpenCL programming model, in which we propose a series of algorithms and related memory size constraints. Experimental results are presented on the effectiveness of these algorithms, yielding GPU speedups between 19x and 39x over the Grep utility in matching PROSITE motifs [2].",
keywords = "DFA membership test, GPGPU, PROSITE, Parallel algorithms, Pattern matching openCL",
author = "Beorn Facchini and Yousun Ko and Jung, {Min Young} and Bernd Burgstaller",
year = "2011",
doi = "10.2316/P.2011.757-014",
language = "English",
isbn = "9780889869073",
series = "Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems",
pages = "73--82",
booktitle = "Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2011",
note = "IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2011 ; Conference date: 14-12-2011 Through 16-12-2011",
}