WAVE-FRONT LONGEST COMMON SUBSEQUENCE ALGORITHM ON MUL TIC ORE AND GPGPU PLATFORM
| dc.contributor.author | ISSA SHEHABAT, BILAL MAHMOUD | |
| dc.date.accessioned | 2016-01-14T06:11:25Z | |
| dc.date.available | 2016-01-14T06:11:25Z | |
| dc.date.issued | 2010-06 | |
| dc.description.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. | en_US |
| dc.identifier.uri | http://hdl.handle.net/123456789/1567 | |
| dc.subject | WAVE-FRONT LONGEST COMMON SUBSEQUENCE | en_US |
| dc.title | WAVE-FRONT LONGEST COMMON SUBSEQUENCE ALGORITHM ON MUL TIC ORE AND GPGPU PLATFORM | en_US |
| dc.type | Thesis | en_US |
Files
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: