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.


Bellekens, Xavier, Seeam, Amar, Tachtatzis, Christos ORCID logoORCID: and Atkinson, Robert ORCID logoORCID:;