Paper Info
Title
On the parallelization of Hirschberg's algorithm for multi-core and many-core systems.
Abstract
Finding the longest common subsequence between two strings in acceptable time frames is crucial to solving various problems in different fields of study. To ensure the optimal solution is found, algorithms based on dynamic programming are employed almost exclusively. While the most commonly adopted algorithm, proposed by Needleman and Wunsch, has quadratic time and space complexity, the linear space complexity of Hirschberg's algorithm favors the comparisons of longer sequences. However, it too has a quadratic time complexity and therefore the effective exploitation of parallelism has become essential. This paper focuses on improving the execution efficiency of Hirschberg's algorithm on multi-core and many-core systems. To achieve this goal, first, enhancements to the sequential version are proposed to take advantage of SIMD instructions available on modern processors. Second, the impact on the performance of different parallelization strategies is investigated and evaluated. Results show that combining these two aspects can greatly improve the performance of Hirschberg's algorithm on these architectures. In relation to the original version, speedups of over 46 were achieved on a dual 18-core server for sequences of 1.6 million characters. Furthermore, experiments with a 68-core Intel Xeon Phi (many-core) system obtained speedups of up to 105 for the same sequence size.
Year
DOI
Venue
2019
10.1002/cpe.5174
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
Keywords
DocType
Volume
Hirschberg's algorithm,longest common subsequence (LCS) problem,many-core processors,multi-core systems,SIMD instructions
Journal
31.0
Issue
ISSN
Citations 
SP18.0
1532-0626
1
PageRank 
References 
Authors
0.36
0
3
Name
Order
Citations
PageRank
Mario João Jr110.36
Alexandre Sena2409.45
Vinod E. F. Rebello3703.44