Efficient Synchronization-Light Work Stealing
OPEN ACCESS
Loading...
Author / Producer
Date
2023-06-17
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
Journal / series
Volume
Pages / Article No.
39 - 49
Publisher
Association for Computing Machinery
Event
35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
scheduling; load balancing; work stealing; synchronization-light; runtime systems
Organisational unit
03338 - Maurer, Ueli (emeritus) / Maurer, Ueli (emeritus)