An escape hatch the size of one fact

TL;DR — a GPU kernel that writes at rows from an index tensor, y[idx[b]], cannot be proved free of races. No analysis can do it, because the rows are data at run time. Vx's new type Distinct<..> lets the programmer add the one missing fact: no two elements of idx are equal. A check on the CPU, or an unsafe block, supplies the fact, and the compiler still checks everything else. C's restrict cannot state this fact. The C tools that get such a loop through do it by turning off the check for the whole loop.

A mixture-of-experts layer sends each token to a few experts. The kernel of one expert computes the results for its tokens and writes them to the rows of those tokens. That is one line of code, and the Vx compiler refused it.

The kernel that did not compile

Here is the write, in the form that the kernel of one expert needs. Block b adds row b of x to the row of token idx[b]:

fn add_to_rows(y : &mut Tensor<f32, [?, ?], Memory::HBM>, idx : &Tensor<i32, [?], Memory::HBM>,
               x : &Tensor<f32, [?, ?], Memory::HBM>) -> void {
  spawn on(Topology::Device) {
    for b in 0..idx.len() across blocks {
      for l in 0..64 across lanes(64) {
        y[idx[b]][l] += x[b][l];
      }
    }
  }
  return;
}
Error[E6032] at add_to_rows.vx:5:9: two passes of this block loop may write the same element of `y`: an index of the write must fix `b`

The passes of a block loop run at the same time, in any order. So Vx refuses a loop unless it can prove that two passes never write the same element. Here it cannot. If idx holds the row 7 twice, two blocks add to row 7 at the same time, and one of the two adds can be lost. The compiler is right to refuse.

But the program is right too. The router gives each token to an expert once, so the list of tokens of one expert has no repeats. The Qwen app in Vx (vx-lang/qwen-vx#16) worked around the refusal. It copied the expert ids of each chunk of tokens to the CPU, sorted the tokens by expert there, and padded each expert to a multiple of 16 rows. Then tile b wrote rows 16b to 16b + 15, an index that fixes b. That cost one wait for the GPU in each layer: 48 waits for each chunk of the 30B model.

What a race checker proves

The general form of the question uses iteration domains, the base of polyhedral compilation. Each pass of a loop nest is a point with integer coordinates. The domain is the set of all the points, written as linear inequalities:

{ (b, l) : 0 <= b < n, 0 <= l < 64 }

Each access is a function from a point to an element. The write y[b][l] maps (b, l) to the element (b, l). The loop over b has a race when two points with different values of b write the same element:

exists (b1, l1), (b2, l2) in the domain:  b1 != b2  and  (b1, l1) == (b2, l2)

When the bounds and the indices are linear, this question is in Presburger arithmetic, which a solver can decide. Here the answer is no: b1 != b2 and b1 == b2 cannot both be true. Tools such as isl, Pluto and LLVM's Polly, and MLIR's affine dialect with its Presburger library, ask such questions all day. The answers prove that a loop can run in parallel, and they let a compiler tile, fuse and reorder loops without changing the result.

The Vx checker today asks a smaller form of this question, with patterns (src/hir/check/across_proof.rs). An index fixes b when its terms are the digits of a mixed-radix number, as in b * 64 + l with l below 64. A plan to replace the patterns with iteration domains and one query to z3 is in #3561.

Where the model stops

The model is exact inside its limits, and the limits are narrow:

The last limit is the one that matters here, and it is not a weakness of the analysis. The values of idx do not exist when the compiler compiles the kernel, so no analysis of the kernel can find them. The fact is not hard to find. It is absent.

Two old answers exist. An inspector reads the index array at run time, before the loop, and picks a parallel or a serial version of the loop. That costs a pass over the indices before each run of the loop. The sparse polyhedral framework keeps the index array in the model as an unknown function, and adds facts about it, such as “no two elements are equal” (Strout, Hall and Olschanowsky, Proceedings of the IEEE, 2018, give an overview). With such facts, a compiler can drop dependences that it must otherwise keep, or check them with a cheaper inspector (Mohammadi and others, PLDI 2019). But someone must supply the facts.

Distinct: the fact, in the type

Vx lets the programmer supply the fact, in the type of the parameter. Change one type in the kernel:

idx : &Distinct<Tensor<i32, [?], Memory::HBM>>

and the kernel compiles. The caller makes the tensor with Distinct::check. It sorts a copy of the values on the CPU, and gives None when two are equal:

match Distinct::check(tokens) {
  Option<Distinct<Tensor<i32, [?]>>>::Some(rows) => {
    let on_gpu = transfer(rows, Memory::HBM);
    add_to_rows(&mut y, &on_gpu, &x);
  }
  Option<Distinct<Tensor<i32, [?]>>>::None => {
    println!("a token is in the list twice");
  }
}

This is the inspector from the last section, with one change: the type keeps its verdict. The program pays for one sort when it makes the tensor, and every launch that takes the tensor after that pays nothing. A program that made the indices itself, and knows that they differ, can skip the sort with unsafe { Distinct(tokens) }.

A function of the library can also make the claim. nn_moe_group in std::nn groups the token-expert pairs of a mixture-of-experts layer by expert, with a counting sort on the GPU. It returns the grouped order as a Distinct tensor. Its one unsafe { Distinct(order) } is inside the library, so the caller needs no check and no unsafe, and the expert ids do not go back to the CPU.

The fact is: if idx[a] == idx[b], then a == b. The checker uses it in one way. A read idx[e] becomes a new variable of the pass, and that variable fixes whatever e fixes. So idx[b] fixes b, as b does. The new variable then takes part in the old rules. (idx[b] as i64) * 4 + (l as i64), with l below 4, fixes b, as b * 4 + l does.

In the iteration-domain form of #3561, idx becomes an unknown function. The race query compares two passes, b1 and b2, so it needs the fact only for those two: idx(b1) == idx(b2) => b1 == b2. The domain and the accesses do not change, and the query has no quantifiers. It stays in a logic that z3 decides (QF_UFLIA: integers, linear terms and unknown functions, with no quantifiers).

Today only the race checker reads the fact. Both code generators lower a Distinct tensor as its tensor, and the optimizer does not use the fact yet.

Why the freedom is bounded

An escape hatch in a type system often turns off a check for a whole region of code. A cast does this, and so does an unsafe block around a loop. Distinct adds one fact about one tensor, and everything else stays checked:

y[idx[b]][0] = y[b][0] + 1.0;      // another pass may write row b
y[idx[b / 2]][0] = 1.0;                // passes 0 and 1 write row idx[0]
y[idx[b]][0] = y[idx[b + 1]][0];      // pass b + 1 writes that row

One case surprised us. With i64 elements, out[idx[b] * 4 + l] is still E6032. The elements are different, but idx[b] * 4 can wrap in 64 bits, and two different elements can then give the same index. With i32 elements cast to i64, the product cannot wrap, and the write compiles. The fact says that the elements differ. It says nothing about the arithmetic that follows.

After Distinct::check, no safe code can change the values, so the claim stays true. With unsafe { Distinct(t) }, the claim can be false. Then two passes write the same element. That is a data race, and Vx makes no promise about the result. This is what the unsafe means. But the program makes the claim at one line, where it makes the tensor, and only the code that fills the tensor needs an audit. A kernel that takes a Distinct has no unsafe in it.

We rejected three other designs:

What restrict can say

C has had one keyword for facts about memory since C99. A restrict pointer promises that, while it lives, an object changed through it is reached only through it. It is a fact about pointers: it says that y, idx and x do not overlap. Here is the same scatter-add, in C, with every pointer restrict:

void scatter_add(float *__restrict y, const int *__restrict idx,
                 const float *__restrict x, int n) {
  for (int i = 0; i < n; i++)
    y[idx[i]] += x[i];
}

clang 22, at -O3 -march=x86-64-v4, does not vectorize it:

scatter.c:5:15: remark: loop not vectorized: unsafe dependent memory operations in loop

clang is right. Two passes with the same idx value read and write one element of y, and restrict has no words for the values of idx. It cannot say that idx[i] and idx[j] differ, because the loop reads both through the same pointer.

C gets this loop through only by turning off the check for the whole loop: #pragma clang loop vectorize(assume_safety), #pragma GCC ivdep, #pragma omp simd, or #pragma omp parallel for for threads. With assume_safety, clang vectorizes the loop eight lanes wide, with a gather and a scatter. We ran both versions with 16 passes over 4 rows, each row 4 times, each pass adding 1:

plain:          4 4 4 4
assume_safety:  2 2 2 2

The pragma version is wrong, and nothing warned. That input breaks the promise, so the answer is fair by the rules of C. The point is what the promise covers. The pragma states that no two passes of the loop touch one element, for every access in the loop, and the compiler checks none of it. Distinct states one fact about one tensor, and the compiler checks the rest.

Three more limits of restrict:

restrictassume_safety, ivdep, ompDistinct
StatesTwo pointers do not overlapNo two passes touch one elementNo two elements of a tensor are equal
AboutPointersEvery access in a loopThe values in one tensor
Where it livesA parameter, dropped from the function typeA loopThe type, in the signature
CheckedNoNoEvery access by the compiler. The fact by Distinct::check at run time, or by no one after unsafe
Can state that idx has no repeatsNoOnly as part of a claim about the whole loopYes

What is left

Rows from a tensor of indices in the book has the rules and a program that runs. Vx is Apache 2.0 with the LLVM exception — install it, or read Parallel code on a GPU for the rest of the race checker.