4 ms·

The issue with jumps/branches during instruction fetch is that the CPU doesn't 100% know whether an instruction is a branch or not. OK, how is this an issue? We

by Cyph0n 10y ago

The issue with jumps/branches during instruction fetch is that the CPU doesn't 100% know whether an instruction is a branch or not. OK, how is this an issue? Well, the instruction prefetcher will end up fetching useless instructions! So "modern" (1980s+) CPUs add a branch predictor[1] to the fetch stage. The job of the branch predictor is to determine two things: (1) Is this instruction a branch? [2] (2) If it's a branch, is it taken or not? For the case of unconditional jumps, we can just focus on (1). Therefore, given that the branch predictor is never 100% accurate, even an unconditional branch can result in garbage instructions fetched into the CPU pipeline. So replacing some key unconditional jumps might in fact improve performance. [1]: Actually, I was lying. There is also the BTB, collapsing buffer, and trace cache. [2]: The fetch stage doesn't know what an instruction is; that's the job of the decode stage.

innocenat 10y ago
I understand your point. However, branch prediction is so good nowadays that it rarely matter, especially for short branch [1] My main concern about trace cache/micro-ops buffer is how it would act when it encounter an instruction boundary change? Would it get flushed? Decoding can be bottleneck for some workload (e.g. SIMD Integer). [1]: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html
- Cyph0n 10y ago
  I agree, it does seem kind of unusual to need something like this. My hope is that OP wrote about this because his/her workload was somehow struggling with trace cache misses for unconditional jumps. I can't really think of such a workload though...
- anarazel 10y ago
  Branch prediction has gotten a lot better, that's true. Especially by taking more preceding branches into account. But saying that branch mispredictions rarely matter seems a way too strong statement. In a lot of halfway performance critical software a large number of pipeline stalls are caused by wrongly predicted branches, and utilizing the pipeline efficiently is IMO becoming Mir, not less, important.
AgentME 10y ago
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.

by Cyph0n 10y ago

innocenat 10y ago

I understand your point. However, branch prediction is so good nowadays that it rarely matter, especially for short branch [1] My main concern about trace cache/micro-ops buffer is how it would act when it encounter an instruction boundary change? Would it get flushed? Decoding can be bottleneck for some workload (e.g. SIMD Integer). [1]: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html

Cyph0n 10y ago
I agree, it does seem kind of unusual to need something like this. My hope is that OP wrote about this because his/her workload was somehow struggling with trace cache misses for unconditional jumps. I can't really think of such a workload though...
anarazel 10y ago
Branch prediction has gotten a lot better, that's true. Especially by taking more preceding branches into account. But saying that branch mispredictions rarely matter seems a way too strong statement. In a lot of halfway performance critical software a large number of pipeline stalls are caused by wrongly predicted branches, and utilizing the pipeline efficiently is IMO becoming Mir, not less, important.

AgentME 10y ago

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.