Several classes of algorithms for combinatorial search and optimization problems employ memoization datastructures to speed up their serial convergence. However, accesses to these datastructures impose dependences t...
详细信息
ISBN:
(纸本)9781450359863
Several classes of algorithms for combinatorial search and optimization problems employ memoization datastructures to speed up their serial convergence. However, accesses to these datastructures impose dependences that obstruct program parallelization. Such programs often continue to function correctly even when queries into these datastructures return a partial view of their contents. Weakening the consistency of these datastructures 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 datastructures with weaklyconsistent semantics. MEMODYN provides 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 MEMODYN shows that it achieves efficient parallelization, providing significant improvements over competing techniques in terms of both runtime performance and solution quality.
暂无评论