The Library
Efficient longest common subsequence computation using bulk-synchronous parallelism
Tools
Tools
Tools
UNSPECIFIED (2006) Efficient longest common subsequence computation using bulk-synchronous parallelism. In: International Conference on Computational Science and Its Applications (ICCSA 2006), MAY 08-AUG 11, 2003, Glasgow, SCOTLAND.
Full text not available from this repository.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: | Conference Item (UNSPECIFIED) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Series Name: | LECTURE NOTES IN COMPUTER SCIENCE |
| Journal or Publication Title: | COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 5 |
| Publisher: | SPRINGER-VERLAG BERLIN |
| ISBN: | 3-540-34079-3 |
| ISSN: | 0302-9743 |
| Editor: | Gavrilova, M and Gervasi, O and Kumar, V and Tan, CJK and Taniar, D and Lagana, A and Mun, Y and Choo, H |
| Date: | 2006 |
| Volume: | 3984 |
| Number of Pages: | 10 |
| Page Range: | pp. 165-174 |
| Publication Status: | Published |
| Title of Event: | International Conference on Computational Science and Its Applications (ICCSA 2006) |
| Location of Event: | Glasgow, SCOTLAND |
| Date(s) of Event: | MAY 08-AUG 11, 2003 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/33381 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
