Parallel Approach for Longest Common Subsequence problem on GPU
HANA Research Group, University of Manouba, Tunisia
High Performance Computing & Simulation (HPCS) Conference, 2011
@article{issaoui2011parallel,
title={Parallel Approach for Longest Common Subsequence problem on GPU},
author={Issaoui, R. and Draief, A. and Belghith, A.},
year={2011}
}
Recent developments in genomic and molecular technologies produced a tremendous amount of information related to molecular biology. The management and analysis of these biological data require intensive computing power. Sequence aligning is one of the algorithmic tools in bioinformatics to look for resemblance among sequences of amino acids. The longest common subsequence (LCS) of biological sequences is an essential and effective technique in sequence matching. For a constant number of input sequences, the LCS problem is solvable in polynomial time by dynamic programming. However, for a large number of input sequences extensive computations are still needed. Graphics Processing Units (GPU) may well assist us here. In this paper, we are interested to ascertain the possible speed up achievable by GPUs using different parallel programming languages. Our contribution is two fold. First, we develop the parallelization of a dynamic programming to solve the LCS problem on a Nvidia GT 430 . On randomly generated sequences of different lengths, our experimental results show, in particular, that the algorithm is about 17 times faster on the used GPU than on a typical CPU. Secondly, we show that the language CUDA is better suitable than OpenCL for such an LCS problem on an Nvidia GPU.
November 16, 2011 by hgpu
