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: Contribution to conference › Paper › peer-review

41 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 language	English
Publication status	Published - 19 Feb 2017
Event	International Conferences on Pervasive Patterns and Applications - Athens, Greece Duration: 19 Feb 2017 → 23 Feb 2017 Conference number: 9 https://www.iaria.org/conferences/PATTERNS.html

Conference

Conference	International Conferences on Pervasive Patterns and Applications
Abbreviated title	PATTERNS
Country/Territory	Greece
City	Athens
Period	19/02/17 → 23/02/17
Internet address	https://www.iaria.org/conferences/PATTERNS.html

Keywords

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

Access to Document

Bellekens-etal-PATTERNS-2017-Trie-compression-for-GPU-accelerated-multi-pattern-matchingAccepted author manuscript, 1.24 MB

Cite this

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

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",

}

TY - CONF

T1 - Trie compression for GPU accelerated multi-pattern matching

AU - Bellekens, Xavier

AU - Seeam, Amar

AU - Tachtatzis, Christos

AU - Atkinson, Robert

N1 - Conference code: 9

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

T2 - International Conferences on Pervasive Patterns and Applications

Y2 - 19 February 2017 through 23 February 2017

ER -

Trie compression for GPU accelerated multi-pattern matching

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this