The Library
Efficient parallel string comparison
Tools
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) |
Official URL: http://www.fz-juelich.de/nic-series/volume38/volum...
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, Engineering and Medicine > 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: |
|
||||
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 |