Improving matrix-based dynamic programming on massively parallel accelerators
作者：
Highlights：
• Dynamic programming algorithms with matrix organization (e.g., Levenshtein distance).
• Employing task parallelism and SIMD/SIMT vectorization.
• Proposed hierarchical algorithm optimized for CPUs, Intel Xeon Phi devices, and GPUs.
• Can be efficiently parallelized if inputs are large or many distances are computed.
• Experiments also determine optimal configurations for current hardware.
摘要
Highlights•Dynamic programming algorithms with matrix organization (e.g., Levenshtein distance).•Employing task parallelism and SIMD/SIMT vectorization.•Proposed hierarchical algorithm optimized for CPUs, Intel Xeon Phi devices, and GPUs.•Can be efficiently parallelized if inputs are large or many distances are computed.•Experiments also determine optimal configurations for current hardware.
论文关键词：Parallel,Multicore,GPU,Intel Xeon Phi,Dynamic programming,Edit distance,Dynamic time warping
论文评审过程：Received 1 December 2015, Revised 6 May 2016, Accepted 3 June 2016, Available online 16 June 2016, Version of Record 20 December 2016.
论文官网地址：https://doi.org/10.1016/j.is.2016.06.001
