@inproceedings{49bbea3b6d3c4f6587f18021242ed8a6,
title = "MemoDyn: ExploitingWeakly consistent data structures for dynamic parallel memoization",
abstract = "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. 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.",
keywords = "Adaptivity, Automatic parallelization, Implicit parallelism, Memorization, Programming model, Runtime, Tuning, Weakly consistent data structures",
author = "Prakash Prabhu and Beard, {Stephen R.} and Sotiris Apostolakis and Ayal Zaks and August, {David I.}",
note = "Publisher Copyright: {\textcopyright} 2018 Association for Computing Machinery.; 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018 ; Conference date: 01-11-2018 Through 04-11-2018",
year = "2018",
month = nov,
day = "1",
doi = "10.1145/3243176.3243193",
language = "English (US)",
series = "Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "Proceedings - 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018",
address = "United States",
}