On the efficiency of localized work stealing

DOI10.1016/J.IPL.2015.10.002zbMATH Open1346.68248arXiv1804.04773OpenAlexW2239865733MaRDI QIDQ894447FDOQ894447

Tao B. Schardl, Warut Suksompong, Charles E. Leiserson

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: This paper investigates a variant of the work-stealing algorithm that we call the localized work-stealing algorithm. The intuition behind this variant is that because of locality, processors can benefit from working on their own work. Consequently, when a processor is free, it makes a steal attempt to get back its own work. We call this type of steal a steal-back. We show that the expected running time of the algorithm is $T_1/P+O(T_{i}nftyP)$, and that under the "even distribution of free agents assumption", the expected running time of the algorithm is $T_1/P+O(T_{i}nftylgP)$. In addition, we obtain another running-time bound based on ratios between the sizes of serial tasks in the computation. If $M$ denotes the maximum ratio between the largest and the smallest serial tasks of a processor after removing a total of $O(P)$ serial tasks across all processors from consideration, then the expected running time of the algorithm is $T_1/P+O(T_{i}nftyM)$.

Full work available at URL: https://arxiv.org/abs/1804.04773

Recommendations

• A tighter analysis of work stealing
• The Natural Work-Stealing Algorithm is Stable
• Efficient scheduling of strict multithreaded computations
• The data locality of work stealing
• Upper bounds on number of steals in rooted trees

zbMATH Keywords

localizationwork stealingparallel algorithmsmultithreaded computation

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cites Work

• Upper bounds on number of steals in rooted trees
• Randomized parallel algorithms for backtrack search and branch-and-bound computation
• Scheduling multithreaded computations by work stealing
• The data locality of work stealing

Cited In (2)

• The data locality of work stealing
• The Natural Work-Stealing Algorithm is Stable

This page was built for publication: On the efficiency of localized work stealing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894447)