Trie compression for GPU accelerated multi-pattern matching

Xavier Bellekens, Amar Seeam, Christos Tachtatzis, Robert Atkinson

Research output: Contribution to conferencePaper

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.

Conference

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

Fingerprint

Pattern matching
Data storage equipment
Program processors
Textures
Throughput
Graphics processing unit

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.
Bellekens, Xavier ; Seeam, Amar ; Tachtatzis, Christos ; Atkinson, Robert. / Trie compression for GPU accelerated multi-pattern matching. Paper presented at International Conferences on Pervasive Patterns and Applications, Athens, Greece.
@conference{29bc9f9f236a4e4f987e1f912558dbfe,
title = "Trie compression for GPU accelerated multi-pattern matching",
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.",
keywords = "pattern matching algorithm, trie compression, searching, data compression, GPU, graphics processing units",
author = "Xavier Bellekens and Amar Seeam and Christos Tachtatzis and Robert Atkinson",
year = "2017",
month = "2",
day = "19",
language = "English",
note = "International Conferences on Pervasive Patterns and Applications, PATTERNS ; Conference date: 19-02-2017 Through 23-02-2017",
url = "https://www.iaria.org/conferences/PATTERNS.html",

}

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, 19/02/17 - 23/02/17, .

Trie compression for GPU accelerated multi-pattern matching. / Bellekens, Xavier; Seeam, Amar; Tachtatzis, Christos; Atkinson, Robert.

2017. Paper presented at International Conferences on Pervasive Patterns and Applications, Athens, Greece.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Trie compression for GPU accelerated multi-pattern matching

AU - Bellekens, Xavier

AU - Seeam, Amar

AU - Tachtatzis, Christos

AU - Atkinson, Robert

PY - 2017/2/19

Y1 - 2017/2/19

N2 - 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.

AB - 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.

KW - pattern matching algorithm

KW - trie compression

KW - searching

KW - data compression

KW - GPU

KW - graphics processing units

UR - https://www.iaria.org/conferences2017/PATTERNS17.html

M3 - Paper

ER -

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