ACM SIGPLAN Notices · 2009 · 40 citations · 12 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureFormal MethodsParallel ComputingMemory ConsistencyMemory Consistency ModelsMemory ModelingMicroarchitecture DesignMultiprocessor SystemsProcessor MicroarchitectureConsistency SemanticsConsistency VerificationMemory CoherenceMemory Management ModelsMemory Model SemanticsMicroarchitectural ModelingParallel Program SemanticsRelaxed Memory Models
Multiprocessors are now dominant, but real multiprocessors do not provide the sequentially consistent memory that is assumed by most work on semantics and verification. Instead, they have subtle relaxed (or weak) memory models, usually described only in ambiguous prose, leading to widespread confusion. We develop a rigorous and accurate semantics for x86 multiprocessor programs, from instruction decoding to relaxed memory model, mechanised in HOL. We test the semantics against actual processors and the vendor litmus-test examples, and give an equivalent abstract-machine characterisation of our axiomatic memory model. For programs that are (in some precise sense) data-race free, we prove in HOL that their behaviour is sequentially consistent. We also contrast the x86 model with some aspects of Power and ARM behaviour. This provides a solid intuition for low-level programming, and a sound foundation for future work on verification, static analysis, and compilation of low-level concurrent code.
12
Shared memory consistency models: a tutorial
Sarita V. Adve, Kourosh Gharachorloo · Computer · 1996 · 1.1K citations
Jeremy Manson, William Pugh, Sarita V. Adve · 2005 · 732 citations · Full text
Causal memory: definitions, implementation, and programming
Mustaque Ahamad, Gil Neiger, James E. Burns et al. · Distributed Computing · 1995 · 433 citations
Sebastian Burckhardt, Rajeev Alur, Milo M. K. Martin · 2007 · 228 citations