A Parallel BMH String Matching Algorithm Based on OpenMP
| Autor: | Xiao Qi, Yanning Du, Yuancheng Li, Dangdang Niu, Bin Liu, Yuxiang Li |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
020203 distributed computing
Speedup Computer science Boyer–Moore–Horspool algorithm 0206 medical engineering Parallel algorithm 02 engineering and technology String searching algorithm Parallel computing 0202 electrical engineering electronic engineering information engineering Segmentation 020602 bioinformatics Sequential algorithm Blossom algorithm |
| Zdroj: | HPCC/SmartCity/DSS |
| DOI: | 10.1109/hpcc/smartcity/dss.2019.00026 |
| Popis: | BMH(Boyer-Moore-Horspool) string matching algorithms have played an important role in the field of biological sequence alignment, text processing, spell checking, and computer virus signature matching. However, with the explosive growth of the data, the serial string matching algorithm is too slow to finish the matching task within an acceptable time. This paper proposed a parallel BMH string matching algorithm based on OpenMP. The parallelism of the BMH algorithm is first identified by theoretical analysis. Then, the sequential algorithm is designed as a parallel algorithm in a data-parallel form and the larger string matching task is divided into multiple sub-string matching tasks by partitioning strategy. Furthermore, using the thread-level parallel technique, each thread carries out string matching operations on different sub-string blocks in parallel. Compared with the serial BMH algorithm, the parallel BMH matching algorithm with 8 threads can achieve up to 3.53 times speedup. On the OpenMP platform, experimental results show that the proposed parallel algorithm can acquire a significant increase in speedup. Under the accuracy of ensuring the string matching, the optimal number of threads and the most optimal block segmentation scheme are obtained through experimental tests. It indicates that the OpenMP-based parallel BMH algorithm has excellent acceleration performance, and an advantageous application prospect in various field. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|