Hierarchical Parallelism of Bit-Parallel Algorithm for Approximate String Matching on GPUs
Cheng Hung Lin, Guan Hong Wang, Chun Cheng Huang · 2014
Approximate string matching has been widely used in many areas, such as web searching, and deoxyribonucleic acid sequence matching, etc. Approximate string matching allows difference between a string and a pattern caused by insertion, deletion and substitution. Because approximate string matching is a data-intensive task, accelerating approximate string matching has become crucial for processing big data. In this paper, we propose a hierarchical parallelism approach to accelerate the bit-parallel algorithm on NVIDIA GPUs. A data parallelism approach is used to accelerate the kernel of the bit-parallel algorithm while a task parallelism approach is used to overlap data transfer with kernel computation. In addition, we propose to use hashing to reduce the memory usage and achieve 98.4% of memory reduction. The experimental results show that the bit-parallel algorithm performed on GPUs achieves 7 to 11 times faster than the multithreaded CPU implementation. Compared to the state-of-the-art approaches, the proposed approach achieves 2.8 to 104.8 times improvement.