TY - JOUR

T1 - Efficient parallel string comparison

AU - Krusche, Peter

AU - Tiskin, Alexander

PY - 2008/1/1

Y1 - 2008/1/1

N2 - The longest common subsequence (LCS) problem is a classical method of string comparison. Several coarse-grained parallel algorithms for the LCS problem have been proposed in the past. However, none of these algorithms achieve scalable communication. In this paper, we propose the first coarse-grained parallel LCS algorithm with scalable communication. Moreover, the algorithm is work-optimal, synchronisation-efficient, and solves a more general problem of semi-local string comparison, improving in at least two of these aspects on each of the predecessors. © 2008 The authors and IOS Press. All rights reserved.

AB - The longest common subsequence (LCS) problem is a classical method of string comparison. Several coarse-grained parallel algorithms for the LCS problem have been proposed in the past. However, none of these algorithms achieve scalable communication. In this paper, we propose the first coarse-grained parallel LCS algorithm with scalable communication. Moreover, the algorithm is work-optimal, synchronisation-efficient, and solves a more general problem of semi-local string comparison, improving in at least two of these aspects on each of the predecessors. © 2008 The authors and IOS Press. All rights reserved.

UR - http://www.scopus.com/inward/record.url?scp=84906502934&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84906502934

VL - 15

SP - 193

EP - 200

JO - Advances in Parallel Computing

JF - Advances in Parallel Computing

SN - 0927-5452

ER -