Publication
Title
Performance analysis of work stealing strategies in large-scale multithreaded computing
Author
Abstract
Distributed systems use randomized work stealing to improve performance and resource utilization. In most prior analytical studies of randomized work stealing, jobs are considered to be sequential and are executed as a whole on a single server. In this article, we consider a homogeneous system of servers where parent jobs spawn child jobs that can feasibly be executed in parallel. When an idle server probes a busy server in an attempt to steal work, it may either steal a parent job or multiple child jobs. To approximate the performance of this system, we introduce a Quasi-Birth-Death Markov chain and express the performance measures of interest via its unique steady state. We perform simulation experiments that suggest that the approximation error tends to zero as the number of servers in the system becomes large. To further support this observation, we introduce a mean field model and show that its unique fixed point corresponds to the steady state of the Quasi-Birth-Death Markov chain. Using numerical experiments, we compare the performance of various simple stealing strategies as well as optimized strategies.
Language
English
Source (journal)
ACM transactions on modeling and computer simulation / Association for Computing Machinery. - New York
Publication
New York : 2023
ISSN
1049-3301
DOI
10.1145/3584186
Volume/pages
33 :4 (2023) , p. 1-23
Article Reference
15
ISI
001136788100005
Medium
E-only publicatie
Full text (Publisher's DOI)
Full text (publisher's version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identifier
Creation 01.02.2024
Last edited 25.04.2024
To cite this reference