Paper Info
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.
Year
DOI
Venue
2006
10.1007/11751649_18
ICCSA (5)
Keywords
Field
DocType
parallel algorithm,different parallel architecture,performance result,bsp model,variable grid size,appropriate optimized bsp library,efficient longest common subsequence,grid size parameter,different bsp programming library,bsp context,bulk-synchronous parallelism,computational complexity,longest common subsequence,bulk synchronous parallel
Dynamic programming,Longest common subsequence problem,Computer science,Parallel algorithm,Parallel computing,Algorithm,String (computer science),Grid,Computation,Computational complexity theory,Scalability
Conference
Volume
ISSN
ISBN
3984
0302-9743
3-540-34079-3
Citations 
PageRank 
References 
6
0.44
12
Authors
2
Name
Order
Citations
PageRank
Peter Krusche1252.83
Alexander Tiskin222015.50