DocumentCode :
1954794
Title :
An algorithm for fast edit distance computation on GPUs
Author :
Farivar, R. ; Kharbanda, H. ; Venkataraman, Shivaram ; Campbell, Roy H.
Author_Institution :
Univ. of Illinois at Urbana-Champaign, Champaign, IL, USA
fYear :
2012
fDate :
13-14 May 2012
Firstpage :
1
Lastpage :
9
Abstract :
The problem of finding the edit distance between two sequences (and its closely related problem of longest common subsequence) are important problems with applications in many domains like virus scanners, security kernels, natural language translation and genome sequence alignment. The traditional dynamic-programming based algorithm is hard to parallelize on SIMD processors as the algorithm is memory intensive and has many divergent control paths. In this paper we introduce a new algorithm which modifies the dynamic programming method to reduce its amount of data storage and eliminate control flow divergences. Our algorithm divides the problem into independent `quadrants´ and makes efficient use of shared memory and registers available in GPUs to store data between different phases of the algorithm. Further, we eliminate any control flow divergences by embedding condition variables in the program logic to ensure all the threads execute the same instructions even though they work on different data items. We present an implementation of this algorithm on an NVIDIA GeForce GTX 275 GPU and compare against an optimized multi-threaded implementation on an Intel Core i7-920 quad core CPU with hyper-threading support. Our results show that our GPU implementation is up to 8x faster when operating on a large number of sequences.
Keywords :
dynamic programming; graphics processing units; multi-threading; shared memory systems; storage management; Intel Core i7-920 quad core CPU; NVIDIA GeForce GTX 275 GPU; SIMD processors; condition variables embedding; control flow divergence elimination; data storage; divergent control paths; dynamic-programming based algorithm; fast edit distance computation algorithm; hyperthreading support; longest common subsequence problem; multithreaded implementation; program logic; shared memory; Algorithm design and analysis; Graphics processing unit; Heuristic algorithms; Instruction sets; Memory management; Registers;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Innovative Parallel Computing (InPar), 2012
Conference_Location :
San Jose, CA
Print_ISBN :
978-1-4673-2632-2
Electronic_ISBN :
978-1-4673-2631-5
Type :
conf
DOI :
10.1109/InPar.2012.6339593
Filename :
6339593
Link To Document :
بازگشت