Improving matrix-based dynamic programming on massively parallel accelerators |
| |
Affiliation: | 1. Software Technology for Embedded Systems, Department of Computer Science, TU Chemnitz, Strasse der Nationen 62, 09111 Chemnitz, Germany;2. Department of Distributed and Dependable Systems, Faculty of Mathematics and Physics, Charles University in Prague, Malostranske namesti 25 Praha 1, Czech Republic;3. Computer Engineering, Department of Computer Science, TU Chemnitz, Strasse der Nationen 62, 09111 Chemnitz, Germany |
| |
Abstract: | Dynamic programming techniques are well-established and employed by various practical algorithms, including the edit-distance algorithm or the dynamic time warping algorithm. These algorithms usually operate in an iteration-based manner where new values are computed from values of the previous iteration. The data dependencies enforce synchronization which limits possibilities for internal parallel processing. In this paper, we investigate parallel approaches to processing matrix-based dynamic programming algorithms on modern multicore CPUs, Intel Xeon Phi accelerators, and general purpose GPUs. We address both the problem of computing a single distance on large inputs and the problem of computing a number of distances of smaller inputs simultaneously (e.g., when a similarity query is being resolved). Our proposed solutions yielded significant improvements in performance and achieved speedup of two orders of magnitude when compared to the serial baseline. |
| |
Keywords: | Parallel Multicore GPU Intel Xeon Phi Dynamic programming Edit distance Dynamic time warping |
本文献已被 ScienceDirect 等数据库收录! |
|