Race Conditions Can Be Useful for Parallelism • Hacker News Board

Re: Race Conditions Can Be Useful for Parallelism

#21

Post by touisteur » Sun, Oct 02, 2022, 2:20 PM UTC

mgaunard wrote: post #16

touisteur wrote: post #7

Tell me about non guaranteed order of operations in GPU reductions and floating point results changing slightly between two runs. Yes it's useful and you get the goddamn FP32 TFLOPS, but damn it makes testing, validating, qualifying systems harder. And yes, I know one shouldn't rely and test on equality, but not knowing the actual order of FP operations makes numerical analysis of the actual error harder (just take t…

There is nothing wrong with testing for equality so long as your computation is exact or correctly-rounded.

Yes, I know. For purely sequential code that's the actual use (though sometimes, golden tests are generated through matlab or python, in double precision and then every divergence becomes a game of whack a mole. And don't start me on x87-80 bits extended precision suddenly compiled to SSE, so actual ieee754... We have integrated some of the FP static and dynamic analysis tools in our CI/CD pipeline for new code but ugh...

Anyway, as time passes by I veer off equality and think about the actual necessary accuracy and wish there was a way to set it as a spec for proof (SPARK/Ada or a higher level DSL that can be lowered to proper accuracy analysis tools...

I wish I could also specify 'no NaNs please' as a postcondition. Need to check in with the SPARK team and get an introduction article going...

Re: Race Conditions Can Be Useful for Parallelism

#22

Post by touisteur » Sun, Oct 02, 2022, 2:22 PM UTC

chrisseaton wrote: post #20

mgaunard wrote: post #16

Earlier quoted context omitted.

There is nothing wrong with testing for equality so long as your computation is exact or correctly-rounded.

I think some people have gotten the mistaken idea that floating point arithmetic is inherently somehow non-deterministic. It is of course entirely deterministic, and if you do the same FP operations in the same order you will get the same result.

I was thinking and talking specifically of GPUs and reductions (aka multiple core interacting) during which you don't always know the exact order of operations.

And also, tell that to the people that went from a compiler using x87 instructions to one using SSE instructions and between two binaries from the same code get different results. Yes, the exact same suite of FP instructions should always give the same results. And that's also supposing you're not loading some library that sets ugly fast-maths flags (see the recent yak-shaving session by @moyix).

Re: Race Conditions Can Be Useful for Parallelism

#23

Post by tialaramex » Sun, Oct 02, 2022, 2:25 PM UTC

tonyarkles wrote: post #11

User23 wrote: post #8

Earlier quoted context omitted.

It’s worth noting that algorithms can be designed correct under nondeterministic execution. For example, quicksort is correct with a randomly selected pivot. And for associative and commutative functions it doesn’t matter what order they’re executed in the final result is always the same. Dijkstra’s guarded commands don’t specify an order for the conditional. The semantics is that the process is free to execute any o…

> And for associative and commutative functions it doesn’t matter what order they’re executed in the final result is always the same. Not directed at you specifically, but just a reminder for anyone who hasn’t been burned by it yet: floating point addition is not associative. (a+b)+c != a+(b+c). It’s close, but if you’re not careful you can get bad results where the accumulated small errors turn into wrong answers.

Not just floating point maths either. The built-in "integers" in your computer don't behave like the integers taught in school either but that's how we tend to think about them. This is why I argue trapping is the most acceptable choice for arithmetic problems in general purpose languages, if the program tries to add 150 to 150 in an unsigned 8-bit integer, that's a programming error. By all means offer wrapping arithmetic, sometimes it's what the programmer actually wanted and they benefit from being able to clarify that - but most often they didn't want that and would be astonished that 150 + 150 = 44.

Re: Race Conditions Can Be Useful for Parallelism

#24

Post by kazinator » Sun, Oct 02, 2022, 2:26 PM UTC

shwestrick wrote: post #17

bheadmaster wrote: post #3

Slight nitpick - the definition of "race condition" on Wikipedia [0] is: [...] the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events If we take the first example - Parallel BFS - the correctness of the output could be considered "system's substantive behavior". Properly implemented atomic checks (as demo…

Author here. I think it would be very strange to say that this code does not have a race condition. The whole point of the term is to identify circumstances where non-deterministic timing of events influences how you reason about correctness, which is exactly what we're doing here.

If we put on a cynical hat, your page reads like "I've never heard of lock-free algorithms based on atomic operations. I therefore must have just invented it and I get to name it: how about beneficial use of race conditions?"

Re: Race Conditions Can Be Useful for Parallelism

#25

Post by [deleted] » Sun, Oct 02, 2022, 2:27 PM UTC

touisteur wrote: post #22

chrisseaton wrote: post #20

Earlier quoted context omitted.

I think some people have gotten the mistaken idea that floating point arithmetic is inherently somehow non-deterministic. It is of course entirely deterministic, and if you do the same FP operations in the same order you will get the same result.

I was thinking and talking specifically of GPUs and reductions (aka multiple core interacting) during which you don't always know the exact order of operations. And also, tell that to the people that went from a compiler using x87 instructions to one using SSE instructions and between two binaries from the same code get different results. Yes, the exact same suite of FP instructions should always give the same result…

[deleted]

Re: Race Conditions Can Be Useful for Parallelism

#26

Post by ajross » Sun, Oct 02, 2022, 2:27 PM UTC

chrisseaton wrote: post #15

ajross wrote: post #13

Earlier quoted context omitted.

That definition seems to conflate "determinism" (something largely impossible to achieve in asynchronously parallel systems) with "correctness" (an abstracted property of a system that doesn't have anything to do with determinism per se). It just doesn't seem useful. No, in overwhelmingly common usage, programmers use the term "race condition" as a category of software bug. We mean it in the correctness sense, not th…

> That definition seems to conflate "determinism" (something largely impossible to achieve in asynchronously parallel systems) There are plenty of examples of entirely deterministic parallel models. Fork-join for one.

I think you missed the point. Let me expand.

I mean, yes, what you say is true, but it just amounts to saying "synchronization is a solvable problem". At their core, ALL synchronization paradigms (spin polling, interrupt masking, OS-managed process suspend, hardware memory barriers, weird lockless tricks like Dekker's algorithm, you name it) can be understood to be ways of enforcing "para-determinism" on environments that don't provide it.

In SMP, things don't happen in reliable orders. They don't. They never will. They can't. But your hardware and OS platforms are smart and provide trickery so that at least you can guarantee that "some" things happen in reliable orders. And then you construct software such that correct behavior is dependent only on that subset of ordering and not everything.

Because there is no determinism in SMP, only that which you construct.

Re: Race Conditions Can Be Useful for Parallelism

#27

Post by nextaccountic » Sun, Oct 02, 2022, 2:28 PM UTC

mgaunard wrote: post #16

touisteur wrote: post #7

Tell me about non guaranteed order of operations in GPU reductions and floating point results changing slightly between two runs. Yes it's useful and you get the goddamn FP32 TFLOPS, but damn it makes testing, validating, qualifying systems harder. And yes, I know one shouldn't rely and test on equality, but not knowing the actual order of FP operations makes numerical analysis of the actual error harder (just take t…

There is nothing wrong with testing for equality so long as your computation is exact or correctly-rounded.

There is if the algorithm contains race conditions that cause non-deterministic output. The submitted article goes above and beyond to guarantee that the code always output the same answer even though it has race conditions. But that's sometimes not possible or, if it's possible, it's too much of a hassle so it's rarely done.

For example, this project https://github.com/EmbarkStudios/texture-synthesis generates textures and if you run the same code with the same input various times, the results will be slightly different. Here https://github.com/EmbarkStudios/texture-synthesis#notes it says: "When using multiple threads for generation, the output image is not guaranteed to be deterministic with the same inputs. To have 100% determinism, you must use a thread count of one"

Re: Race Conditions Can Be Useful for Parallelism

#28

Post by bheadmaster » Sun, Oct 02, 2022, 2:29 PM UTC

shwestrick wrote: post #17

bheadmaster wrote: post #3

Slight nitpick - the definition of "race condition" on Wikipedia [0] is: [...] the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events If we take the first example - Parallel BFS - the correctness of the output could be considered "system's substantive behavior". Properly implemented atomic checks (as demo…

Author here. I think it would be very strange to say that this code does not have a race condition. The whole point of the term is to identify circumstances where non-deterministic timing of events influences how you reason about correctness, which is exactly what we're doing here.

I've personally only heard the term "race condition" used to refer to bugs that have their source in non-deterministic execution of programs. In most cases, they refer to a specific sequence of events that the programmer did not foresaw, which lead to incorrect computation.

Using the term "race condition" in context of correct programs would make it cover exactly the same universe of programs as the term "non-determinism". I that think the distinction, however trivial (race condition = incorrect behavior, non-determinism = correct behavior), is still useful.

Great article, by the way. I did not mean to criticize it in any way. My "slight nitpick" about meaning of the words is really just that - a nitpick :)

Re: Race Conditions Can Be Useful for Parallelism

#29

Post by nextaccountic » Sun, Oct 02, 2022, 2:33 PM UTC

chrisseaton wrote: post #20

mgaunard wrote: post #16

Earlier quoted context omitted.

There is nothing wrong with testing for equality so long as your computation is exact or correctly-rounded.

I think some people have gotten the mistaken idea that floating point arithmetic is inherently somehow non-deterministic. It is of course entirely deterministic, and if you do the same FP operations in the same order you will get the same result.

You get the same result if you run on the same architecture and with the same instructions (or if you run on machines that implement IEEE 754-2008 [*], which was the first standard that guaranteed cross-platform determinism for a subset of floating point operations, which means, no SIMD!! =/), and you don't have non-determinism introduced by thread interleaving and race conditions (unless you very carefully account for that, like the article submitted in this thread)

I wish we had a language that guaranteed that the results of a computation were deterministic, all the while it properly enabled the use of all available hardware resources (so: using SIMD, all CPU cores, and also offloading some code to the a GPU if available), even if it had some overhead. Doing this manually is ridiculously difficult if you want to write high performance software, specially if you use GPUs.

[*] See https://stackoverflow.com/questions/42181795/is-ieee-754-200... - the amazing Rapier physics engine https://rapier.rs/ leverages IEEE 754-2008 to have a cross-platform deterministic mode that will run physics exactly the same way in every supported platform https://rapier.rs/docs/user_guides/rust/determinism/ - but this means taking a huge performance hit: you can't use SIMD and you must run the physics on a single thread.

Re: Race Conditions Can Be Useful for Parallelism

#30

Post by bheadmaster » Sun, Oct 02, 2022, 2:36 PM UTC

ajross wrote: post #13

chrisseaton wrote: post #6

Earlier quoted context omitted.

I don't know where Wikipedia got this 'substantive behaviour' requirement from, but for example it explicitly isn't part of the definition in the industry's definitive reference for parallelism - Padua. > A race condition occurs in a parallel program execution when two or more threads access a common resource, e.g., a variable in shared memory, and the order of the accesses depends on the timing, i.e., the progress o…

That definition seems to conflate "determinism" (something largely impossible to achieve in asynchronously parallel systems) with "correctness" (an abstracted property of a system that doesn't have anything to do with determinism per se). It just doesn't seem useful. No, in overwhelmingly common usage, programmers use the term "race condition" as a category of software bug. We mean it in the correctness sense, not th…

> No, in overwhelmingly common usage, programmers use the term "race condition" as a category of software bug

This was exactly my point.

    race condition = incorrect behavior
    non-determinism = correct behavior

Language is tricky sometimes.