Paper Info
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.
Year
DOI
Venue
2020
10.1145/3350755.3400225
SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures Virtual Event USA July, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-6935-0
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Alexander Tiskin122015.50