Work Stealing - Executors
The final bits of our executor design are coming together, so we’re just far enough to talk specifics of their role in enabling work stealing in Hemlock. It’s the last big design piece that needed to be solidified, so we finally have a pretty solid picture of how the entire ecosystem around work stealing actually works.
A quick aside… As we answered the final few design questions about work stealing this week, we spent some time dreaming about what Hemlock would do on the newly-revealed dual-package, 256-core AMD computers. In a few years, we might have kibicore (1024-core!) computers available, along with straight-line Hemlock code that makes every single one of those cores glow red.
Onward, to the designs of our recent labor.
Executors schedule their runnable actors much like Erlang, allocating a time slice of run-time and using reduction count for CPU-time accounting. On every function return (a back-edge), an actor debits some of its allocated reductions (the number of intermediate representation instructions, which generally reflects the cost of the function). When the actor exhausts its allocated reductions, it yields control back to its executor.
An actor that willingly yields in this manner is actually consuming its CPU time. It’s not I/O-bound
for now. There’s a strong possibility that it is CPU-bound and that it has stealable work embedded
in its execution stack, marked in a stack frame by a quantum generation (QG) value. When the actor
yields, the executor searches its execution stack for any QG. If the executor finds zero values,
it initializes them to the value of the actor’s just-finished quantum (Q). If the executor finds two
or more initialized QG values from some number of quanta ago, it may try to steal the work.
The actor that has work stolen becomes the victim and the newly-created actors that take on the stolen work are delegates. Delegates can reference values from the victim’s heap. To keep such memory access simple, we pause the victim to ensure that garbage collection never moves its memory around. Since the victim is paused, the executor must create at least two delegates to actually gain parallelism. The executor self-assigns one of the delegates (the self-delegate), and assigns the remaining delegates to other executors. The self-delegate is special in that it may continue to delegate work from itself or from the victim on which it is based. The tree of delegates and victims spawned from a single basal victim is called a posse and the executors they map onto is called a cabal. The most basal (root) victim of the posse keeps the account of which executors are members of the cabal. [1]
Executor Executor
+--------------------------+ +---------------------------+
| Victim: Q = 20 | | Delegate |
| +--------------+ | | +--------------+ |
| /--f0 | QG = 1 | | /------->f2 | | |
| | +--------------+ | | | +--------------+ |
| | f1 | QG = 2 |-----/ | f3 | | |
| | +--------------+ | | +--------------+ |
| | f2 | QG = 5 | | | f4 | QG = 4 | |
| | +--------------+ | | +--------------+ |
| | f3 | QG = 'zero' | | | f5 | | |
| | +--------------+ | | +--------------+ |
| | | | f6 | QG = 6 | |
| | Self-delegate | | +--------------+ |
| | +--------------+ | | f7 | QG = 'zero' | |
| \->f1 | QG = 2 | | | +--------------+ |
| +--------------+ | | |
| f2 | QG = 'zero' | | | |
| +--------------+ | | |
| | | |
+--------------------------+ +---------------------------+
When an executor wants to create N delegates, it checks with N - 1 random executors that are not
yet members of the cabal. Potential factors for deciding whether to induct the new executor into the
cabal are load factor (overloaded executors should be more resistant to taking on work) and how many
quanta the work has been available (more quanta means higher likelihood that the work is large
enough to be worth stealing).
Surprisingly, that’s it. Work stolen.
Citations
-
Evans, Cameron, and Jason Evans “Terminology” GitHub, https://github.com/BranchTaken/Hemlock/blob/ main/doc/design/work_stealing.md#terminology. Work stealing, Accessed 07, Nov. 2021. ↩