skip to main content
10.1145/2578948.2560690acmconferencesArticle/Chapter ViewAbstractPublication PagesppoppConference Proceedingsconference-collections
tutorial

Fast Longest Common Subsequence with General Integer Scoring Support on GPUs

Published: 07 February 2014 Publication History

Abstract

Graphic Processing Units (GPUs) have been gaining popularity among high-performance users. Certain classes of algorithms benefit greatly from the massive parallelism of GPUs. One such class of algorithms is longest common subsequence (LCS). Combined with bit parallelism, recent studies have been able to achieve terascale performance for LCS on GPUs. However, the reported results for the one-to-many matching problem lack correlation with weighted scoring algorithms. In this paper, we describe a novel technique to improve the score significance of the length of LCS algorithm for multiple matching. We extend the bit-vector algorithms for LCS to include integer scoring and parallelize them for hybrid CPU-GPU platforms. We benchmark our algorithm against the well-known sequence alignment algorithm on GPUs, CUDASW++, for accuracy and report performance on three different systems.

References

[1]
CUDA Dynamic Parallelism Programming Guide. Retrieved October 20, 2013 from http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf.
[2]
L. Allison and T. I. Dix. A bit-string longest-common-subsequence algorithm. Inf. Process. Lett., 23(6):305--310, Dec. 1986.
[3]
M. J. Atallah and S. Fox, editors. Algorithms and Theory of Computation Handbook. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 1998.
[4]
G. Benson, Y. Hernandez, and J. Loving. A bit-parallel, general integer-scoring sequence alignment algorithm. In Combinatorial Pattern Matching, volume 7922 of Lecture Notes in Computer Science, pages 50--61. Springer Berlin Heidelberg, 2013.
[5]
L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. In String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on, pages 39--48, 2000.
[6]
M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon, and J. F. Reid. A fast and practical bit-vector algorithm for the longest common subsequence problem. Information Processing Letters, 80:279--285, 2000.
[7]
M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994.
[8]
E. Edmiston, N. Core, J. Saltz, and R. Smith. Parallel processing of biological sequence comparison algorithms. International Journal of Parallel Programming, 17(3):259--275, 1988.
[9]
A. Guo and H. Siegelmann. Time-Warped Longest Common Subsequence Algorithm for Music Retrieval. pages 258--261. Universitat Pompeu Fabra, Oct. 2004.
[10]
D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
[11]
D. Hains, Z. Cashero, M. Ottenberg, W. Bohm, and S. Rajopadhye. Improving CUDASW++, a Parallelization of Smith-Waterman for CUDA Enabled Devices. In Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, IPDPSW '11, 2011.
[12]
T. S. Han, S.-K. Ko, and J. Kang. Efficient subsequence matching using the longest common subsequence with a dual match index. In Proceedings of the 5th international conference on Machine Learning and Data Mining in Pattern Recognition, MLDM '07, pages 585--600, Berlin, Heidelberg, 2007. Springer-Verlag.
[13]
D. S. Hirschberg. An information-theoretic lower bound for the longest common subsequence problem. Inf. Process. Lett., 7(1):40--41.
[14]
D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Commun. ACM, 18(6):341--343, June 1975.
[15]
D. S. Hirschberg. Algorithms for the longest common subsequence problem. J. ACM, 24(4):664--675, Oct. 1977.
[16]
H. Hyyro. A bit-vector algorithm for computing levenshtein and damerau edit distances. Nordic Journal of Computing, page 2003, 2003.
[17]
H. Hyyro. Bit-parallel lcs-length computation revisited. In In Proc. 15th Australasian Workshop on Combinatorial Algorithms (AWOCA, pages 16--27, 2004.
[18]
Y. S. Jiaoyun Yang, Yun Xu. An Efficient Parallel Algorithm for Longest Common Subsequence Problem on GPUs. Proceedings of the World Congress on Engineering, 1, 2010.
[19]
N. C. Jones and P. A. Pevzner. An Introduction to Bioinformatics Algorithms (Computational Molecular Biology). The MIT Press, Aug. 2004.
[20]
K. Kawanami and N. Fujimoto. Gpu accelerated computation of the longest common subsequence. In Facing the Multicore - Challenge II, volume 7174 of LNCS, pages 84--95. Springer Berlin, 2012.
[21]
A. Khajeh-Saeed, S. Poole, and J. B. Perot. Acceleration of the Smith-Waterman algorithm using single and multiple graphics processors. Journal of Computational Physics, 229(11):4247--4258, 2010.
[22]
J. Kloetzli, B. Strege, J. Decker, and M. Olano. Parallel longest common subsequence using graphics hardware. In Proceedings of Eurographics conference on Parallel Graphics and Visualization, 2008.
[23]
V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8):707--710, 1966.
[24]
Y. Liu, D. Maskell, and B. Schmidt. CUDASW++: Optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC research notes, 2(1), 2009.
[25]
Y. Liu, B. Schmidt, and D. L. Maskell. CUDASW++2.0: Enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC research notes, 3(1), 2010.
[26]
S.-y. Lu and K.-S. Fu. A sentence-to-sentence clustering procedure for pattern analysis. Systems, Man and Cybernetics, IEEE Transactions on, 8(5):381--389, 1978.
[27]
S. A. Manavski and G. Valle. CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics, 9, 2008.
[28]
E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1:251--266, 1986.
[29]
G. Myers. A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM, 46:1--13, 1999.
[30]
S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443--453, 1970.
[31]
NVIDIA. CUDA C Programming Guide, 2013.
[32]
A. Ozsoy, A. Chauhan, and M. Swany. Achieving TeraCUPS on Longest Common Subsequence Problem using GPGPUs. The 19th IEEE International Conference on Parallel and Distributed Systems (ICPADS'13), 2013.
[33]
T. K. Sellis. Multiple-query optimization. ACM Trans. Database Syst., 13(1):23--52, Mar. 1988.
[34]
T. Smith and M. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195--197, 1981.
[35]
X. Tian, Y. Song, X. Wang, and X. Gong. Shortest path based potential common friend recommendation in social networks. In Cloud and Green Computing (CGC), 2012 Second International Conference on, pages 541--548, 2012.
[36]
G. Von Laszewski, G. C. Fox, A. J. Younge, A. Kulshrestha, G. G. Pike, W. Smith, J. Vockler, R. J. Figueiredo, J. Fortes, and K. Keahey. Design of the futuregrid experiment management framework. In 2010 Gateway Computing Environments Workshop GCE, pages 1--10, 2010.
[37]
R. A. Wagner and M. J. Fischer. The string-to-string correction problem. J. ACM, 21(1):168--173, Jan. 1974.
[38]
S. Wu, U. Manber, G. Myers, and W. Miller. An O(NP) sequence comparison algorithm. Information Processing Letters, 35(6):317--323, 1990.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PMAM'14: Proceedings of Programming Models and Applications on Multicores and Manycores
February 2014
156 pages
ISBN:9781450326575
DOI:10.1145/2578948
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 February 2014

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Bit parallel
  2. CUDA
  3. GPU
  4. Longest common subsequence

Qualifiers

  • Tutorial
  • Research
  • Refereed limited

Conference

PPoPP '14
Sponsor:

Acceptance Rates

Overall Acceptance Rate 53 of 97 submissions, 55%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 04 Nov 2024

Other Metrics

Citations

Cited By

View all

View Options

Get Access

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media