Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Race Conditions Can Be Useful for Parallelism

shwestrick.github.io

Post reply on HN
Print view View original

11–20 of 72 posts

Re: Race Conditions Can Be Useful for Parallelism

#11

Post by tonyarkles »

User23 wrote: post #8
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…

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.

Re: Race Conditions Can Be Useful for Parallelism

#13

Post by ajross »

chrisseaton wrote: post #6
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…

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 the one used in the linked article nor your reference. You'd be met with some very weird stares if you tried to explain how arbitrary SMP ordering of log entries or whatever was a "race condition".

Re: Race Conditions Can Be Useful for Parallelism

#14

Post by ajross »

User23 wrote: post #8
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…

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…

> It’s worth noting that algorithms can be designed correct under nondeterministic execution.

In fact the whole concept of "symmetric multiprocessing" demands it.

Re: Race Conditions Can Be Useful for Parallelism

#15

Post by chrisseaton »

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…

> 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.

Re: Race Conditions Can Be Useful for Parallelism

#16

Post by mgaunard »

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.

Re: Race Conditions Can Be Useful for Parallelism

#17

Post by shwestrick »

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.

Re: Race Conditions Can Be Useful for Parallelism

#18

Post by shwestrick »

heydenberk wrote: post #12

I appreciate a provocative title, but I think the practical lesson in almost all cases is the inverse: fixing race conditions can introduce performance bottlenecks.

Author here. It all depends on what the goal is. If performance is the goal, then perhaps race conditions can be considered acceptable, if the gains are significant enough.

I would hope that the primary takeaway from this post is that race conditions are not necessarily bugs. Race conditions are not necessarily something that need to be "fixed".

Re: Race Conditions Can Be Useful for Parallelism

#19

Post by shwestrick »

compressedgas wrote: post #2

This reminds me of Kuper and Newton's LVars paper that introduces lattice variables in Haskell: https://users.soe.ucsc.edu/~lkuper/papers/lvars-fhpc13.pdf http://dx.doi.org/10.1145/2502323.2502326

Yes! It's a very similar idea. If I remember correctly, LVars are restricted enough to enforce determinism statically, which is quite nice.

Re: Race Conditions Can Be Useful for Parallelism

#20

Post by chrisseaton »

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.

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.
Post reply on HN