A primer on memory consistency and cache coherence
Many modern computer systems and most multicore chips (chip multiprocessors) support shared memory in hardware. In a shared memory system, each of the processor cores may read and write to a single shared address space. For a shared memory machine, the memory consistency model defines the architecturally visible behavior of its memory system. Consistency definitions provide rules about loads and stores (or memory reads and writes) and how they act upon memory. As part of supporting a memory consistency model, many machines also provide cache coherence protocols that ensure that multiple cached copies of data are kept up-to-date. The goal of this primer is to provide readers with a basic understanding of consistency and coherence. This understanding includes both the issues that must be solved as well as a variety of solutions. We present both high level concepts as well as specific, concrete examples from real-world systems.
Stats for nerds
6recommend
8mentions
7people
2019–2026years
88% recommend13% neutral
Mentions per year
What Hacker News says
- I would probably recommend the art of multiprocessor programming (herlihy and shavitz) as a good starting point for concurrent programming. There is also " A primer on memory consistency and cache coherence" (Nagarajan et al) if you want to get more into the interaction between memory consistency and coherence.
- I'd recommend "A Primer on Memory Consistency and Cache Coherence, Second Edition" - Synthesis Lectures on Computer Architecture 15:1 (2020) - Vijay Nagarajan, Daniel J. Sorin, Mark D. Hill, David A. Wood - (open access, freely available): https://doi.org/10.2200/S00962ED2V01Y201910CAC049
For more see: https://github.com/MattPD/cpplinks/blob/master/atomics.lockf...
- Start here: "The Microarchitecture of Superscalar Processors," J.E. Smith and G.S. Sohi, Proc. IEEE, vol. 83 (1995) https://doi.org/10.1109/5.476078 https://courses.cs.washington.edu/courses/cse471/01au/ss_cgi...
It's very brief (so if you only have time to read one thing you won't waste a single minute: it's to the point) and (perhaps surprisingly, given its publication date) highly relevant: In fact, right after reading Section IV.C (AMD K5) you should be able to immediately jump to and understand the microarchitectural diagrams of, say, AMD Zen 2: http://web.archive.org/web/20231213180041/https://en.wikichi... http://web.archive.org/web/20231213180041/https://en.wikichi... ...and any other contemporary CPU.
Smith & Sohi paper is going to give you great intuition for what's essentially implemented by all modern CPUs: restricted dataflow (RDF) architecture.
A great follow-up is a short blog post "A whirlwind introduction to dataflow graphs" by Fabian “ryg” Giesen: https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...
For context, all superscalar dynamically scheduled (out-of-order) CPUs implement RDF, introduced by Yale Patt's research group's work on High Performance Substrate (HPS). This work pretty much defined the modern concept of a restricted dataflow CPU: breaking complex instructions into smaller micro-operations and dynamically scheduling these to execute out-of-order (or, to be more specific, in a restricted dataflow order) on multiple execution units.
(If you're curious, the "restricted" part comes from the finite instruction window delimiting the operations to be scheduled, which stems from the finite size of all the physical resources in real hardware, like the ROB/reorder buffer. The "dataflow" comes from having to respect data dependencies, like `A = 1` and `B = 2` having to execute before `C = A + B`, or `MOV A, 1` and `MOV B, 2` having to execute before `ADD C, A, B`; but note that you can freely reorder the aforementioned moves among themselves as long as you execute them before the add: a schedule/execution order of `MOV B, 2; MOV A, 1; ADD C, A, B` is just as valid).
For the historical background, see "HPS papers: A retrospective", https://www.researchgate.net/publication/308371952_HPS_paper... (Minor per peeve warning:) It also sets the record straight w.r.t. to the RISC being orthogonal to the historical development of modern superscalar out-of-order CPUs: In particular, it's worth noting that the aforementioned micro-operations have absolutely _nothing_ to do with RISC! Another great resource on that is Fabian's video "CPU uArch: Microcode", https://www.youtube.com/watch?v=JpQ6QVgtyGE (also worth noting that micro-operations and microcode are _very_ different concepts; that's also very well covered by the video).
Another good, succinct description of the historical background is the 2024 IEEE CS Eckert-Mauchly Award (Wen-mei Hwu was a PhD student in the aforementioned Yale Patt's group): "Hwu was one of the original architects of the High-Performance Substrate (HPS) model that pioneered superscalar microarchitecture, introducing the concepts of dynamic scheduling, branch prediction, speculative execution, a post-decode cache, and in-order retirement." - https://www.acm.org/articles/bulletins/2024/june/eckert-mauc...
On a side note, load-store architecture introduced by CDC 6600 (designed by Seymour Cray in the 1960s) is sometimes mistaken for RISC (which came decade+ later, arguably introduced in IBM 801 designed by John Cocke in the late 1970s/early 1980), https://en.wikipedia.org/wiki/Load%E2%80%93store_architectur...
One could say load-store architecture does have an influence on compiler backends implementation, after a fashion (thinking of instruction scheduling, with a complex operation combining, say, LOAD with arithmetic operation OP, broken down in the scheduling models as separate LOAD and OP operations/effects).
For more, I'd recommend:
"Performance Analysis and Tuning on Modern CPU" by Denis Bakhvalov https://github.com/dendibakh/perf-book/releases
Agner Fog's Optimization Manuals https://www.agner.org/optimize/
Prof. Onur Mutlu's Lecture Videos and Materials https://people.inf.ethz.ch/omutlu/lecture-videos.html
These are absolutely fantastic--I've followed all of these a few years back and can vouch for the quality and being up-to-date or at least decades ahead of the general computer architecture textbooks: the lectures and readings cover contemporary work including ISCA and MICRO papers that have only recently found their way to the implementation in production CPUs (e.g., the hashed perceptron predictor that's one of the branch predictor units in AMD Zen 2, http://web.archive.org/web/20231213180041/https://en.wikichi...).
There are more, topic-specific texts that are very good, e.g., A Primer on Memory Consistency and Cache Coherence, Second Edition; Synthesis Lectures on Computer Architecture 15:1 (2020); Vijay Nagarajan, Daniel J. Sorin, Mark D. Hill, David A. Wood; open access (freely available) at https://doi.org/10.2200/S00962ED2V01Y201910CAC049 but when you are at this point you're likely going to be good at finding the relevant resources yourself, so I'm going to leave it to you to explore further :-)
- Probably "A Primer on Memory Consistency and Cache Coherence"
- Answering only the latter question:
A Primer on Memory Consistency and Cache Coherence, Second Edition
https://www.morganclaypool.com/doi/10.2200/S00962ED2V01Y2019...
(free online book) would help
- i know, this was a tongue-firmly-in-cheek kind of comment, but on the off by one chance that you are serious, look no further than: 'A Primer on Memory Consistency and Cache Coherence' (https://www.amazon.com/gp/product/1608455645/)
and ofcourse, while you are at it, you might want to check out 'UNIX Systems for Modern Architectures: Symmetric Multiprocessing and Caching' as well, it also is pretty good, but with a broader focus (https://www.amazon.com/dp/0201633388)
Related
Parallel distributed processing
5 recommend · 29
The art of multiprocessor programming
27 recommend · 64
Programming Massively Parallel Processors
8 recommend · 15
Core memory
5 recommend · 6
Shared-Memory Synchronization
2 recommend · 3
Memory systems
2 recommend · 5
