5 ms·

> Cache coherency ensures that the behavior is correct, but every time a cache is invalidated and the same memory has to be retrieved from main memory again, it

> Cache coherency ensures that the behavior is correct, but every time a cache is invalidated and the same memory has to be retrieved from main memory again, it pays the performance penalty of reading from main memory. 1. First no. If any such rereads occur, they will be from the LLC (last-level cache, or L3 cache for Intel/AMD CPUs). 2. Second no. IIRC, modern caches are snooping and/or directory caches. This means that when Core#0 says "I'm changing cacheline X", Core#0 knows that Core#1 has it in its L2 (or deeper) caches. So Core#0 will publish the results of that change to Core#1 3. The examples they gave are missing read/write barriers, which are rather important. #2 will only happen during read/write barriers. That is to say: your code is memory-unsafe by default. If order and cache-invalidation matters, you actually need a barrier instruction (!!!) to make sure all these messages are passed to the right place at the right time. --------- For better or for worse, modern CPU design is about doing things thread-unsafe by default. If the programmer recognizes a problem may occur, it is the responsibility of the programmer to put the memory barriers in the right place. This is because the CPU is not the only thing that can reorder things... but also the cache system... as well as the compiler. So memory barriers inform the compiler + CPU + cache system when to synchronize. The original Netflix article is more precisely worded. > This consistency is ensured with so-called “cache coherency protocol.” With a link to MESIF (F for Forwarding state, which is one such protocol / way to share L1 cache info without going all the way to LLC or DRAM) I'm pretty sure that GPUs actually invalidate the cache dumbly, without any MESI / MESIF (or whatever). GPUs are actually really bad at these kinds of ping-pong operations and synchronization... preferring thread-fences and other synchronization mechanisms instead. ------ That being said, I think the blogpost is a good introduction to the subject. But note that its a bit imprecise with some of the low level details. I guess its correct for the GPU-world though, so its not completely inaccurate... ----- The original Netflix article has an even more difficult problem revolving around Java's Superclass cache and how it is affecting "true sharing" of caches. I'm not very familiar with JVM internals, so I lost track of the discussion at that point.

bluGill 4y ago
Not all the world is x86, arm doesn't do as much.
- dragontamer 4y ago
  ARM is cache coherent, meaning it has some kind of MESI (or better, like MESIF) protocol going on. ARM is _RELAXED_ however, or perhaps... "more relaxed" than x86. More orderings are possible on ARM, but that only makes memory-fences (load-acquire, store-release) even more important.
  - brooksbp 4y ago
    > but that only makes memory-fences (load-acquire, store-release) even more important. I would say that the importance is in the correctness of the algorithm that implements the shared memory synchronization. Lowering the algorithm/code to architecture instructions that enforce memory ordering is trivial at that point. So what if it means a fence instruction isn't needed on x86 but it is on arm64 at some particular point in the code.
    - jeffreygoesto 4y ago
      Makes me wonder why there are no portable system language keywords that abstract "hey, I know my peripheral touched this DRAM, please don't take it from the cache".
      - tremon 4y ago
        Isn't that what C's volatile keyword does?
        jeffreygoesto 4y ago
        Close, but not fully. Volatile enforces using an assembly read instruction (does not use a register cached value), but no memory barriers. In ye (really) olden days that seemed enough, but then you know, backwards compatibility...
        dragontamer 4y ago
        Well, that's what Java's "volatile" actually enforces. C's "volatile" isn't enough, but more recent C compilers have atomics and memory models. The memory-model problem wasn't solved until the 00s (that late!!!) when multicore CPUs became more commonplace. Java, C++11, and other language / language updates after that point quickly adopted memory models. And the rest is history. So yeah, use atomics + memory barriers.
nwallin 4y ago
> 3. The examples they gave are missing read/write barriers, which are rather important. #2 will only happen during read/write barriers. That is to say: your code is memory-unsafe by default. If order and cache-invalidation matters, you actually need a barrier instruction (!!!) to make sure all these messages are passed to the right place at the right time. Wait... wait what? Am to understand that if I have code like this: struct { int foo; int bar; } foobar; mutex io_mutex; void baz(int* x, int n) { *x = 0; for (int i = 0; i <= n; i++) *x += i; lock io_mutex; print *x; unlock io_mutex; } thread t1 { baz(&foobar.foo, 10000); }; thread t2 { baz(&foobar.bar, 10000); }; You're saying this code is memory-unsafe without adding barrier instructions? (as opposed to just having terrible performance) (let's also assume the compiler isn't smart enough to just compile that down to `x = n (n-1) / 2;` and actually reads/writes the value in the pointer.)
- vouwfietsman 4y ago
  But you aren't actually mixing data here, right? Even though foo and bar could be on the same cache-line, the threads need to read/write either foo OR bar, so the respective core caches being out of sync for the var they don't use does not really cause any safety issues. Maybe I'm missing the point of your example. No idea how these two separate cache lines get merged to main memory in the end though, is there some kind of write mask for that? Also I imagine them being in the same struct is really just an implementation detail and shouldn't actually influence the memory safety?
- dragontamer 4y ago
  lock io_mutex; print \*x; unlock io_mutex; Have you ever looked at lock/unlock code? There's a memory + compiler barrier inside of any mutex. The easiest way to use memory barriers is through locking/unlocking mutexes. Alas, that's too slow for a number of applications, so advanced programmers have begun to use more complicated patterns.
kfrzcode 4y ago
https://netflixtechblog.com/seeing-through-hardware-counters-a-journey-to-threefold-performance-increase-2721924a2822 https://netflixtechblog.com/seeing-through-hardware-counters... Link from the OP, for the lazy
throwawaylinux 4y ago
Directory vs snooping just means you either know exactly which other agents have an interest in a line so you can target them directly, or that you don't so you broadcast and other agents have to "snoop" requests and respond to relevant ones. The logical coherency protocol that is (somewhat) above that level is what would dictate whether you can forward modified data between CPUs or it would have to write back and be fetched from memory. AFAIK protocols don't tend to have the writer publish its modification to other owners for two major reasons. First because you then would no longer own it exclusive and would have to go off-chip if it wanted to modify it again immediately afterwards. Second because problems with supporting atomic operations and preventing deadlocks in the protocol can become unmanageable if you could have other owners while you are writing lines. I believe generally the transfer of data is demand-driven, so core 1 wanted to read the line, it would ask core 0 for it. And that modifications will always remove access permission from other cores before the modification completes, so core 0 would have send an intent to write message to core 1 in this case before its store could reach coherency. Barriers don't necessarily drive any coherency on a cache line level. Caches are always coherent (ignoring access by incoherent agents, where the coherency has to be managed at a software level). Barriers provide ordering between more than one memory access. The MESIF page is a good basic intro to concepts, naturally state of the art has moved beyond that. Here for example https://course.ece.cmu.edu/~ece742/f12/lib/exe/fetch.php?media=le_power6.pdf https://course.ece.cmu.edu/~ece742/f12/lib/exe/fetch.php?med... a 15 year old CPU has 13 states in its coherency protocol. It's difficult to find a lot of public information about this stuff. Suffice to say these things are so complex that mathematical proofs are used to ensure correctness, no deadlocks, etc. You are right right that data including updates can go directly between agents rather than via memory. But no matter how smart the hardware gets, the advice to programmers is still the same: stores to a line will slow down access to that line by any other agent, so sharing read-only lines between CPUs is fine, but don't add a lot of writes to the mix.
namibj 4y ago
> For better or for worse, modern CPU design is about doing things thread-unsafe by default. If the programmer recognizes a problem may occur, it is the responsibility of the programmer to put the memory barriers in the right place. This so much. I truly wish RISC-V had decided on the weak memory model (WMM)[0] that allowed load-value speculation in the absence of explicit `Reconcile` fences between dependent loads (i.e., when first loading an address from memory and then loading a value from that address, it can load an old value that was stored after the value's address was stored to memory, provided it speculated the value (of pointer-type) of the first load correctly and loaded from this speculated address before it properly executed the first load). Not needing to repeat the load from a speculated address in response to that address getting a cache invalidation before the load that fetched the (correctly speculated) pointer "goes though" severs the cache snooping/invalidating feed to the reorder buffer(ROB). Essentially, the difference to banning the dependent-load-load reordering is that WMM frees up the second load's ROB entry once the value speculation of the first load confirms, so when the first load instruction returns and affirms the value speculated for it, the second load can retire immediately with the first load to free up both ROB entries. The decoupling between an L2 invalidating other L2's and responding to another L2's read-request allows the "Invalidation Buffer" of an L2 to function similar to an L1's store buffer. So if L3 is implemented by just giving each core a large multi-bank L2 so the L3-slices are just the different core's L2s, write-congestion into an L2 through other cores all writing to the same bank is just buffered away (and redundant stores can be squashed/adjacent stores write-combined, useful if the writing cores specify they themselves don't want read access to the cachelines those writes target). See this excerpt from the paper: > Speculations: OOO can issue a load speculatively byaggressive predictions, such as branch prediction (Figure 3d),memory dependency prediction (Figure 3e) and even load-value prediction (Figure 3f). As long as all predictions relatedto the load eventually turn out to be correct, the load resultgot from the speculative execution can be preserved. Nofurther check is needed. Speculations effectively reorderdependent instructions, e.g., load-value speculation reordersdata-dependent loads. Since WMM does not require preserving any dependency ordering, speculations will neither breakWMM nor affect the above correspondence between OOOand WMM. Yes, WMM is similar to Alpha, just that Alpha allowed a load from some address to be reordered after a store to a different address (which is forbidden in WMM). [0]: https://arxiv.org/abs/1707.05923 https://arxiv.org/abs/1707.05923
ChuckMcM 4y ago
I was going to say something like this but I like this version better. Key things to keep in mind, this is Intel Core micro-architecture, other micro-architectures may make other choices. In particular using snooping or shoot downs it one of those choices. Why use one or the other? Consider whether or not your memory controller is "single threaded" or not[1]. If you have multiple memory controllers that have access to the same "slow" memory, then a shoot down (cache invalidation message) over the cache coherency interconnect, can start the refresh transaction for unoccupied memory controller context. In these cases you can overlap memory transactions and "hide" some of the latency. If you're snooping, and see a write through (where write is headed for main memory), you can mirror a copy of that write through to update your cache, but you might simply invalidate your cache if there is a shared cache with the CPU (thread) in question, as it will get changed in the shared cache and the invalidation will cause the shared cache to move it from L2 to L1 as soon as you look at it again. The availability of multi-core RISC-V designs for FPGAs give someone who is interested in this an opportunity to actually try the different strategies and to compare instruction throughput (instructions per clock) and maximum latency for correct operation. There was a good paper at Microprocessor Forum in the early 2000's from Toshiba on a multi-core cache design where the L2 cache was visible but segmented between cores (it appeared as a single cache where you didn't have access to invalidate all of the look aside buffers. I thought it was very creative and it of course rewarded algorithms that understood that. (small working set per thread, larger working set for application) [1] Basically how many memory transactions can it have outstanding at any given time.

bluGill 4y ago

Not all the world is x86, arm doesn't do as much.

dragontamer 4y ago
ARM is cache coherent, meaning it has some kind of MESI (or better, like MESIF) protocol going on. ARM is _RELAXED_ however, or perhaps... "more relaxed" than x86. More orderings are possible on ARM, but that only makes memory-fences (load-acquire, store-release) even more important.
- brooksbp 4y ago
  > but that only makes memory-fences (load-acquire, store-release) even more important. I would say that the importance is in the correctness of the algorithm that implements the shared memory synchronization. Lowering the algorithm/code to architecture instructions that enforce memory ordering is trivial at that point. So what if it means a fence instruction isn't needed on x86 but it is on arm64 at some particular point in the code.
  - jeffreygoesto 4y ago
    Makes me wonder why there are no portable system language keywords that abstract "hey, I know my peripheral touched this DRAM, please don't take it from the cache".
    - tremon 4y ago
      Isn't that what C's volatile keyword does?
      - jeffreygoesto 4y ago
        Close, but not fully. Volatile enforces using an assembly read instruction (does not use a register cached value), but no memory barriers. In ye (really) olden days that seemed enough, but then you know, backwards compatibility...
        dragontamer 4y ago
        Well, that's what Java's "volatile" actually enforces. C's "volatile" isn't enough, but more recent C compilers have atomics and memory models. The memory-model problem wasn't solved until the 00s (that late!!!) when multicore CPUs became more commonplace. Java, C++11, and other language / language updates after that point quickly adopted memory models. And the rest is history. So yeah, use atomics + memory barriers.

nwallin 4y ago

> 3. The examples they gave are missing read/write barriers, which are rather important. #2 will only happen during read/write barriers. That is to say: your code is memory-unsafe by default. If order and cache-invalidation matters, you actually need a barrier instruction (!!!) to make sure all these messages are passed to the right place at the right time. Wait... wait what? Am to understand that if I have code like this: struct { int foo; int bar; } foobar; mutex io_mutex; void baz(int* x, int n) { *x = 0; for (int i = 0; i <= n; i++) *x += i; lock io_mutex; print *x; unlock io_mutex; } thread t1 { baz(&foobar.foo, 10000); }; thread t2 { baz(&foobar.bar, 10000); }; You're saying this code is memory-unsafe without adding barrier instructions? (as opposed to just having terrible performance) (let's also assume the compiler isn't smart enough to just compile that down to `x = n (n-1) / 2;` and actually reads/writes the value in the pointer.)

vouwfietsman 4y ago
But you aren't actually mixing data here, right? Even though foo and bar could be on the same cache-line, the threads need to read/write either foo OR bar, so the respective core caches being out of sync for the var they don't use does not really cause any safety issues. Maybe I'm missing the point of your example. No idea how these two separate cache lines get merged to main memory in the end though, is there some kind of write mask for that? Also I imagine them being in the same struct is really just an implementation detail and shouldn't actually influence the memory safety?
dragontamer 4y ago
lock io_mutex; print \*x; unlock io_mutex; Have you ever looked at lock/unlock code? There's a memory + compiler barrier inside of any mutex. The easiest way to use memory barriers is through locking/unlocking mutexes. Alas, that's too slow for a number of applications, so advanced programmers have begun to use more complicated patterns.

kfrzcode 4y ago

https://netflixtechblog.com/seeing-through-hardware-counters-a-journey-to-threefold-performance-increase-2721924a2822 https://netflixtechblog.com/seeing-through-hardware-counters... Link from the OP, for the lazy

throwawaylinux 4y ago

Directory vs snooping just means you either know exactly which other agents have an interest in a line so you can target them directly, or that you don't so you broadcast and other agents have to "snoop" requests and respond to relevant ones. The logical coherency protocol that is (somewhat) above that level is what would dictate whether you can forward modified data between CPUs or it would have to write back and be fetched from memory. AFAIK protocols don't tend to have the writer publish its modification to other owners for two major reasons. First because you then would no longer own it exclusive and would have to go off-chip if it wanted to modify it again immediately afterwards. Second because problems with supporting atomic operations and preventing deadlocks in the protocol can become unmanageable if you could have other owners while you are writing lines. I believe generally the transfer of data is demand-driven, so core 1 wanted to read the line, it would ask core 0 for it. And that modifications will always remove access permission from other cores before the modification completes, so core 0 would have send an intent to write message to core 1 in this case before its store could reach coherency. Barriers don't necessarily drive any coherency on a cache line level. Caches are always coherent (ignoring access by incoherent agents, where the coherency has to be managed at a software level). Barriers provide ordering between more than one memory access. The MESIF page is a good basic intro to concepts, naturally state of the art has moved beyond that. Here for example https://course.ece.cmu.edu/~ece742/f12/lib/exe/fetch.php?media=le_power6.pdf https://course.ece.cmu.edu/~ece742/f12/lib/exe/fetch.php?med... a 15 year old CPU has 13 states in its coherency protocol. It's difficult to find a lot of public information about this stuff. Suffice to say these things are so complex that mathematical proofs are used to ensure correctness, no deadlocks, etc. You are right right that data including updates can go directly between agents rather than via memory. But no matter how smart the hardware gets, the advice to programmers is still the same: stores to a line will slow down access to that line by any other agent, so sharing read-only lines between CPUs is fine, but don't add a lot of writes to the mix.

namibj 4y ago

> For better or for worse, modern CPU design is about doing things thread-unsafe by default. If the programmer recognizes a problem may occur, it is the responsibility of the programmer to put the memory barriers in the right place. This so much. I truly wish RISC-V had decided on the weak memory model (WMM)[0] that allowed load-value speculation in the absence of explicit `Reconcile` fences between dependent loads (i.e., when first loading an address from memory and then loading a value from that address, it can load an old value that was stored after the value's address was stored to memory, provided it speculated the value (of pointer-type) of the first load correctly and loaded from this speculated address before it properly executed the first load). Not needing to repeat the load from a speculated address in response to that address getting a cache invalidation before the load that fetched the (correctly speculated) pointer "goes though" severs the cache snooping/invalidating feed to the reorder buffer(ROB). Essentially, the difference to banning the dependent-load-load reordering is that WMM frees up the second load's ROB entry once the value speculation of the first load confirms, so when the first load instruction returns and affirms the value speculated for it, the second load can retire immediately with the first load to free up both ROB entries. The decoupling between an L2 invalidating other L2's and responding to another L2's read-request allows the "Invalidation Buffer" of an L2 to function similar to an L1's store buffer. So if L3 is implemented by just giving each core a large multi-bank L2 so the L3-slices are just the different core's L2s, write-congestion into an L2 through other cores all writing to the same bank is just buffered away (and redundant stores can be squashed/adjacent stores write-combined, useful if the writing cores specify they themselves don't want read access to the cachelines those writes target). See this excerpt from the paper: > Speculations: OOO can issue a load speculatively byaggressive predictions, such as branch prediction (Figure 3d),memory dependency prediction (Figure 3e) and even load-value prediction (Figure 3f). As long as all predictions relatedto the load eventually turn out to be correct, the load resultgot from the speculative execution can be preserved. Nofurther check is needed. Speculations effectively reorderdependent instructions, e.g., load-value speculation reordersdata-dependent loads. Since WMM does not require preserving any dependency ordering, speculations will neither breakWMM nor affect the above correspondence between OOOand WMM. Yes, WMM is similar to Alpha, just that Alpha allowed a load from some address to be reordered after a store to a different address (which is forbidden in WMM). [0]: https://arxiv.org/abs/1707.05923 https://arxiv.org/abs/1707.05923

ChuckMcM 4y ago

I was going to say something like this but I like this version better. Key things to keep in mind, this is Intel Core micro-architecture, other micro-architectures may make other choices. In particular using snooping or shoot downs it one of those choices. Why use one or the other? Consider whether or not your memory controller is "single threaded" or not[1]. If you have multiple memory controllers that have access to the same "slow" memory, then a shoot down (cache invalidation message) over the cache coherency interconnect, can start the refresh transaction for unoccupied memory controller context. In these cases you can overlap memory transactions and "hide" some of the latency. If you're snooping, and see a write through (where write is headed for main memory), you can mirror a copy of that write through to update your cache, but you might simply invalidate your cache if there is a shared cache with the CPU (thread) in question, as it will get changed in the shared cache and the invalidation will cause the shared cache to move it from L2 to L1 as soon as you look at it again. The availability of multi-core RISC-V designs for FPGAs give someone who is interested in this an opportunity to actually try the different strategies and to compare instruction throughput (instructions per clock) and maximum latency for correct operation. There was a good paper at Microprocessor Forum in the early 2000's from Toshiba on a multi-core cache design where the L2 cache was visible but segmented between cores (it appeared as a single cache where you didn't have access to invalidate all of the look aside buffers. I thought it was very creative and it of course rewarded algorithms that understood that. (small working set per thread, larger working set for application) [1] Basically how many memory transactions can it have outstanding at any given time.