matthew (nobody.delete@this.example.com) on August 19, 2018 12:51 pm wrote:
> I think there's a good counter-example to your point, which is the Itanium McKinley implementation
> of fetchadd. If the line is in L1, the CPU does it. If it's not, the core tells the
> L2 to do it. Obviously no-one's citing Itanium as a good example of much these days,
> but I never heard anyone complain about its implementation of atomics.

As far as I can tell McKinley only ever had 1 core, right? So was this some kind of optimization for multiple socket machines? The line still had to get back to the core, since this is fetch and add, so you always suffer L2 latency?

Here the L2 is still private so it's kind of still a local operation. I guess the idea maybe is that atomic operations are a signal that a line might be probed by another socket so leaving the current value in the L2 reduces latency if that happens.

Keep in mind that this is also a quantitative tradeoff: atomic operations used to take 100+ cycles and so in that case doing something in the L2 might have been essentially free given the overall high cost of the operation.

Atomics now are down to maybe a dozen(ish) cycles on more quality implementations and are non-blocking (i.e., the core can order around them, and the 12-20 cycle latency is really a worst case where you are doing back-to-back operations which is not necessarily that common: so the real impact might be less).

>
> Let's talk about something that might make sense. A lock is typically on a cacheline which contains other
> data that is also being operated on. If the lock is uncontended (either no CPU has the cacheline or another
> CPU has the cacheline in an unlocked state), you want to bring in the cacheline. If the lock is contended,
> the last thing you want is to steal the cacheline from that CPU; at the very least it wants to access the
> cacheline again to release the lock, and chances are it's operating on other data in that cacheline.

Definitely, that's one way I can see this working: either with new instructions/hints for the cases the developer knows benefit from remote atomics, or some kind of prediction/dynamic behavior. The locking one is a good example: right now you have to steal the cache line only to find out that it's locked, maybe you could have a type of atomic that leaves the line in place if it is the locked state, since stealing it won't be useful anyways. Still, that's not really "remote atomics" because when you do get the lock you want to bring it into your cache so that unlock and subsequent lock/unlock pairs are really fast. It's more like an optimization of the RFO protocol to embed knowledge of the locking into the probe.

Stuff like that doesn't seem to popular though: there is a lot of probably low hanging fruit to really optimize locking: for example with some cooperation with the OS scheduler you could avoid switching out threads that were in the middle of short, contended critical sections since that ends causing a big caravan as all the other threads slam up against the lock before the owning thread is scheduled. It seems "easy" to do something like this in a fairly cheap way (e.g,. set a flag in the thread control block or something), maybe on an opt-in basis, but it hasn't happened.

The whole spin-locking idea could probably use some hardware optimization, like a userland MONITOR/MWAIT type of thing which can be efficiently use by the unlocking thread to signal a waiting thread without involving the OS, and without needing the cache line to be in shared state across all waiters, and then be invalidated on all of them, etc.


> So _if_ we have a way to indicate to the CPU that "this op is a lock acquire", then it might
> make sense to have a mechanism in the inter-core protocol to have the L2 cache steal the cacheline
> from the CPU, perform the operation, then _depending on the result of the operation_ either
> return the cacheline or report back to the requester the result of the operation.

Yeah, agreed.

> It's fiendishly complicated. It'd almost be better to have a way to transmit a series of operations
> and have the remote CPU execute them, because there isn't just one way to acquire a lock.

Sure, making it general is tough.

Then you also have to understand what you are saving. The current mechanism is that the waiting CPU sends a "message" (a probe) which is snooped by the CPU holding lock, which invalidates its copy of the line (without really slowing down), and then the line goes back to the waiting CPU, and after that it can perform local operations on it (spinning) until the holding CPU finally wants to exit the lock at which point it needs to steal the line back (and then finally the holding waiting CPU takes the line back one more time and this time probably gets the lock).

So it's only a few couple of messages, and all the loads done while spinning except for the initial and final ones occur locally and don't incur any concurrency traffic. Similarly, any number of other threads can participate in spinning and after the initial transfer also spin on their shared line locally. So it's not all that terrible.

Consider sending instructions to a remote CPU to execute. This has the downside of slowing down the very CPU that is holding the lock, which is the one agent in the system you don't want to slow down! Also, if getting the lock fails, you haven't brought the line back locally, so every time you want to check the lock again, you need to interrupt the lock-holding CPU. Add more cores and the problem gets worse.

So the way MESI (and enhancements) works isn't actually all that terrible even for locking scenarios, and it's no surprise that pretty much everyone uses it.

> Maynard's ideas are, as usual, poorly thought through.

I mean what really pissed me off is he's like "Oh, this is all Intel and Linux old-style never-innovate, stuck-in-the-mud type stuff" of course ignoring the fact that everyone implements it like this and his beloved Apple makes great CPUs by mostly leveraging all of the same really good tried and tested ideas.