Concurrent dynamic programming

Question

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

Answer 1

IIRC, what you usually do with dynamic programming is to recursively divide the problem into sub-tasks and compile optimal solutions from optimal sub-revolutions. Efficiency lies in the fact that all the optimal adjustments are built into the cache, so they do not need to be re-arranged.

If the problem can be divided in several ways, you can break the solver for each sub-revolution. If each (auxiliary) problem averages 1 + epsilon (for epsilon it is more interesting than zero) of the possible subsets, then you will get a lot of parallelism in this way. You will probably need to block cache entries to protect individual solutions from being created more than once.

You need a language in which you can fork subtasks cheaper than working to solve them, and which is happy to have many forked tasks at once. Typical parallel sentences in most languages ​​do this poorly; you cannot have many forked tasks in systems that use the "large stack model" (see How does the levelless language work? ).

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

Answer 2

We recently published a document showing how to parallelize any dp on a multi-core shared-memory computer using a shared hash table without locking:

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

http://dx.doi.org/10.1016/j.jpdc.2010.01.004

In fact, you start several threads, they all run the same code, starting with the dp value you want to calculate, calculate it from top to bottom (recursively) and store it in a public hash table without blocking, but randomize the order in which subtasks are calculated so that threads diverged in what subtasks they calculate.

In terms of implementation, we just used C and pthreads for systems like UNIX, all you need is to have shared memory and CompareAndSwap (CAS) for synchronization without blocking between threads.

Since this document was published in Elsevier magazine, you need to access the above through a university library or the like with a subscription to it. You may be able to get a preliminary copy through the Prof web page. Stuckey.