Krusche, Peter and Tiskin, Alexander (2007) Efficient parallel string comparison. In: Bischof, C. and Bücker, M. and Gibbon, P. and Joubert, G. R. and Lippert, T. and Mohr, B. and Peters, F., (eds.) Parallel Computing: Architectures, Algorithms and Applications. NIC Series, Volume 38 . Julich: John von Neumann-Institut für Computing. ISBN 9783981084344

PDF krusche.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (347Kb)

Request Changes to record.

Abstract

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.

Item Type:	Book Item
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Series Name:	NIC Series
Publisher:	John von Neumann-Institut für Computing
Place of Publication:	Julich
ISBN:	9783981084344
Book Title:	Parallel Computing: Architectures, Algorithms and Applications
Editor:	Bischof, C. and Bücker, M. and Gibbon, P. and Joubert, G. R. and Lippert, T. and Mohr, B. and Peters, F.
Official Date:	December 2007
Dates:	Date Event December 2007 Published
Volume:	Volume 38
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item