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

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
StatePublished - 28 Feb 2017
EventPATTERNS 2017 - Athens, Greece

Publication series

Name
ISSN (Print)2308-3557

Conference

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

Fingerprint

Pattern matching
Program processors
Textures
Throughput

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

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

Proceedings of the 9th International Conferences on Pervasive Patterns and Applications. International Academy, Research, and Industry Association (IARIA), 2017.

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

@inbook{0a8e023079114da7a14144aed5a2249d,
title = "Trie compression for GPU accelerated multi-pattern matching",
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.",
author = "Xavier Bellekens and Amar Seeam and Christos Tachtatzis and Robert Atkinson",
year = "2017",
month = "2",
isbn = "9781612085340",
publisher = "International Academy, Research, and Industry Association (IARIA)",
booktitle = "Proceedings of the 9th International Conferences on Pervasive Patterns and Applications",

}

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), PATTERNS 2017, Athens, Greece, 19-23 February.

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

Proceedings of the 9th International Conferences on Pervasive Patterns and Applications. International Academy, Research, and Industry Association (IARIA), 2017.

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

TY - CHAP

T1 - Trie compression for GPU accelerated multi-pattern matching

AU - Bellekens,Xavier

AU - Seeam,Amar

AU - Tachtatzis,Christos

AU - Atkinson,Robert

PY - 2017/2/28

Y1 - 2017/2/28

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

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

M3 - Conference contribution

SN - 9781612085340

BT - Proceedings of the 9th International Conferences on Pervasive Patterns and Applications

PB - International Academy, Research, and Industry Association (IARIA)

ER -

Bellekens X, Seeam A, Tachtatzis C, Atkinson R. 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). 2017.