Cache Conscious Parallel Pattern Matching for Aho-Corasick Algorithm on a GPU

Pattern matching is a common and important operation in many applications including network security, bioinformatics, etc. Among many pattern matching algorithms, Aho-Corasick (AC) algorithm is intensively used in these applications. In order to speed up and meet the real-time performance requirement for AC algorithm, developing an efficient parallelization technique is essential. In this paper, we develop a new parallelization approach to cache both the input text data and the reference data organized as a 2-dimensional table in the on-chip memories (or caches) on the Graphic Processing Unit (GPU). The new approach also schedules memory accesses carefully to minimize the overhead in loading data to the on-chip shared memory. The approach significantly cuts down the memory latency to load the data and leads to impressive performance improvement. Experimental results on NVidia GT9500 GPU shows up to 15x speedup compared with a serial version on 2.2Ghz Core2Duo Intel processor.