Perfect Hashing Based Parallel Algorithms for Multiple String Matching on Graphic Processing Units
| Autor: | Shih-Chieh Chang, Cheng-Hung Lin, Jin-Cheng Li, Chen-Hsiung Liu |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computer science
String (computer science) Parallel algorithm Uniform memory access Commentz-Walter algorithm 02 engineering and technology String searching algorithm Parallel computing Approximate string matching Memory map 020202 computer hardware & architecture Memory management Computational Theory and Mathematics Hardware and Architecture Signal Processing Memory architecture 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm design Pattern matching Perfect hash function |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 28:2639-2650 |
| ISSN: | 1045-9219 |
| DOI: | 10.1109/tpds.2017.2674664 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|