有什么好的论文讨论如何采用动态程序并将其并行化吗？
我们最近发表了一篇论文，展示了如何通过本文中的共享无锁哈希表在共享内存多核计算机上并行化任何动态编程算法：
本质上，您启动多个线程，所有线程都从 d.p 的值开始运行相同的代码。你想要计算，自上而下（递归地）计算它，并在共享的无锁哈希表中记忆，但随机化子问题的计算顺序，以便线程在计算子问题时发散。
在实现方面，我们只是在UNIX类型的系统上使用了C和pthreads，你所需要的只是能够拥有共享内存，以及CompareAndSwap（CAS）来实现线程之间的无锁同步。
由于本文发表在爱思唯尔期刊上，因此您需要通过大学图书馆或类似图书馆订阅来访问上述内容。不过，您也许可以通过 Stuckey 教授的网页获得预印本。
IIRC，通常使用动态规划所做的就是将问题递归地划分为子问题，并从最佳子解决方案中组装最佳解决方案。它之所以有效，是因为所有最优子解都内置在缓存中，因此不需要重新计算。
如果问题可以分为多种方式，您可以为每个子解决方案分叉求解器。如果每个（子）问题平均有 1+epsilon（有趣的是，epsilon 大于零）可能的子解决方案，那么您将通过这种方式获得大量并行性。您可能需要锁定缓存条目，以防止单个解决方案被多次构造。
您需要一种语言，在这种语言中，您可以比解决子任务的工作更便宜地分叉子任务，并且很高兴能够同时处理大量分叉任务。大多数语言中典型的并行产品在这方面做得很糟糕。在使用“大堆栈模型”的系统中不能有大量的分叉任务（请参阅无堆栈语言如何工作？）。
我们实现了并行编程语言 PARLANSE，以获得具有正确属性的语言。
已经有一些与在 GPU 上实现动态规划算法相关的工作。例如：