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]
Preview
 Text. Filename: Bellekens_etal_PATTERNS_2017_Trie_compression_for_GPU_accelerated_multi_pattern_matching.pdf
Accepted Author Manuscript
Download (1MB)| Preview

Abstract

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.

ORCID iDs

Bellekens, Xavier, Seeam, Amar, Tachtatzis, Christos ORCID logoORCID: https://orcid.org/0000-0001-9150-6805 and Atkinson, Robert ORCID logoORCID: https://orcid.org/0000-0002-6206-2229;
CORE (COnnecting REpositories)