3 ms·

Memory Consistency Models (2016)

39 points by sorrow17 6y ago

RcouF1uZ4gsC 6y ago
> 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.
- avianes 6y ago
  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)
  - BeeOnRope 6y ago
    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".
    - avianes 6y ago
      > 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.
      - BeeOnRope 6y ago
        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.
tedunangst 6y ago
If you like this, you may like https://www.linuxjournal.com/article/8211 https://www.linuxjournal.com/article/8211 and https://www.linuxjournal.com/article/8212 https://www.linuxjournal.com/article/8212.
BeeOnRope 6y ago
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.
- gpderetta 6y ago
  I suppose the additional bits are memory barriers and how to recover sequential consistency.
  - BeeOnRope 6y ago
    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.

39 points by sorrow17 6y ago

> 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.

avianes 6y ago
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)
- BeeOnRope 6y ago
  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".
  - avianes 6y ago
    > 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.
    - BeeOnRope 6y ago
      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.

tedunangst 6y ago

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

BeeOnRope 6y ago

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.

gpderetta 6y ago
I suppose the additional bits are memory barriers and how to recover sequential consistency.
- BeeOnRope 6y ago
  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.