Lars Langner:

Myers Bit-Vector Algorithm on GPU for Seqan

Abstract

This work will be about the possibilty to use GPGPU methodes in Seqan (especially with NVidia CUDA) and the implementation and parallelization of Myers fast bitvector algorithm for approximate string matchings. It is stated that using massive multiprocessor programming can dramatically increases the speed and performance of algorithms, depending on the amount that could be parallized and the efficiency it is implemented. Using hundreds or thousands of parallel threads for read mapping/ localizing/matching to a genom with the fast GPU cores and Myers fast matching algorithm can give an great gain of speed for sequence analyse and string matchings. 

Academic Advisor
Knut Reinert, David Weese
Discipline
Bioinformatics
Degree
Master of Science (M.Sc.)
Date
Apr 01, 2011
Project
Status
finished

Contents

 

Several issues have to be worked out:

  • denote what preconditions are needed for using and compiling GPGPU / NVidia CUDA in Seqan
  • if and how generic programming or meta-programming can be used within the algorithm on GPU
  • generic implementation with any desired bitvector-length in an efficient manner for Seqan
  • generic implementation of Myers bitvector algorithm on CPU and GPU with different strategies (global vs. thread-local memorys)
  • extension to the banded Myers bitvector algorithm (Ukkonen Trick)
  • usage of different distance measures (Levenshtein and Damerau Edit Distances)
  • efficently distribution/scheduling of the tasks onto the GPU  processors/threads
  • testing, performance and usage analyse for the algorithm and comparing to the CPU variant

 

This will require an efficient adopting of the problem and problem-size for partitioning the parallel work most effective on GPU with different hardware settings.

 

Literature:

[1] Myers, G. (1999). A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming, Journal of the ACM, 46(3): 495-415

[2] Hyyrö, H. (2001). A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances

[3] Gröpl, C., Klau, G. and Reinert, K. (2009). Bit-parallel string matching

[4] Bailey, M., Cunningham, S. (2009). Graphics Shaders - Theory and Practice

[5] Kirk, David B., Hwu, Wen.mei W. (2010). Programming Massively Parallel Processors - A Hands-on Approach

Downloads