Parallel Dynamic Programming

Question

Are there any good papers discussing how to take a dynamic program and parallelize it?

Sachsen

I did a paper on this in College, and I found a ton of books in the library, but almost no papers. – Natala

And where do we find your paper? – Tristram

@Windfinder: here's your chance.... – Farnesol

Answer 1

IIRC, what you typically do with dynamic programming is to recursively divide a problem into subproblems, and assemble optimal solutions from optimal subsolutions. What makes it effective is that all optimal subsolutions are built into a cache so they need not be recomputed.

If the problem can be divided several ways, you can fork the solver for each subsolution. If each(sub) problem averages 1+epsilon (for epsilon interestingly more than zero) possible subsolutions, then you'll get a lot of parallelism this way. You'll probably need locks on the cache entries to protect the individual solutions from being constructed more than once.

You need a language in which you can fork subtasks more cheaply than the work to solve them, and which is happy to have lots of forked tasks at once. The typical parallel offerings in most languages do this badly; you can't have lots of forked tasks in systems that use "the big stack model" (see How does a stackless language work?).

We implemented our parallel programming langauge, PARLANSE, to get a language that had the right properties.

Farnesol

Answer 2

We recently published a paper showing how to parallelize any dynamic programming on a shared memory multicore computer by means of a shared lock-free hash table in this paper:

Stivala, A. and Stuckey, P. J. and Garcia de la Banda, M. and Hermenegildo, M. and Wirth, A. 2010 "Lock-free parallel dynamic programming" J. Parallel Distrib. Comput. 70:839-848 doi:10.1016/j.jpdc.2010.01.004

Essentially, you start multiple threads, all running the same code starting at the value of the dynamic programming you want to compute, computing it top-down (recursively), and memoizing in a shared lock-free hash table, but randomizing the order in which subproblems are computed so that the threads diverge in which subproblems they compute.

In terms of implementation, we just used C and pthreads on UNIX-type systems, all you need is to be able to have shared memory, and CompareAndSwap (CAS) for lock-free synchronization between threads.

Because this paper was published in an Elsevier journal, you'll need to access the above through a University library or similar with a subscription to it. You might be able to get a pre-print copy via Prof. Stuckey's webpage though.

Fontanez

If the hash table storing answers is large, the contention rate for any hash table element is probably close to zero. It isn't clear to me that the "lock free" version would be faster than a straightforward well-implemented lock since every attempt to lock will statistically succeed on the first try. (CAS may be used for lock-free but still locks the access to a cache line during the CAS execution, as would any synchronizing primitive) – Farnesol

Answer 3

There have been some works related to implementing dynamic programming algorithms on GPUs. For e.g.:

Dynamic Programming with CUDA
GPU optimized dynamic programming
A GPU Implementation of Dynamic Programming for the Optimal Polygon Triangulation

Ellita