Problem Set Solutions/Memory Consistency/Problem05

Sequential consistency ensures that all memory accesses execute as if we process them one at a time, each time selecting a core and letting it complete its next access in program order. Note that this does not require round-robin selection of cores – it even allows one core to be selected several times in a row. This allows for many possible interleavings of accesses from different cores, but it prevents accesses from one core from being reordered.

Weak consistency distinguishes between synchronization and non-synchronization accesses. Synchronization accesses (such as those used to acquire or release a lock) are never reordered amongst themselves or with other accesses. This means that synchronization accesses are done in a sequentially-consistent way, but non-synchronization accesses that a core makes between synchronization accesses can be reordered freely (note that this reordering is still limited by coherence and dependences in program order).

Release consistency further distinguishes between acquire (e.g. lock acquire) and release (e.g. lock release) synchronization accesses. They are still not reordered amongst themselves, but non-synchronization accesses can be reordered freely, except that non-synchronization writes must complete before the next release synchronization event and reads cannot execute before the preceding acquire event.

Note that weak consistency can be achieved using release consistency by treating every every synchronization event as both an acquire and a release. Also note that sequential consistency can be achieved using weak consistency by treating every access as a synchronization access.

It is impossible to write code that will always (in every execution) distinguish between the three consistency models! Explain why. Hint: if the execution order obeys the rules of sequential consistency, can it break the rules of weak of release consistency?

Solution:

All three consistency models allow the execution on each processor to follow program order – they differ only in which other orderings are allowed. Therefore, it is possible for the program to proceed without reordering and thus produce exactly the same results under weak or release consistency as it would under sequential consistency. As a result, we cannot write a program that will always (in every run) produce different results under different consistency models.