By: --- (---.delete@this.redheron.com), September 3, 2022 10:13 am
Room: Moderated Discussions
Overall this has been a somewhat frustrating experience for both of us. I think, even with goodwill on both sides, we've been frustrated by
- lack of a common terminology
- a lack of common background, so that we've each taken for granted things that seemed obvious to us (but were not), and then been forced to treat the other party as a child by trying to explain in baby language what we mean – an no-one likes being spoken to in baby language.
Even so, I think the whol experience has been worthwhile. I've been forced to think much more clearly about the Cloudflare graphs, I've learned the sorts of things I wanted to learn about some other CPU families, and I have modified my BTB discussion quite substantially.
During this interaction I've written about a bunch of things (eg prefetching, or how the M1 BTB is populated) which are interesting and tangentially related to the graphs, but below I'm going to include my final analysis of the Cloudflare graphs.
The TL;DR is that
- Apple probably has a two level BTB (Maynard wrong)
- The 2nd level BTB is at least 8192 entries in size and this size has nothing to do with the second jump in the M1 graphs (Cloudflare wrong)
- At the low end for both Apple and AMD we see the results of aliasing indices which give the L1 BTBs a substantially smaller effective size when the successive traces are power-of-2 separated (neither Maynard nor Cloudflare drew attention to this important effect)
If you want to read along, open the Cloudflare article and look at both the M1 predicted jmp graph and the AMD EPYC 7642 predicted jmp graph. I'll try to include those below - who knows if the tags will work!
At this point, maybe it's worth discussing the Cloudflare results:
https://blog.cloudflare.com/branch-predictor/
I no longer have access to an M1, so I cannot independently verify these but assuming the code is what I think it is, let's proceed.
Note the big jumps for Apple at 3072 and 6144, and for AMD at 4096.
In both Apple cases 3072 traces that are each 64B long, and 6144 traces each 32B long comes to 192KiB. But the AMD curves all jump at 4096.
To me this suggests that
- AMD's BTB (second level BTB) holds 4096 entries. Doesn't matter how long the traces are, things go bad once we exceed the BTB capacity and cannot accurately predict the next trace to fetch.
- 4096*64B=256KiB. This is much larger than the AMD L1I size. So AMD are successfully prefetching I-lines into the L1I. This could result from a simple sequential I-prefetcher (notice that three successive I-cache lines have been touched and prefetch the next one, like a data sequential prefetcher); or it could results from FDIP.
Note the block size/trace size is 64B but contains one jump, so one cache line (64B) is processed in what looks like about 3.5 cycles.
That means Address Prediction can possibly run ahead of Fetch and Decode (eg if some BTB accesses hit the faster BTB0 and BTB1, with the remaining accesses taking 3 cycles in BTB2), and runahead address prediction can be used for Fetch far in advance of when the instructions are decoded (so acting like a prefetch, like FDIP).
What about Apple? The Apple pattern is very different in that, at the high end, we start paying more cycles at the point where we exceed L1I, ie based on the length of the traces, not the number of traces. This suggests that
- the BTB infrastructure can hold at least 8192 traces
- for this type of code pattern Apple is not prefetching a line into the L1I, so that as soon as we exceed L1I size we pay the cost of an L2 access.
This in turn implies that Apple has neither a sequential I-fetch predictor (unsurprising; this is not a great design for an I-prefetcher) nor a fully decoupled fetch (which would be able to queue up the relevant fetch addresses in advance of cache access and thus have them act as FDIP).
The second difference between Apple and AMD is that AMD's cost per cycle (ie cost per trace) is the same at the high end, regardless of the trace length. This again tells us that the cost is a trace related cost, eg the cost of a mis-predict then flush.
For Apple the cost at the high end is different for larger traces vs shorter traces. This tells us the cost is associated with the amount of data being moved.
Assume Apple is moving two lines of data from L2 to L1I, and the L2 access delay is about 14 cycles. Now assume 64B blocks. Then that 14 cycles is amortized over two fetches (one that missed to L2, one that was able to hit the successor line that was next-line-prefetched into L1I) and so the average cost per block is 14/2+ some BTB overhead.
Likewise the same case but with 32B blocks. Now that 14 cycles is amortized over four fetches, so the average cost per block is 14/4+ some BTB overhead. That essentially matches what we see.
The second interesting question is what happens at the lower end.
For AMD we know that Zen2 has an L1 BTB of 512 entries and and L2 BTB of 7168 entries, according to https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Block_Diagram
I'm not sure why the 7168 BTB2 seems to give us an effective size (~4000) that's so low; maybe we are seeing terrible aliasing effects because the blocks all begin at power-of-2 address offsets, so we land up using only half the indices?
The same sort of thing seems to hold for the L1 BTB; we're hitting that and getting a throughput that looks like 1+some overhead, but only for about 256, not the full 512 entries.
Once again the Apple story is very different. Once again there isn't an obvious number of traces (ie number of blocks, to use the terminology of the graph) at which we jump, rather we jump from 1 cycle to 3 cycles when the total size of the loop (number of blocks * block size) exceeds 4096B.
So an initial hypothesis is that this is again a cache size issue.
As we will eventually see, again in great detail, Apple has a tiered set of Instruction "caches" depending on the exact details of the code. The simplest short loops are held in a loop buffer; while more complex loops(longer and/or requiring branch prediction because the branch outcomes are not constant), but which fit, are held in an L0I.
Suppose we are seeing performance within this L0I vs performance in the L1I.
+ This fits with the effect being linked to a constant loop size regardless of the block size.
+ On the other hand, I can't see any obvious reason why performance should drop when a loop exceeds the size of the L10! The L10 loop buffer exists for energy reasons, not performance reasons. And we don't see any sort of data movement penalty (cost dependent on block length) like we saw when M1 was missing L1I and had to go out to L2.
So I think this hypothesis fails.
A different interpretation of the low end of the Cloudflare graph is that it reflects a cleaner version of what we saw with with the AMD results: aliasing of address indices into the table, ie as the blocks get larger successive block addresses match at intermediate address bits, and so we use fewer and fewer sets.
This sort of thing can be fixed with a fancier BTB indexing hash, but maybe there isn't enough time for such hash?
If this were my code, I'd try a few runs with different block sizes, like say 2^n-1, to try to avoid this sort of aliasing.
If this interpretation is correct, we can summarize that:
+ Apple's primary BTB (we will see that there are other specialist BTBs) is 1024 entries in size, and uses a very simple indexing hash that is easily broken by powers-of-two addresses [which admittedly are extremely fake and not present in real life]!) AMD likewise probably doesn't care about such fake address aliasing possibilities.
+ with an L2 BTB that holds at least 8192 entries.
It is striking that Apple never mentions an L2 BTB in their BTB-related patents, but it's possible that this was considered an irrelevant distraction; or that the split from a single level medium-sized BTB to a larger, but split, BTB was implemented after the most recent BTB patent I have seen (2017).
One final question you may wonder is why was AMD, at the high end, only able to use half their L2 BTB? If this is indexing related, why didn't we see the same sort of staggered pattern of graph jumps, like we saw at the low-end for both Apple and AMD?
My guess is that
- some sort of hash of address bits is being performed for the L2 BTB (we've already accepted that that doesn't have to be single cycle, probably for both Apple and AMD) but
- AMD is passing through the second lowest address bit unchanged and unhashed as the lowest index bit (perhaps used as an energy saver, so only one of two halves of a tag SRAM are woken up), and since that second lowest bit never changes (our addresses are always four aligned) we only have access to half the indices. In more realistic code, fetch addresses would probably be randomly scattered at this 16bit granularity, so this would not be a real hardship to performance.
- lack of a common terminology
- a lack of common background, so that we've each taken for granted things that seemed obvious to us (but were not), and then been forced to treat the other party as a child by trying to explain in baby language what we mean – an no-one likes being spoken to in baby language.
Even so, I think the whol experience has been worthwhile. I've been forced to think much more clearly about the Cloudflare graphs, I've learned the sorts of things I wanted to learn about some other CPU families, and I have modified my BTB discussion quite substantially.
During this interaction I've written about a bunch of things (eg prefetching, or how the M1 BTB is populated) which are interesting and tangentially related to the graphs, but below I'm going to include my final analysis of the Cloudflare graphs.
The TL;DR is that
- Apple probably has a two level BTB (Maynard wrong)
- The 2nd level BTB is at least 8192 entries in size and this size has nothing to do with the second jump in the M1 graphs (Cloudflare wrong)
- At the low end for both Apple and AMD we see the results of aliasing indices which give the L1 BTBs a substantially smaller effective size when the successive traces are power-of-2 separated (neither Maynard nor Cloudflare drew attention to this important effect)
If you want to read along, open the Cloudflare article and look at both the M1 predicted jmp graph and the AMD EPYC 7642 predicted jmp graph. I'll try to include those below - who knows if the tags will work!
At this point, maybe it's worth discussing the Cloudflare results:
https://blog.cloudflare.com/branch-predictor/
I no longer have access to an M1, so I cannot independently verify these but assuming the code is what I think it is, let's proceed.
Note the big jumps for Apple at 3072 and 6144, and for AMD at 4096.
In both Apple cases 3072 traces that are each 64B long, and 6144 traces each 32B long comes to 192KiB. But the AMD curves all jump at 4096.
To me this suggests that
- AMD's BTB (second level BTB) holds 4096 entries. Doesn't matter how long the traces are, things go bad once we exceed the BTB capacity and cannot accurately predict the next trace to fetch.
- 4096*64B=256KiB. This is much larger than the AMD L1I size. So AMD are successfully prefetching I-lines into the L1I. This could result from a simple sequential I-prefetcher (notice that three successive I-cache lines have been touched and prefetch the next one, like a data sequential prefetcher); or it could results from FDIP.
Note the block size/trace size is 64B but contains one jump, so one cache line (64B) is processed in what looks like about 3.5 cycles.
That means Address Prediction can possibly run ahead of Fetch and Decode (eg if some BTB accesses hit the faster BTB0 and BTB1, with the remaining accesses taking 3 cycles in BTB2), and runahead address prediction can be used for Fetch far in advance of when the instructions are decoded (so acting like a prefetch, like FDIP).
What about Apple? The Apple pattern is very different in that, at the high end, we start paying more cycles at the point where we exceed L1I, ie based on the length of the traces, not the number of traces. This suggests that
- the BTB infrastructure can hold at least 8192 traces
- for this type of code pattern Apple is not prefetching a line into the L1I, so that as soon as we exceed L1I size we pay the cost of an L2 access.
This in turn implies that Apple has neither a sequential I-fetch predictor (unsurprising; this is not a great design for an I-prefetcher) nor a fully decoupled fetch (which would be able to queue up the relevant fetch addresses in advance of cache access and thus have them act as FDIP).
The second difference between Apple and AMD is that AMD's cost per cycle (ie cost per trace) is the same at the high end, regardless of the trace length. This again tells us that the cost is a trace related cost, eg the cost of a mis-predict then flush.
For Apple the cost at the high end is different for larger traces vs shorter traces. This tells us the cost is associated with the amount of data being moved.
Assume Apple is moving two lines of data from L2 to L1I, and the L2 access delay is about 14 cycles. Now assume 64B blocks. Then that 14 cycles is amortized over two fetches (one that missed to L2, one that was able to hit the successor line that was next-line-prefetched into L1I) and so the average cost per block is 14/2+ some BTB overhead.
Likewise the same case but with 32B blocks. Now that 14 cycles is amortized over four fetches, so the average cost per block is 14/4+ some BTB overhead. That essentially matches what we see.
The second interesting question is what happens at the lower end.
For AMD we know that Zen2 has an L1 BTB of 512 entries and and L2 BTB of 7168 entries, according to https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Block_Diagram
I'm not sure why the 7168 BTB2 seems to give us an effective size (~4000) that's so low; maybe we are seeing terrible aliasing effects because the blocks all begin at power-of-2 address offsets, so we land up using only half the indices?
The same sort of thing seems to hold for the L1 BTB; we're hitting that and getting a throughput that looks like 1+some overhead, but only for about 256, not the full 512 entries.
Once again the Apple story is very different. Once again there isn't an obvious number of traces (ie number of blocks, to use the terminology of the graph) at which we jump, rather we jump from 1 cycle to 3 cycles when the total size of the loop (number of blocks * block size) exceeds 4096B.
So an initial hypothesis is that this is again a cache size issue.
As we will eventually see, again in great detail, Apple has a tiered set of Instruction "caches" depending on the exact details of the code. The simplest short loops are held in a loop buffer; while more complex loops(longer and/or requiring branch prediction because the branch outcomes are not constant), but which fit, are held in an L0I.
Suppose we are seeing performance within this L0I vs performance in the L1I.
+ This fits with the effect being linked to a constant loop size regardless of the block size.
+ On the other hand, I can't see any obvious reason why performance should drop when a loop exceeds the size of the L10! The L10 loop buffer exists for energy reasons, not performance reasons. And we don't see any sort of data movement penalty (cost dependent on block length) like we saw when M1 was missing L1I and had to go out to L2.
So I think this hypothesis fails.
A different interpretation of the low end of the Cloudflare graph is that it reflects a cleaner version of what we saw with with the AMD results: aliasing of address indices into the table, ie as the blocks get larger successive block addresses match at intermediate address bits, and so we use fewer and fewer sets.
This sort of thing can be fixed with a fancier BTB indexing hash, but maybe there isn't enough time for such hash?
If this were my code, I'd try a few runs with different block sizes, like say 2^n-1, to try to avoid this sort of aliasing.
If this interpretation is correct, we can summarize that:
+ Apple's primary BTB (we will see that there are other specialist BTBs) is 1024 entries in size, and uses a very simple indexing hash that is easily broken by powers-of-two addresses [which admittedly are extremely fake and not present in real life]!) AMD likewise probably doesn't care about such fake address aliasing possibilities.
+ with an L2 BTB that holds at least 8192 entries.
It is striking that Apple never mentions an L2 BTB in their BTB-related patents, but it's possible that this was considered an irrelevant distraction; or that the split from a single level medium-sized BTB to a larger, but split, BTB was implemented after the most recent BTB patent I have seen (2017).
One final question you may wonder is why was AMD, at the high end, only able to use half their L2 BTB? If this is indexing related, why didn't we see the same sort of staggered pattern of graph jumps, like we saw at the low-end for both Apple and AMD?
My guess is that
- some sort of hash of address bits is being performed for the L2 BTB (we've already accepted that that doesn't have to be single cycle, probably for both Apple and AMD) but
- AMD is passing through the second lowest address bit unchanged and unhashed as the lowest index bit (perhaps used as an energy saver, so only one of two halves of a tag SRAM are woken up), and since that second lowest bit never changes (our addresses are always four aligned) we only have access to half the indices. In more realistic code, fetch addresses would probably be randomly scattered at this 16bit granularity, so this would not be a real hardship to performance.
