Is sequential consistency equivalent to performing memory accesses by a processes in program order and performing each memory access atomically?

Question

In Fundamentals of Parallel Multicore Architecture, by Yan Solihin, p304 defines sequential consistency memory model:

Overall, we can express programmers’ implicit expectation of memory access ordering as: memory accesses coming out of a processor should be performed in program order, and each of them should be performed atomically. Such an expectation was formally defined as the sequential consistency (SC) model. The following is Lamport [37]’s definition of sequential consistency:

A multiprocessor is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor occur in this sequence in the order specifed by its program.

where the atomicity of memory accesses is defined on p303 as

an expectation that each memory access occurs in an instant, without being overlapped with other memory accesses. In the example, the expectation assumes that when process P0 writes to shared variable x, the write is instantly propagated to both processes P1 and P2.

I was wondering if sequential consistency is equivalent to the combination of

• "memory accesses coming out of a processor should be performed in program order", and
• "each of them should be performed atomically"?

I guess yes because "each of them should be performed atomically" is required by SC and its "instant write propagation" seems to guarantee "the result of any execution is the same as if the operations of all the processors were executed in some sequential order". But I can't prove or disprove my suspision.

Thanks.

Answer 1

No, your definition is not quite equivalent to the definition of sequential consistency but would be closer to strict consistency. There are two relevant aspects: (a) there are multiple processors/processes involved, and (b) they only have to behave as if they were being executed in a total order. The atomicity is not required in reality, only in the “as if” model. That memory accesses are performed in program order is already true pretty much by definition.

There is a consistency model called strict consistency that requires that writes take effect in the order they were executed. If a process writes to x at time t₁, then all later reads at time t₂ > t₁ from x should return the written value. This would require atomic writes that propagate immediately to all other processes. Even on a single multicore CPU, this is impossible due to speed of light constraints unless exclusive locks are used, effectively enforcing that reads/writes actually obey a global order – no “as if”.

Sequential consistency is a weaker consistency model. We do not require that writes take effect immediately/atomically, but merely that all processes observe writes in the same order, i.e. that they agree on a total order of operations.

Let's look at some processes that manipulate a shared global variable x. I'll write W(x)a when a process writes the value a to x, and R(x)a when the process reads from x and gets a. We'll have four processes that perform a sequence of operations:

• process 1: W(x)a
• process 2: W(x)b
• process 3: R(x)_, R(x)_
• process 4: R(x)_, R(x)_

Here's some ASCII-Art that illustrates the different times at which the operations could be executed by the processes. The different processes are shown above each other, and the time axis increases to the right.

Here's a strictly consistent execution where all writes take effect immediately:

   -----------------------------> time
1: W(x)a
2:       W(x)b
3:             R(x)b       R(x)b
4:                   R(x)b R(x)b

But here is an execution that is sequentially consistent, yet not strictly consistent:

   -----------------------------> time
1: W(x)a
2:       W(x)b
3:             R(x)b       R(x)a
4:                   R(x)b R(x)a

Here, process 1 first performs the W(x)a operation. However, this operation does not take effect immediately. Now, process 2 executes W(x)b and this write is observed by the other processes. Processes 3 and 4 execute R(x)b, i.e. they get the value b that was just written by process 2. At this point, the write from process 1 takes effect and is observed by the next reads R(x)a of processes 3 and 4.

The important point is that although the writes were not executed atomically, all processes agreed on an order of events, in particular write events. The behaviour of all processes was as if they had been executed in a particular order, although this agreed-upon order was different from the actual temporal order. We don't care about when a write is observed, only about the order between writes.

In contrast, here's an execution where processes 3 and 4 don't agree on the order of W(x)a and W(x)b:

   -----------------------------> time
1: W(x)a
2:       W(x)b
3:             R(x)b       R(x)a
4:                   R(x)a R(x)b

Here, process 3 has observed events W(x)b, W(x)a, whereas process 4 has observed W(x)a, W(x)b. This is not sequentially consistent.

In practice, sequential consistency is easily achievable for single variables e.g. when using locks. The C memory model also enables sequential consistency for single memory locations when all accesses to that location use appropriate memory order.

With multiple variables things tend to get tricky, in particular because sequential consistency is a fairly strong consistency guarantee. The Jepsen.io project has developed tools for fuzzing (distributed) databases in search of consistency violations, and has a good overview of consistency models.

Answer 2

A very nice question!

Some definitions.

A memory order is the order in which loads and stores are globally performed (so either on cache/memory). It is key to understand that the actual memory order isn't relevant. There is no way to prove what the actual memory order was unless you hook up some very advanced measuring equipment to the CPU.

An execution is a single run of a program.

To determine if an execution is cache coherent, you need to find a memory order such that:

1. there is a total order of all loads and stores per address.

2. the order is consistent with the program order of each CPU

3. a load needs to see the most recent store before it in the memory order.

Let have a look at sequential consistency (SC). To determine if an execution is SC, you need to find a memory order such that:

4. there is a total order of all loads and stores over ALL addresses.

5. the order is consistent with the program order of each CPU

6. a load needs to see the most recent store before it in the memory order.

Sequential consistency is a restriction of cache coherence where by the memory order needs to have a total order of loads and stores over all addresses instead of a single address. So there are memory orders that are cache coherent, but not sequential consistent. But not the other way around because cache coherence is a relaxation of SC.

Lets have a look at your definition:

A) "memory accesses coming out of a processor should be performed in program order"

B) "each of them should be performed atomically"?

I'll assume that you mean with 'performed' that the load/store is performed in the memory order (so either loaded from memory or from cache) and not when it is actually executed.

'B' will confine the allowed memory orders such that there is a total order over all loads and stores on a single address. Because atomicity will not order loads/stores to different addresses.

'A' will confine the allowed memory orders to the ones preserving PO between all loads/stores (also the loads/stores to different addresses) issued by a single processors. Combined with B, I believe we have 4) 5).

The key part that is missing is 6), a read needs to see the most recent write before it in the memory order.

So if you would add 6) then I believe your definition is compatible with SC.

You might ask yourself the question why do I get a total order over all loads/stores if the PO between different addresses is preserved? So how do we move from a total order of a single address to a total order over multiple addresses? If different CPU's are executing loads and stores concurrently, then these loads and stores are independent because they can't be causally related. So these loads and stores do not need to not ordered with respect to each other and hence we have no total order. The nice thing is we can just pretend a total order exist because nobody can prove otherwise. In mathematical terms: you can always create a topological sort of the memory order (which is a DAG: an acyclic partial order) and create one or more total orders.