是否有任何好的论文讨论如何采用动态程序并将其并行化？
问问题
6105 次
3 回答
13
我们最近发表了一篇论文，展示了如何通过共享无锁哈希表在共享内存多核计算机上并行化任何 dp：
Stivala, A. 和 Stuckey, PJ 和 Garcia de la Banda, M. 和 Hermenegildo, M. 和 Wirth, A. 2010 “无锁并行动态编程”J. Parallel Distrib。计算。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 和 pthread，您所需要的只是能够拥有共享内存，以及用于线程之间无锁同步的 CompareAndSwap (CAS)。
因为这篇论文发表在 Elsevier 期刊上，你需要通过大学图书馆或类似的图书馆订阅它来访问上述内容。不过，您也许可以通过 Stuckey 教授的网页获得预印本。
于 2010-09-28T01:36:52.643 回答
6
IIRC，您通常对动态编程所做的是将问题递归地划分为子问题，并从最佳子解决方案中组装最佳解决方案。使其有效的原因是所有最佳子解决方案都内置在缓存中，因此无需重新计算。
如果问题可以分为多种方式，您可以为每个子解派生求解器。如果每个（子）问题平均有 1+epsilon（对于 epsilon 有趣地大于零）可能的子解决方案，那么您将通过这种方式获得很多并行性。您可能需要锁定缓存条目，以保护单个解决方案不被多次构建。
你需要一种语言，在这种语言中，你可以比解决它们的工作更便宜地分叉子任务，并且很高兴一次有很多分叉的任务。大多数语言中典型的并行产品在这方面做得很糟糕。在使用“大堆栈模型”的系统中，您不能有很多分叉任务（请参阅无堆栈语言如何工作？）。
我们实现了我们的并行编程语言 PARLANSE，以获得具有正确属性的语言。
于 2009-07-20T03:26:20.080 回答
0
已经有一些与在 GPU 上实现动态编程算法相关的工作。例如：
于 2020-07-22T13:20:53.943 回答