Cache Locality-Centric Parallel String Matching on Many-Core Accelerator Chips

Abstract EN

Aho-Corasick (AC) algorithm is a multiple patterns string matching algorithm commonly used in computer and network security and bioinformatics, amongmany others.

In order to meet the highly demanding computational requirementsimposed on these applications, achieving high performance for the AC algorithm iscrucial.

In this paper, we present a high performance parallelization of the AC onthe many-core accelerator chips such as the Graphic Processing Unit (GPU) fromNvidia and the Intel Xeon Phi.

Our parallelization approach significantly improvesthe cache locality of the AC by partitioning a given set of string patterns into multiple smaller sets of patterns in a space-efficient way.

Using the multiple patternsets, intensive pattern matching operations are concurrently conducted with respect to the whole input text data.

Compared with the previous approaches wherethe input data is partitioned amongst multiple threads instead of partitioning thepattern set, our approach significantly improves the performance.

Experimentalresults show that our approach leads up to 2.73 times speedup on the Nvidia K20GPU and 2.00 times speedup on the Intel Xeon Phi compared with the previous approach.

Our parallel implementation delivers up to 693 Gbps throughputperformance on the K20.