THE FOLD / CO-OP / THE MERGE / THE WORK STEALING
THE WORK STEALING
it does not schedule more cleverly, it schedules later
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Deciding who does what before you start only works if you already know how long each piece takes. When you do not, seven workers finish early and stand still while the eighth is buried.
LIT verified live. 2,000 tasks, 74,359 units of work, 8 workers. A fixed block split finishes at 35,505 — 3.82× the ideal 9,294.9, with the fleet idle 73.82% of the time. Letting a free worker take the next task off the most loaded queue finishes at 9,511: 2.3% off ideal, 2.27% idle, 3.73× faster, after 358 steals. Same tasks, same workers, same total work.
LIT verified live. 2,000 tasks, 74,359 units of work, 8 workers. A fixed block split finishes at 35,505 — 3.82× the ideal 9,294.9, with the fleet idle 73.82% of the time. Letting a free worker take the next task off the most loaded queue finishes at 9,511: 2.3% off ideal, 2.27% idle, 3.73× faster, after 358 steals. Same tasks, same workers, same total work.
2 HOW IT WAS WEAVED · AI + HUMAN
Work stealing is the scheduler in Cilk, in Go’s runtime, in Java’s fork/join pool; the deque-with-stealing shape is Blumofe and Leiserson’s.
AVAN (AI) first ran this with tasks dealt round-robin, and measured 0 steals — because 250 random draws per worker converge to the same sum, so there was nothing to steal. That is not the case the technique exists for. Static partitioning only loses when the work is skewed, and the experiment has to put the skew somewhere a fixed split cannot see it.
AVAN (AI) first ran this with tasks dealt round-robin, and measured 0 steals — because 250 random draws per worker converge to the same sum, so there was nothing to steal. That is not the case the technique exists for. Static partitioning only loses when the work is skewed, and the experiment has to put the skew somewhere a fixed split cannot see it.
3 ONE DIMENSION
Eight workers, decided up front and decided as it goes.
4 TWO DIMENSIONS · INTERACTIVE
Change the skew and watch the fixed split fail.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: seven idle, one buried.
AVAN’s addition (the inverse-companion): the forward reading is that stealing beats planning. The inverse is that the plan was never wrong — it was made too early. A fixed split is optimal for the information available when it is made, and it stays committed to that information after the work has told you something better. Read backwards, work stealing does not schedule more cleverly; it schedules later, and almost all of the 3.73× is the value of not having decided yet.
LIT 2,000 tasks totalling 74,359 units across 8 workers finish at 35,505 under a fixed block split - 3.82 times the ideal 9,294.9, with the fleet idle 73.82% of the time - against 9,511 when a free worker takes the next task off the most loaded queue, which is 2.3% off ideal and 2.27% idle, a speedup of 3.73 after 358 steals
FIG Work stealing is the scheduler in Cilk, in Go's runtime and in Java's fork/join pool; the deque-with-stealing shape is Blumofe and Leiserson's. AVAN first ran this with tasks dealt round-robin and measured 0 steals, because 250 random draws per worker converge to the same sum and there was nothing to steal. Static partitioning only loses when the work is skewed, and the experiment has to put the skew somewhere a fixed split cannot see it.
FIG Work stealing is the scheduler in Cilk, in Go's runtime and in Java's fork/join pool; the deque-with-stealing shape is Blumofe and Leiserson's. AVAN first ran this with tasks dealt round-robin and measured 0 steals, because 250 random draws per worker converge to the same sum and there was nothing to steal. Static partitioning only loses when the work is skewed, and the experiment has to put the skew somewhere a fixed split cannot see it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN