Memory Consistency and Process Coordination for SPARC v8 Multiprocessors

Jalal Kawash and Lisa Higham

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


Abstract

The capabilities of two SPARC memory consistency models, Total Store Ordering (TSO) and Partial Store Ordering (PSO), to support solutions to fundamental process coordination problems without resorting to expensive synchronization primitives is determined. To achieve this, mathematical descriptions of the behavior of these systems in terms of partial order constraints on possible computations are derived from and proved equivalent to the machine-level descriptions. The problems studied are critical section coordination and both set and queue variants of producer/consumer coordination. Our results show that neither PSO nor TSO models are capable of supporting a read/write solution to the critical section problem, but both can support such solutions to some variants of the producer/consumer problem. These results contrast with the two previous attempts to specify these machines, one of which would incorrectly imply a read/write solution to the critical section problem for TSO, and the other of which is too complicated to be useful to programmers.