Work stealing

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"[2] or "strands".[8] Edges represent serial computation.[9][note 1]

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 f(1, 2) gives rise to the following computation graph:

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.

The randomized version of the work stealing algorithm presented by Blumofe and Leiserson maintains several threads of execution and schedules these onto ${\displaystyle P}$ 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:[2]^: 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.

Several variants of work stealing have been proposed. The randomized variant due to Blumofe and Leiserson executes a parallel computation in expected time ${\displaystyle T_{1}/P+O(T_{\infty })}$ on ${\displaystyle P}$ processors; here, ${\displaystyle T_{1}}$ is the work, or the amount of time required to run the computation on a serial computer, and ${\displaystyle T_{\infty }}$ is the span, the amount of time required on an infinitely parallel machine.[note 2] This means that, in expectation, the time required is at most a constant factor times the theoretical minimum.[2] However, the running time (in particular, the number of steals executed) can be exponential in ${\displaystyle T_{\infty }}$ in the worst case.[10] 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.[11][12]

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

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 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 P_A ≤ P of the P processors in the computer, because other processes may be using the remaining processors. In this setting, work stealing with a pool of 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.[14][15]

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

$${\displaystyle O\left({\frac {T_{1}}{P_{\mathrm {avg} }}}+{\frac {T_{\infty }P}{P_{\mathrm {avg} }}}\right),}$$

where P_avg is the average number of processors allocated to the computation by the OS scheduler over the computation's running time.[16] The multiprogramming work-scheduler differs from the traditional version in two respects:

• Its queues are non-blocking. While on dedicated processors, access to the queues can be synchronized using locks, this is not advisable in a multiprogramming environment since the operating system might 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 "yield" system call that yields the processor on which it is scheduled to the OS, in order to prevent starvation.

Attempts to improve on the multiprogramming work stealer have focused on cache locality issues[12] and improved queue data structures.[17]

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,[18] as well giving better performance in some situations where the cores of a chip multiprocessor share a cache.[1]