THE FOLD / BOSS / THE CHOKE POINT / THE FLAT COMBINING
THE FLAT COMBINING
building the bottleneck on purpose
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Sixty-four threads fighting for one lock is sixty-four cache-line transfers to do sixty-four small things. Let each publish its request and let one thread take the lock and do all sixty-four — the structure moves once.
LIT verified live. 64 threads, 128 rounds, 8,192 operations. The lock-based version takes 8,192 lock acquisitions and moves the shared structure 8,192 times. Flat combining takes 128 — one per round, a factor of 64 — and reaches an identical final state. The fairness result is the one worth having: with the combiner rotating, every thread ends up executing exactly 128 operations under both schemes. Nobody does more total work. What changes is the burst: the combiner executes 64 operations back to back where a lock-holder executes 1.
LIT verified live. 64 threads, 128 rounds, 8,192 operations. The lock-based version takes 8,192 lock acquisitions and moves the shared structure 8,192 times. Flat combining takes 128 — one per round, a factor of 64 — and reaches an identical final state. The fairness result is the one worth having: with the combiner rotating, every thread ends up executing exactly 128 operations under both schemes. Nobody does more total work. What changes is the burst: the combiner executes 64 operations back to back where a lock-holder executes 1.
2 HOW IT WAS WEAVED · AI + HUMAN
Flat combining is Hendler, Incze, Shavit and Tzafrir (2010).
AVAN (AI) checked the final state against the sequential application before reporting any speed number, because a scheme where one thread executes another thread’s operation is exactly where a silent reordering would hide. The per-thread work count was the surprise worth keeping: the intuition is that the combiner is exploited, and over a rotation it is not — 128 and 128. The cost is not unfairness in total, it is 64× latency variance, which is a different complaint and a real one.
AVAN (AI) checked the final state against the sequential application before reporting any speed number, because a scheme where one thread executes another thread’s operation is exactly where a silent reordering would hide. The per-thread work count was the surprise worth keeping: the intuition is that the combiner is exploited, and over a rotation it is not — 128 and 128. The cost is not unfairness in total, it is 64× latency variance, which is a different complaint and a real one.
3 ONE DIMENSION
8,192 lock acquisitions become 128.
4 TWO DIMENSIONS · INTERACTIVE
Watch one thread do everyone else's work.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that combining removes contention. The inverse is that it removes contention by removing concurrency — on purpose. The critical section is not made shorter or safer; it is made singular, and every other thread is now waiting on a stranger’s scheduling decisions rather than on a lock it could at least see. Read backwards, this is the deliberate construction of a bottleneck, justified by the discovery that the bottleneck already existed and was merely being paid for in cache traffic instead of in queueing.
LIT 64 threads, 128 rounds, 8,192 operations: the lock-based version takes 8,192 lock acquisitions and moves the shared structure 8,192 times, while flat combining takes 128 - one per round, a factor of 64 - and reaches an identical final state; and with the combiner rotating, every thread executes exactly 128 operations under BOTH schemes, so nobody does more total work, what changes is the burst of 64 operations back to back against 1
FIG Flat combining is Hendler, Incze, Shavit and Tzafrir (2010). AVAN checked the final state against the sequential application before reporting any speed number, because a scheme where one thread executes another thread's operation is exactly where a silent reordering would hide. The per-thread work count was the surprise worth keeping: the intuition is that the combiner is exploited, and over a rotation it is not - 128 and 128. The cost is 64x latency variance, which is a different complaint and a real one.
FIG Flat combining is Hendler, Incze, Shavit and Tzafrir (2010). AVAN checked the final state against the sequential application before reporting any speed number, because a scheme where one thread executes another thread's operation is exactly where a silent reordering would hide. The per-thread work count was the surprise worth keeping: the intuition is that the combiner is exploited, and over a rotation it is not - 128 and 128. The cost is 64x latency variance, which is a different complaint and a real one.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN