Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In the paper "Heterogeneous-Race-Free Memory Models" [1], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why this is. Can anyone explain how this can happen?
[1] Derek R. Hower et al., "Heterogeneous-Race-Free Memory Models". In Proceedings of ASPLOS '14, ACM, 2014. (PDF)
Hopefully they didn't say explicitly say exactly "a program consisting only of atomics is race free in SC-DRF." That's incorrect.
They do say that "[in] scoped synchronization ... it is possible to write a racey program that is composed entirely of atomics if those atomics do not use scopes correctly," [top of page 2], which is slightly different (and uses the word "racey" ambiguously, perhaps leading you to believe they meant the incorrect statement.) They perhaps should have instead said said that in scoped synchronization it is possible to write a non sequentially consistent program that is composed entirely of atomics if those atomics do not use scopes correctly.
SC-DRF (roughly: the memory semantics for C++ and Java) divide memory locations into two classes, synchronization objects, (sometimes called atomics), and data objects. For the most part all operations on synchronization objects are guaranteed to be sequentially consistent.[1] (Not race free.) This is a constraint on the compiler, not the programmer. It says that if the programmer says that one thread writes atomic object a then writes atomic object b, all the threads will see the writes occur in this order. (The compiler is not allowed to reorder the accesses, and is required to insert the appropriate memory barriers and fences on machines that aren't sequentially consistent.)
Sequentially consistent means that all threads on all processors agree on a total order of all memory operations. If one thread thinks that operation $x$ happened before operation $y$, all the threads think that operation $x$ happened before operation $y$. Sequentially consistent does not mean not racey and it does not mean deterministic. For example, two different threads could try to write the same synchronization variable at approximately the same time. These accesses will be racey. A sequentially consistent system will just guarantee that if one thread thinks that write $x$ happened before write $y$, all the threads will agree that write $x$ happened before write $y$. Sequential consistency is useful because you can use it to construct and reason about useful non-deterministic synchronization objects like mutexes and condition variables.
SC-DRF then says that if your program is data race free, the operations on data objects will appear to be sequentially consistent. The compiler is permitted to reorder (or even sometimes eliminate) operations on data objects, and if the underlying machine is not sequentially consistent, the compiler is not required to insert memory barriers or fences. But the compiler is not allowed to reorder operations on data objects with respect to operations on synchronization objects.
Data race free is not the same as race free. And sequentially consistent is not the same as race free. A particular program execution schedule is data race free if for any pair of data object accesses, $x$ and $y$, by two different threads (at least one of which is a write operation) we can use the (sequentially consistent) order of atomic object accesses to prove that either $x$ happened before $y$ or $y$ happened before $x$. If we can not do the proof then that execution schedule is data racey.
A program is data race free if all possible execution schedules are data race free. A program is data racey if there is an execution schedule that is data racey.
Being data race free is a constraint on the programmer, not the compiler. It says that if your program is data racey, then your program has no semantics. The compiler is allowed to do anything it wants, including halting the program, going into an infinite loop, or blowing up the computer.
Oh dear. TL; DR! I haven't even mentioned SC-for-HRC yet!
In SC-for-HRC the atomics need to specify what scope they belong to. Atomic accesses are guaranteed (by the compiler) to be sequentially consistent only within their own scope. All threads within the scope will agree about the order in which the atomic accesses occur, but threads in a different scope may not agree (and may not even be able to see the accesses at all, let alone their order.)
For example it might be the case that all the GPU threads agree that thread 19 acquired mutex A then acquired mutex B, but all the CPU threads do not agree (or know) that thread 19 acquired mutex A or mutex B at all. SC-DRF does not have "scopes" so doesn't suffer this problem.
[1] The exceptions to the sequentially consistent atomics have to do with explicitly using std::memory_order_relaxed. So don't do that. (And I'll ignore the exceptions in the rest of what I'm saying.)
