On the parallelization of Hirschberg's algorithm for multi‐core and many‐core systems. (14th February 2019)

• Record Type: Journal Article
• Authors: João, Mario; Sena, Alexandre C.; Rebello, Vinod E. F.
• Other Names: Boeres Cristina guestEditor.; Bentes Cristiana guestEditor.; Moreno Edward guestEditor.; De Rose Cesar A. F. guestEditor.; Castrol Márcio guestEditor.
• Is Part Of: Concurrency and computation. Volume 31:Number 18(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-02-14
• Subjects: Hirschberg's algorithm -- longest common subsequence (LCS) problem -- many‐core processors -- multi‐core systems -- SIMD instructions; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5174
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: 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.