Memory Consistency Models (2016) | Hacker News Reader

Memory Consistency Models (2016)

cs.utexas.edu

39 pointssorrow179 comments

> There are, of course, only two hard things in computer science: cache invalidation, naming things, and off-by-one errors. But there is another hard problem lurking amongst the tall weeds of computer science: seeing things in order.

Seeing things in order is a sub problem of cache invalidation. The reason multiprocessor systems have trouble seeing things in order is because of cache. A lot of the memory consistency models can be thought of as specifying when the CPU catches become invalidated.

It’s cache invalidation all the way down.

Cache invalidation is a sub-problem of cache coherency. But the cache coherency is not the consistency model.

"seeing things in order" is a problem that arises even for uncached accesses. If multiprocessor systems have trouble seeing things in order, it's due of the memory interconnect. Even with an effective cache invalidation you might see things out of order. (e.g. between two data on different cache lines or with uncached accesses)

Actually the main reason you see things out of order on a modern CPU are core-local reasons, like store buffering, store forwarding, load buffering, delayed invalidation processing and out of order execution.

If that wasn't the case, memory barriers would be very expensive non-local operations, but they aren't.

The cache and memory subsystem is basically sequentially consistent and the core is the one "causing the problems".

> Actually the main reason you see things out of order on a modern CPU are core-local reasons, like store buffering, store forwarding, load buffering, delayed invalidation processing and out of order execution.

yes, precisely, since the store buffer is designed to ensure access ordering according to the consistency model. Otherwise there is no guarantee that two accesses with different addresses (potentially targeting different memories) will be performed and visible in the original order. That's why we need to specify the memory consistency model, and design hardware components to satisfy it.

The store buffer helps keeps stores in order, sure, but the store buffer is the main reason (on x86) that reordering happens. So positioning it as the savior of consistency doesn't seem right.

Store buffer is there for some key reasons apart from consistency: (a) in OoO execution stores must not escape the core until instruction retirement (or else speculative results could become visible), so you need to buffer them and (b) performance.

(a) already implies an ordered buffer, and you also have to keep some notion of ordering to satisfy store forwards correctly.

If you like this, you may like https://www.linuxjournal.com/article/8211 and https://www.linuxjournal.com/article/8212.

The article metions that x86-TSO differs from the basic idea of store buffering:

> Researchers at Cambridge have poured significant effort into formalizing x86-TSO to make clear the intended behaviors of x86’s TSO implementation (and in particular, where it differs from this notion of store buffering).

Does anyone have an example or litmus test of this difference? My mental model of x86-TSO for the last few years is that is exactly what you'd get for a TSO system with store buffering and store forwarding (it isn't clear if the store forwarding part is included in the "basic" TSO model the author discusses, so that could be the difference).

I'm assuming WB memory, not anything exotic like WC memory, NT stores, etc.

I suppose the additional bits are memory barriers and how to recover sequential consistency.

Yeah could be, although I thought the author was saying there are parts that are different (e.g,. different allowed orderings in some cases), not just that there are additional features like barriers.

Reply on news.ycombinator.com