0
$\begingroup$

I have read reviews of this book, and quote the following from one of the reviews (emphasis mine):

Other than straining your eyes with old-styled C++, you can read such misconceptions in the book like "Since Boolean values are generally atomic, setting and checking can be done simultaneously without risk or requiring a mutex." Which ignores the facts that, the compiler doesn't necessarily have to generate instructions to resync the value in register with the one in memory. And even if it does, the hardware doesn't have to resync the cache lines.

I have also followed all of the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube) and learned about cache coherency protocols.

From what I have learned, modern processors will use the write-invalidate protocol; when one core writes to a block, any other cores that share this same block will learn of the change via an invalidation message sent on the bus so they will have to go and get the new value from memory instead of using their cached copy.

With this in mind, what is the author of this comment talking about? It seems the coherency protocol is doing everything for me, hence there is no need to use synchronisation? Are they wrong or am I missing something?

PS Yes I know I mention C++ but I feel this is more hardware related hence me asking it here.

PPS If I've missed something, please post a link to the information before just downvoting; a downvote without explanation is useless.

Update

If a boolean b was being used in two threads, each one on a different core, what would making the variable atomic/using a sync variable do regarding the cache coherency that doesn't happen with a none-atomic var/no use of a sync variable? (I think this is the problem in my understanding - I am believing that the cache coherency protocol fires off "for free" (is this right?); or do I need to use some special instruction to "start it off" (that is, trigger the sending of the invalidation message on the bus) for want of a better phrase?)

Update 2

Write Invalidate Snooping Coherence - Georgia Tech - HPCA: Part 5 talks about how the caches of different cores operating on the same block are synchronized.

My confusion stems from the fact that the comment I quote seems to state that boolean values are not guaranteed to be synchronized between caches on different cores, and that some sort of atomic operation or synchronization primitive (eg mutex) is needed to do this. The video I link to however mentions nothing of the sort; it suggests (to me at least) that the caches are updated automatically by virtue of the coherency protocol, not by any special instructions (such as those generated for atomic operations or synchronization primitives) in the code. This is what I am asking for clarification on.

$\endgroup$
1
$\begingroup$

This is very simple actually, and has nothing to do with hardware whatsoever. If you have a variable

static bool b;

and some code

b = true;
dosomething();
b = false;
dosomethingelse();
b = true;

If the compiler can figure out that dosomething() and dosomethingelse() don't read or write b, then the compiler is not required to generate code for the assignments to b, except the last one.

With the book's subtitle "Write robust, concurrent, and parallel applications" this is quite worrying.

$\endgroup$
  • $\begingroup$ OK, thanks. You clearly understand this topic, so I have edited the question based on this comment; could you address this, and also comment as to why is this a problem in this code as-is; it doesn't seem to be!? $\endgroup$ – Wad May 2 at 12:41
  • 1
    $\begingroup$ @Wad its a little odd editing your question to add another clause after an answer is given, and expecting the one who answered to accommodate. $\endgroup$ – lox May 2 at 14:44
  • $\begingroup$ @lox, No, its not odd at all. Whereas the answer above is useful, it does not answer all of posed questions, specifically the part regarding what (if anything) atomic variables/sync primitives give me that I don't get automatically with the coherence protocol. My update merely elaborated this by using gnasher729's comment as context. $\endgroup$ – Wad May 2 at 16:08
1
$\begingroup$

There are at least three aspects to consider. And you are looking at only one of them.

The first aspect is transformation from the programming language to the machine language. A compiler is allowed to do a lot of things which may not be intuitive. And if it is not aware that you want an atomic variable, it may avoid to generate the instructions you expect and for instance keep a variable in a register in which case the cache coherence algorithm is not triggered. This is what the comment writer and @gnasher729 are referencing.

The second aspect is the cache coherence guarantees. That is, what the processors are seeing when you modify a single memory cell. Here you are right, on the majority of current systems, an access to a sufficiently small data residing in a single cache line is atomic without the need of further instructions than the load/store one.

The third aspect is the memory consistency guarantees. That is, what the processors are seeing when you modify several memory cells. Even if the cache is coherent and guarantee atomic access without further instructions, these may be needed if you want to ensure that their order appears consistent in the several processors.

C++ has means to indicate that a variable is atomic and to control the memory consistency properties you want, so that the compiler will generate the machine code needed for what you want. A C++ book which does not mention them in its section on multithreading is outdated whatever is its publication date. I've read the first edition of this one and that makes me think that the second must be good.

$\endgroup$
  • $\begingroup$ Thank you for commenting. I think my question must be badly worded. I am asking why the person who made the comment on the book is stating that boolean operations that are NOT atomic, or protected by a sync variable, are "bad", when everything I have learned about cache coherency protocols tells me, basically, that "it just happens". My edit is now poking at the idea that it doesn't "just happen" (i.e. WE NEED to use some sort of instruction to force the coherency protocol to send out the invalidation on the bus), and that this is indeed what using a sync primative/atomic op causes... $\endgroup$ – Wad May 2 at 16:18
1
$\begingroup$

OK, you can read CPU specs and write ASM program exploiting all their features. It's OK and will work as far as you don't change your hardware :)

Now, when you start to write C (or any other high-level language), you no more spoke to hardware specs, you spoke to the language specs. According to C specs, this code:

bool found = false;
while(!found);

may lead to endless loop (even if the variable changed in another thread), since compiler may cache the variable value in register and never read it again inside the cycle

Now, when you change it to

atomic<bool> found = false;
while(!found);

-- you again need to read language specs about meaning of this atomic thing, and eventually about memory models. These are guarantees that the language specs gives to you, everything else is implementation-specific and may differ depending on hardware, compiler name and version, flags and the moon phase.

As you see, guaranteed part of your program behavior never depends on actual hardware, but only on the language specs. Therefore, if you want to play safe, don't base your reasoning on hardware specs.

OTOH, when you talk about speed, you will usually look into actual asm code generated by compiler and interpret it according to hardware specs. Just remember that this code may depend on compiler name, version ... the moon phase (and hardware may change/be different too).

$\endgroup$
  • $\begingroup$ Thanks Bulat. So does the use of sync primitives force the cache (to which a write has been done) to send out the invalidation message on the bus to all other caches that also have this same cache line or not? $\endgroup$ – Wad May 2 at 19:14
  • $\begingroup$ I wonder what is the "sync primitive"? Is it part of C++ or asm language? Give us the link to its description $\endgroup$ – Bulat May 2 at 19:18
  • $\begingroup$ OK, sorry, I mean anything like an atomic variable (eg 'atomic_bool') or a general synchronisation primitive such as a mutex. I want to re-iterate the question: apart from the example you post in your answer, what is the problem with using a normal bool shared between threads? Because the cache coherency protocol I mentioned ensures that all caches are updated when a write occurs in one, so why is the comment I quote in my question talking about the compiler not generating instructions to sync caches, if it is the coherency protocol that does the syncing for us? $\endgroup$ – Wad May 2 at 19:33
  • $\begingroup$ ^^ And that is why I was asking, since it IS the protocol that is ultimately responsible for updating caches (by sending out the invalidation message on the bus), do we need to use a "sync primitive" to force this protocol to do its job? (That is, if we don't use a sync primitive, and just use a normal bool say, will the cache coherency mechanism NOT send out the invalidation message on the bus??) $\endgroup$ – Wad May 2 at 19:35
  • $\begingroup$ you don't got the point - when you program in HLL, you write against the language specs rather than hardware (i.e. assembler) specs. It's compiler duty to match then program you written to hardware abilities and generate correct asm code. Since you have no direct control of the machine code generated, you cannot rely your algorithm on anything you know about hardware $\endgroup$ – Bulat May 3 at 5:22
-1
$\begingroup$

After an extended chat with @Bulat here we can boil this down to the fact that, regarding the cache coherency protocol:

...your video says how it CAN be done, and actually done in many systems, but not not all

and that generally atomic variables/sync primitives should be used when threading is involved. With this point in mind, using these must force the coherency protocol in my video to sync the caches.

$\endgroup$
  • $\begingroup$ No, my main point was that you cannot control the asm code generated from your C++ code, and therefore can't reason in terms of hardware specs i.e. asm code $\endgroup$ – Bulat May 3 at 10: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.