Efficient Synchronization-Light Work Stealing

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

1 Citation (Scopus)

Abstract

Work Stealing (Ws) is a provably efficient scheduler of parallel computations. In WS each processor owns a deque that it uses as a call stack; when out of work, processors try to steal tasks from other processors' deques. Unfortunately, the concurrent nature of processors' deques entails expensive synchronization even when processors access their own deques. Recently, Rito and Paulino have found that the use of split deques allows to provably avoid most synchronization costs while keeping WS's asymptotically optimal expected runtime; in Low-Cost Work Stealing (LCWS) - the variant of WS introduced in their work - processors need not synchronization for most local accesses to their (split) deques. In this paper we assess the concrete efficiency gains of LCWS in practice. More concretely, we implemented LCWS in the Parlay library and show how it compares against Parlay's original work stealing algorithm on the execution of the benchmarks from the Problem-Based Benchmark Suite (PBBS). Experimental results show that our signal-based LCWS implementation obtains speedups with regard to WS for at least 65% of PBBS' benchmarks in three different computers.

Original languageEnglish
Title of host publicationSPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherACM - Association for Computing Machinery
Pages39-49
Number of pages11
ISBN (Electronic)9781450395458
DOIs
Publication statusPublished - 17 Jun 2023
Event35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023 - Orlando, United States
Duration: 17 Jun 202319 Jun 2023

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023
Country/TerritoryUnited States
CityOrlando
Period17/06/2319/06/23

Keywords

  • load balancing
  • runtime systems
  • scheduling
  • synchronization-light
  • work stealing

Fingerprint

Dive into the research topics of 'Efficient Synchronization-Light Work Stealing'. Together they form a unique fingerprint.

Cite this