Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA
Citations Over TimeTop 10% of 2012 papers
Abstract
Approximate string matching using the k-mismatch technique has been widely applied to many fields such as virus detection and computational biology. The traditional parallel algorithms are all based on multiple processors, which have high costs of computing and communication. GPU has high parallel processing capability, low cost of computing, and less time of communication. To the best of our knowledge, there is no any parallel algorithm for approximate string matching with k mismatches on GPU. With a new parallel programming model based on CUDA, we present three parallel algorithms and their implementations on GPU, namely, the thread parallel algorithm, the block-thread parallel algorithm, and the OPT-block-thread parallel algorithm. The OPT-block thread parallel algorithm can take full advantage of the powerful parallel capability of GPU. Furthermore, it balances the load among the threads and optimizes the execution time with the memory model of GPU. Experimental results show that compared with the traditional sequential algorithm on CPU, our best parallel algorithm on GPU in this paper achieves speedup of 40-80.
Related Papers
- → String pattern searching algorithm based on characters indices(2019)4 cited
- A fast improved pattern matching algorithm based on BM(2013)
- → Development of the Pattern Matching Engine using Regular Expression(2008)
- Two Improved Fast Single Pattern Matching Algorithms of QS(2013)
- A New Algorithm for String Single Pattern Matching(2008)