UNSPECIFIED. (2003) The natural work-stealing algorithm is stable. SIAM JOURNAL ON COMPUTING, 32 (5). pp. 1260-1279. ISSN 0097-5397

Full text not available from this repository.

Abstract

In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n generators to the n processors. We consider a fixed, but arbitrary, distribution D over generator-allocation functions. During each time step of our process, a generator-allocation function h is chosen from D, and the generators are allocated to the processors according to h. Each generator may then generate a unit-time task, which it inserts into the queue of its host processor. It generates such a task independently with probability.. After the new tasks are generated, each processor removes one task from its queue and services it. For many choices of D, the work-generation model allows the load to become arbitrarily imbalanced, even when. lambda < 1. For example, D could be the point distribution containing a single function h which allocates all of the generators to just one processor. For this choice of D, the chosen processor receives around &lambda;n units of work at each step and services one. The natural work-stealing algorithm that we analyze 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 favor of one of the requests. The number of tasks which are transferred from the nonempty 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) = [l/2], which transfers (roughly) half of the tasks. We analyze the long-term behavior 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. Most intuitively sensible functions are included in this class ( for example, every monotonically nondecreasing function f which satisfies 0 less than or equal to f(l) less than or equal to l/2 and f(l) = omega(1) as a function of l is included). 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:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Journal or Publication Title:	SIAM JOURNAL ON COMPUTING
Publisher:	SIAM PUBLICATIONS
ISSN:	0097-5397
Date:	2003
Volume:	32
Number:	5
Number of Pages:	20
Page Range:	pp. 1260-1279
Identification Number:	10.1137/S0097539701399551
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/9264

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item