Trie compression for GPU accelerated multi-pattern matching

Xavier Bellekens, Amar Seeam, Christos Tachtatzis, Robert Atkinson

Research output: Contribution to conferencePaper

11 Downloads (Pure)

Abstract

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.
Original languageEnglish
Publication statusPublished - 19 Feb 2017
EventInternational Conferences on Pervasive Patterns and Applications - Athens, Greece
Duration: 19 Feb 201723 Feb 2017
Conference number: 9
https://www.iaria.org/conferences/PATTERNS.html

Conference

ConferenceInternational Conferences on Pervasive Patterns and Applications
Abbreviated titlePATTERNS
CountryGreece
CityAthens
Period19/02/1723/02/17
Internet address

    Fingerprint

Keywords

  • pattern matching algorithm
  • trie compression
  • searching
  • data compression
  • GPU
  • graphics processing units

Cite this

Bellekens, X., Seeam, A., Tachtatzis, C., & Atkinson, R. (2017). Trie compression for GPU accelerated multi-pattern matching. Paper presented at International Conferences on Pervasive Patterns and Applications, Athens, Greece.