Perfect Hashing Based Parallel Algorithms for Multiple String Matching on Graphic Processing Units

Cheng-Hung Lin, Jin Cheng Li, Chen Hsiung Liu, Shih Chieh Chang

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

Multiple string matching has a wide range of applications such as network intrusion detection systems, spam filters, information retrieval systems, and bioinformatics. To accelerate multiple string matching, many hardware approaches are proposed to accelerate string matching. Among the hardware approaches, memory architectures have been widely adopted because of their flexibility and scalability. A conventional memory architecture compiles multiple string patterns into a state machine and performs string matching by traversing the corresponding state transition table. Due to the ever-increasing number of attack patterns, the memory used for storing the state transition table increased tremendously. Therefore, memory reduction has become a crucial issue in optimizing memory architectures. In this paper, we propose two parallel string matching algorithms which adopt perfect hashing to compact a state transition table. Different from most state-of-the-art approaches implemented on specific hardware such as TCAM, FPGA, or ASIC, our proposed approaches are easily implemented on commodity DRAM and extremely suitable to be implemented on GPUS. The proposed algorithms reduce up to 99.5 percent memory requirements for storing the state transition table compared to the traditional two-dimensional memory architecture. By studying existing approaches, our results obtain significant improvements in memory efficiency.

Original languageEnglish
Article number7864442
Pages (from-to)2639-2650
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Volume28
Issue number9
DOIs
Publication statusPublished - 2017 Sep 1

Fingerprint

Memory architecture
Parallel algorithms
Data storage equipment
String searching algorithms
Hardware
Information retrieval systems
Dynamic random access storage
Intrusion detection
Application specific integrated circuits
Bioinformatics
Computer hardware
Field programmable gate arrays (FPGA)
Scalability
Graphics processing unit

Keywords

  • Perfect hashing
  • deterministic finite automaton
  • string matching

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

Perfect Hashing Based Parallel Algorithms for Multiple String Matching on Graphic Processing Units. / Lin, Cheng-Hung; Li, Jin Cheng; Liu, Chen Hsiung; Chang, Shih Chieh.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 28, No. 9, 7864442, 01.09.2017, p. 2639-2650.

Research output: Contribution to journalArticle

@article{eedff075f75542ca97eb07647b669c94,
title = "Perfect Hashing Based Parallel Algorithms for Multiple String Matching on Graphic Processing Units",
abstract = "Multiple string matching has a wide range of applications such as network intrusion detection systems, spam filters, information retrieval systems, and bioinformatics. To accelerate multiple string matching, many hardware approaches are proposed to accelerate string matching. Among the hardware approaches, memory architectures have been widely adopted because of their flexibility and scalability. A conventional memory architecture compiles multiple string patterns into a state machine and performs string matching by traversing the corresponding state transition table. Due to the ever-increasing number of attack patterns, the memory used for storing the state transition table increased tremendously. Therefore, memory reduction has become a crucial issue in optimizing memory architectures. In this paper, we propose two parallel string matching algorithms which adopt perfect hashing to compact a state transition table. Different from most state-of-the-art approaches implemented on specific hardware such as TCAM, FPGA, or ASIC, our proposed approaches are easily implemented on commodity DRAM and extremely suitable to be implemented on GPUS. The proposed algorithms reduce up to 99.5 percent memory requirements for storing the state transition table compared to the traditional two-dimensional memory architecture. By studying existing approaches, our results obtain significant improvements in memory efficiency.",
keywords = "Perfect hashing, deterministic finite automaton, string matching",
author = "Cheng-Hung Lin and Li, {Jin Cheng} and Liu, {Chen Hsiung} and Chang, {Shih Chieh}",
year = "2017",
month = "9",
day = "1",
doi = "10.1109/TPDS.2017.2674664",
language = "English",
volume = "28",
pages = "2639--2650",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "9",

}

TY - JOUR

T1 - Perfect Hashing Based Parallel Algorithms for Multiple String Matching on Graphic Processing Units

AU - Lin, Cheng-Hung

AU - Li, Jin Cheng

AU - Liu, Chen Hsiung

AU - Chang, Shih Chieh

PY - 2017/9/1

Y1 - 2017/9/1

N2 - Multiple string matching has a wide range of applications such as network intrusion detection systems, spam filters, information retrieval systems, and bioinformatics. To accelerate multiple string matching, many hardware approaches are proposed to accelerate string matching. Among the hardware approaches, memory architectures have been widely adopted because of their flexibility and scalability. A conventional memory architecture compiles multiple string patterns into a state machine and performs string matching by traversing the corresponding state transition table. Due to the ever-increasing number of attack patterns, the memory used for storing the state transition table increased tremendously. Therefore, memory reduction has become a crucial issue in optimizing memory architectures. In this paper, we propose two parallel string matching algorithms which adopt perfect hashing to compact a state transition table. Different from most state-of-the-art approaches implemented on specific hardware such as TCAM, FPGA, or ASIC, our proposed approaches are easily implemented on commodity DRAM and extremely suitable to be implemented on GPUS. The proposed algorithms reduce up to 99.5 percent memory requirements for storing the state transition table compared to the traditional two-dimensional memory architecture. By studying existing approaches, our results obtain significant improvements in memory efficiency.

AB - Multiple string matching has a wide range of applications such as network intrusion detection systems, spam filters, information retrieval systems, and bioinformatics. To accelerate multiple string matching, many hardware approaches are proposed to accelerate string matching. Among the hardware approaches, memory architectures have been widely adopted because of their flexibility and scalability. A conventional memory architecture compiles multiple string patterns into a state machine and performs string matching by traversing the corresponding state transition table. Due to the ever-increasing number of attack patterns, the memory used for storing the state transition table increased tremendously. Therefore, memory reduction has become a crucial issue in optimizing memory architectures. In this paper, we propose two parallel string matching algorithms which adopt perfect hashing to compact a state transition table. Different from most state-of-the-art approaches implemented on specific hardware such as TCAM, FPGA, or ASIC, our proposed approaches are easily implemented on commodity DRAM and extremely suitable to be implemented on GPUS. The proposed algorithms reduce up to 99.5 percent memory requirements for storing the state transition table compared to the traditional two-dimensional memory architecture. By studying existing approaches, our results obtain significant improvements in memory efficiency.

KW - Perfect hashing

KW - deterministic finite automaton

KW - string matching

UR - http://www.scopus.com/inward/record.url?scp=85028451934&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028451934&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2017.2674664

DO - 10.1109/TPDS.2017.2674664

M3 - Article

AN - SCOPUS:85028451934

VL - 28

SP - 2639

EP - 2650

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 9

M1 - 7864442

ER -