DocumentCode :
1710619
Title :
The natural work-stealing algorithm is stable
Author :
Berenbrink, Petra ; Friedetzky, Tom ; Goldberg, Leslie
Author_Institution :
Dept. of Comput. Sci., Warwick Univ., Coventry, UK
fYear :
2001
Firstpage :
178
Lastpage :
187
Abstract :
In this paper we analyse a very simple dynamic work-stealing algorithm. In the work-generation model, there are n generators which are arbitrarily distributed among a set of n processors. During each time-step, with probability λ, each generator generates a unit-time task which it inserts into the queue of its host processor. After the new tasks are generated, each processor removes one task from its queue and services it. Clearly, the work-generation model allows the load to grow more and more imbalanced, so, even when λ<1, the system load can be unbounded. The natural work-stealing algorithm that we analyse works as follows. During each time step, each empty processor sends a request to a randomly selected other processor. Any non-empty processor having received at least one such request in turn decides (again randomly) in favour of one of the requests. The number of tasks which are transferred from the non-empty processor to the empty one is determined by the so-called work-stealing function f. We analyse the long-term behaviour of the system as a function of λ and f. We show that the system is stable for any constant generation rate λ<1 and for a wide class of functions f. We give a quantitative description of the functions f which lead to stable systems. Furthermore, we give upper bounds on the average system load (as a function of f and n).
Keywords :
distributed algorithms; numerical stability; resource allocation; average system load; constant generation rate; dynamic work stealing algorithm; empty processor; host processor; long-term behaviour; natural work stealing algorithm stability; nonempty processor; probability; queue; unit-time task; upper bounds; work-generation model; Algorithm design and analysis; Computer science; Contracts; Distributed computing; Heuristic algorithms; Kernel; Load management; Load modeling; Parallel programming; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
Print_ISBN :
0-7695-1116-3
Type :
conf
DOI :
10.1109/SFCS.2001.959892
Filename :
959892
Link To Document :
بازگشت