有没有好的论文讨论如何采取动态程序并将其并行化?
我们最近发表了一篇论文,展示了如何通过共享无锁哈希表并行化共享内存多核计算机上的任何 d.p.:
Stivala,A.and Stuckey,P.J.and Garcia de la Banda,M.and Hermenegildo,M.and Wirth,A.2010 "Lock-free parallel dynamic programming" J.Parallel Distrib.Comput.70:839-848 doi:10.1016 / j.
http://dx.doi.org/10.1016/j.jpdc.2010.01.004从本质上讲,您启动多个线程,所有这些线程都运行相同的代码,从您要计算的 d.p.的值开始,自上而下(递归)计算它,并在共享的无锁哈希表中进行记忆,但随机化子问题的计算顺序,以便线程在计算子问题时有所不同。
在实现方面,我们只是在 UNIX 类型的系统上使用了 C 和 pthreads,您所需要的只是能够拥有共享内存,以及用于线程之间无锁同步的 CompareAndSwap(CAS)。
因为这篇论文发表在爱思唯尔杂志上,你需要通过大学图书馆或类似的订阅来访问上面的内容。不过,你可能可以通过 Stuckey 教授的网页获得预打印副本。
IIRC,您通常使用动态编程将问题递归地划分为子问题,并从最优子解组装最优解。有效的是,所有最优子解都内置于缓存中,因此无需重新计算。
如果问题可以分为几种方式,您可以为每个子解分叉求解器。如果每个(子)问题平均为 1 + epsilon(有趣的是 epsilon 大于零)可能的子解,那么您将以这种方式获得很多并行性。您可能需要在缓存条目上锁定以保护单个解决方案不被多次构造。
您需要一种语言,在这种语言中,您可以比解决子任务的工作更便宜地分叉子任务,并且很高兴一次有很多分叉任务。大多数语言中典型的并行产品做得很糟糕;在使用“大堆栈模型”的系统中,您不可能有很多分叉任务(请参阅How does a stackless language work?)。
我们实现了并行编程语言 PARLANSE,以获得具有正确属性的语言。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(71条)