The Library
The natural workstealing algorithm is stable
Tools
Berenbrink, Petra, Friedetzky, Thomas and Goldberg, Leslie Ann (2001) The natural workstealing algorithm is stable. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

PDF
WRAP_csrr381.pdf  Other  Requires a PDF viewer. Download (246Kb)  Preview 
Abstract
In this paper we analyse a very simple dynamic workstealing algorithm. In the workgeneration model, there are n generators which are arbitrarily distributed among a set of n processors. The distribution of generators is arbitrary  generators may even move at the beginning of each time step. During each timestep, each generator may generate a unittime task which it inserts into the queue of its host processor. It generates such a task independently with probability lambda. After the new tasks are generated, each processor removes one task from its queue and services it. Clearly, the workgeneration model allows the load to grow more and more imbalanced, so, even when lambda<1, the system load can be unbounded. The natural workstealing algorithm that we analyse is widely used in practical applications and works as follows. During each time step, each empty processor (with no work to do) sends a request to a randomly selected other processor. Any nonempty 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 nonempty processor to the empty one is determined by the socalled workstealing function f. In particular, if a processor that accepts a request has l tasks stored in its queue, then f(l) tasks are transferred to the currently empty one. A popular workstealing function is f(l)=floor(l/2), which transfers (roughly) half of the tasks. We analyse the longterm behaviour of the system as a function of lambda and f. We show that the system is stable for any constant generation rate lambda<1 and for a wide class of functions f. Most intuitively sensible functions are included in this class (for example, every function f(l) which is omega(1) as a function of l is included). 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). Our proof techniques combine Lyapunov function arguments with domination arguments, which are needed to cope with dependency.
Item Type:  Report  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science, Engineering and Medicine > Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Electronic data processing  
Series Name:  Department of Computer Science research report  
Publisher:  University of Warwick. Department of Computer Science  
Official Date:  26 April 2001  
Dates: 


Number:  Number 381  
Number of Pages:  14  
DOI:  CSRR381  
Institution:  University of Warwick  
Theses Department:  Department of Computer Science  
Status:  Not Peer Reviewed  
Publication Status:  Unpublished  
Funder:  Engineering and Physical Sciences Research Council (EPSRC), Fifth Framework Programme (European Commission) (FP5)  
Grant number:  GR/M96940 (EPSRC), IST199914186 (FP5), IST199914036 (FP5)  
Related URLs: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 