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

Preview

PDF WRAP_cs-rr-381.pdf - Other - Requires a PDF viewer. Download (246Kb) | Preview

Request Changes to record.

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. The distribution of generators is arbitrary --- generators may even move at the beginning of each time step. During each time-step, each generator may generate a unit-time 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 work-generation model allows the load to grow more and more imbalanced, so, even when lambda<1, the system load can be unbounded. The natural work-stealing 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 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. 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 work-stealing function is f(l)=floor(l/2), which transfers (roughly) half of the tasks. We analyse the long-term 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:	Date Event 26 April 2001 Completion
Number:	Number 381
Number of Pages:	14
DOI:	CS-RR-381
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), IST-1999-14186 (FP5), IST-1999-14036 (FP5)
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item