并行动态规划

Question

有没有什么好的论文讨论如何采用动态程序并将其并行化？

Answer 1

我们最近发表了一篇论文,展示了如何通过共享无锁哈希表在共享内存多核计算机上并行化任何dp:

Stivala,A.和Stuckey,PJ和Garcia de la Banda,M.和Hermenegildo,M.和Wirth,A.2010"无锁并行动态编程"J. Parallel Distrib.COMPUT.70:839-848 doi:10.1016/j.jpdc.2010.01.004

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

本质上,您启动多个线程,所有线程都从您要计算的dp值开始运行相同的代码,自上而下(递归)计算,并在共享无锁哈希表中进行记忆,但随机化顺序计算子问题,以便线程在他们计算的子问题中发散.

在实现方面,我们只在UNIX类型系统上使用C和pthreads,您只需要能够拥有共享内存,并使用CompareAndSwap(CAS)来实现线程之间的无锁同步.

由于本文发表在Elsevier期刊上,您需要通过大学图书馆或类似的方式访问上述文章并订阅.您可以通过Stuckey教授的网页获得预打印副本.

Answer 2

IIRC,你通常用动态编程做的是递归地将问题划分为子问题,并从最优的子解决方案中组合最优解.使其有效的是所有最佳子解码都内置在缓存中,因此无需重新计算.

如果问题可以分为几种方式,则可以为每个子解析分叉求解器.如果每个(子)问题平均1 + epsilon(对于有趣的ε大于零)可能的子解决方案,那么你将以这种方式得到很多并行性.您可能需要锁定缓存条目以保护单个解决方案不会被构造多次.

你需要一种语言,你可以比解决它们的工作更便宜地分叉子任务,并且很高兴同时拥有大量的分叉任务.大多数语言中典型的并行产品都很糟糕; 在使用"大堆栈模型"的系统中,你不能有很多分叉的任务(请参阅无堆栈语言如何工作？).

我们实现了并行编程语言PARLANSE,以获得具有正确属性的语言.