20
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Note that we don't like questions of the form "please check my answer!". Can you add a more specific question? Where do you feel your gap could be? $\endgroup$
    – Raphael ♦
    Jan 28, 2014 at 22:32
  • $\begingroup$ @Raphael you are right, and it was not very good feeling when I was writing the question. But what to do if I could not find an answer on the Internet (except vague claims like 'coherence talks about one bit, which is different from consistency which talks about all bits'), and so tried to find an answer, and when seems to found it wasn't sure if it is correct. Should I have come up with a fishy question? Or don't provide an answer in the question?:) $\endgroup$
    – Ayrat
    Jan 29, 2014 at 9:50
  • $\begingroup$ @Ayrat I read the last part of your question as an answer you want checked. If that's the case, there should be some doubt (else, why ask?) which you should pinpoint for readers. Maybe I misread? $\endgroup$
    – Raphael ♦
    Jan 29, 2014 at 18:43
  • $\begingroup$ @Raphael 'the last part want to be checked' - yes. 'why ask?' - the topic is new, and I wasn't sure the conclusion is correct. I will try to avoid this kind of questions in future and probably find someone around to check it.) $\endgroup$
    – Ayrat
    Jan 30, 2014 at 11:19

1 Answer 1

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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