Trie compression for GPU accelerated multi-pattern matching

Xavier Bellekens; Amar Seeam; Christos Tachtatzis; Robert Atkinson

Trie compression for GPU accelerated multi-pattern matching

Xavier Bellekens, Amar Seeam, Christos Tachtatzis, Robert Atkinson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

62 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 language	English
Title of host publication	Proceedings of the 9th International Conferences on Pervasive Patterns and Applications
Publisher	International Academy, Research, and Industry Association (IARIA)
ISBN (Print)	9781612085340
Publication status	Published - 28 Feb 2017
Event	PATTERNS 2017: The Ninth International Conferences on Pervasive Patterns and Applications - Athens, Greece Duration: 19 Feb 2016 → 23 Feb 2016

Publication series

Name
ISSN (Print)	2308-3557

Conference

Conference	PATTERNS 2017
Country/Territory	Greece
City	Athens
Period	19/02/16 → 23/02/16

Keywords

Pattern matching algorithm
Trie compression
Searching
Data compression
GPU

Access to Document

Bellekens_TrieCompressionforGPU_Published_2017Final published version, 196 KB

http://www.thinkmind.org/index.php?view=instance&instance=PATTERNS+2017

Cite this

@inproceedings{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 = feb,

day = "28",

language = "English",

isbn = "9781612085340",

publisher = "International Academy, Research, and Industry Association (IARIA)",

booktitle = "Proceedings of the 9th International Conferences on Pervasive Patterns and Applications",

note = "PATTERNS 2017 : The Ninth International Conferences on Pervasive Patterns and Applications ; Conference date: 19-02-2016 Through 23-02-2016",

}

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/02/16. <http://www.thinkmind.org/index.php?view=instance&instance=PATTERNS+2017>

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 proceeding › Conference contribution

TY - GEN

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)

T2 - PATTERNS 2017

Y2 - 19 February 2016 through 23 February 2016

ER -

Trie compression for GPU accelerated multi-pattern matching

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this