MemoDyne: exploiting weakly consistent data structures for dynamic parallel memoization
MemoDyne: exploiting weakly consistent data structures for dynamic parallel memoization
复制标题
MemoDyne：利用弱一致性数据结构进行动态并行记忆
DOI：
10.1145/3243176.3243193
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
August, David I.
中科院分区：
文献类型：
--
作者：
Prabhu, Prakash;Beard, Stephen R.;Apostolakis, Sotiris;Zaks, Ayal;August, David I.
组合搜索和优化问题的几种算法使用记忆数据结构来加速它们的串行收敛。然而，对这些数据结构的访问带来的依赖性阻碍了程序的并行化。即使对这些数据结构的查询返回其内容的部分视图，这些程序通常也能继续正常工作。削弱这些数据结构的一致性可以释放新的并行性机会，潜在地以额外的计算为代价。因此，必须谨慎利用这些机会，以便全面加速。本文介绍了MemoDyn，一个用于访问具有弱一致语义的数据结构的并行循环的框架。memodyn提供编程抽象来表达弱语义，并由一个并行编译器和一个运行时系统组成，该系统自动地、自适应地利用语义来优化并行执行。对memodyn的评估表明，它实现了高效的并行化，在运行时性能和解决方案质量方面都比竞争技术有了显著的改进。
Several classes of algorithms for combinatorial search and optimization problems employ memoization data structures to speed up their serial convergence. However, accesses to these data structures impose dependences that obstruct program parallelization. Such programs often continue to function correctly even when queries into these data structures return a partial view of their contents. Weakening the consistency of these data structures can unleash new parallelism opportunities, potentially at the cost of additional computation. These opportunities must, therefore, be carefully exploited for overall speedup. This paper presents MemoDyn, a framework for parallelizing loops that access data structures with weakly consistent semantics. MemoDynprovides programming abstractions to express weak semantics, and consists of a parallelizing compiler and a runtime system that automatically and adaptively exploit the semantics for optimized parallel execution. Evaluation of MemoDynshows that it achieves efficient parallelization, providing significant improvements over competing techniques in terms of both runtime performance and solution quality.