Race Conditions Can Be Useful for Parallelism
shwestrick.github.io
Race Conditions Can Be Useful for Parallelism
1–10 of 72 posts
Re: Race Conditions Can Be Useful for Parallelism
#2This 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
Re: Race Conditions Can Be Useful for Parallelism
#3Slight 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
Of course, the term "race condition" here is taken colloquially, for the sake of familiarity to the reader - the article has correctly recognized that the appropriate term for this kind of behavior is "non-determinism".
Re: Race Conditions Can Be Useful for Parallelism
#4Slight 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…
[deleted]
Re: Race Conditions Can Be Useful for Parallelism
#5Slight 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…
Why not use the right term, then? "Coloquial" shouldn't be a thing with technical terms.
Race conditions are hard enough to explain to people and misusing the term just makes it more difficult.
Re: Race Conditions Can Be Useful for Parallelism
#6Slight 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 of individual threads.
> The disposition for a race condition is in the parallel program. In different executions of the same program on the same input access events that constitute a race can occur in different order, which may but does not generally result in different program behaviors (non-determinacy).
Sometimes you deliberately program a full-on data race (which isn't a bug by definition, as the article says) for performance reasons.
> Data races that are not manifestations of program bugs are called benign data races.
Re: Race Conditions Can Be Useful for Parallelism
#7Tell 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 the worst case of every reduction, ugh).
EDIT: and don't get me started on tensor cores and clever tricks to have them do 'fp32-alike' accuracy. Yes, wonderful magic but how do you reason about these new objects without a whole new slew of tools.
Re: Race Conditions Can Be Useful for Parallelism
#8Slight 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…
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 one of the cases that has a true guard. Nevertheless he found them useful for developing and describing many algorithms.
Re: Race Conditions Can Be Useful for Parallelism
#9Slight 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…
Interesting, it's almost like one could call this a "randomized algorithm" (which we know can be faster than deterministic algorithms) but the non-determinism comes from the input data and code execution rather than a RNG.
Re: Race Conditions Can Be Useful for Parallelism
#10Slight 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…
Interesting, it's almost like one could call this a "randomized algorithm" (which we know can be faster than deterministic algorithms) but the non-determinism comes from the input data and code execution rather than a RNG.
[deleted]