A GPU-based Bit-Parallel Multiple Pattern Matching Algorithm

Che Lun Hung, Tzu Hung Hsu, Hsiao Hsi Wang, Chun Yuan Lin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

String matching algorithms have played critical role in many applications, such as DNA sequence comparison, network intrusion detection systems, and so forth. In this paper, we present a parallel multiple pattern matching method based on general purpose graphic processing units to realize fast string searching. In proposed method, we adopt a bit-parallel pattern comparison concept to accelerates string search to achieve efficient parallel search of multiple patterns of different lengths. In addition, we use CUDA framework to enhance the performance of searching string by leveraging GPU computing power. From the experimental results, the proposed method can achieve higher search throughput than other string matching methods. The proposed method is useful for genome sequence comparison and packet payload filtering.

Original languageEnglish
Title of host publicationProceedings - 20th International Conference on High Performance Computing and Communications, 16th International Conference on Smart City and 4th International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1219-1222
Number of pages4
ISBN (Electronic)9781538666142
DOIs
StatePublished - 22 Jan 2019
Event20th International Conference on High Performance Computing and Communications, 16th IEEE International Conference on Smart City and 4th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2018 - Exeter, United Kingdom
Duration: 28 Jun 201830 Jun 2018

Publication series

NameProceedings - 20th International Conference on High Performance Computing and Communications, 16th International Conference on Smart City and 4th International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2018

Conference

Conference20th International Conference on High Performance Computing and Communications, 16th IEEE International Conference on Smart City and 4th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2018
Country/TerritoryUnited Kingdom
CityExeter
Period28/06/1830/06/18

Keywords

  • Bit-Parallel
  • GPU
  • Multiple Pattern
  • Parallel Computing
  • String Match

Fingerprint

Dive into the research topics of 'A GPU-based Bit-Parallel Multiple Pattern Matching Algorithm'. Together they form a unique fingerprint.

Cite this