The Library
Efficient longest common subsequence computation using bulk-synchronous parallelism
Tools
Krusche, Peter and Tiskin, Alexander (2006) Efficient longest common subsequence computation using bulk-synchronous parallelism. In: Gavrilova, M. and Gervasi, O. and Kumar, V. and Tan, C. J. K. and Taniar, D. and Lagana, A. and Mun, Y. and Choo, H., (eds.) Computational Science and Its Applications - ICCSA 2006. Lecture Notes in Computer Science, Volume 3984 . Springer Berlin Heidelberg, pp. 165-174. ISBN 9783540340799
PDF
fulltext12.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (528Kb) |
Abstract
This paper presents performance results for parallel algorithms that compute the longest common subsequence of two strings. This algorithm is a representative of a class of algorithms that compute string to string distances and has computational complexity O(n(2)). The parallel algorithm uses a variable grid size, runs in O(p) supersteps (synchronization phases) and has linear communication costs. We study this algorithm in BSP context, give runtime estimations and compare the predictions to experimental values measured on three different parallel architectures, using different BSP programming libraries and an efficient implementation for sequential computation. We find that using the BSP model and the appropriate optimized BSP library improves the performance over plain MPI, and that scalability can be improved by using a tuned grid size parameter.
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: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783540340799 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Computational Science and Its Applications - ICCSA 2006 | ||||
Editor: | Gavrilova, M. and Gervasi, O. and Kumar, V. and Tan, C. J. K. and Taniar, D. and Lagana, A. and Mun, Y. and Choo, H. | ||||
Official Date: | 2006 | ||||
Dates: |
|
||||
Volume: | Volume 3984 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 165-174 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Date of first compliant deposit: | 28 July 2016 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | International Conference on Computational Science and Its Applications (ICCSA 2006) | ||||
Type of Event: | Conference | ||||
Location of Event: | Glasgow, Scotland | ||||
Date(s) of Event: | 08 May - 11 Aug 2003 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |