Make a parallel reduction deterministic

Why this is a drill and not a lab

The lab proved parallel accumulation breaks determinism. It did not tell you what to do instead, and “do it single-threaded” is a real answer that is sometimes correct and often unacceptable — a reduction over 500,000 entities on one core while seven sit idle is a cost you will not always be willing to pay.

So: keep the cores, keep the determinism. There is a well-known family of solutions and this drill does not name it, because deriving it is the exercise. Everything you need is in the constraint list if you read it as a specification rather than as rules.

| Constraint | The shortcut it closes | |---|---| | Bit-identical, checked on raw bits | Comparing with a tolerance hides exactly the divergence that matters | | Must use multiple cores | The trivial single-threaded answer | | No integer/fixed-point escape | Sidestepping non-associativity instead of managing it | | Order must not depend on completion | The ParallelWriter-shaped near-miss from the lab | | No full sort per frame | Trading nondeterminism for an asymptotic regression |

The fourth constraint is the specification in disguise. It says the combination order must be something, just not completion order. Deciding what that something should be is the whole drill.

How to work it

Milestones, not steps.

Reproduce the failure. Take the lab’s MODE 2 and confirm you get varying checksums. You need a failing baseline before a fix means anything.
Separate the two facts. Threads adding numbers is fine. Threads combining their results in a variable order is the problem. Write down which part you intend to keep.
Get a correct-but-slow version. Single-threaded, deterministic. This is your reference checksum — the number a correct parallel version must reproduce exactly.
Parallelize without changing the answer. Your parallel version must produce the reference checksum bit-for-bit, not approximately.
Verify the invariants. Vary worker thread count. Reorder entities in memory without changing the set. Both checks in the list exist to catch solutions that are accidentally stable on your machine.
Measure the crossover. At what entity count does your version beat the single-threaded one? Below that, single-threaded is the right answer, and knowing where the line is is part of the deliverable.

trap

The failure that looks like success: your solution produces identical checksums on ten consecutive runs on your machine, and you conclude it is deterministic. But if the slot assignment depends on anything about the current machine’s scheduling — thread index, completion order, core count — you have built something stable locally and divergent across machines, which is the worst possible outcome because it passes every test you can easily run and fails only in production, on someone else’s hardware, as unexplainable desync.

The check that catches this is “changing the number of worker threads does not change the result.” Run it deliberately. If you cannot vary worker count in your setup, at minimum reason explicitly about whether your slot identity is a property of the data or a property of the machine. Only the first is safe.

When you are done

Answer without checking your code:

What determines the combination order in your solution, and why is that thing stable across machines and runs?
Your reduction produces the same answer as the single-threaded version. Is that a coincidence of your test data, or is it structural? How would you know?
What is the crossover entity count, and what does that imply about when to reach for this at all?
If you needed to reduce over 50 million entities, does your approach still hold, or does the final combination step become the bottleneck? At what size?
Which of your invariant checks would catch a solution that is deterministic on your machine but not on a player’s?

That last question is the one that matters most. The lab showed you that nondeterminism can be invisible. This drill is only complete if you can name the specific test that would have caught the invisible version.

you gain

A deterministic parallel reduction is the piece that makes the rest of the course's parallelism compatible with rollback, replay and lockstep networking. Without it, any simulation needing determinism has to serialize every reduction, and that ceiling gets low fast. Deriving it rather than being handed it means you can recognize the same problem shape when it appears in a different guise.

you pay

Fixed-order combination costs something real — either extra memory for partials, an extra pass, or a constraint on how work is distributed — so it is slower than the fastest nondeterministic reduction. There is a genuine crossover below which single-threaded wins outright, and pretending otherwise is how people end up with a complex parallel reduction that is slower than a for-loop on their actual data sizes.

If you conclude that for your entity counts the single-threaded reduction wins, that is a legitimate and well-earned outcome — provided you can state the crossover number you measured. An unmeasured “it’s probably fine” is not the same conclusion.