Basically any parallel map-reduce operation using non-commutative reduce operators[0] is non-deterministic unless you specifically sort after/during the gather, or block on the gather (and gather to a thread-determined memory location). Sorting and blocking takes time. If you remove the sort/block, you will get a non-deterministic answer when operating on floats for a wide variety of reduce operations, but it will be faster. This is true of any parallel map-reduce, done anywhere (MPI, cuda kernels, openMP, spark, etc.), and is not unique to gpus/cuda.
> If you ask them to add a million floats in order, you get the same result every time.
There are a bunch of ways to add a million floats in order on a gpu, but they will all get you different results.:
* split the million floats into ‘n’ chunks, each chunk is summed, then you sum the ‘n’ results.
* if you sum results as they are gathered (you don’t need to block) you will get a non-deterministic result, as the threads finishing (outside of a warp) is non-deterministic in order.
* if you change ‘n’, your result will change.
* if you sort after gathering , your result will change.
TLDR: parallel race-conditions are nondeterministic. Map-reduce has an underlying race-condition that you can prevent, but it costs time/performance. Sometimes you don’t care about the non-determinism enough to pay the performance penalty to fix it.
Your comment, along with cpgxiii and n2d4’s are all really good. I have a question: suppose training and inference of an LLM were made to be deterministic at the cost of performance.
Would the cost be “everything will take twice as long” or would it be more like “inference will take a week and training will take a couple lifetimes”?
If it’s the latter, then it seems disingenuous to call this a “bug.” It’s like saying F1 cars could be horse drawn, and they only use internal combustion for “performance reasons.” If its the former, then maybe there is a more interesting discussion to be had about the potential benefits of determinism? (That said, I agree with n2d4 that it’s stupid to insult the authors. Talk is cheap and building is hard.)
> That said, I agree with n2d4 that it’s stupid to insult the authors. Talk is cheap and building is hard.
If your code offers an expectation of determinism then it's sloppy to not distinguish where there isn't determinism. There's nothing difficult about writing a comment to the effect of "this function is non-deterministic. For deterministic results, use X".
The code is sloppy if the developers didn't consider determinism and offer nothing to consumers, or if the consumers writing software cannot know where non-determinism is introduced.
If that's somehow insulting then I'd say someone has very thin skin.
Yes, if you eschew determinism for the sake of raw performance then the result will be non-deterministic. But you don't have to do this, nor is it inherently untenable to solve these problems in a deterministic way.
Sure it may require some performance overhead, and increase development time, but it's no different than writing deterministic code elsewhere. It's disingenuous to hand-wave away the solution because of some opaque cost or overhead we're unwilling to entertain. None of the parent posts ever mention performance tradeoffs.
In particular there is no indication that the problem being discussed couldn't be solved with determinism in an equivalent amount of time. You're making my point: GPUs are deterministic, software may decide not to be.
FWIW, I took “GPUs are deterministic” to mean they are deterministic in all possible intended use cases. This is not strictly true, since the whole point of using them is massive parallelism, which brings along non-determinism, for reasons that others have noted. Of course it’s possible to choose to forego that, but what is the point of a GPU in that case?
This is a false dichotomy. You can have massive parallelism and determinism.
You can trade determinism for convenience, but that doesn't make things easier: now you have to deal with the determinism.
But to suggest that massive parallelism somehow implies non-determinism is quite disingenuous from my perspective.
We have mutexes and lock-free ring buffers and stable sorts and all sorts of bells and whistles to make parallelism safe elsewhere. We also already have tools to solve this for GPUs.
> If you ask them to add a million floats in order, you get the same result every time.
There are a bunch of ways to add a million floats in order on a gpu, but they will all get you different results.:
* split the million floats into ‘n’ chunks, each chunk is summed, then you sum the ‘n’ results. * if you sum results as they are gathered (you don’t need to block) you will get a non-deterministic result, as the threads finishing (outside of a warp) is non-deterministic in order. * if you change ‘n’, your result will change. * if you sort after gathering , your result will change.
TLDR: parallel race-conditions are nondeterministic. Map-reduce has an underlying race-condition that you can prevent, but it costs time/performance. Sometimes you don’t care about the non-determinism enough to pay the performance penalty to fix it.
[0] https://www.microsoft.com/en-us/research/wp-content/uploads/...