Standard

Communication vs Synchronisation in Parallel String Comparison. / Tiskin, Alexander.

SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2020. p. 479-489 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

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

Harvard

Tiskin, A 2020, Communication vs Synchronisation in Parallel String Comparison. in SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, pp. 479-489, 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020, Virtual, Online, United States, 15/07/20. https://doi.org/10.1145/3350755.3400225

APA

Tiskin, A. (2020). Communication vs Synchronisation in Parallel String Comparison. In SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (pp. 479-489). (Annual ACM Symposium on Parallelism in Algorithms and Architectures). Association for Computing Machinery. https://doi.org/10.1145/3350755.3400225

Vancouver

Tiskin A. Communication vs Synchronisation in Parallel String Comparison. In SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery. 2020. p. 479-489. (Annual ACM Symposium on Parallelism in Algorithms and Architectures). https://doi.org/10.1145/3350755.3400225

Author

Tiskin, Alexander. / Communication vs Synchronisation in Parallel String Comparison. SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2020. pp. 479-489 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

BibTeX

@inproceedings{bfd82c349d854fc197620545600902ee,
title = "Communication vs Synchronisation in Parallel String Comparison",
abstract = "The longest common subsequence (LCS) problem is fundamental in computer science and its many applications. Parallel algorithms for this problems have been studied previously, in particular in the bulk-synchronous parallelism (BSP) model, which treats local computation, communication and synchronisation as independent scarce resources of a computing system. We consider primarily BSP algorithms running in either constant or polylogarithmic synchronisation. Based on our previous results on the algebraic structure and efficient algorithms for semi-local LCS, we present BSP algorithms for parallel semi-local LCS, improving on the existing upper bounds on communication and synchronisation; in particular we present the first constant-sync work-optimal LCS algorithm.",
keywords = "bulk-synchronous parallelism (BSP), longest common subsequence (LCS), string comparison",
author = "Alexander Tiskin",
note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020 ; Conference date: 15-07-2020 Through 17-07-2020",
year = "2020",
month = jul,
day = "6",
doi = "10.1145/3350755.3400225",
language = "English",
series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
pages = "479--489",
booktitle = "SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures",
address = "United States",

}

RIS

TY - GEN

T1 - Communication vs Synchronisation in Parallel String Comparison

AU - Tiskin, Alexander

N1 - Publisher Copyright: © 2020 ACM.

PY - 2020/7/6

Y1 - 2020/7/6

N2 - The longest common subsequence (LCS) problem is fundamental in computer science and its many applications. Parallel algorithms for this problems have been studied previously, in particular in the bulk-synchronous parallelism (BSP) model, which treats local computation, communication and synchronisation as independent scarce resources of a computing system. We consider primarily BSP algorithms running in either constant or polylogarithmic synchronisation. Based on our previous results on the algebraic structure and efficient algorithms for semi-local LCS, we present BSP algorithms for parallel semi-local LCS, improving on the existing upper bounds on communication and synchronisation; in particular we present the first constant-sync work-optimal LCS algorithm.

AB - The longest common subsequence (LCS) problem is fundamental in computer science and its many applications. Parallel algorithms for this problems have been studied previously, in particular in the bulk-synchronous parallelism (BSP) model, which treats local computation, communication and synchronisation as independent scarce resources of a computing system. We consider primarily BSP algorithms running in either constant or polylogarithmic synchronisation. Based on our previous results on the algebraic structure and efficient algorithms for semi-local LCS, we present BSP algorithms for parallel semi-local LCS, improving on the existing upper bounds on communication and synchronisation; in particular we present the first constant-sync work-optimal LCS algorithm.

KW - bulk-synchronous parallelism (BSP)

KW - longest common subsequence (LCS)

KW - string comparison

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

U2 - 10.1145/3350755.3400225

DO - 10.1145/3350755.3400225

M3 - Conference contribution

AN - SCOPUS:85088635416

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 479

EP - 489

BT - SPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020

Y2 - 15 July 2020 through 17 July 2020

ER -

ID: 97180643