Standard

Efficient longest common subsequence computation using bulk-synchronous parallelism. / Krusche, Peter; Tiskin, Alexander.

Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006). 2006. p. 165-174 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3984).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Krusche, P & Tiskin, A 2006, Efficient longest common subsequence computation using bulk-synchronous parallelism. in Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3984, pp. 165-174. https://doi.org/10.1007/11751649_18

APA

Krusche, P., & Tiskin, A. (2006). Efficient longest common subsequence computation using bulk-synchronous parallelism. In Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006) (pp. 165-174). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3984). https://doi.org/10.1007/11751649_18

Vancouver

Krusche P, Tiskin A. Efficient longest common subsequence computation using bulk-synchronous parallelism. In Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006). 2006. p. 165-174. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11751649_18

Author

Krusche, Peter ; Tiskin, Alexander. / Efficient longest common subsequence computation using bulk-synchronous parallelism. Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006). 2006. pp. 165-174 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1b6c23e78fa046e198fed07b4224fd07,
title = "Efficient longest common subsequence computation using bulk-synchronous parallelism",
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(n2). 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. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",
author = "Peter Krusche and Alexander Tiskin",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11751649_18",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "165--174",
booktitle = "Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006)",

}

RIS

TY - GEN

T1 - Efficient longest common subsequence computation using bulk-synchronous parallelism

AU - Krusche, Peter

AU - Tiskin, Alexander

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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(n2). 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. © Springer-Verlag Berlin Heidelberg 2006.

AB - 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(n2). 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. © Springer-Verlag Berlin Heidelberg 2006.

UR - http://www.scopus.com/inward/record.url?scp=33745940915&partnerID=8YFLogxK

U2 - 10.1007/11751649_18

DO - 10.1007/11751649_18

M3 - Conference contribution

AN - SCOPUS:33745940915

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 165

EP - 174

BT - Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006)

ER -

ID: 127757490