The Library
The natural work-stealing algorithm is stable
Tools
Tools
Tools
Berenbrink, Petra, Friedetzky, Thomas and Goldberg, Leslie Ann (2003) The natural work-stealing algorithm is stable. SIAM Journal on Computing, Volume 32 (Number 5). pp. 1260-1279. doi:10.1137/S0097539701399551 ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/S0097539701399551
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 λ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 |
||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||
| ISSN: | 0097-5397 | ||||
| Official Date: | 2003 | ||||
| Dates: |
|
||||
| Volume: | Volume 32 | ||||
| Number: | Number 5 | ||||
| Number of Pages: | 20 | ||||
| Page Range: | pp. 1260-1279 | ||||
| DOI: | 10.1137/S0097539701399551 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
