Beorn Facchini, Yousun Ko, Min-Young Jung, and Bernd Burgstaller
GPGPU, DFA membership test, Pattern matching, OpenCL
Pattern matching is often implemented on the CPU today 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. 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.
Important Links:
Go Back
