conference paper · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · 2012

Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA

Yu Liu, Longjiang Guo, Jinbao Li, Meirui Ren, Keqin Li

Cited by 20Abstract and details only

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.

Cite this paper

APA 7

Liu, Y., Guo, L., Li, J., Ren, M., & Li, K. (2012). Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, 15, 2414–2422. https://doi.org/10.1109/ipdpsw.2012.298

MLA 9

Liu, Yu, et al. “Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA.” IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, vol. 15, 2012, pp. 2414–22, https://doi.org/10.1109/ipdpsw.2012.298.

Chicago

Liu, Yu, Longjiang Guo, Jinbao Li, Meirui Ren, and Keqin Li. 2012. “Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA.” IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum 15: 2414–22. https://doi.org/10.1109/ipdpsw.2012.298.

Harvard

Liu, Y. et al. (2012) ‘Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA’, IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, 15, pp. 2414–2422. Available at: https://doi.org/10.1109/ipdpsw.2012.298.

BibTeX

@article{liu2012parallel,
  title = {{Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA}},
  author = {Liu, Yu and Guo, Longjiang and Li, Jinbao and Ren, Meirui and Li, Keqin},
  journal = {IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum},
  volume = {15},
  pages = {2414--2422},
  year = {2012},
  doi = {10.1109/ipdpsw.2012.298}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.