6
$\begingroup$

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)

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the succinct explanation of SC. This is the best I've read so far. I did not want it to end :) Could you please also explain what "race free" is then, as you say it is different from data race free and SC? $\endgroup$ – sanatana Aug 10 '14 at 22:06
  • $\begingroup$ "Race free" means that both your data and your synchronization are "race free", which means that your synchronization must be deterministic. (A "race" is an ordering that is determined (resolved) by a non-deterministic process.) There are deterministic synchronization systems (e.g. groups.csail.mit.edu/commit/papers/09/asplos073-olszewski.pdf) but they are unusual, and this isn't one. $\endgroup$ – Wandering Logic Aug 11 '14 at 0:01
  • $\begingroup$ Personally, I would prefer that nobody use the term "racey" or "race-free" with respect to synchronization operations. I'd prefer that they used "non-deterministic" and "deterministic" for the resolution of who acquires a mutex. And thus I'd prefer that the word "race" always be preceded by the word "data." $\endgroup$ – Wandering Logic Aug 11 '14 at 0:06
  • $\begingroup$ You say "the compiler is not allowed to reorder operations on data objects with respect to operations on synchronization objects." - Isn't the (C++) compiler (and CPU) allowed to reorder per the implicit acquire/release characteristics of SeqCst operations ? (that is, reorder operations on data objects one-way with SeqCst stores and reorder them in opposite direction with SeqCst loads) $\endgroup$ – LWimsey Dec 29 '17 at 22:28
  • $\begingroup$ @LWimsey Yes, I think you are correct. My answer was already too long, so I was imprecise with respect to acquire/release. $\endgroup$ – Wandering Logic Dec 30 '17 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.