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   

779

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.
Rating: 3.8/5. From 8 votes.
Please wait...

* * *

* * *

Featured events

2018
November
27-30
Hida Takayama, Japan

The Third International Workshop on GPU Computing and AI (GCA), 2018

2018
September
19-21
Nagoya University, Japan

The 5th International Conference on Power and Energy Systems Engineering (CPESE), 2018

2018
September
22-24
MediaCityUK, Salford Quays, Greater Manchester, England

The 10th International Conference on Information Management and Engineering (ICIME), 2018

2018
August
21-23
No. 1037, Luoyu Road, Hongshan District, Wuhan, China

The 4th International Conference on Control Science and Systems Engineering (ICCSSE), 2018

2018
October
29-31
Nanyang Executive Centre in Nanyang Technological University, Singapore

The 2018 International Conference on Cloud Computing and Internet of Things (CCIOT’18), 2018

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: