16996

Trie Compression for GPU Accelerated Multi-Pattern Matching

Xavier Bellekens, Amar Seeam, Christos Tachtatzis, Robert Atkinson
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}

}

Download Download (PDF)   View View   Source Source   

476

views

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.
VN:F [1.9.22_1171]
Rating: 5.0/5 (4 votes cast)
Trie Compression for GPU Accelerated Multi-Pattern Matching, 5.0 out of 5 based on 4 ratings

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: