Efficient Parallelization Using Rank Convergence in Dynamic Programming Algorithms.
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 pa...
| Publicado en: | Communications of the ACM Vol. 59; no. 10; pp. 85 - 93 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Oct2016
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=118436924&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 118436924 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Oct2016 vid: 59 iid: 10 pid: 68 pub: Association for Computing Machinery artinfo: ui: 118436924 10.1145/2983553 ppf: 85 ppct: 8 formats: tig: atl: Efficient Parallelization Using Rank Convergence in Dynamic Programming Algorithms. aug: au: Maleki, Saeed Musuvathi, Madanlal Mytkowicz, Todd affil: Microsoft Research, Redmond, WA su: Parallel algorithms Dynamic programming Viterbi decoding Parallel computers Computer programming sug: subj: Parallel algorithms Dynamic programming Viterbi decoding Parallel computers Computer programming ab: 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. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|