Efficient parallel string comparison
Krusche, Peter and Tiskin, Alexander (2008) Efficient parallel string comparison. In: International Parallel Computing Conference 2007, RWTH Aachen Univ, Aachen, France, 04-07 Sep 2007. Published in: Advances in Parallel Computing, Volume 15 pp. 193-200.Full text not available from this repository.
Official URL: http://www.booksonline.iospress.nl/Content/View.as...
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 (Paper)|
|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|
|Editor:||Bischof, C and Bucker, C and Gibbon, P and Joubert, G and Lippert, T and Mohr, B and Peters, F|
|Number of Pages:||8|
|Page Range:||pp. 193-200|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Title of Event:||International Parallel Computing Conference 2007|
|Type of Event:||Conference|
|Location of Event:||RWTH Aachen Univ, Aachen, France|
|Date(s) of Event:||04-07 Sep 2007|
Actions (login required)