Efficient parallel string comparison
Peter Krusche, Alexander Tiskin · Warwick Research Archive Portal (University of Warwick) · 2007
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.