4 ms·

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

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.

n2d4 3y ago
No, this is not true for GPUs. https://www.twosigma.com/articles/a-workaround-for-non-determinism-in-tensorflow/ 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.
- Tunabrain 3y ago
  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.
  - n2d4 3y ago
    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.
    - xyzzy_plugh 3y ago
      Right but that's not an inherent GPU determinism issue. It's a software issue. https://github.com/tensorflow/tensorflow/issues/3103#issuecomment-422062420 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.
      - n2d4 3y ago
        What I'm saying is "there are non-deterministic primitives", not "there are no deterministic primitives".
        xyzzy_plugh 3y ago
        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.
        cpgxiii 3y ago
        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.
- jiggawatts 3y ago
  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...
  - n2d4 3y ago
    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.
    - xyzzy_plugh 3y ago
      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.
      - spott 3y ago
        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/2016/02/icsecomp14seip-seipid15-p.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- ascar 3y ago
  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.
- nextaccountic 3y ago
  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-non-determinism-when-training-on-a-gpu https://stackoverflow.com/questions/50744565/how-to-handle-n...
- DeathArrow 3y ago
  So you can generate true random numbers using just the GPU parallelism? Consider me impressed!
  - WithinReason 3y ago
    Yes you can, and it's been done: https://link.springer.com/article/10.1007/s11071-015-2287-7 https://link.springer.com/article/10.1007/s11071-015-2287-7
- xyzzy_plugh 3y ago
  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.
- jes5199 3y ago
  it’s basically always reasonable to insult someone’s code because we are computer programmers and we know what we have done
- benreesman 3y ago
  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.
- johndough 3y ago
  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#avoiding-nondeterministic-algorithms 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 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.
- zx14 3y ago
  There isn't much of a culture around code quality in ML / AI / DS.
  - PeterisP 3y ago
    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.
- mschuster91 3y ago
  > 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.
  - earthboundkid 3y ago
    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.
    - mschuster91 3y ago
      I 'member that joke. Think it must have gone around while OpenStack transitioned from Python 2 to 3. What a fucking mess.
alexnewman 3y ago
Small nit. You mean errors due to floating point math
dwpdwpdwpdwpdwp 3y ago
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.
- water9 3y ago
  When theory fails to consult reality.
- stevefan1999 3y ago
  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.
neatze 3y ago
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 https://forumgeom.fau.edu/FG2012volume12/FG201216.pdf
KolenCh 3y ago
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.
- DeathArrow 3y ago
  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.
  - WithinReason 3y ago
    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 https://link.springer.com/article/10.1007/s11071-015-2287-7
  - namibj 3y ago
    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.
- toxik 3y ago
  Minor nit but commutative is the wrong term. Floats always obey a+b == b+a, but not associativity: (a+b)+c != a+(b+c).
  - 3y ago
DeathArrow 3y ago
On a large scale, not having memory with good ECC is enough to have entropy.

n2d4 3y ago

No, this is not true for GPUs. https://www.twosigma.com/articles/a-workaround-for-non-determinism-in-tensorflow/ 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.

Tunabrain 3y ago
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.
- n2d4 3y ago
  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.
  - xyzzy_plugh 3y ago
    Right but that's not an inherent GPU determinism issue. It's a software issue. https://github.com/tensorflow/tensorflow/issues/3103#issuecomment-422062420 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.
    - n2d4 3y ago
      What I'm saying is "there are non-deterministic primitives", not "there are no deterministic primitives".
      - xyzzy_plugh 3y ago
        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.
        cpgxiii 3y ago
        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.
jiggawatts 3y ago
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...
- n2d4 3y ago
  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.
  - xyzzy_plugh 3y ago
    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.
    - spott 3y ago
      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/2016/02/icsecomp14seip-seipid15-p.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
ascar 3y ago
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.
nextaccountic 3y ago
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-non-determinism-when-training-on-a-gpu https://stackoverflow.com/questions/50744565/how-to-handle-n...
DeathArrow 3y ago
So you can generate true random numbers using just the GPU parallelism? Consider me impressed!
- WithinReason 3y ago
  Yes you can, and it's been done: https://link.springer.com/article/10.1007/s11071-015-2287-7 https://link.springer.com/article/10.1007/s11071-015-2287-7
xyzzy_plugh 3y ago
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.
jes5199 3y ago
it’s basically always reasonable to insult someone’s code because we are computer programmers and we know what we have done
benreesman 3y ago
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.
johndough 3y ago
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#avoiding-nondeterministic-algorithms 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 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.
zx14 3y ago
There isn't much of a culture around code quality in ML / AI / DS.
- PeterisP 3y ago
  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.
mschuster91 3y ago
> 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.
- earthboundkid 3y ago
  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.
  - mschuster91 3y ago
    I 'member that joke. Think it must have gone around while OpenStack transitioned from Python 2 to 3. What a fucking mess.

alexnewman 3y ago

Small nit. You mean errors due to floating point math

dwpdwpdwpdwpdwp 3y ago

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.

water9 3y ago
When theory fails to consult reality.
stevefan1999 3y ago
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.

neatze 3y ago

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 https://forumgeom.fau.edu/FG2012volume12/FG201216.pdf

KolenCh 3y ago

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.

DeathArrow 3y ago
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.
- WithinReason 3y ago
  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 https://link.springer.com/article/10.1007/s11071-015-2287-7
- namibj 3y ago
  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.
toxik 3y ago
Minor nit but commutative is the wrong term. Floats always obey a+b == b+a, but not associativity: (a+b)+c != a+(b+c).
- 3y ago

DeathArrow 3y ago

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