I don't think the reverse of (3) is possible (though I did miss the example that someone had mentioned). Here's my intuition:
If TSO does not match => there always exists some PC execution order which also does not match.
Said another way, the set of PC execution orderings are a superset of the possible TSO orderings. If I can find an ordering in TSO which does not match that of SC, then that ordering is also a member of the PC execution orderings. In some sense, PC feels like a generalization of TSO (and as @kayvonf said it's weaker).
I'm still not 100% though. Does anybody remember the example that was pitched?
Olorin
I'm pretty sure you're exactly right -- PC just involves a weakening of one of the requirements for TSO.
aoeuidhtns
Could you explain why it's strictly weaker?
Olorin
slide 14 talks about the two. PC is the same as TSO, except that TSO mandates that reads by other processors cannot return a new value of A until the write to A is observed by ALL processors (so we have the guarantee that if processor i sees a new value of A, so does processor j, as long as neither i nor j were doing the write).
PC, on the other hand, drops this guarantee: Processor i can see a new value of A before processor j does.
andymochi
@Olorin What is meant by the word 'strictly'? In the two thread case (1,2, and 4) the extra requirement does not mean anything?
Olorin
Oh, yeah, you're right. I mis-typed. I think I meant just that there were no situations in which PC agreed with SC but TSO didn't, but that isn't what the word "strictly" normally means.
jcarchi
Just wanted to point out how we filled out this chart: first we found states that were impossible in SC and figured out if it was possible in TSO/PC
afzhang
To clarify, since this confused me when I was reviewing these slides: sequential consistency means the result of any parallel operation (so any one of the various possible outputs due to race conditions) == the memory operations in a sequential ordering of the program. When the instructions are executed can be interleaved or whatnot; the memory operations within 1 thread have to happen in the order of the code but there are no guarantees about memory operations between threads.
andrewwuan
Could somebody explain to me how TSO would be different from SC on the 4th example? I can't imagine how TSO would let the program print 2 '0's...
srw
@andrewwuan, TSO is NOT actually different from PC in the 2 thread case. TSO means that if thread 0 writes a value, then thread 1 sees the change if and only if thread 2 sees it. It means that threads which did NOT make the change see it at the same time. Note that this guarantee is pretty much meaningless on a two thread system. So TSO is the same as PC in example 4. Both of them may see the other's read and write out of order and print 0.
I don't think the reverse of (3) is possible (though I did miss the example that someone had mentioned). Here's my intuition:
If TSO does not match => there always exists some PC execution order which also does not match.
Said another way, the set of PC execution orderings are a superset of the possible TSO orderings. If I can find an ordering in TSO which does not match that of SC, then that ordering is also a member of the PC execution orderings. In some sense, PC feels like a generalization of TSO (and as @kayvonf said it's weaker).
I'm still not 100% though. Does anybody remember the example that was pitched?
I'm pretty sure you're exactly right -- PC just involves a weakening of one of the requirements for TSO.
Could you explain why it's strictly weaker?
slide 14 talks about the two. PC is the same as TSO, except that TSO mandates that reads by other processors cannot return a new value of A until the write to A is observed by ALL processors (so we have the guarantee that if processor i sees a new value of A, so does processor j, as long as neither i nor j were doing the write).
PC, on the other hand, drops this guarantee: Processor i can see a new value of A before processor j does.
@Olorin What is meant by the word 'strictly'? In the two thread case (1,2, and 4) the extra requirement does not mean anything?
Oh, yeah, you're right. I mis-typed. I think I meant just that there were no situations in which PC agreed with SC but TSO didn't, but that isn't what the word "strictly" normally means.
Just wanted to point out how we filled out this chart: first we found states that were impossible in SC and figured out if it was possible in TSO/PC
To clarify, since this confused me when I was reviewing these slides: sequential consistency means the result of any parallel operation (so any one of the various possible outputs due to race conditions) == the memory operations in a sequential ordering of the program. When the instructions are executed can be interleaved or whatnot; the memory operations within 1 thread have to happen in the order of the code but there are no guarantees about memory operations between threads.
Could somebody explain to me how TSO would be different from SC on the 4th example? I can't imagine how TSO would let the program print 2 '0's...
@andrewwuan, TSO is NOT actually different from PC in the 2 thread case. TSO means that if thread 0 writes a value, then thread 1 sees the change if and only if thread 2 sees it. It means that threads which did NOT make the change see it at the same time. Note that this guarantee is pretty much meaningless on a two thread system. So TSO is the same as PC in example 4. Both of them may see the other's read and write out of order and print 0.
@srw Thanks for the clarification! I got it now