Nondeterminism in Futhark

Last week, I had the pleasure of attending IFL2026, an exceptional conference experience. Among the many noteworthy presentations, Michael Haddon's talk on The Replay Lattice stood out. This type system focuses on floating-point reproducibility, specifically within the demonstration language Lane. Intrigued by nondeterminism in Futhark, which possesses some nondeterminism, I began to ponder the potential costs of eliminating it.

When discussing determinism and nondeterminism in data parallel programming, it's easy to overlook the subtleties. However, Michael Haddon's work provides valuable insights into these concepts. He introduced terminology such as Exact, Replay, and Approx to clarify the differences.

Exact computations consistently produce the same result, guaranteed. Replay implies that rerunning the computation with the same schedule (or machine) yields identical results, albeit possibly on different machines. Approx computations, on the other hand, may yield nondeterministic results, a phenomenon more common in floating-point rounding errors.

A prime example is the non-associativity of addition. When summing an array of numbers, the result depends on the order of addition. Parallelizing a summation often involves splitting numbers into blocks, summing each block on separate processors, and then combining the partial results. This approach alters the order of addition, leading to different outcomes.

Although the parallelized result need not be numerically worse than a serial left-to-right summation, it will differ. Additionally, an efficient implementation may select a number of chunks proportional to the number of processors, resulting in varying outcomes across machines.

There are two sources of nondeterminism in Futhark. First, programmers may violate mandated constraints, disregarding safety checks. Second, floating-point roundoff errors contribute to nondeterminism. Let's examine these sources further.

One issue arises from using the #[unsafe] attribute, disabling safety checks. This can be mitigated by passing --safe to the compiler or avoiding such practices altogether. Another more insidious problem revolves around the scatter construct. The scatter operation pairs indexes with corresponding values and writes each value to the appropriate index.

To ensure parallel execution, Futhark requires that the indexes have no duplicates or, in a weakened condition, that duplicate indexes have identical values. However, these conditions are not dynamically checked, and violating them can lead to unpredictable write behavior, including torn writes. This behavior is thorny, and even experienced Futhark programmers occasionally make this mistake.

Lastly, parallel reductions, such as reductions and histograms, require associative and commutative operators. While documented, these properties are unchecked in Futhark. Programmers may use arbitrary operators, potentially resulting in nonsensical or nondeterministic outcomes. Treating reduce as a general fold and using non-associative operators is a common error among new Futhark programmers.