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

    44 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 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
    Publication statusPublished - 28 Feb 2017
    EventPATTERNS 2017: The Ninth International Conferences on Pervasive Patterns and Applications - Athens, Greece
    Duration: 19 Feb 201623 Feb 2016

    Publication series

    Name
    ISSN (Print)2308-3557

    Conference

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

    Fingerprint Dive into the research topics of 'Trie compression for GPU accelerated multi-pattern matching'. Together they form a unique fingerprint.

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