WAVE-FRONT LONGEST COMMON SUBSEQUENCE ALGORITHM ON MUL TIC ORE AND GPGPU PLATFORM
Loading...
Date
2010-06
Authors
ISSA SHEHABAT, BILAL MAHMOUD
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Longest common subsequence (LCS) algorithm is used as homology measurement
between two sequences. It is a very important operation used in many applications in the
different fields of science. Longest common subsequence (LCS) problem is a case of an
approximate string matching finds the longest subsequence that is common between two
different sequences. Longest common subsequence (LCS) problem takes a quadratic time
which is slow comparatively. This study aims to parallelize the LCS algorithm to
improve its execution speed. Applying the wavefront approach in order to overcome the
data dependency between cells in the dynamic programming array, and parallelize it on
the Multicore and GPGPU (General Purpose Graphical Processing Unit) for getting high
speed. The proposed algorithm was implemented on multicore using OpenMP and
CUDA platform using C programming language and was done on DNA sequences in
different sizes. The perfonnance of the parallel algorithm gave 2.43 speedup time for two
DNA sequences of size 10 KB and 58.95% for the percentage of perfonnance gain by
using the GPGPU platfonn and 1.45 speedup time and 31.10% percentage of
performance gain on 2 cores using OpenMP, knowing that the speedup and percentage of
performance gain are directly proportional with the data size.
Description
Keywords
WAVE-FRONT LONGEST COMMON SUBSEQUENCE