View source for Work stealing

{{Short description|Parallel computing algorithm}}
{{about|a parallel computing term|uncompensated taking of labor|wage theft}}
In [[parallel computing]], '''work stealing''' is a [[Scheduling (computing)|scheduling]] strategy for [[multithreading (software)|multithreaded]] computer programs. It solves the problem of executing a ''dynamically multithreaded'' computation, one that can "spawn" new threads of execution, on a ''statically multithreaded'' computer, with a fixed number of processors (or [[processor core|cores]]). It does so efficiently in terms of execution time, memory usage, and inter-processor communication.

In a work stealing scheduler, each processor in a computer system has a queue of work items (computational tasks, threads) to perform. Each work item consists of a series of instructions, to be executed sequentially, but in the course of its execution, a work item may also ''spawn'' new work items that can feasibly be executed in parallel with its other work. These new items are initially put on the queue of the processor executing the work item. When a processor runs out of work, it looks at the queues of the other processors and "steals" their work items. In effect, work stealing distributes the scheduling work over idle processors, and as long as all processors have work to do, no scheduling overhead occurs.{{r|dfs}}

Work stealing contrasts with ''work sharing'', another popular scheduling approach for dynamic multithreading, where each work item is scheduled onto a processor when it is spawned. Compared to this approach, work stealing reduces the amount of [[process migration]] between processors, because no such migration occurs when all processors have work to do.<ref name="jacm">{{cite journal |last1=Blumofe |first1=Robert D. |first2=Charles E. |last2=Leiserson |author-link2=Charles E. Leiserson |title=Scheduling multithreaded computations by work stealing |journal=J ACM |volume=46 |issue=5 |year=1999 |pages=720–748 |url=http://supertech.csail.mit.edu/papers/ft_gateway.pdf |doi=10.1145/324133.324234|s2cid=5428476 }}</ref>

The idea of work stealing goes back to the implementation of the [[Multilisp]] programming language and work on parallel [[functional programming]] languages in the 1980s.<ref name="jacm"/> It is employed in the scheduler for the [[Cilk]] programming language,<ref>{{cite journal |last1=Blumofe |first1=Robert D. |first2=Christopher F. |last2=Joerg |first3=Bradley C. |last3=Kuszmaul |first4=Charles E. |last4=Leiserson |first5=Keith H. |last5=Randall |first6=Yuli |last6=Zhou |title=Cilk: An efficient multithreaded runtime system |journal= Journal of Parallel and Distributed Computing|volume=37 |issue=1 |year=1996 |pages=55–69 |doi=10.1006/jpdc.1996.0107|doi-access=free }}</ref> the [[Java (programming language)|Java]] fork/join framework,<ref name="lea">{{cite conference |author=Doug Lea |author-link=Doug Lea |title=A Java fork/join framework |year=2000 |url=http://gee.cs.oswego.edu/dl/papers/fj.pdf |conference=ACM Conf. on Java}}</ref> the .NET [[Task Parallel Library]],<ref>{{cite journal |last1=Leijen |first1=Daan |first2=Wolfram |last2=Schulte |first3=Sebastian |last3=Burckhardt |title=The Design of a Task Parallel Library |journal=ACM SIGPLAN Notices |volume=44 |issue=10 |pages=227 |year=2009|doi=10.1145/1639949.1640106 |citeseerx=10.1.1.146.4197 }}</ref> and the [[Rust (programming language)|Rust]] [[Tokio (software)|Tokio runtime]].<ref>{{Cite web|title=What is Tokio? · Tokio|url=https://tokio.rs/docs/overview/|website=tokio.rs|access-date=2020-05-27}}</ref><ref>{{Cite web|last=Krill|first=Paul|date=2021-01-08|title=Tokio Rust runtime reaches 1.0 status|url=https://www.infoworld.com/article/3602776/tokio-rust-runtime-reaches-10-status.html|access-date=2021-12-26|website=InfoWorld|language=en}}</ref>

==Execution model==
Work stealing is designed for a "strict" [[fork–join model]] of parallel computation, which means that a computation can be viewed as a [[directed acyclic graph]] with a single source (start of computation) and a single sink (end of computation). Each node in this graph represents either a ''fork'' or a ''join''. Forks produce multiple ''logically parallel'' computations, variously called "threads"<ref name="jacm"/> or "strands".<ref name="primer">{{cite tech report |first=Arch |last=Robison |title=A Primer on Scheduling Fork–Join Parallelism with Work Stealing |number=N3872 |institution=[[ISO/IEC JTC 1/SC 22]]/WG 21—The [[C++]] Standards Committee |date=15 January 2014 |url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3872.pdf}}</ref> Edges represent serial computation.<ref>{{cite tech report |first=Pablo |last=Halpern |title=Strict Fork–Join Parallelism |number=N3409=12-0099 |institution=[[ISO/IEC JTC 1/SC 22]]/WG 21—The [[C++]] Standards Committee |date=24 September 2012 |url=https://www.cilkplus.org/sites/default/files/papers/N3409_strict_fork_join_parallelism.pdf}}</ref><ref group="note">In the original presentation, serial computations were represented as nodes as well, and a directed edge represented the relation "is followed by".</ref>

As an example, consider the following trivial fork–join program in [[Cilk]]-like syntax:

 '''function''' f(a, b):
     c ← '''fork''' g(a)
     d ← h(b)
     '''join'''
     return c + d
 
 '''function''' g(a):
     return a × 2
 
 '''function''' h(a):
     b ← '''fork''' g(a)
     c ← a + 1
     '''join'''
     return b + c

The function call {{mono|f(1, 2)}} gives rise to the following computation graph:

[[File:Fork-join computation.svg|Graph representation of a [[:w:en:fork–join model|fork–join]] computation.]]

In the graph, when two edges leave a node, the computations represented by the edge labels are logically parallel: they may be performed either in parallel, or sequentially. The computation may only proceed past a ''join'' node when the computations represented by its incoming edges are complete. The work of a scheduler, now, is to assign the computations (edges) to processors in a way that makes the entire computation run to completion in the correct order (as constrained by the join nodes), preferably as fast as possible.

==Algorithm==
The [[randomized algorithm|randomized]] version of the work stealing algorithm presented by Blumofe and Leiserson maintains several threads of execution and schedules these onto <math>P</math> processors. Each of the processors has a [[double-ended queue]] (deque) of threads. Call the ends of the deque "top" and "bottom".

Each processor that has a current thread to execute, executes the instructions in the thread one by one, until it encounters an instruction that causes one of four "special" behaviors:<ref name="jacm"/>{{rp|10}}

* A ''spawn'' instruction causes a new thread to be created. The current thread is placed at the bottom of the deque, and the processor starts executing the new thread.
* A ''stalling'' instruction is one that temporarily halts execution of its thread. The processor pops a thread off the bottom of its deque and starts executing that thread. If its deque is empty, it starts work stealing, explained below.
* An instruction may cause a thread to ''die''. The behavior in this case is the same as for an instruction that stalls.
* An instruction may ''enable'' another thread. The other thread is pushed onto the bottom of the deque, but the processor continues execution of its current thread.

Initially, a computation consists of a single thread and is assigned to some processor, while the other processors start off idle. Any processor that becomes idle starts the actual process of work stealing, which means the following:

* it picks another processor uniformly at random;
* if the other processor's deque is non-empty, it pops the top-most thread off the deque and starts executing that;
* else, repeat.

===Child stealing vs. continuation stealing===
Note that, in the rule for ''spawn'', Blumofe and Leiserson suggest that the "parent" thread execute its new thread, as if performing a function call (in the C-like program {{mono|f(x); g(y);}}, the function call to {{mono|f}} completes before the call to {{mono|g}} is performed). This is called "continuation stealing", because the [[continuation]] of the function can be stolen while the spawned thread is executed, and is the scheduling algorithm used in [[Cilk Plus]].<ref name="primer"/> It is not the only way to implement work stealing; the alternative strategy is called "child stealing" and is easier to implement as a [[software library|library]], without [[compiler]] support.<ref name="primer"/> Child stealing is used by [[Threading Building Blocks]], Microsoft's Task Parallel Library and [[OpenMP]], although the latter gives the programmer control over which strategy is used.<ref name="primer"/>

==Efficiency==
Several variants of work stealing have been proposed. The [[Randomized algorithm|randomized]] variant due to Blumofe and Leiserson executes a parallel computation in [[expected time]] <math>T_1/P + O(T_\infty)</math> on <math>P</math> processors; here, <math>T_1</math> is the ''work'', or the amount of time required to run the computation on a serial computer, and <math>T_\infty</math> is the ''span'', the amount of time required on an infinitely parallel machine.<ref group="note">See [[analysis of parallel algorithms]] for definitions.</ref> This means that, [[expected value|in expectation]], the time required is at most a constant factor times the theoretical minimum.<ref name="jacm"/> However, the running time (in particular, the number of steals executed) can be exponential in <math>T_\infty</math> in the worst case.<ref>{{cite journal |last1=Leiserson |first1=Charles E. |author-link1=Charles E. Leiserson |first2=Tao B. |last2=Schardl |first3=Warut | last3=Suksompong |title=Upper Bounds on Number of Steals in Rooted Trees |journal=Theory of Computing Systems |volume=58 |issue=2 |year=2016 |pages=223–240 |doi=10.1007/s00224-015-9613-9|arxiv=1706.08219 |s2cid=424692 }}</ref> A localized variant, in which a processor attempts to steal back its own work whenever it is free, has also been analyzed theoretically and practically.<ref>{{cite journal |last1=Suksompong |first1=Warut |first2=Charles E. | last2=Leiserson |author-link2=Charles E. Leiserson |first3=Tao B. |last3=Schardl |title=On the efficiency of localized work stealing |journal=Information Processing Letters |volume=116 |issue=2 |year=2016 |pages=100–106|doi=10.1016/j.ipl.2015.10.002|arxiv=1804.04773 |s2cid=1180480 }}</ref><ref name="local"/>

===Space usage===
A computation scheduled by the Blumofe–Leiserson version of work stealing uses <math>O(S_1 P)</math> [[call stack|stack space]], if <math>S_1</math> were the stack usage of the same computation on a single processor,<ref name="jacm"/> fitting the authors' own earlier definition of space efficiency.<ref>{{cite journal |last1=Blumofe |first1=Robert D. |first2=Charles E. |last2=Leiserson |author-link2=Charles E. Leiserson |title=Space-efficient scheduling of multithreaded computations |journal=SIAM J. Comput. |volume=27 |issue=1 |year=1998 |pages=202–229 |doi=10.1137/s0097539793259471|citeseerx=10.1.1.48.9822 }}</ref> This bound requires continuation stealing; in a child stealing scheduler, it does not hold, as can be seen from the following example:<ref name="primer"/>

 '''for''' i = 0 '''to''' n:
     '''fork''' f(i)
 '''join'''

In a child-stealing implementation, all "forked" calls to {{mono|f}} are put in a work queue that thus grows to size {{mono|n}}, which can be made arbitrarily large.

==Multiprogramming variant==
The work stealing algorithm as outlined earlier, and its analysis, assume a computing environment where a computation is scheduled onto a set of dedicated processors. In a [[multiprogramming]] (multi-tasking) environment, the algorithm must be modified to instead schedule computation tasks onto a [[thread pool|pool of worker threads]], which in turn are scheduled onto the actual processors by an [[operating system]] scheduler. At any given time, the OS scheduler will assign to the work stealing process some number {{math|''P<sub>A</sub>'' ≤ ''P''}} of the {{mvar|P}} processors in the computer, because other processes may be using the remaining processors. In this setting, work stealing with a pool of {{mvar|P}} worker threads has the problem that workers acting as thieves may cause [[livelock]]: they may block the execution of workers that would actually spawn useful tasks.<ref>{{cite conference |title=BWS: Balanced Work Stealing for Time-Sharing Multicores |first1=Xiaoning |last1=Ding |first2=Kaibo |last2=Wang |first3=Phillip B. |last3=Gibbons |first4=Xiaodong |last4=Zhang |conference=EuroSys |year=2012 |url=http://www.istc-cc.cmu.edu/publications/papers/2012/BWS-Eurosys12.pdf}}</ref><ref>{{cite tech report |first1=Robert D. |last1=Blumofe |first2=Dionisios |last2=Papadopoulos |title=The Performance of Work Stealing in Multiprogrammed Environments |institution=[[University of Texas at Austin]], Department of Computer Sciences |year=1998 |citeseerx=10.1.1.48.2247}}</ref>

A variant of work stealing has been devised for this situation, which executes a computation in expected time

<math display="block">O\left(\frac{T_1}{P_\mathrm{avg}} + \frac{T_\infty P}{P_\mathrm{avg}}\right),</math>

where {{math|''P''<sub>avg</sub>}} is the average number of processors allocated to the computation by the OS scheduler over the computation's running time.<ref name="arora">{{cite journal |last1=Arora |first1=Nimar S. |first2=Robert D. |last2=Blumofe |first3=C. Greg |last3=Plaxton |title=Thread scheduling for multiprogrammed multiprocessors |journal=Theory of Computing Systems |volume=34 |issue=2 |year=2001 |pages=115–144 |url=http://www.geocities.ws/nimar_arora/publications/tocs01.pdf |doi=10.1007/s002240011004}}</ref>
The multiprogramming work-scheduler differs from the traditional version in two respects:

* Its queues are [[Non-blocking algorithm|non-blocking]]. While on dedicated processors, access to the queues can be synchronized using [[Lock (computer science)|locks]], this is not advisable in a multiprogramming environment since the operating system might [[Preemption (computing)|preempt]] the worker thread holding the lock, blocking the progress of any other workers that try to access the same queue.
* Before each attempt to steal work, a worker thread calls a "{{mono|yield}}" system call that yields the processor on which it is scheduled to the OS, in order to prevent [[Starvation (computer science)|starvation]].

Attempts to improve on the multiprogramming work stealer have focused on [[Locality of reference|cache locality]] issues<ref name="local">{{cite journal |first1=Umut A. |last1=Acar |first2=Guy E. |last2=Blelloch |author-link2=Guy Blelloch |first3=Robert D. |last3=Blumofe |title=The Data Locality of Work Stealing |journal=Theory of Computing Systems |volume=35 |issue=3 |pages=321–347 |doi=10.1007/s00224-002-1057-3 |url=http://www-2.cs.cmu.edu/~blelloch/papers/locality2000.pdf|year=2002 |citeseerx=10.1.1.19.3459 |s2cid=10235838 }}</ref> and improved queue data structures.<ref>{{cite conference |first1=David R. |last1=Chase |first2=Yosef |last2=Lev |title=Dynamic Circular Work-Stealing Deque |conference=ACM Symp. on Parallelism in Algorithms and Architectures |year=2005 |citeseerx=10.1.1.170.1097}}</ref>

==Alternatives==
Several scheduling algorithms for dynamically multithreaded computations compete with work stealing. Besides the traditional work sharing approach, there is a scheduler called ''parallel depth-first'' (PDF) that improves on the space bounds of work stealing,<ref>{{Cite journal |last1=Blelloch |first1=Guy E. |first2=Phillip B. |last2=Gibbons |first3=Yossi |last3=Matias |title=Provably efficient scheduling for languages with fine-grained parallelism |journal=[[Journal of the ACM]] |volume=46 |issue=2 |year=1999 |pages=281–321 |url=http://cs.cmu.edu/afs/cs.cmu.edu/Web/People/blelloch/papers/jacm99.pdf |doi=10.1145/301970.301974|citeseerx=10.1.1.48.8238 |s2cid=47102937 }}</ref> as well giving better performance in some situations where the cores of a [[chip multiprocessor]] share a cache.<ref name="dfs">{{cite conference |last1=Chen |first1=Shimin
|first2=Phillip B. |last2=Gibbons
|first3=Michael |last3=Kozuch
|first4=Vasileios |last4=Liaskovitis
|first5=Anastassia |last5=Ailamaki
|first6=Guy E. |last6=Blelloch
|first7=Babak |last7=Falsafi
|first8=Limor |last8=Fix
|first9=Nikos |last9=Hardavellas
|first10=Todd C. |last10=Mowry
|first11=Chris |last11=Wilkerson
|title=Scheduling threads for constructive cache sharing on CMPs |conference=Proc. ACM Symp. on Parallel Algorithms and Architectures |pages=105–115 |year=2007 |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/blelloch/papers/CGK07.pdf}}</ref>

==Notes==
{{reflist|group=note}}

==References==
{{reflist|30em}}

[[Category:Processor scheduling algorithms]]
[[Category:Parallel computing]]