Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331029 | Information Processing Letters | 2016 | 7 Pages |
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 T1/P+O(TâP), and that under the “even distribution of free agents assumption”, the expected running time of the algorithm is T1/P+O(Tâlgâ¡P). 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 T1/P+O(TâM).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Warut Suksompong, Charles E. Leiserson, Tao B. Schardl,