3 ms·

Why wouldn't the CPU 100% know whether an instruction is a branch or not? Doesn't it need to know to execute it?

• Cyph0n 10y ago
  Modern CPUs are pipelined, which is a fancy word for "splitting instruction processing into a number of stages to increase parallelism". The first stage is instruction fetch - "get the instruction at this address from memory". The second stage is instruction decode - "figure out what the instruction is (opcode) and its arguments (operands)". The important thing to understand is that all stages execute simultaneously. For example, when the pipeline is fetching instruction #2, it is also decoding instruction #1. So why not do branch prediction during decode so the CPU knows it's a branch? Well, it could, but then the prediction would only be available to the fetch stage in the next cycle! Keep reading if you want an illustrative example. So where does branch prediction come in? Let's take a simple example where your CPU doesn't have a branch predictor. The instruction stream is A B C D, where B is a branch that is taken and jumps to instruction X. I'll use this diagram to represent a 4-stage pipeline: [ | | | ]. The stages are: fetch, decode, execute, and write results. Just focus on the first two stages for this example. Let's walk through it cycle-by-cycle: * Cycle 1: [ A | | | ] -> A is fetched * Cycle 2: [ B | A | | ] -> B is fetched, A is decoded * Cycle 3: [ C | B | A | ] -> C is fetched, B is decoded, A is executed * Cycle 4: [ D | C | B | A ] -> D is fetched, C is decoded, B is executed, A write its results Cycle 4 is the moment when the CPU knows the result of B, i.e., taken or not taken. But there's a problem: we just ended up fetching two useless instructions! So the pipeline is flushed, and fetching starts from X. * Cycle 5: [ X | | | B ] -> X is fetched, B writes its results In other words, we effectively wasted two cycles. This is where branch prediction comes in. Branch prediction is added to the fetch stage in order to predict whether or not a branch is taken, and if it is taken, fetch the correct instructions. Let's add a branch predictor and repeat our example. For simplicity, we will assume a 100% accurate branch predictor. * Cycle 1: [ A | | | ] -> A is fetched * Cycle 2: [ B | A | | ] -> B is fetched, A is decoded Now B is in the fetch stage and is passed to the branch predictor. But we have yet to reach the decode stage, so the CPU has no idea if B is a branch!. First, the CPU decides if B is in fact a branch - BTB and trace cache are two options for implementing this - then it decides whether or not the branch will be taken. * Cycle 3: [ X | B | A | ] -> X is fetched, B is decoded, A is executed At this point, we have utilized our pipeline fully and have avoided wasting time on incorrect instructions.