Synchronization using remote-scope promotion

Marc S. Orr, Shuai Che, Ayse Yilmazer, Bradford M. Beckmann, Mark D. Hill, David A. Wood

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Citations (Scopus)

Abstract

Heterogeneous system architecture (HSA) and OpenCL" define scoped synchronization to facilitate low overhead communication across a subset of threads. Scoped synchronization works well for static sharing patterns, where consumer threads are known a priori. It works poorly for dynamic sharing patterns (e.g., work stealing) where programmers cannot use a faster small scope due to the rare possibility that the work is stolen by a thread in a distant slower scope. This puts programmers in a conundrum: optimize the common case by synchronizing at a faster small scope or use work stealing at a slower large scope. In this paper, we propose to extend scoped synchronization with remote-scope promotion. This allows the most frequent sharers to synchronize through a small scope. Infrequent sharers synchronize by promoting that remote small scope to a larger shared scope. Synchronization using remote-scope promotion provides performance robustness for dynamic workloads, where the benefits provided by scoped synchronization and work stealing are hard to anticipate. Compared to a naïve baseline, static scoped synchronization alone achieves a 1.07x speedup on average and dynamic work stealing alone achieves a 1.18x speedup on average. In contrast, synchronization using remote-scope promotion achieves a robust 1.25x speedup on average, across a diverse set of graph benchmarks and inputs.

Original languageEnglish
Title of host publicationASPLOS 2015 - 20th International Conference on Architectural Support for Programming Languages and Operating Systems
PublisherAssociation for Computing Machinery
Pages73-86
Number of pages14
ISBN (Electronic)9781450328357
DOIs
Publication statusPublished - 14 Mar 2015
Externally publishedYes
Event20th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2015 - Istanbul, Turkey
Duration: 14 Mar 201518 Mar 2015

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS
Volume2015-January

Conference

Conference20th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2015
Country/TerritoryTurkey
CityIstanbul
Period14/03/1518/03/15

Bibliographical note

Publisher Copyright:
Copyright 2015 ACM.

Keywords

  • Graphics processing unit (GPU)
  • Memory model
  • Scope promotion
  • Scoped synchronization
  • Work stealing

Fingerprint

Dive into the research topics of 'Synchronization using remote-scope promotion'. Together they form a unique fingerprint.

Cite this