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 typeDistinct<..>lets the programmer add the one missing fact: no two elements ofidxare equal. A check on the CPU, or anunsafeblock, supplies the fact, and the compiler still checks everything else. C'srestrictcannot 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:
- Linear forms only. A bound or an index must be a sum of variables times
constants.
i * jis outside the model, and so isb * nwhennis a value that the program reads. - No control that depends on data. An
ifon a value from memory is not an inequality on the point. A tool must take both ways. - Arrays must not overlap. The model gives each array its own space. In C, two
pointers can point into one array, so a tool must first prove that they do not, or be told.
That is the job of
restrict. - Cost. Integer programming is NP-complete. Tools are fast on the small loop nests of real programs, but a compiler must bound the time it spends.
- Indices from memory.
y[idx[b]]mapsbto a value that the program loads. The model has no term for it, so a tool must assume that the write can touch any row. The loop is then not parallel.
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:
- Making one needs a check or
unsafe.Distinct::check(t)checks the values.Distinct(t)does not, and outside anunsafeblock it is E5001. Both take only a tensor of integers with one dimension (E3004), and both movet, so no old name can change the values later. - It is read only. A write to an element is E4006, because a write could make two elements equal.
- It is in the signature. The caller makes the claim, and the kernel relies on it. Neither needs the body of the other. This is a rule of Vx: a function's signature is its whole contract, so the compiler can check each function by itself, in parallel.
- Only a parameter counts. A
Distinctlocal or field does not fixb, and neither does a parameter whose name the body binds again. - Every other access is still checked. Each of these is still E6032:
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:
- A
requiresclause,requires idx.distinct(), checked on the host at each launch. Each launch pays for a pass over the indices, and the fact does not travel to the next function.Distinct::checkpays once, and the type carries the result. unsafeon each write. That turns off the check at each place, and it states nothing about the data.- Finding the fact in the caller. The values come from the router at run time, so no analysis of the caller can see them either. And a check that reads the caller's body breaks the rule that a signature is the whole contract.
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:
- It is not part of the function's type. In C11 (6.7.6.3), the compiler drops
a qualifier on a parameter when it compares two function types. So
void f(int *restrict p)andvoid f(int *p)declare the same function, and a caller learns nothing from the declaration. - C++ has no
restrict.__restrictis an extension of each compiler, not a part of the standard. - Nobody checks it. A false
restrictis undefined behavior, with no diagnostic. The definition (C11 6.7.3.1) is hard to read, and compilers use a part of it, such as LLVM'snoaliason function parameters.
restrict | assume_safety, ivdep, omp | Distinct | |
|---|---|---|---|
| States | Two pointers do not overlap | No two passes touch one element | No two elements of a tensor are equal |
| About | Pointers | Every access in a loop | The values in one tensor |
| Where it lives | A parameter, dropped from the function type | A loop | The type, in the signature |
| Checked | No | No | Every access by the compiler. The fact by Distinct::check at run time, or by no one after unsafe |
Can state that idx has no repeats | No | Only as part of a claim about the whole loop | Yes |
What is left
- Speed of the grouping.
nn_moe_groupran correctly on an H200, and its speed is still being tuned. - The optimizer. #3561 plans to pass the fact to MLIR, so that tiling and fusion can use it too.
- The combine. A token goes to several experts, and their results add into one row. That is a scatter-add with repeats on purpose, so it still needs atomics or a separate pass.
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.