DocumentCode
3705143
Title
A GPU based implementation of Needleman-Wunsch algorithm using skewing transformation
Author
Anuj Chaudhary;Deepkumar Kagathara;Vibha Patel
Author_Institution
Department of CSE, Institute of Technology, Nirma University, Ahmedabad, India 382481
fYear
2015
Firstpage
498
Lastpage
502
Abstract
We present a new parallel approach of Needleman-Wunsch algorithm for global sequence alignment. This approach uses skewing transformation for traversal and calculation of the dynamic programming matrix. We compare the execution time of sequential CPU based implementation with two parallel GPU based implementations: Single-kernel invocation with lock-free block synchronization and multi-kernel invocation at block-synchronization points. Both the GPU based implementations gave upto 6 times performance improvement over the sequential CPU based implementation.
Keywords
"Graphics processing units","Synchronization","Heuristic algorithms","Dynamic programming","Kernel","Proteins","Central Processing Unit"
Publisher
ieee
Conference_Titel
Contemporary Computing (IC3), 2015 Eighth International Conference on
Print_ISBN
978-1-4673-7947-2
Type
conf
DOI
10.1109/IC3.2015.7346733
Filename
7346733
Link To Document