Parallel Computing the Longest Common Subsequence (LCS) on GPUs: Efficiency and Language Suitability
HANA Research Group, University of Manouba, Tunisia
The First International Conference on Advanced Communications and Computation (INFOCOMP), 2011
@inproceedings{dhraief2011parallel,
title={Parallel Computing the Longest Common Subsequence (LCS) on GPUs: Efficiency and Language Suitability},
author={Dhraief, A. and Issaoui, R. and Belghith, A.},
booktitle={INFOCOMP 2011, The First International Conference on Advanced Communications and Computation},
pages={143–148},
year={2011}
}
Sequence alignment is one of the most used tools in bioinformatic to find the resemblance among many sequences like ADN, ARN, amino acids. The longest common subsequence (LCS) of biological sequences is an essential and effective technique in sequence alignment. For solving the LCS problem, we resort to dynamic programming approach. Due to the growth of databases sizes of biological sequences, parallel algorithms are the best solution to solve these large size problems. Meantime, the GPU has become an important element for applications that can benefit from parallel computing. In this paper, we first study and compare some languages for parallel development on GPU (CUDA and OpenCL). Then, we present a parallelization approach for solving the LCS problem on GPU. Finally, we evaluate our proposed algorithm on an platform using CUDA, OpenCL and on CPU using the C Language and the OpenMP API. The experiment results show that the implementation of our algorithms in CUDA outperforms the implementation in OpenCL, and the execution time is about 17 times faster on GPUs than on typical CPUs.
October 28, 2011 by hgpu
