CODEWITHSUNDEEP
cachingatomiccpu-architecturecpu-cachememory-model
TwITe
TwITe

Reputation: 430

Multicopy atomicity vs Cache Coherence

Can you explain what's difference between multicopy atomicity and cache coherence? How are they related?

Upvotes: 1

Views: 1207

Answers (1)

pveentjer
pveentjer

Reputation: 11307

Coherence:

  • There is a total order over all loads and stores to a single location
  • A read sees the most recent write in this total order
  • This order is consistent with the (preserved) program order.

So coherence only say something about loads/stores to a single location, but not about different addresses; that is the task of consistency.

If you need a total order over multiple addresses, you need multi-copy atomicity. So CPU's can't disagree on the order of stores issued by different CPUs to different addresses.

The typical example of this is the IRIW litmus test.

int a=0
int b=0

thread1:
   a=1

thread2
   b=1

thread3:
   r1=a
   [LoadLoad]
   r2=b

thread4:
   r3=b
   [LoadLoad]
   r4=a

Can it be that r1=1, r2=0, r3=1, r4=0. So can different CPUs see the stores in different orders? Since these are loads and stores to different addresses, (in)coherence is not the issue here.

In a system that is multi-copy atomic, the above situation can't happen.

Most modern CPUs are multi-copy atomic btw (x86, ARMv8). The modifications to a cache line are linearizable because the moment (linearization point) the cache line becomes visible to all other CPUs is between the start of writing to the cache (and waiting for the RFO acknowledgements) and the completion of writing to the cache. Because linearizability is composable, the whole cache is linearizable. And because it is linearizable, there exist always some total order and that is exactly what is needed for multi-copy atomicity.

That doesn't imply that the hardware memory model always has a total order even though it is build on top of a coherent cache. E.g. due to store-to-load forwarding or sharing the store buffer with a subset of the cores, you could lose the total order.

A great book on the topic you can download for free.

Upvotes: 4

Related Questions