Name
Abstract | ||
|---|---|---|
Work-stealing is a promising approach for effectively exploiting software parallelism on parallel hardware. A programmer who uses work-stealing explicitly identifies potential parallelism and the runtime then schedules work, keeping otherwise idle hardware busy while relieving overloaded hardware of its burden. Prior work has demonstrated that work-stealing is very effective in practice. However, work-stealing comes with a substantial overhead: as much as 2x to 12x slowdown over orthodox sequential code. In this paper we identify the key sources of overhead in work-stealing schedulers and present two significant refinements to their implementation. We evaluate our work-stealing designs using a range of benchmarks, four different work-stealing implementations, including the popular fork-join framework, and a range of architectures. On these benchmarks, compared to orthodox sequential Java, our fastest design has an overhead of just 15%. By contrast, fork-join has a 2.3x overhead and the previous implementation of the system we use has an overhead of 4.1x. These results and our insight into the sources of overhead for work-stealing implementations give further hope to an already promising technique for exploiting increasingly available hardware parallelism. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2384616.2384639 | OOPSLA |
Keywords | Field | DocType |
potential parallelism,parallel hardware,available hardware parallelism,work-stealing schedulers,work-stealing implementation,work-stealing design,different work-stealing implementation,idle hardware,substantial overhead,overloaded hardware,scheduling,task parallelism | Instruction-level parallelism,Programming language,Programmer,Task parallelism,Scheduling (computing),Computer science,Parallel computing,Schedule,Data parallelism,Software,Work stealing | Conference |
Volume | Issue | ISSN |
47 | 10 | 0362-1340 |
Citations | PageRank | References |
17 | 0.71 | 14 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vivek Kumar | 1 | 22 | 1.48 |
| Daniel Frampton | 2 | 261 | 12.73 |
| Stephen M. Blackburn | 3 | 1067 | 64.22 |
| David Grove | 4 | 1883 | 138.77 |
| Olivier Tardieu | 5 | 462 | 32.13 |