MemoDyn: ExploitingWeakly consistent data structures for dynamic parallel memoization

Prakash Prabhu, Stephen R. Beard, Sotiris Apostolakis, Ayal Zaks, David I. August

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450359863
DOIs
StatePublished - Nov 1 2018
Event27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018 - Limassol, Cyprus
Duration: Nov 1 2018Nov 4 2018

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
ISSN (Print)1089-795X

Conference

Conference27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018
CountryCyprus
CityLimassol
Period11/1/1811/4/18

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Adaptivity
  • Automatic parallelization
  • Implicit parallelism
  • Memorization
  • Programming model
  • Runtime
  • Tuning
  • Weakly consistent data structures

Fingerprint Dive into the research topics of 'MemoDyn: ExploitingWeakly consistent data structures for dynamic parallel memoization'. Together they form a unique fingerprint.

Cite this