Trie compression for GPU accelerated multi-pattern matching

Xavier Bellekens, Amar Seeam, Christos Tachtatzis, Robert Atkinson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 9th International Conferences on Pervasive Patterns and Applications
PublisherInternational Academy, Research, and Industry Association (IARIA)
ISBN (Print)9781612085340
Publication statusPublished - 28 Feb 2017
EventPATTERNS 2017: The Ninth International Conferences on Pervasive Patterns and Applications - Athens, Greece
Duration: 19 Feb 201623 Feb 2016

Publication series

Name
ISSN (Print)2308-3557

Conference

ConferencePATTERNS 2017
CountryGreece
CityAthens
Period19/02/1623/02/16

Fingerprint Dive into the research topics of 'Trie compression for GPU accelerated multi-pattern matching'. Together they form a unique fingerprint.

  • Cite this

    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