Parallel Computation for Extended Edit Distances Using the Shared Memory on GPU


KIPS Transactions on Computer and Communication Systems, Vol. 4, No. 7, pp. 213-218, Jul. 2015
10.3745/KTCCS.2015.4.7.213, Full Text:

Abstract

Given two strings X and Y (|X|=m, |Y|=n) over an alphabet Σ, the extended edit distance between X and Y can be computed using dynamic programming in O(mn) time and space. Recently, a parallel algorithm that takes O(m+n) time and O(mn) space using m threads to compute the extended edit distance between X and Y was presented. In this paper, we present an improved parallel algorithm using the shared memory on GPU. The experimental results show that our parallel algorithm runs about 19~25 times faster than the previous parallel algorithm.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
Y. Kim, J. C. Na and J. S. Sim, "Parallel Computation for Extended Edit Distances Using the Shared Memory on GPU," KIPS Transactions on Computer and Communication Systems, vol. 4, no. 7, pp. 213-218, 2015. DOI: 10.3745/KTCCS.2015.4.7.213.

[ACM Style]
Youngho Kim, Joong Chae Na, and Jeong Seop Sim. 2015. Parallel Computation for Extended Edit Distances Using the Shared Memory on GPU. KIPS Transactions on Computer and Communication Systems, 4, 7, (2015), 213-218. DOI: 10.3745/KTCCS.2015.4.7.213.