Trie Compression for GPU Accelerated Multi-Pattern Matching
Division of Computing and Mathematics, Abertay University, Dundee, Scotland
arXiv:1702.03657 [cs.DS], (13 Feb 2017)
@article{bellekens2017trie,
title={Trie Compression for GPU Accelerated Multi-Pattern Matching},
author={Bellekens, Xavier and Seeam, Amar and Tachtatzis, Christos and Atkinson, Robert},
year={2017},
month={feb},
archivePrefix={"arXiv"},
primaryClass={cs.DS}
}
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.
February 18, 2017 by hgpu
