last day (16 days later) » 

9:00 PM
2
Q: Are load ops deallocated from the RS when they dispatch, complete or some other time?

BeeOnRopeOn modern Intel1 x86, are load uops freed from the RS (Reservation Station) at the point they dispatch2, or when they complete3, or somewhere in-between4? 1 I am also interested in AMD Zen and sequels, so feel free to include that too, but for the purposes of making the question manageable I l...

 
Can't be on dispatch; the possibility of uop replay (even for ALU uops dependent on a load that misses in cache) means it needs to hold onto its slot. (Otherwise it would have to handle the corner case of RS being full when it gets to the end of the pipe and discovers that it can't complete). We know (from Andy Glew) that Intel CPUs have "completion ports", which I assume is for signalling complete or replay back to the RS / ROB. I'd assume that deallocs
 
@Peter - I'm not following why a replay means that the load itself (rather than the dependent uops) need to stay in the RS, unless you mean that the load might replay because it's address was wrong because whatever it depended on didn't execute at the right time?
 
Hmm, do load uops themselves get re-dispatched to catch the possibly-arriving data from L2? Or is just ALU uops in anticipation of data arriving? I was thinking the former, but now that you point it out, the latter (just eager ALU dispatch) makes more sense. Load uops do replay for cache-line splits, though. So an RS entry could maybe be freed before the load buffer, if the RS entry is only needed once we're sure the load doesn't need to replay any more, leaving just the load buffer tracking the incoming data.
 
@PeterCordes - I am not sure. I thought they replayed the load, but it is possible my test was wrong. How do you know they replay for splits?
 
@BeeOnRope Where are loads replayed from if they don't stay in the scheduler until completion? From the Load Queue (or, in general, from the MOB)? This is the approach taken by Henry Wong when synthesizing an x86-compatible CPU on FPGA. Also, NetBurst had a "MOB_load_replay" event. I made some notes when I researched "replay sources" (digging in the patents) and found three of them: The scheduler, the MOB and the uOP cache. However, they are cryptic to the me of today, and I didn't link the patents. 🤦‍♀️🤦‍♀️🤦‍♀️
 
9:00 PM
Ok, if we agree that a load uop (and its dependent ALU uops) might need to replay, then it follows that they need to be scheduled and dispatched to that port again. (We know from perf counters that uops_dispatched.port2 and so on count again for replayed uops). As @Margaret says, where else would they dispatch from? The RS needs to know not to dispatch something else to that port in that cycle; the logical option is for the uop to stay in the RS (so it's the oldest-ready uop for that port that cycle).
 
@MargaretBloom - well my first question is why loads need to be replayed. Do they need to be replayed because they don't execute at the expected latency (eg L1 miss), or is only their dependent uops that need to be replayed? Certainly I thought the former and wrote tests that appeared to show that, but my tests had the problem that I was doing a bunch of dependent loads, so it actually can't distinguish the two cases: except for the first and very loads, every load is both a dependent and dependee of another load, so the numbers would come out the same under either theory.
Specifically, in the scenario where you have a load, followed by a uop that depends on the load, and the load misses in L1 and hits in L2 (which I know causes a replay), will it be the dependent uop that replays, or the load, or perhaps both? Easy to test, not sure why I'm writing loquacious instead of just testing it :).
 
Re: split load replaying: we can see from uops_dispatched port counts that cache-line split loads need to run through the load port twice, once for each half of the load. In one edit of How can I accurately benchmark unaligned access speed on x86_64, I added a paragraph about that after testing on my own SKL. uops_dispatched_port.port_2 = 2x number of mov rdi, [rdi] dependent loads. (This implies that line-split buffers are right in the load ports, which makes sense.) IIRC, split stores are the same way.
 
@PeterCordes - still playing the devil's advocate: your test doesn't show whether the load that missed needed to be replayed, or the load that depended on it. Imagine that the load itself doesn't need to be replayed: after all, it didn't fail: it is continuing along checking the L2 next, it doesn't start over. Maybe only the dependent ops need to be replayed. I'll say that I don't necessarily thing this is the case: but I'm repeating an argument someone else made to me which I think was plausible.
 
Yes, it's very plausible for the miss case. The test test I did was for the line-split case. (That's easier to test; you don't have to generate L1 misses.) Perhaps a good test would be a load -> alu -> load -> alu dep chain so you never have a load directly feeding a load. (imul by 1 or or reg, 0). Or just independent loads feeding ALU uops, with a PRNG or something for the addresses to get cache misses. Then look at counters and see if any of the loads were dispatched multiple times. Hmm, or just stride through an array touching memory faster than HW prefetch can keep up.
 
Or just turn off HW prefetch. Anyways I'm doing the test. However, I consider it equally plausible for miss vs split? That is, to the RS any case other than 5 cycle (4 cycles for fast-mode loads but that's known statically) looks like a failure and something (probably) needs to get replayed. @PeterCordes
 
9:00 PM
I did the strided test idx+=256 bytes to get mostly L1d/L2 misses, or all L1d hits if I wrap the index every iteration instead of just to a large length (godbolt.org/z/vHAUNG). Dependent ALU uops get replayed but there's no evidence of load replays on cache misses at all. (For aligned dword loads, i7-6700k.) The loads addresses come from a loop counter, not dependent on other loads. Out of 800M ALU uops, we had 1930M dispatches for mostly L3 hits.
(An earlier version of this had many fewer replays when the ALU chain consuming it formed a single dependency. That other dependency on the previous load+add stopped eager replay of most uops: 948M dispatches out of 800M ALU instructions executed.) That 800M includes the loop overhead of 300M that don't depend on any loads, so actually replays took us from 500M to 1630M, for mostly L1/L2 miss, L3 hit. Or 648M dispatches out of 500M successes when the load->add forms a dependency into a single add chain.
 
@PeterCordes What do you mean by "formed a single dependency"?
 
I mean I was doing independent loads into ECX, but then consuming it with add edx, ecx every time, for all 5 loads in the unrolled loop, not taking advantage of the unroll. Using 5 different accumulators allows more replays. But there's still the inter-iteration dependency. Removing that, too, by using lea edx, [rcx + rcx] after every load, leads to ~4678M ALU uops dispatched. So ~4378M load-dependent LEAs dispatched for 500M successful executions. That's an average of 8.75 dispatches per success!! Must be more aggressive than just replaying at an expected arrival time.
 
@PeterCordes - I see, I guess you edited the link in your comment because I had this one open, which has the old style I guess (your comment made sense with the new code).
@PeterCordes - can you link your newest code with lea?
 
godbolt.org/z/HJF3BN - LEA has no output dependency so I just used the same LEA to consume each load. Probably something like and ecx,0 or add ecx,ecx would work just as well as an independent uop consuming the load (and could run on any port, not just the 2 LEA ports). A copy-and-operate seemed good, but in hindsight we can trust register renaming to kill WAW and WAR dependencies for the ALU uop the same as we are for the load. (OTOH, LEA's limited ports means that all the loop overhead runs on p0 / p6, with LEA on p1 / p5. IDK if we could get even more replay.)
 
@PeterCordes - that is really interesting, I cannot explain so many replays. In principle you could have several replayed ops for each time a load failed to arrive at the expected time, if several ops depended on the load (either directly, or perhaps indirectly). So if each load "fails" 2 times each one could get dispatched 2+1=3 times, so if 3 ops depended on the load not hard to see 3*3=9 replays (for example).
However in this case only a single uop depends on each load as far as I can tell so no idea where the other replays are coming from. Maybe another source of conflicts, or something goes weird when all the LFBs are full and the load keeps trying to get an LFB and in the meantime the dependent uop keeps replaying: but you don't see any load replays, right?
 
9:00 PM
Yeah. My initial hypothesis is that once you go off-core, the expected latency of an L3 hit isn't predictable down to the cycle. So apparently the core spams the uops in case the load arrived in time for that cycle? We know P4 had a replay mechanism something like this that was notorious for lots of replays, right? I don't remember the details of that at all, though. We should test with L2 hits, L1d misses. I have to head out soon (Ultimate frisbee game :), I'll leave that to you.
 
> So apparently the core spams the uops in case the load arrived in time for that cycle? It crossed my mind but it seems really dumb. I seem to recall that in my own replay tests (which had a single long dependency chain of loads), there were no additional replays after you get to L2 misses: i.e., it tried at the L1 latency, the L2 latency, but then no more: there is already a mechanism to just not speculatively issue the uop and wait until the source phys regs are ready, so you would presumably just use that b/c a cycle or two extra doesn't matter much at L3 latencies.
 
a cycle or two extra doesn't matter much at L3 latencies OTOH, if there is literally no other work to do on a given port, a bunch of work dependent on that L3 result is probably waiting to run. Hopefully the scheduler will dispatch younger uops that are definitely ready before optimistic dispatch of uops dependent on loads (throwing a hail-mary pass to the execution ports :P). If there aren't any younger uops (for that port), then it just costs power. But how early does dispatch abort if the input isn't ready after all? Maybe not much if it's detected early.
Or maybe it can steal cycles from younger independent work; perhaps we can design an experiment to test that, like maybe an ALU dep chain that bottlenecks the loop on latency, so loop cycles/iteration goes up if resource conflicts steal cycles from it? It would have to be pretty long for an L3 miss to not bottleneck it even more.
 
9:37 PM
@PeterCordes - i did the split line test
on my SKL I found that the "window" for replay seems to be 2 cycles
i.e., instructions dependent on the load, that will dispatch 0 or 1 cycles after the load, are subject to replay
e.g.
load eax, [eax]
add eax, 0
add eax, 0
add eax, 0
the two two add will replay basically 100% of the time, the third one never
as an implication, something like:

load eax, [eax]
add eax, 0
load eax, [eax]
add eax, 0
...

the load will replay (as well as the add), because it is within in the 2 cycle window (maybe i should call it a 1 cycle window? not sure if it's zero based or not)
 
10:04 PM
if you have multiple ops dependent on the load, directly (0 latency away),you can get lots of replays: for 8 dependent adds, I got 9 replays per load (the 8 adds, plus the load itself)
 
 
2 hours later…
11:40 PM
@BeeOnRope Interesting. I would have expected that there'd be time for split detection to figure out that the first uop wouldn't produce a load result, and do so in time to not dispatch dependent uops. If it takes 2 cycles to generate a linear virtual address from the AGU, that's still 2 or 3 cycles before L1d load-use latency. But apparently it doesn't work that way. Maybe the uop is marked as "in flight" or something, and that's enough for dependent uops to dispatch.
 

  last day (16 days later) »