|
Title
|
|
|
|
Performance analysis of work stealing strategies in large scale multi-threaded 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 paper 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. Using numerical experiments we compare the performance of various simple stealing strategies as well as optimized strategies. |
|
|
|
Language
|
|
|
|
English
|
|
|
Source (journal)
|
|
|
|
Lecture notes in computer science. - Berlin, 1973, currens
|
|
|
Source (book)
|
|
|
|
Quantitative Evaluation of Systems : 18th International Conference, QEST 2021, Paris, France, August 23–27, 2021, Proceedings / Abate, A. [edit.]; Marin A. [edit.]
|
|
|
Source (series)
|
|
|
|
Theoretical Computer Science and General Issues (LNTCS) ; 12846
|
|
|
Publication
|
|
|
|
Berlin
:
Springer International Publishing
,
2021
|
|
|
ISSN
|
|
|
|
1611-3349
0302-9743
|
|
|
ISBN
|
|
|
|
978-3-030-85171-2
978-3-030-85172-9
|
|
|
DOI
|
|
|
|
10.1007/978-3-030-85172-9_18
|
|
|
Volume/pages
|
|
|
|
12846
, p. 329-348
|
|
|
ISI
|
|
|
|
000696682500018
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
|
Full text (open access)
|
|
|
|
|
|