Trie compression for GPU accelerated multi-pattern matching

Bellekens, Xavier and Seeam, Amar and Tachtatzis, Christos and Atkinson, Robert (2017) Trie compression for GPU accelerated multi-pattern matching. In: International Conferences on Pervasive Patterns and Applications, 2017-02-19 - 2017-02-23.

[thumbnail of Bellekens-etal-PATTERNS-2017-Trie-compression-for-GPU-accelerated-multi-pattern-matching]
Text. Filename: Bellekens_etal_PATTERNS_2017_Trie_compression_for_GPU_accelerated_multi_pattern_matching.pdf
Accepted Author Manuscript

Download (1MB)| Preview


Graphics Processing Units allow for running massively parallel applications offloading the CPU from computationally intensive resources, however GPUs have a limited amount of memory. In this paper a trie compression algorithm for massively parallel pattern matching is presented demonstrating 85% less space requirements than the original highly efficient parallel failure-less aho-corasick, whilst demonstrating over 22 Gbps throughput. The algorithm presented takes advantage of compressed row storage matrices as well as shared and texture memory on the GPU.