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.