Performance Optimization of Aho-Corasick Algorithm on a GPU

摘要

Aho-Corasick (AC) algorithm is a multiple patternsmatching algorithm commonly used for applications such ascomputer and network security, bioinformatics, image processing, among others. These applications are computationallydemanding, thus optimizing performance for AC algorithm iscrucial. In this paper, we present a performance optimizationstrategy for the AC algorithm on a Graphic Processing Unit(GPU). Our strategy efficiently utilizes the high degree of the onchipparallelism and the complicated memory hierarchy of theGPU so that the aggregate performance (or throughput) for theAC algorithm can be optimized. The strategy significantly cutsdown the effective memory access latencies and efficiently utilizesthe memory bandwidth. Also, it maximizes the effects of themultithreading capability of the GPU through optimal threadscheduling. Experimental results on Nvidia GeForce GTX 285GPU show that our approach delivers up to 127 Gbps throughputperformance and 222-times speedup compared with a serialversion running on single core of 2.2Ghz Core2Duo Intelprocessor.