Efficient parallelization using rank convergence in dynamic programming algorithms
| Autor: | Madanlal Musuvathi, Todd Mytkowicz, Saeed Maleki |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
General Computer Science
Rank (computer programming) Parallel algorithm 0102 computer and information sciences 02 engineering and technology Parallel computing Viterbi algorithm 01 natural sciences Matrix multiplication Semiring Longest common subsequence problem Dynamic programming symbols.namesake Viterbi decoder 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering symbols Algorithm Mathematics |
| Zdroj: | Communications of the ACM. 59:85-92 |
| ISSN: | 1557-7317 0001-0782 |
| DOI: | 10.1145/2983553 |
| Popis: | This paper proposes an efficient parallel algorithm for an important class of dynamic programming problems that includes Viterbi, Needleman--Wunsch, Smith--Waterman, and Longest Common Subsequence. In dynamic programming, the subproblems that do not depend on each other, and thus can be computed in parallel, form stages, or wavefronts. The algorithm presented in this paper provides additional parallelism allowing multiple stages to be computed in parallel despite dependences among them. The correctness and the performance of the algorithm relies on rank convergence properties of matrix multiplication in the tropical semiring, formed with plus as the multiplicative operation and max as the additive operation. This paper demonstrates the efficiency of the parallel algorithm by showing significant speedups on a variety of important dynamic programming problems. In particular, the parallel Viterbi decoder is up to 24× faster (with 64 processors) than a highly optimized commercial baseline. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|