A Tunable Coarse-Grained Parallel Algorithm for Irregular Dynamic Programming Applications

摘要

Dynamic programming is a widely applied algorithm design technique in many areas such as computational biology and scientific computing. Typical applications using this technique are compute-intensive and suffer from long runtimes on sequential architectures. Therefore, many parallel algorithms for both fine-grained and coarse-grained architectures have been introduced. However, the commonly used data partitioning scheme can not be efficiently applied to irregular dynamic programming applications, i.e. dynamic programming applications with an uneven computational load density. In this paper we present an efficient coarse-grained parallel algorithm for such kind of applications. This new algorithm can balance the load among processors using a tunable block-cyclic data partitioning scheme. We present a theoretical analysis and experimentally show that it leads to significant runtime savings for several irregular dynamic programming applications on PC clusters.