Cache coherence is worthless and does nothing?

Question

When you perform a write on a multi-cpu system, relevant cache flushes are done to ensure that the other cpus see the change immediately.

BUT

That write was issued from an independent thread on a preempting operating system, so there never was any expectation that it would arrive at any particular time. All that cache coherency achieves is to change the 'no particular time' of the data's arrival to a slightly different 'no particular time'. How is that of even the slightest value ?

Answer 1

It is false to assume that a write to a cache-line will cause a flush to main memory. Caches on modern CPUs are always coherent. Modern caches are also write behind caches meaning that in theory they never need to write to main memory. The primary reasons for a cache-line to end up at main memory are:

• lack of space in the cache.
• limitation in the cache coherence algorithm. E.g. with MESI if a different CPU wants to read a dirty cache-line, the cache-line needs to be written to main memory to prevent the change being lost. MOESI solves this problem.
• I/O DMA.

Cache coherence provides 'coherence':

1. a total order over all loads and stores on a single address.
2. a read needs to see the most recent write before it this order.

In very simple terms: cache coherence provides sequential consistency per address.

An example test for #1:

initial state:
   a=0

CPU1: 
   a=1
CPU2:
   a=2
CPU3:
   r1=a
   r2=a
CPU4:
   r3=a
   r4=a

Can it be that r1=1, r2=2, r3=2, r4=1 (so CPU3 saw the changes in different order than CPU4). No. this is not allowed.

An example test for #2:

initial state:
   a=0

cpu1:
   a=1
cpu2: 
   r1=a
   r2=a

Can it be that r1=1 and r2=0? So are you allowed to see a 'stale' value once you read a newer value? No, this can't happen because once you see 1, you can't go back in time and see the value before it.

Coherence is the key to understand any memory model. If you don't understand coherence, everything you build on top remains fragile. In almost all modern processors (GPU is the only exception I know of) caches are always coherent.

For an excellent read on the topic, see A primer on memory consistency and cache coherence second edition.. The book can be downloaded for free which is pretty amazing seen the quality of the book.

Answer 2

Cache coherency protocols (generally) do not enforce time, they enforce order.

There is an essential (i.e. non-removable) race condition if two CPUs try to write to the same cache line at the same time. One of them will win and one of them will lose. That doesn't matter as long as all CPUs see them as happening in the same order. And if it does matter, that's a concurrency bug in the program.

Memory barriers also enforce order, not time. Think about what must happen when a CPU releases a lock: all writes in the critical section must occur before the write that releases the lock. This is an ordering constraint, not a time constraint.

Answer 3

Consider implementing a mutex. A mutex is either locked or unlocked. If it is locked by another processor, you can't lock it. If two processors try to lock a mutex at exactly the same time, one "wins" and locks the mutex and owns the mutex, and one "loses" and doesn't own the mutex.

There's no guarantee which processor wins if they both try at the same time. But cache coherency can make sure that one wins and one loses and both know who is the winner and who is the loser. Without that, implementing a mutex that works correctly 100% of the time and not 99.999999% of the time would be very, very hard.

And pveentjer's link looks very good.