A Parallel Framework for Horizontally Local Dynamic Programming Problems

The technique of Dynamic Programming (DP) is used to solve a wide variety of combinatorial search and optimization problems. For a subset of these problems, each update to a cell in the DP table is a function of the contents of the previously computed cells belonging to the immediately previous row. We call these problems Horizontally Local Dynamic Programming (HLDP) problems. In this paper, we develop a parallel GPU based framework for solving HLDP problems. We categorize them depending upon the distribution and position of dependencies. We propose suitable techniques for each of these categories. Finally, we consider several case study problems to show how our framework can be used.