On the efficiency of localized work stealing
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120140 https://orcid.org/0000-0001-6386-5552 https://orcid.org/0000-0003-0198-3283 |
| Summary: | 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[subscript 1]/P + O(T[subscript ∞]P), and that under the “even distribution of free agents assumption”, the expected running time of the algorithm is T[subscript 1]/P + O(T[subscript ∞]lgP) . 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[subscript 1]/ P+ O(T[subscript ∞]M). Keywords: Parallel algorithms; Multihreaded computation; Work stealing; Localization |
|---|