Abstract
Dynamic programming techniques are well established and employed by various practical algorithms, for instance the edit-distance algorithm. These algorithms usually operate in iteration-based fashion where new values are computed from values of the previous iterations, thus they cannot be processed by simple data-parallel approaches.
In this paper, we investigate possibilities of employing multicore CPUs and Xeon Phi devices for efficient evaluation of a class of dynamic programming algorithms. We propose a parallel implementation of Wagner-Fischer algorithm for Levenshtein edit-distance that demonstrates utilization of task parallelism and SIMD parallelism which are native to both architectures.
The proposed solution has been subjected to empirical evaluation and its results are also presented in this work.