并行动态规划

Question

有什么好论文讨论如何采取动态的程序和并行呢？

Answer 1

IIRC，你通常做动态规划是什么递归分割问题划分为若干子，以及最佳上下解组合优化的解决方案。是什么使得它有效的是，所有的最佳上下解中内置了一个高速缓存，使他们不必重新计算。

如果该问题可分为几种方法，可以叉每个下解的解算器。如果每个（子）问题平均1 +小量（小量为有趣的大于零）可能上下解，那么你会得到很多的并行这种方式。你可能需要在缓存项锁来保护个人的解决方案，从正在建设中不止一次。

您需要在其中您可以更便宜地派生的子任务比工作语言来解决这些问题，并且很高兴一下子有很多的分叉任务。在大多数语言中典型的并行产品做不好;你不能有很多的分叉任务系统中使用“大堆栈模型”（见的如何做一个无堆栈语言文字工作？）。

我们实现我们的并行编程的langauge，PARLANSE，得到的是有正确的性的语言。

Answer 2

我们最近发表了如何并行任何D.P.纸

：由共享无锁哈希表的手段的共享存储器多核计算机上

Stivala，A。和斯塔基，P. J.和加西亚德拉班，M。和Hermenegildo，M。和维尔特，A. 2010“无锁并行动态编程” J.并行DISTRIB。 COMPUT。 70：839-848 DOI：10.1016 / j.jpdc.2010.01.004

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

从本质上讲，在开始多个线程，所有正在运行的相同的代码开始于D.P.值要计算，计算它自顶向下（递归的），和memoizing在共享无锁哈希表，但随机化，其中子问题被计算的顺序，以使线程发散，其中子问题它们计算。

在实施方面，我们只是用C和并行线程在UNIX型系统中，所有需要的是能够具有用于线程之间无锁同步共享存储器，和比较并交换（CAS）。

由于该论文发表在Elsevier期刊，你需要通过一个大学图书馆或类似访问上面订阅了它。你也许能够获得通过斯塔基教授的网页预打印副本虽然。