Graphics Processing Units (GPU) 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.
|Title of host publication||Proceedings of the 9th International Conferences on Pervasive Patterns and Applications|
|Publisher||International Academy, Research, and Industry Association (IARIA)|
|Publication status||Published - 28 Feb 2017|
|Event||PATTERNS 2017: The Ninth International Conferences on Pervasive Patterns and Applications - Athens, Greece|
Duration: 19 Feb 2016 → 23 Feb 2016
|Period||19/02/16 → 23/02/16|
Bellekens, X., Seeam, A., Tachtatzis, C., & Atkinson, R. (2017). Trie compression for GPU accelerated multi-pattern matching. In Proceedings of the 9th International Conferences on Pervasive Patterns and Applications International Academy, Research, and Industry Association (IARIA). http://www.thinkmind.org/index.php?view=instance&instance=PATTERNS+2017