Hacker News Reader

Comment by jiggawatts | Hacker News Reader

Floating point inaccuracies are generally deterministic - running the same calculations twice ought to yield the same results, down to the bit.

You only get divergent results if there is some other source of state or entropy: not zeroing buffers correctly, race conditions, not setting rounding mode flags consistently, etc…

From the quality of the code I’ve seen being cobbled together in the AI/ML ecosystem I would assume all three of those issues going on, and maybe more.

View on HN

No, this is not true for GPUs. https://www.twosigma.com/articles/a-workaround-for-non-deter...

(In this particular case, the order in which the numbers are summed up is non-deterministic due to GPU parallelism, which may change the result slightly.)

I would generally refrain from insulting other people's code if you don't know much about the system it's written on.

Editing here since all the replies to this are mostly saying the same thing: Yes, CPUs can also be parallel and it can happen there as well, but unlike a CPU where most instructions on their own are deterministic, CUDA provides primitives that aren't. This is very much by design (as they're faster than their deterministic counterparts), and I mostly just take issue with how parent phrased this as a bug caused by bad code.

GPUs are deterministic machines, even for floating point.

The behavior in the linked article has to do with the use of atomic adds to reduce sums in parallel. Floating point addition is not associative, so the order in which addition occurs matters. When using atomic adds this way, you get slightly different results depending on the order in which threads arrive at the atomic add call. It's a simple race condition, although one which is usually deemed acceptable.

I just edited my comment while you were writing your comment to add an explanation. The point here is that some primitives in eg. cudNN are non-deterministic. Whether you classify that as a race condition or not is a different question; but it's intended behaviour.

Right but that's not an inherent GPU determinism issue. It's a software issue.

https://github.com/tensorflow/tensorflow/issues/3103#issueco... is correct that it's not necessary, it's a choice.

Your line of reasoning appears to be "GPUs are inherently non-deterministic don't be quick to judge someone's code" which as far as I can tell is dead wrong.

Admittedly there are some cases and instructions that may result in non-determinism but they are inherently necessary. The author should thinking carefully before introducing non-determinism. There are many scenarios where it is irrelevant, but ultimately the issue we are discussing here isn't the GPU's fault.

What I'm saying is "there are non-deterministic primitives", not "there are no deterministic primitives".

Yes, and `gettimeofday` is a non-deterministic primitive. There is nothing special about GPUs here. If you write tests that fail sometimes because you used non-deterministic primitives like gettimeofday and someone files a bug we don't throw up our hands and say "this is not a bug but due to how CPUs work." We remove the non-deterministic bit.

There's no difference here. This isn't a GPU problem.

Except the issue is inextricably linked to GPUs. All of the work in practical DNNs exists because of the extreme parallel performance available from GPUs, and that performance is only possible with non-deterministic threading. You can't get reasonable training and inference time on existing hardware without it.

1000 threads can run in parallel. It doesn't prevent us to sum their results deterministically:

    results = ThreadPool(workers=1000).imap_unordered(calc, inputs)
    print(math.fsum(results))

Due to the magic of the fsum alg, the result is deterministic whatever order we get results in. https://docs.python.org/3/library/math.html#math.fsum

That's not the operation being performed on GPUs that is the problem. The issue is that fundamentally GPUs allow for high performance operations using atomics, but this comes at the cost of nondeterministic results. You can get deterministic results but doing so comes with a significant performance costs.

Using atomics is easier than warp operations (using warp shuffle for example), but warp shuffle is quite fast.

I guess if determinism is so important implementations can be changed, it is just maybe not that high priority.

That summation is slow and would not be used in practice.

You could use just one thread on your 10000 thread GPU too and it would be deterministic, sure. Completely beside the point.

In my experience cuBLAS is deterministic, since matmul is the most intensive part I don‘t see other reasons for non-determinism other than sloppyness (at least when just a single GPU is involved)

Yeah. In curated transformers [1] we are seeing completely deterministic output across multiple popular transformer architectures on a single GPU (there can be variance between GPUs due to different kernels). Of course, it completely depends on what ops and implementations you are using. But most transformers do not use ops that are typically non-deterministic to be fast (like scatter-add).

One non-determinism we see with a temperature of 0 is that once you have quantized weights, many predicted pieces will have the same probability, including multiple pieces with the highest probability. And then the sampler (if you are not using a greedy decoder) will sample from those pieces. So, generation is non-deterministic with a temperature of 0.

In other words, a temperature of 0 is a poor man’s greedy decoding. (It is totally possible that OpenAI’s implementation switches to a greedy decoder with a temperature of 0).

[1] https://github.com/explosion/curated-transformers

If the hardware is deterministic, so are the results. You can't generate random numbers purely in software with deterministic hardware.

The behaviour of atomic operations is definitely not deterministic. E.g. if you have a lot of atomic adds, every time you run the code you'll get a different result without a random number generator.

Read the article you linked.

It literally says that the GPU is deterministic, the NVIDIA libraries on top are deterministic, but it is Tensorflow that introduces variability (errors!) for “performance”.

My argument is that it is the AI/ML code that is introducing non-determinism, usually by sacrificing repeatability to gain performance.

That's precisely what's happening here. Tensorflow introduced a "harmless"[1] data race to improve performance by not having to use a deterministic but slower algorithm.

The individual floating point computations are deterministic, it's the multi-threaded design on top that's introducing the variability in the output.

[1] Used to be harmless, but cutting corners like this will make it nigh impossible to repeatably validate the safety of future models like GPT5. That seems pretty dangerous...

As the article says, cuBLAS is deterministic, but other CUDA primitives (eg. some of those in cudNN) are not.

Yes, the non-determinism is being introduced somewhere, but that is splitting hairs. The point is that the primitives that you work with on GPUs are non-deterministic by design.

I mostly take issue with you phrasing it as a bug and using it to insult the authors.

How is that splitting hairs?

> The point is that the primitives that you work with on GPUs are non-deterministic by design.

This is just blatantly wrong. There are _some_ operations that can be non-deterministic in some scenarios but they are not necessary.

GPUs are deterministic. If you ask them to add a million floats in order, you get the same result every time. If you ask them to add a million floats in some arbitrary order, then you may get different results every time. The distinction is that someone had to ask the GPU to do that. It's a choice.

> I mostly take issue with you phrasing it as a bug and using it to insult the authors.

It's a bug, whether it insults the authors or not is irrelevant. It's most definitely a bug.

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.

[0] https://www.microsoft.com/en-us/research/wp-content/uploads/...

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.

There are flags[1] for that indeed. It feels like half of the people commenting here don't know all that much about the topic they're commenting upon

1: https://pytorch.org/docs/stable/generated/torch.use_determin...

Nothing I said conflicts with this, though?

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.

I think whether it’s a bug or not depends on the software requirements and expectations. If the code has some expected bounds on runtime, switching the GPU code to sequential processing (for the sake of exact reproducibility) would break that expectation and could be considered a bug as well. If we expect performant code and exact reproducibility, that just might not be possible…

It's hard to call it a bug given that any concurrent float sum or product will be different in regards to changing the amount of concurrency. Even if you order the final value per thread before reducing the result will differ if you use a different amount of threads to split the problem.

Because in floating point arithmetic 1 + 2 + 3 + 4 is different than (1+2) + (3+4).

To nitpick in addition to the already existing comments: this has nothing to do with GPUs per se. You would see the same issue in multithreaded code on a CPU. Even on a single core CPU this can happen with a multithreaded program depending on how the OS schedules and interrupts the threads. It just happens to be an implementation choice in a GPU library/API.

As far as I can tell this article doesn't explain why this happens on the GPU (for example, why Tensorflow's reduce_sum is non-deterministic). My hypothesis is that this is entirely due to concurrency: if the same code can be run in two or more different interleavings, they can produce different results. This is corroborated by the first answer here [0].

If so, this exact same issue happens in CPU code as well: have two or more threads, run the program many times, observe different interleavings that expose race conditions which (depending on the algorithm) may or may not produce different results. This can happen even if you don't use floating point, and has nothing to do with floating point non-determinism itself. For example, have a thread print "Hello" and another thread print "World"; even without tearing, you may see either Hello World or World Hello on the screen.

Now, proper floating point non-determinism happens in two cases. One is that when you run the same code in two different architectures you could have different answers (because of rounding modes, or because some architecture doesn't support subnormal numbers or signaling nans, because transcedental functions like sine are implemented with different accuracy, etc). In this case it's deterministic when run the same in the same machine, but may run differently in another machine with a different architecture.

The other case is that some "optimizations" actually break your code if applied carelessly (you enable those broken optimizations with -ffast-math in C for example). Among other things, this may break numerical stability of algorithms like Kahan summation. And, if you let the compiler decide which exact optimizations will be applied and in what order, you get non-determinism between different compilers. So in this case it's deterministic when compiled with the same compiler, but may run differently with another compiler.

[0] https://stackoverflow.com/questions/50744565/how-to-handle-n...

You've moved the goal posts. You're conflating CUDA with GPUs. From Wikipedia:

> CUDA (or Compute Unified Device Architecture) is a proprietary and closed source parallel computing platform and application programming interface (API) that allows software to use certain types of graphics processing units (GPUs) for general purpose processing, an approach called general-purpose computing on GPUs (GPGPU). CUDA is a software layer that gives direct access to the GPU's virtual instruction set and parallel computational elements, for the execution of compute kernels.

Is the issue we're discussing because of the GPU or is it because of choices made in software libraries?

The parent is right, there is a deterministic, reproducible way to solve these problems, so if determinism is a desired or expected property, then this is a bug. It's not an inherent problem like you make it out to be. The fact that "workarounds" are given in what you link prove this.

it’s basically always reasonable to insult someone’s code because we are computer programmers and we know what we have done

I don’t know about how insulting it is, I don’t like rushing things out but we’ve all had to.

People are rushing like crazy to get there first with X for AI all over the place, it would be pretty shocking if there weren’t wires sticking out everywhere.

I don’t think that says anything positive or negative about the hackers involved.

The PyTorch documentation has an entire section about how to make your code deterministic. In my experience, the performance difference is negligible.

https://pytorch.org/docs/stable/notes/randomness.html#avoidi...

Unfortunately, determinism across devices or even driver versions is not that easy. You'd have to write your own BLAS kernels using only basic operations, which are guaranteed to follow IEEE 754 semantics.

https://docs.nvidia.com/cuda/floating-point/index.html

One gotcha are fused multiply-adds, which the compiler may or may not introduce, so you have to wrap all your floating point operations with __fma* intrinsics to make sure the compiler does not interpret them differently.

So you can generate true random numbers using just the GPU parallelism? Consider me impressed!

Yes you can, and it's been done:

https://link.springer.com/article/10.1007/s11071-015-2287-7

There isn't much of a culture around code quality in ML / AI / DS.

It's not a code quality issue, there are ways to ensure determinism (sometimes you just need to set a flag), however, they are intentionally explicitly not used in order to gain performance.

> I would generally refrain from insulting other people's code if you don't know much about the system it's written on.

Well, the general state of how utterly shoddy most of the code in the AI/ML ecosystem is is observable to anyone trying to follow a guide on how to set up Stable Diffusion on AWS. It's a fucking mess of trying various combinations of driver versions, Ubuntu kernel versions, Python versions, and the fact that Python requirements.txt (similar to NodeJS) doesn't pin versions of transitive dependencies doesn't make it easier because it makes for very brittle and not reproducible builds/guides. Oh, and at least some of that stuff won't work without root.

Yeah I'll keep AI shit cordoned off in its own subnet.

Years before ChatGPT I made the joke that AI would want to take over the world like a computer virus, but it’s written in Python, so it can’t figure out how to install itself on other computers.

I think the joke was on Twitter, RIP.

I 'member that joke. Think it must have gone around while OpenStack transitioned from Python 2 to 3. What a fucking mess.

What you said can be violated when parallelism is involved. One such example is that we know some floating point operations such as addition and multiplication are non-commutative, hence it depends on order of execution to complete reduction for example. And then in parallel situation, some implementation will make the order or reduction non-deterministic (for performance reason) and hence the final result also non-deterministic.

It's still deterministic even if the results appear not to be. If you have memory, CPU cache, CPU registers in the same state, you will get the very same results. You need a source of entropy for the results to be non deterministic.

Sure, but they will never be in the same state, which can even be used as a source of entropy: https://link.springer.com/article/10.1007/s11071-015-2287-7

Actually, clock domain crossing for asynchronous clocks (as is AFAIK typical for granular dynamic frequency scaling, like running CPU cores at individual frequencies instead of all at the same, because it quite softly smoothes over to any new target frequency to prevent glitches) implicitly includes thermal noise in the raw transistors that determine which of the two involved clock edges happened earlier (a decision that eventually ends up truly random when they are at (almost) exactly the same time). And this is involved in even L3 hit latency.

Minor nit but commutative is the wrong term. Floats always obey a+b == b+a, but not associativity: (a+b)+c != a+(b+c).

Right!

Mathematically, computation is deterministic. The author dismisses or ignores the many ways that the physical apparatus driving the computation can force the result of a software application to be a function of time.

Calling GetTimeOfDay() could do it.

Clock frequency drift between multiple processors could it.

When theory fails to consult reality.

Quantum computer is under the category of computers.

Quantum computation relied on Quantum mechanics.

Quantum mechanics are not deterministic.

So, Quantum computers are not deterministic.

Therefore, unless P=NP, not all computations are deterministic.

hmm, how, I wonder if Alhazen’ s Circular Billiard Problem[1] results for n steps in simulation will be same for multiple runs.

[1] https://forumgeom.fau.edu/FG2012volume12/FG201216.pdf

On a large scale, not having memory with good ECC is enough to have entropy.

Small nit. You mean errors due to floating point math

Reply on news.ycombinator.com