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 (Bellekens-etal-PATTERNS-2017-Trie-compression-for-GPU-accelerated-multi-pattern-matching)
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;