5 ms·

Tangential question, perhaps a dumb one: why do most hardware schedulers try to predict the load on their own, instead of letting users explicitly signal their

Tangential question, perhaps a dumb one: why do most hardware schedulers try to predict the load on their own, instead of letting users explicitly signal their intent? It's everywhere, from CPUs to storage.

hindsightbias 2y ago
We could solve a lot of problems if every user had to take EE180.
082349872349872 2y ago
In this case, I'd consider BL (call) a fairly explicit signal of intent to RET?
- dzaima 2y ago
  Yep. For returns, the more important thing in the article, the "ret"[0] instruction behaves exactly identically to "br x30"[1], just with the hint that it's expected to match a "bl". On x86 things are less pretty as call/ret push/pop the ip from the stack, with no non-matching-hinted versions, but having such would also just not be particularly useful as unpaired call/ret would result in the stack pointer continually drifting without manual fixup (at which point jmp is just clearly better). [0]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/RET https://developer.arm.com/documentation/dui0802/a/A64-Genera... [1]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/BR?lang=en https://developer.arm.com/documentation/dui0802/a/A64-Genera...
  - LegionMammal978 2y ago
    On 32-bit x86, there is the trap of trying to use call/pop to get the absolute instruction pointer. It will work correctly, but it will mess up any call stack prediction and cause great performance penalties. Hence why compiler-generated EIP shims use call/mov/ret instead. (But this is not such a big issue in x86-64 with its RIP-relative addressing.)
hansvm 2y ago
1. "Explicitly signaling your intent" takes space and time. Decoding isn't free, and even if there were no other downsides you'd want to be careful with that change. 2. It's a bit historical. Early CPUs didn't have a RAM/CPU discrepancy and didn't need pipelining. Code wasn't written to account for pipelining. As CPUs got a little faster relative to RAM, you added a few prediction mechanisms so that most consumers and workloads could actually use your brand new 2x faster gigaterrawatthournewton CPUs without having to rewrite all their code. Iterate 10-20 generations, where most software has never been written to care about branch prediction and where modern languages don't even expose the concept, and you have the current status quo.
rcxdude 2y ago
It's supported by some CPUs: the linux kernel has likely/unlikely macros to indicate whether a branch is expected to be taken or not in the common case (which uses GCC attributes which allow this to be propagated through to codegen). It's just that it's generally less effective: firstly because not all branches get annotated, some that are annotated are annotated incorrectly, and in a lot of cases the branching behaviour is data-dependent enough that you can't make an optimal static prediction at all.
pjc50 2y ago
The user doesn't know the capabilities of the system. In particular, anything compiled in is set in stone: you don't know the capabilities of systems yet unbuilt. New systems don't sell well unless they make existing code run faster, and sell badly if they require you to rebuild everything and make it non-backwards-compatible. The peak example of "let the user do the scheduling" was Itanium, which had a VLIW system which scheduled three instructions at once. It was a huge commercial failure, and allowed AMD to instead define the instruction set people wanted: X64 is IA32 but wider and with more registers, but not substantially different and certainly not as weird as Itanium.
- magicalhippo 2y ago
  I've lost count of the times I've sped up some existing code by removing the hand-optimized assembly and just used a plain C implementation or similar. Sure, it was hand-optimized assembly, but for a 10+ year old CPU. If you're going to do hand-optimized code for a given platform, include the baseline code and measure at runtime to pick the implementation.
  - patmorgan23 2y ago
    Hand optimized assembly was necessary 30 years ago, and a good for several optimizations 20 years ago. But today's computers are SO FAST, it's just not necessary in most situations.
gpderetta 2y ago
Often, but not always, optimal scheduling is data dependent so it can't be statically computed at compile time.
mhh__ 2y ago
They want to be able to guess long, long, before actually executing the instructions.
crote 2y ago
You should look into the history of Itanium, it was designed around the idea that the compiler would do pretty much exactly that. It looked great on paper, but in practice nobody figured out how to actually write a compiler capable of doing it without constantly running into weird edge cases. X86 does have "prefetch" instructions, which tell the CPU that you want to use some data in the near future. There are also "branch hint" instructions which tell the CPU if a branch is usually taken or not. The problem is that they tend to make your code slower: the CPU is already more than capable of predicting it by itself, and the extra instructions slow down the overall execution because they take up cache space and have to be decoded too.
- CalChris 2y ago
  VLIW is pretty successful for loopy DSP and now AI/ML. However, Itanium was trying to work for general purpose code and then as you say, it constantly ran into weird edge cases. It seemed as if VLIW succumbed to the Peter Principle, it had risen to its level of incompetence. But as long as you use it appropriately, VLIW is a best practice and LLVM supports it. BTW, CS252 at Berkeley and Onur Mutlu's ETH lectures give a conventionally disparaging view of VLIW without pointing out its successes.
  - bbatha 2y ago
    Adding on, VLIW is only successful in AI/ML because GPUs are incapable of doing branching in a good way let alone prediction. I would guess the same story applies to DSPs. If someone figures out how to stick a branch predictor in those pipelines Im guessing the VLIW nature of those platforms will disappear overnight.
    - CalChris 2y ago
      The defining character of VLIW is to have the brilliant compiler software schedule dumb parallel hardware instructions statically and then not depend on power/transistor expensive dynamic branch prediction and OOO execution. In a perfect VLIW world that would mean you don't spend any transistors or power on branch prediction or out of order instruction searches. Indeed the original VLIW paper [1] spends vastly most its paragraphs on solving the (hard) compiler instruction scheduling problem with trace scheduling which is still used. The VLIW hardware itself is dead simple. [1] https://safari.ethz.ch/architecture/fall2022/lib/exe/fetch.php?media=p140-fisher.pdf https://safari.ethz.ch/architecture/fall2022/lib/exe/fetch.p... So if VLIW fits the problem it has fantastic performance characteristics. If it doesn't fit, and far and away most don't, then VLIW is terrible. VLIW is very brittle. I need to make a caveat about the Mill CPU which is a VLIW but I see I've written too much already.
ww520 2y ago
GCC has the _builtin_expect macro to give hint for branch prediction. C++ has added something similar recently .
- mhh__ 2y ago
  These are usually for the compiler rather than the CPU e.g. I don't want my error-handling code inlined! (But the compiler can't work this out without a hint)
  - astrange 2y ago
    Yes, there actually isn't a way to explicitly hint branch predictors on modern CPUs.
phire 2y ago
Because it can't actually see that return instruction until way too late. Apple M1 CPU here loads and decodes 8 instructions per cycle, and the instruction cache access, plus the decoding takes multiple cycles. I don't know exactly how many cycles (more cycles allow for bigger instruction caches, and Apple gave the M1 a massive 192KB instruction cache), but the absolute minimum is 3 cycles. And until the instruction is decoded, it has no idea that there is even a return instruction there. 3 cycles at 8 instructions per cycle is a full 24 instructions, so the M1 CPU will be a full 24 instructions past the return before it even knows the return exists. The loop body in this article is only 7 instructions long, so overrunning by an extra 24 instructions on every iteration of the loop would be a massive performance hit. What actually happens is that the branch predictor remembers the fact that there is a return at that address, and on the very next cycle after starting the icache fetch of the return instruction, it pops the return address of it's return address prediction stack and starts fetching code from there. For short functions, the branch predictor might need to follow the call on one cycle, and the return on the next cycle. The call instruction hasn't even finished decoding yet, but the branch predictor has already executed both the call and the return.

hindsightbias 2y ago

We could solve a lot of problems if every user had to take EE180.

082349872349872 2y ago

In this case, I'd consider BL (call) a fairly explicit signal of intent to RET?

dzaima 2y ago
Yep. For returns, the more important thing in the article, the "ret"[0] instruction behaves exactly identically to "br x30"[1], just with the hint that it's expected to match a "bl". On x86 things are less pretty as call/ret push/pop the ip from the stack, with no non-matching-hinted versions, but having such would also just not be particularly useful as unpaired call/ret would result in the stack pointer continually drifting without manual fixup (at which point jmp is just clearly better). [0]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/RET https://developer.arm.com/documentation/dui0802/a/A64-Genera... [1]: https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/BR?lang=en https://developer.arm.com/documentation/dui0802/a/A64-Genera...
- LegionMammal978 2y ago
  On 32-bit x86, there is the trap of trying to use call/pop to get the absolute instruction pointer. It will work correctly, but it will mess up any call stack prediction and cause great performance penalties. Hence why compiler-generated EIP shims use call/mov/ret instead. (But this is not such a big issue in x86-64 with its RIP-relative addressing.)

hansvm 2y ago

1. "Explicitly signaling your intent" takes space and time. Decoding isn't free, and even if there were no other downsides you'd want to be careful with that change. 2. It's a bit historical. Early CPUs didn't have a RAM/CPU discrepancy and didn't need pipelining. Code wasn't written to account for pipelining. As CPUs got a little faster relative to RAM, you added a few prediction mechanisms so that most consumers and workloads could actually use your brand new 2x faster gigaterrawatthournewton CPUs without having to rewrite all their code. Iterate 10-20 generations, where most software has never been written to care about branch prediction and where modern languages don't even expose the concept, and you have the current status quo.

rcxdude 2y ago

It's supported by some CPUs: the linux kernel has likely/unlikely macros to indicate whether a branch is expected to be taken or not in the common case (which uses GCC attributes which allow this to be propagated through to codegen). It's just that it's generally less effective: firstly because not all branches get annotated, some that are annotated are annotated incorrectly, and in a lot of cases the branching behaviour is data-dependent enough that you can't make an optimal static prediction at all.

pjc50 2y ago

The user doesn't know the capabilities of the system. In particular, anything compiled in is set in stone: you don't know the capabilities of systems yet unbuilt. New systems don't sell well unless they make existing code run faster, and sell badly if they require you to rebuild everything and make it non-backwards-compatible. The peak example of "let the user do the scheduling" was Itanium, which had a VLIW system which scheduled three instructions at once. It was a huge commercial failure, and allowed AMD to instead define the instruction set people wanted: X64 is IA32 but wider and with more registers, but not substantially different and certainly not as weird as Itanium.

magicalhippo 2y ago
I've lost count of the times I've sped up some existing code by removing the hand-optimized assembly and just used a plain C implementation or similar. Sure, it was hand-optimized assembly, but for a 10+ year old CPU. If you're going to do hand-optimized code for a given platform, include the baseline code and measure at runtime to pick the implementation.
- patmorgan23 2y ago
  Hand optimized assembly was necessary 30 years ago, and a good for several optimizations 20 years ago. But today's computers are SO FAST, it's just not necessary in most situations.

gpderetta 2y ago

Often, but not always, optimal scheduling is data dependent so it can't be statically computed at compile time.

mhh__ 2y ago

They want to be able to guess long, long, before actually executing the instructions.

crote 2y ago

You should look into the history of Itanium, it was designed around the idea that the compiler would do pretty much exactly that. It looked great on paper, but in practice nobody figured out how to actually write a compiler capable of doing it without constantly running into weird edge cases. X86 does have "prefetch" instructions, which tell the CPU that you want to use some data in the near future. There are also "branch hint" instructions which tell the CPU if a branch is usually taken or not. The problem is that they tend to make your code slower: the CPU is already more than capable of predicting it by itself, and the extra instructions slow down the overall execution because they take up cache space and have to be decoded too.

CalChris 2y ago
VLIW is pretty successful for loopy DSP and now AI/ML. However, Itanium was trying to work for general purpose code and then as you say, it constantly ran into weird edge cases. It seemed as if VLIW succumbed to the Peter Principle, it had risen to its level of incompetence. But as long as you use it appropriately, VLIW is a best practice and LLVM supports it. BTW, CS252 at Berkeley and Onur Mutlu's ETH lectures give a conventionally disparaging view of VLIW without pointing out its successes.
- bbatha 2y ago
  Adding on, VLIW is only successful in AI/ML because GPUs are incapable of doing branching in a good way let alone prediction. I would guess the same story applies to DSPs. If someone figures out how to stick a branch predictor in those pipelines Im guessing the VLIW nature of those platforms will disappear overnight.
  - CalChris 2y ago
    The defining character of VLIW is to have the brilliant compiler software schedule dumb parallel hardware instructions statically and then not depend on power/transistor expensive dynamic branch prediction and OOO execution. In a perfect VLIW world that would mean you don't spend any transistors or power on branch prediction or out of order instruction searches. Indeed the original VLIW paper [1] spends vastly most its paragraphs on solving the (hard) compiler instruction scheduling problem with trace scheduling which is still used. The VLIW hardware itself is dead simple. [1] https://safari.ethz.ch/architecture/fall2022/lib/exe/fetch.php?media=p140-fisher.pdf https://safari.ethz.ch/architecture/fall2022/lib/exe/fetch.p... So if VLIW fits the problem it has fantastic performance characteristics. If it doesn't fit, and far and away most don't, then VLIW is terrible. VLIW is very brittle. I need to make a caveat about the Mill CPU which is a VLIW but I see I've written too much already.

ww520 2y ago

GCC has the _builtin_expect macro to give hint for branch prediction. C++ has added something similar recently .

mhh__ 2y ago
These are usually for the compiler rather than the CPU e.g. I don't want my error-handling code inlined! (But the compiler can't work this out without a hint)
- astrange 2y ago
  Yes, there actually isn't a way to explicitly hint branch predictors on modern CPUs.

phire 2y ago

Because it can't actually see that return instruction until way too late. Apple M1 CPU here loads and decodes 8 instructions per cycle, and the instruction cache access, plus the decoding takes multiple cycles. I don't know exactly how many cycles (more cycles allow for bigger instruction caches, and Apple gave the M1 a massive 192KB instruction cache), but the absolute minimum is 3 cycles. And until the instruction is decoded, it has no idea that there is even a return instruction there. 3 cycles at 8 instructions per cycle is a full 24 instructions, so the M1 CPU will be a full 24 instructions past the return before it even knows the return exists. The loop body in this article is only 7 instructions long, so overrunning by an extra 24 instructions on every iteration of the loop would be a massive performance hit. What actually happens is that the branch predictor remembers the fact that there is a return at that address, and on the very next cycle after starting the icache fetch of the return instruction, it pops the return address of it's return address prediction stack and starts fetching code from there. For short functions, the branch predictor might need to follow the call on one cycle, and the return on the next cycle. The call instruction hasn't even finished decoding yet, but the branch predictor has already executed both the call and the return.