Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Myths Programmers Believe about CPU Caches (2018)

software.rajivprab.com

Post reply on HN
Print view View original

121–130 of 143 posts

Re: Myths Programmers Believe about CPU Caches (2018)

#121

Post by throwawaylinux »

Dylan16807 wrote: post #117
throwawaylinux wrote: post #110

Earlier quoted context omitted.

> How would you do cache coherency in software? I don't follow. Hardware caches which are not coherent require e.g., writeback and flushes to be coherent with other agents. > When you read address X that refers to address Y, it's impossible to read Y and know it's the version that X refers to (or a more recent version). I would call that Y being "stale, as per the memory model". I'm pretty sure that's a normal use of…

> It isn't, because it's relative. "Most recent" is according to the observer, and if you couldn't previously observe something that is "newer" (within the rules of memory consistency model), then it is not stale. Why is most recent according to the observer, and not the core(s) that actually did the writes? The value in Y caused the value in X. Surely that's worth something in terms of ordering?

Your example was hard to follow. What do you mean exactly. Write it in terms of memory operations performed and values observed by each CPU and address, with assertions that are or are not violated according to your example.

Re: Myths Programmers Believe about CPU Caches (2018)

#122

Post by gpderetta »

Dylan16807 wrote: post #117
throwawaylinux wrote: post #110

Earlier quoted context omitted.

> How would you do cache coherency in software? I don't follow. Hardware caches which are not coherent require e.g., writeback and flushes to be coherent with other agents. > When you read address X that refers to address Y, it's impossible to read Y and know it's the version that X refers to (or a more recent version). I would call that Y being "stale, as per the memory model". I'm pretty sure that's a normal use of…

> It isn't, because it's relative. "Most recent" is according to the observer, and if you couldn't previously observe something that is "newer" (within the rules of memory consistency model), then it is not stale. Why is most recent according to the observer, and not the core(s) that actually did the writes? The value in Y caused the value in X. Surely that's worth something in terms of ordering?

What if the write hasn't happened at all?

Writer:

    0:    mov $0 $random_cell // zero initialize $random_Cell
    1:    mov $0 $random_cell_ready // zero initialize $random_cell_ready
    3:    rng r1 // generates a non-zero random number in r1, takes 300 hundreds cycles
    4:    mov r1 $random_cell // write generated value to memory location $random_cell
    5:    mov 1 $random_cell_ready // sets a flag to notify that the value has been written
Reader

   0:    test $random_cell_ready
   1:    jz 0  // spin-wait for cell ready
   2:    mov $random_cell r1
Consider an 1-wide OoO[0] machine with a maximally relaxed memory model. There are no caches, but magic memory with 1 clock cycle latency, so no coherence issues: at time t writers starts computing a random number (writer:3): rng is going to take a few hundreds cycles before writing the result to r1. Next clock cycle t+1 it can't execute writer:4 as r1 is not ready. Instead it executes writer:5 that has no dependencies. writer:3 is only executed at t+300.

At time t, the reader will read a zero form the flag, so at t+1 loops back. On t+2 it sees the flag set to 1. So t+3 the jump falls through and t+4 we read 0 form $random_cell. That's obviously wrong as the data is not there. It is certainly not reading stale data as that's literally the last value that was written to this memory location: a newer value hasn't even been computed yet.

To fix this you need a fence #StoreStore between writer:4 and writer:5 and a corresponding fence #LoadLoad between reader:1 and reader:2 to implement release and acquire semantics [1]. In particular the fence on the writer side will stall the pipeline [2] until previous stores in program order have committed.

As you can see there are no caches, only a single shared memory which is necessarily always coherent. There is no stale data. Yet we need fences for correctness.

You can now reintroduce caches, but MESI give the illusion to the rest of the CPU that it is actually talking with uncached, fully coherent memory, except that latency is now variable.

Ergo, generally, fences and caches are completely orthogonal concepts.

[0] BTW the example would be broken even on a machine with scoreboarding but no renaming (so no fully OoO).

[1] proper release and acquire require slightly stronger fences, but these are sufficient for this example

[2] a better option is to just prevent further stores to be dispatched.

edit: some light editing

Re: Myths Programmers Believe about CPU Caches (2018)

#123

Post by Dylan16807 »

throwawaylinux wrote: post #118
Dylan16807 wrote: post #116

Earlier quoted context omitted.

>That is not what a release barrier does. > That is not a "normal barrier" though, writeback and invalidate operations are software coherency. I think I was unclear when I said "the cache line". I meant the one containing a releasing store. Let me try wording it a different way. A store_release requires all previous writes to be ordered before it. This obviously includes other memory addresses, but its own memory add…

> I think I was unclear when I said "the cache line". I meant the one containing a releasing store. Not sure what you mean by that. > Let me try wording it a different way. A store_release requires all previous writes to be ordered before it. This obviously includes other memory addresses, but its own memory address isn't an exception. So even without cache consistency as a general rule, the nature of a release gives…

When I talk about how the cache protocol has to do XYZ to implement a barrier, you complain that that isn't what a barrier is.

When I talk about what memory barriers do in pure terms, you complain that I'm not mentioning the cache protocol.

When I give an example of a cache protocol in isolation, you start talking about which memory barriers I'm missing.

I don't know what you want.

> Coherency is not about ordering, it's about ensuring agents don't see stale data.

Well, if I go by "if it's part of the memory model then it's not stale", then you can allow a relaxed ordering on single addresses without having stale data.

When a core takes Exclusive control of a cache line, put all other Shared copies into the state "might be an old version, but that's allowed by the protocol and the memory model".

Some instructions can read "might be an old version, but that's allowed by the protocol and the memory model" values and some can't. The exact details of "some instructions" are flexible/irrelevant. See the memory model (not provided) for details.

There. Done. Minimal proof established of a design that doesn't always guarantee cache coherency, but can enforce as much cache coherency as you need. You don't need to add any explicit writebacks or flushes to manage it from software, and enforcing it doesn't take any significant effort beyond a normal CPU's coherency protocol.

Agents will never be confused. They know that Shared means everyone has the same value, and "might be an old version, but that's allowed by the protocol and the memory model" does not mean everyone has the same value. They know that transitioning from "might be an old version, but that's allowed by the protocol and the memory model" to Shared or Exclusive requires reading the data anew, just like transitioning from Invalid to Shared to Exclusive.

If agents want to always be as up to date as possible, they can simply not use this state. If an agent wants to be up to date some of the time, then it can allow this state but purge it at will.

This state only allows for "old" values going back to the most recent purge, so it's not a useless act to read from it. And this state can give you data faster than acquiring a Shared state, so there's a reason to use it.

> The same goes for acquire though.

I'm pretty sure the entire point of acquire is that you can't reorder reads from after it to before it.

Re: Myths Programmers Believe about CPU Caches (2018)

#124

Post by gpderetta »

Dylan16807 wrote: post #105
gpderetta wrote: post #101

Earlier quoted context omitted.

How would you implement the c++11 memory model in a non-cc system exactly? Let's say you build linked list, spanning a few cachelines and then publish it by storing the address of the first node to into an atomic with release semantics. Another thread load-consumes its address and start traversing it. On a cc system the only thing the release barrier needs to ensure is that all previous stores commit to L1 (in any or…

In that example I don't think anything really changes. With cache coherency a release barrier makes sure all previous stores are committed to L1, and by implication any old versions of the cache line have been invalidated. Without cache coherency a release barrier makes sure all previous stores are committed to L1, and explicitly says that any old versions of the cache line have been invalidated. If you had a design…

So to be clarify, I understand from this comment and other in this thread that you are talking about a mostly CC system, with coherency messages and the full MESI transition; The only relaxation is that you allow an additional Stale state. I don't see what you gain here, you still need to send RFOs for every write (including plain reads) to not yet exclusive lines as you can't delay sending invalidates to other caches on a fence as otherwise two cores might be writing to the same cacheline at the same time.

I guess this improves the false sharing scenario as you can read from data on a stale line if the data you care is not the one that actually caused the line to go stale and a barrier is needed to fully invalidate it, but the cost is that your release barriers, instead of being cheap purely core-local effect, now have to cross the coherence fabric. This can move the cost from a dozen of cycles to hundreds.

Re: Myths Programmers Believe about CPU Caches (2018)

#125

Post by Dylan16807 »

gpderetta wrote: post #124
Dylan16807 wrote: post #105

Earlier quoted context omitted.

In that example I don't think anything really changes. With cache coherency a release barrier makes sure all previous stores are committed to L1, and by implication any old versions of the cache line have been invalidated. Without cache coherency a release barrier makes sure all previous stores are committed to L1, and explicitly says that any old versions of the cache line have been invalidated. If you had a design…

So to be clarify, I understand from this comment and other in this thread that you are talking about a mostly CC system, with coherency messages and the full MESI transition; The only relaxation is that you allow an additional Stale state. I don't see what you gain here, you still need to send RFOs for every write (including plain reads) to not yet exclusive lines as you can't delay sending invalidates to other cache…

It's not supposed to be a particularly valuable model, it's just to show how it could exist.

> the cost is that your release barriers, instead of being cheap purely core-local effect, now have to cross the coherence fabric. This can move the cost from a dozen of cycles to hundreds.

That's not the intent.

The barrier pushes the lines in this new state to I, but under MESI they already would have been I.

There is no need to have any performance loss compared to MESI. If no lines are in this state then there is no extra work. And if it would be helpful, you can preemptively work on converting those lines to S in the background.

Edit: Oh wait you said release barrier. No, if you're doing the simplest plan based on MESI then there is no need for anything extra when releasing. Those considerations were only if you wanted to look at MOSI where it's already doing write broadcasts.

Re: Myths Programmers Believe about CPU Caches (2018)

#126

Post by Dylan16807 »

gpderetta wrote: post #122
Dylan16807 wrote: post #117

Earlier quoted context omitted.

> It isn't, because it's relative. "Most recent" is according to the observer, and if you couldn't previously observe something that is "newer" (within the rules of memory consistency model), then it is not stale. Why is most recent according to the observer, and not the core(s) that actually did the writes? The value in Y caused the value in X. Surely that's worth something in terms of ordering?

What if the write hasn't happened at all? Writer: 0: mov $0 $random_cell // zero initialize $random_Cell 1: mov $0 $random_cell_ready // zero initialize $random_cell_ready 3: rng r1 // generates a non-zero random number in r1, takes 300 hundreds cycles 4: mov r1 $random_cell // write generated value to memory location $random_cell 5: mov 1 $random_cell_ready // sets a flag to notify that the value has been written Re…

The writing thread I had in mind was not being reordered.

Consider instead a loop that walks through an array looking for a value of 8, then writes the address of that value to memory location X.

Another thread can read X, then read the location, and see a number that is not 8 but used to be there before the 8.

That's allowed by the memory model, but is it wrong to say "stale"?

Is it wrong to say that the 8 was set before X was set?

Re: Myths Programmers Believe about CPU Caches (2018)

#127

Post by gpderetta »

Dylan16807 wrote: post #125
gpderetta wrote: post #124

Earlier quoted context omitted.

So to be clarify, I understand from this comment and other in this thread that you are talking about a mostly CC system, with coherency messages and the full MESI transition; The only relaxation is that you allow an additional Stale state. I don't see what you gain here, you still need to send RFOs for every write (including plain reads) to not yet exclusive lines as you can't delay sending invalidates to other cache…

It's not supposed to be a particularly valuable model, it's just to show how it could exist. > the cost is that your release barriers, instead of being cheap purely core-local effect, now have to cross the coherence fabric. This can move the cost from a dozen of cycles to hundreds. That's not the intent. The barrier pushes the lines in this new state to I, but under MESI they already would have been I . There is no n…

Sorry, I'm losing track of what you are proposing. I guess you mean MOESI plus an additional Stale state? Can you describe all the transitions and when they are performed?

Re: Myths Programmers Believe about CPU Caches (2018)

#128

Post by gpderetta »

Dylan16807 wrote: post #126
gpderetta wrote: post #122

Earlier quoted context omitted.

What if the write hasn't happened at all? Writer: 0: mov $0 $random_cell // zero initialize $random_Cell 1: mov $0 $random_cell_ready // zero initialize $random_cell_ready 3: rng r1 // generates a non-zero random number in r1, takes 300 hundreds cycles 4: mov r1 $random_cell // write generated value to memory location $random_cell 5: mov 1 $random_cell_ready // sets a flag to notify that the value has been written Re…

The writing thread I had in mind was not being reordered. Consider instead a loop that walks through an array looking for a value of 8, then writes the address of that value to memory location X. Another thread can read X, then read the location, and see a number that is not 8 but used to be there before the 8. That's allowed by the memory model, but is it wrong to say "stale"? Is it wrong to say that the 8 was set b…

Your example has a single store, there is no reordering. There is no value before 8, it doesn't require any barrier. If you make and additional store to the array, that's would be equivalent to my example.

Re: Myths Programmers Believe about CPU Caches (2018)

#129

Post by throwawaylinux »

Dylan16807 wrote: post #123
throwawaylinux wrote: post #118

Earlier quoted context omitted.

> I think I was unclear when I said "the cache line". I meant the one containing a releasing store. Not sure what you mean by that. > Let me try wording it a different way. A store_release requires all previous writes to be ordered before it. This obviously includes other memory addresses, but its own memory address isn't an exception. So even without cache consistency as a general rule, the nature of a release gives…

When I talk about how the cache protocol has to do XYZ to implement a barrier, you complain that that isn't what a barrier is. When I talk about what memory barriers do in pure terms, you complain that I'm not mentioning the cache protocol. When I give an example of a cache protocol in isolation, you start talking about which memory barriers I'm missing. I don't know what you want. > Coherency is not about ordering,…

> I don't know what you want.

I don't want anything, I was correcting your misconceptions.

> Well, if I go by "if it's part of the memory model then it's not stale", then you can allow a relaxed ordering on single addresses without having stale data.

I don't know what you're talking about. Memory ordering is not about ordering of a single address. That's cache coherency.

[snip]

> I'm pretty sure the entire point of acquire is that you can't reorder reads from after it to before it.

And you're still wrong. Acquire barrier can be required even if you receive coherency updates in a sequential order. Barriers in modern processors do not flush, invalidate, or perform coherency operations.

This is what I mean by you can't just handwave with a basic idea about the programming semantics (which aren't particularly complicated). It's easy to think up some vaguely plausible sounding implementation of those things, but the reality is infinitely more complicated. Real cache coherency protocols are verified with formal proofs, and not because they are easy. I guarantee if you handwave a new coherency state or give up some property of coherency, you will have bugs.

Re: Myths Programmers Believe about CPU Caches (2018)

#130

Post by throwawaylinux »

gpderetta wrote: post #127
Dylan16807 wrote: post #125

Earlier quoted context omitted.

It's not supposed to be a particularly valuable model, it's just to show how it could exist. > the cost is that your release barriers, instead of being cheap purely core-local effect, now have to cross the coherence fabric. This can move the cost from a dozen of cycles to hundreds. That's not the intent. The barrier pushes the lines in this new state to I, but under MESI they already would have been I . There is no n…

Sorry, I'm losing track of what you are proposing. I guess you mean MOESI plus an additional Stale state? Can you describe all the transitions and when they are performed?

It seems to be a state that can send stale data to loads, but will get invalidated if the CPU performs a barrier.

It doesn't work of course, obviously because there is no forward progress. CPU1 can order all previous stores, then later store some flag or lock variable, and that will never propagate to CPU2 spinning on that waiting for the value.

But also because CPU2 and CPU3 can see different values depending on the state of their caches. If one had no such line and the other had a valid-stale line, then they will end up seeing different values. And the writeback out of CPU1's cache needs to write back and invalidate all possible older such written-to lines. By the time you make it work, it's not a cache it's a store queue but worse because it has to do all these coherency operations and barriers have to walk it and flash or flush it, etc.

Post reply on HN