5
$\begingroup$

In the report "Shared Memory Consistency Models: A Tutorial" (https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf), the authors explain the difference between IBM370, Total Store Ordering, and Processor Consistency via Figure 10 (shown below).

I do not understand why the results for (a) are not possible with IBM370. The report mentions that

these models ... allow a read to be reordered with respect to previous writes from the same processor

(with different addresses). The IBM370 model

prohibits a read from returning the value of a write before the write is made visible to all processors.

I think this means that for the program in (a), P1's read on A must wait for P1's earlier write to A to become visible to P2 before returning. I do not understand how this prevents P1's write to register2 to be reordered to execute before P1's write to Flag1 (which makes the result possible), as described by Figure 10's caption.

figure 10

$\endgroup$
1
$\begingroup$

Good question.

So with TSO loads to a different address can't be reordered (in the global memory order) unless the earlier load can be satisfied by a store in the store buffer and the second load can't. Keep in mind that a load can only be ordered in the global memory order (globally performed) after the store it reads from.

Let have a look at this simple example.

A=B=0

CPU1:
   A=1
   r1=A
   r2=B

CPU2
   B=1
   r3=B
   r4=A

Is it possible to end up with r1=r3=1 and r2=r4=0?

Yes, because the load of r1 is a load which can be satisfied from the store buffer and the load of r2 from the cache. So they can be reordered in the global memory order. And the same goes for r3/r4.

With IBM 370 a load that could be satisfied by a store in the store buffer needs to wait for the store to be globally visible. Of course the load will still see the same value as with TSO; so what is the point? Well, it will make sure a subsequent load that is loaded from the cache, is globally ordered after the earlier load that could have been satisfied from the store buffer.

A=B=0

CPU1:
   A=1
   r1=A
   r2=B

CPU2
   B=1
   r3=A
   r4=B

As a consequence: with IBM 370, the loads can't be reordered. And it is impossible to end up r1=r3=1 and r2=r4=0.

So TSO will give a total order over the stores. I believe that IBM 370 will also give you a total order over the loads; the order of loads in the memory order is consistent with the order of loads in the program order.

Lets go back to the example (a). For TSO this would be a possible memory order that explains the results.

  1. P1:register2=flag2 (0)
  2. P2:register4=flag1 (0)
  3. P1:flag1=1
  4. P1:A=1
  5. P1:register1=A (1)
  6. P2:flag2=1
  7. P2:A=2
  8. P2:register3=A (2)

The trick is with the 2 loads at the end of P1/P2. They have been ordered to the beginning of the memory order since they have a preceding loads that can be satisfied by the store buffer.

With IBM 370 load/load reordering isn't possible. So it is impossible to find a memory order that will be consistent with IBM 370.

PS: I'm no authority, so best to recheck my answer :) I'm also studying this part myself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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