Krusche, Peter and Tiskin, Alexander (2008) Efficient Parallel String Comparison. In: International Parallel Computing Conference 2007, RWTH Aachen Univ, Aachen, France, Sep 04-07, 2007. Published in: Advances in Parallel Computing, Vol.15 pp. 193-200.

Full text not available from this repository.

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:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science Faculty of Science > Centre for Systems Biology
Series Name:	Advances in Parallel Computing
Journal or Publication Title:	Advances in Parallel Computing
Publisher:	I O S PRESS
ISBN:	978-1-58603-796-3
ISSN:	0927-5452
Editor:	Bischof, C and Bucker, C and Gibbon, P and Joubert, G and Lippert, T and Mohr, B and Peters, F
Date:	2008
Volume:	Vol.15
Number of Pages:	8
Page Range:	pp. 193-200
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Title of Event:	International Parallel Computing Conference 2007
Type of Event:	Conference
Location of Event:	RWTH Aachen Univ, Aachen, France
Date(s) of Event:	Sep 04-07, 2007
Related URLs:	Publisher
URI:	http://wrap.warwick.ac.uk/id/eprint/16604

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item