5 ms·

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 sto

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 order) before the final store. There is typically nothing to do on the consume side as the CPU pipeline preserves causality. Everything else is taken care by plain MESI, which will transfer exactly and on-demand those cache lines that contain the list nodes and no more. What would the acquire/consume barriers do on a non-cc system? Consider that, generally, neither the CPU nor the compiler actually have an understanding of the list data structure itself.

Dylan16807 3y ago
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 a lot like MESI, you wouldn't really need release semantics, you'd just have an extra "Shared but maybe stale" state instead of just Invalid, and consume would coerce all those lines into Invalid and they'd have to be re-acquired. But re-acquiring those lines is no worse than if you had vanilla MESI. If you had an Owned state that needs to broadcast changes, you could avoid most broadcasts until seeing a release or similar barrier. In both of these situations you'd probably make the CPU try to sync lines right away, but it could squeeze out some more performance when it's not immediately mandatory.
- throwawaylinux 3y ago
  > 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. That is not what a release barrier does. > 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. That is not a "normal barrier" though, writeback and invalidate operations are software coherency. > If you had a design a lot like MESI, you wouldn't really need release semantics, This is not the case. Release barrier can be required even if your cache coherency operations completed in FIFO order, because reordering could be done before cache coherency.
  - Dylan16807 3y ago
    >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 address isn't an exception. So even without cache consistency as a general rule, the nature of a release gives you all the ordering you need in this situation. I'm sorry for mentioning the word "invalidate", because that's the implementation and not the semantics. > This is not the case. Release barrier can be required even if your cache coherency operations completed in FIFO order, because reordering could be done before cache coherency. So I meant acquire but I think there's also a clear solution based on exactly what I said. The lines that could possibly be affected by the FIFO are all in the "Shared but maybe stale" state. Consume turns those into Invalid. So any read that's from after the Consume, reordered before it, should see those lines as Invalid.
    - throwawaylinux 3y ago
      > 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 you all the ordering you need in this situation. We're talking about cache coherency, not memory consistency. Coherency is not about ordering, it's about ensuring agents don't see stale data. > So I meant acquire but I think there's also a clear solution based on exactly what I said. The same goes for acquire though. > The lines that could possibly be affected by the FIFO are all in the "Shared but maybe stale" state. Consume turns those into Invalid. So any read that's from after the Consume, reordered before it, should see those lines as Invalid. Implementation of CPU memory pipelines and cache coherency aren't really something you can just get a bit of a feel for and then handwave about.
      - 3y ago
- gpderetta 3y ago
  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.
  - Dylan16807 3y ago
    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.
    - gpderetta 3y ago
      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?
      - throwawaylinux 3y ago

Dylan16807 3y ago

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 a lot like MESI, you wouldn't really need release semantics, you'd just have an extra "Shared but maybe stale" state instead of just Invalid, and consume would coerce all those lines into Invalid and they'd have to be re-acquired. But re-acquiring those lines is no worse than if you had vanilla MESI. If you had an Owned state that needs to broadcast changes, you could avoid most broadcasts until seeing a release or similar barrier. In both of these situations you'd probably make the CPU try to sync lines right away, but it could squeeze out some more performance when it's not immediately mandatory.

throwawaylinux 3y ago
> 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. That is not what a release barrier does. > 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. That is not a "normal barrier" though, writeback and invalidate operations are software coherency. > If you had a design a lot like MESI, you wouldn't really need release semantics, This is not the case. Release barrier can be required even if your cache coherency operations completed in FIFO order, because reordering could be done before cache coherency.
- Dylan16807 3y ago
  >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 address isn't an exception. So even without cache consistency as a general rule, the nature of a release gives you all the ordering you need in this situation. I'm sorry for mentioning the word "invalidate", because that's the implementation and not the semantics. > This is not the case. Release barrier can be required even if your cache coherency operations completed in FIFO order, because reordering could be done before cache coherency. So I meant acquire but I think there's also a clear solution based on exactly what I said. The lines that could possibly be affected by the FIFO are all in the "Shared but maybe stale" state. Consume turns those into Invalid. So any read that's from after the Consume, reordered before it, should see those lines as Invalid.
  - throwawaylinux 3y ago
    > 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 you all the ordering you need in this situation. We're talking about cache coherency, not memory consistency. Coherency is not about ordering, it's about ensuring agents don't see stale data. > So I meant acquire but I think there's also a clear solution based on exactly what I said. The same goes for acquire though. > The lines that could possibly be affected by the FIFO are all in the "Shared but maybe stale" state. Consume turns those into Invalid. So any read that's from after the Consume, reordered before it, should see those lines as Invalid. Implementation of CPU memory pipelines and cache coherency aren't really something you can just get a bit of a feel for and then handwave about.
    - 3y ago
gpderetta 3y ago
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.
- Dylan16807 3y ago
  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.
  - gpderetta 3y ago
    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?
    - throwawaylinux 3y ago