Multipattern string matching on a GPU

Author

Zha, Xinyan ; Sahni, Sartaj

Author_Institution

Comput. & Inf. Sci. & Eng., Univ. of Florida, Gainesville, FL, USA

fYear

2011

fDate

June 28 2011-July 1 2011

Firstpage

277

Lastpage

282

Abstract

We develop GPU adaptations of the Aho-Corasick string matching algorithm for the the case when all data reside initially in the GPU memory and the results are to be left in this memory. We consider several refinements to a base GPU implementation and measure the performance gain from each refinement. Experiments conducted on an NVIDIA Tesla GT200 GPU that has 240 cores running off of a Xeon 2.8GHz quad-core host CPU show that our Aho-Corasick GPU adaptation achieves a speedup between 8.5 and 9.5 relative to a single-thread CPU implementation and between 2.4 and 3.2 relative to the best multithreaded implementation.

Keywords

computer graphic equipment; coprocessors; multi-threading; multiprocessing systems; string matching; Aho-Corasick string matching algorithm; GPU memory; NVIDIA Tesla GT200 GPU; Xeon 2.8GHz quad core host CPU; multipattern string matching; multithreaded implementation; single thread CPU implementation; Arrays; Bandwidth; Doped fiber amplifiers; Graphics processing unit; Instruction sets; Memory management; Registers; Aho-Corasick; CUDA; GPU; Multipattern string matching;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers and Communications (ISCC), 2011 IEEE Symposium on

Conference_Location

Kerkyra

ISSN

1530-1346

Print_ISBN

978-1-4577-0680-6

Electronic_ISBN

1530-1346

Type

conf

DOI

10.1109/ISCC.2011.5983790

Filename

5983790