work_stealing_executor.hpp File Reference

Dynamic partitioning by range stealing. More...

#include <cstdint>
#include <mutex>
#include <string_view>
#include <vector>
#include "orrery/backend/cpu_topology.hpp"
#include "orrery/backend/executor.hpp"
#include "orrery/backend/partition.hpp"
#include "orrery/backend/thread_pool.hpp"
#include "orrery/backend/worker_statistics.hpp"
#include "orrery/core/aligned_allocator.hpp"
#include "orrery/core/types.hpp"

Go to the source code of this file.

Classes
class	orrery::backend::WorkStealingExecutor
	Divides the range into equal shares and lets idle workers take from busy ones. More...

Detailed Description

Dynamic partitioning by range stealing.

The scheme this project uses.

The range is divided into equal shares exactly as the static scheme divides it, and each worker starts on its own. The difference is what happens when a worker runs out. Instead of stopping, it looks at the other workers' shares and takes work from one that still has some. A performance core that finishes early therefore spends the time it would have spent waiting doing an efficiency core's work instead, and the region ends when the work is gone rather than when the slowest worker's fixed share is gone.

Nothing in this needs to know which cores are fast. That is the property worth having. A scheme that split the range four-to-one because the performance cores are about twice the throughput of the efficiency ones would need a ratio, the ratio would have to be measured, and it would then be wrong whenever the machine was thermally limited, running on battery, sharing the memory bus with the integrated GPU, or executing a kernel with a different arithmetic mix. Stealing measures the ratio implicitly, continuously and for free.

Why stealing ranges rather than a task deque

The textbook work-stealing scheduler is Chase and Lev's lock-free deque, and it is the right structure for a scheduler that has to support nested spawning and arbitrary task graphs. This one does not: every parallel region here is a flat loop over particle indices whose extent is known before it starts, which is a much weaker problem. So each worker owns a half-open range rather than a queue of tasks, takes chunks from the front of its own, and steals from the back of a victim's, and the whole of the concurrency is two indices that must not cross.

Those two indices are protected by an ordinary mutex rather than by atomics. That deserves stating plainly, because a lock in a work-stealing scheduler looks like a mistake. It is on no hot path. A chunk is sized at roughly a sixteenth of a worker's share, so a lock is taken a few tens of times per worker per region while each chunk is tens of microseconds of arithmetic: the lock is well under a thousandth of the run time, and it is uncontended almost always, since a thief only reaches a victim's mutex after it has run out of its own work. Against that, the lock-free protocol for a range that can be claimed from both ends has a genuinely subtle race where the two ends meet, and its correctness argument lives in a paper rather than in the file. Section 5 of the implementation plan asks that any single file be defensible to a reviewer who did not write it, and this is what that costs here. ADR-0016 records the decision.

Termination

A worker stops when its own range is empty and a full sweep of every other worker's range finds nothing to take. That is safe because work is only ever removed from a range, never added: no region spawns new work, so a range observed empty stays empty for the rest of the region. Work already claimed by another worker is not lost by this worker exiting, because the claimer runs it before checking again, and the pool does not consider the region finished until every worker has returned.