Memory Consistency vs Cache Coherence

Question Detail: 

Is it true that Sequential Consistency is a stronger property than Cache Coherence?

According to

Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence, Morgan & Claypool, 2011

sequential consistency can be described as (not formally):

Sequential consistency memory model specifies that the system must appear to execute all threads' loads and stores to all memory locations in a total order that respects the program order of each thread. Each load gets the value of the most recent store in that total order.

In other words, system is sequentially consistent, if given memory events (loads and stores) of each thread we can order all these events such that: 1) for each thread the order of its events is preserved, and 2) the global order is serial (any load returns latest value stored).

Now they continue and describe coherence:

A definition of coherence that is analogous to the definition of Sequential Consistency is that a coherent system must appear to execute all threads' loads and stores to a single memory location in a total order that respects the program order of each thread.

In other words, system is coherent, if given memory events of each thread for each location we can order events for that location, such that: 1) for each thread the order of its events to that location is preserved, and 2) for each location the order is serial.

Finally, they point out the difference:

This definition highlights an important distinction between coherence and consistency: coherence is specified on a per-memory location basis, whereas consistency is specified with respect to all memory locations.

So it seems the difference is that for coherent systems we need a total order on all events for each location (thus the ordering between events for particular location), while for consistent systems the total order should be defined on the all events (and thus the ordering is also between events for different locations)?

Does that mean that coherence is less strict that consistency? (which seems amusing!) Are there traces that are coherent but not consistent?

Asked By : Ayrat

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20044

Answered By : Wandering Logic

As you pointed out, coherence is a property of an individual memory location while consistency refers to the order of accesses to all memory locations. Sequential consistency is a strictly stronger property than coherence. That is: every system that is sequentially consistent is also coherent at every memory location. The opposite is not true, a memory that is coherent at every location is not necessarily sequentially consistent. In fact, there are many real cache-coherent multiprocessors where the memory model is only weakly consistent (there are cases where different processors observe accesses to different locations happen in different orders.)

Proof of sequentially consistent implies coherent:

Given any trace from a sequentially consistent system, by definition that trace must have a total order that is agreed on by every processor in the system. Now look at the accesses just to location $x$ in that trace. Because a total order is transitive, the accesses just to location $x$ also have a total order on them that is agreed on by every processor in the system. Thus all memory locations are coherent.

The reverse doesn't work out. Consider two coherent memory locations $x$ and $y$ with just a single access to each $x_0$ and $y_0$. All the processors agree on the order of accesses to location $x$ and all the processors agree on the total order of accesses to location $y$, but some processors may observe the order $x \rightarrow y$, while others may observe the order $y \rightarrow x$. So coherence doesn't imply sequential consistency.

This can lead to surprising results. For example

initially A=B=0 process 1               process 2 store A := 1            load B (gets 1) store B := 1            load A (gets 0)  

This trace is coherent:

• for A the order is: proc2 loads A(gets 0), proc1 stores A:=1
• for B the order is: proc1 stores B:=1, proc2 loads B(gets 1)

But it is not consistent! Since if proc2 load B returns 1, then proc1 store A := 1 already happened and proc2 load A should also return 1.