Formal Specification of Memory Models

We introduce a formal framework for specifying the behavior of memory systems for shared memory multiprocessors. Specifications in this framework are axiomatic, thereby avoiding ambiguities inherent in most existing specifications, which are informal. The framework makes it convenient to construct correctness arguments for hardware implementations and to generate proofs of critical program fragments. By providing a common language in which a range of memory models can be specified, the framework also permits comparison of existing models and facilitates exploration of the space of possible models. The framework is illustrated with three examples: the well-known Strong Consistency model, and two store ordered models TSO and PSO defined by the Sun Microsystem’s SPARC architecture. The latter two models were developed using this framework.