How should a parallel reduction API define determinism without lying about associativity?

A parallel reduction API should define determinism as a reproducibility promise over a named execution plan, not as a vague guarantee that any reducer behaves the same under arbitrary parallel schedules. State what the runtime fixes, what algebraic laws the reducer must satisfy, and which scope of repeatability you promise: same build and backend, across thread counts, or across hardware. For floating-point, promise reproducibility under that plan, not mathematical invariance.

What does “deterministic” need to cover?

“Deterministic” is meaningless unless the API names the boundary. A useful contract is: same input, same binary, same backend, same execution policy, same deterministic mode, same result. If you want a stricter contract, define stability across thread counts as part of deterministic mode. If you intend to promise cross-device reproducibility, you will likely need to constrain partitioning and the numeric environment more tightly than for a same-backend guarantee.

That boundary should be part of the API surface, because real reduction libraries already tie semantics to policy. The Kokkos parallel_reduce documentation says work is performed according to the execution policy and also says that neither concurrency nor order of execution are guaranteed. Your API should be equally explicit: determinism belongs to a policy or mode, not to the word “parallel” by itself.

What laws should the reducer satisfy?

Write the reducer contract in plain terms.

If the runtime may regroup operands without changing the answer, require associativity over the allowed value domain. If it may also reorder operands, require commutativity. A fixed-tree mode can instead define that tree’s result for a non-associative operator. Specify closure, identity and side-effect rules explicitly.

Be concrete about identity handling. The Kokkos parallel_reduce documentation documents some cases—such as certain lambda reductions and TeamThreadRange forms—where a sum reduction assumes the value type’s default constructor as the identity when no custom reducer is provided. That kind of detail changes correctness and should be stated up front in your own API docs.

For floating-point, do not pretend IEEE arithmetic is associative. The honest statement is: this operator is not mathematically associative in machine arithmetic, but the runtime can still produce reproducible results by using a fixed partitioning and fixed merge tree.

What ordering should the runtime actually fix?

A good deterministic plan is chunk-then-merge:

• partition the iteration space deterministically
• reduce each chunk in encounter order
• merge chunk results with a fixed tree shape

That is a stronger and more testable contract than “we use atomics.” Atomics serialize updates to one location, but by themselves they do not define a stable operand order across workers. Compiler behavior matters as well: the GCC optimization options documentation says -fassociative-math allows reassociation of floating-point operands and may change computation results, signed zero behavior, NaN handling, and overflow or underflow behavior. A source-level tree alone cannot enforce reproducibility when compiler flags permit reshaping it.

Worked example:

• Integer sum: for signed integers, every intermediate sum in every permitted tree must be representable. Saturating addition is not generally associative. Unsigned modular addition needs an explicit fixed-width contract.
• Floating-point sum: reproducibility usually requires fixing the merge tree and controlling relevant compiler transformations. Depending on the environment, you may also need to pin precision and rounding behavior. The GCC optimization options documentation notes that excess precision and associative-math settings can affect when rounding occurs and whether expressions may be regrouped.
• Min with index: deterministic only if ties are part of the operator, such as “smaller value wins; equal values choose smaller index.”

What should fail loudly instead of being hidden?

Reject or downgrade reducers that mutate external state, depend on randomness, or leave NaN and tie handling unspecified. Document backend limits too. For example, two different backend-specific deterministic plans could still yield different floating-point answers.

A short checklist for docs and tests:

• what reproducibility scope is promised?
• what partitioning and merge order are fixed?
• is regrouping allowed, reordering allowed, or both?
• what identity, NaN, and tie rules apply?
• does deterministic mode reject unsupported reducers or fall back to serial?

Q: Can I call floating-point reduction deterministic?
Yes, if you mean reproducible under a fixed documented plan. No, if you imply equality under arbitrary regrouping.

Q: Should one deterministic mode guarantee the same result on CPU and GPU?
Only if the API explicitly promises cross-backend reproducibility and constrains the execution plan enough to make that credible.

Next step: write your reduction contract as three separate clauses—reducer laws, fixed partitioning and merge order, and reproducibility scope—before you choose the scheduler or backend implementation.

Reviewed: 2026-09-06