Understanding branch prediction

They are just generic ways of referring to cpu registers:

• Rd is usually denotes a destination register.
• Rs, Rt usually denote source registers.

For example, a cpu instruction could be:

add Rs,Rt,Rd

Which would mean: Rd = Rs+Rt

The Rd,Rs,Rt are placeholders for the actual registers used in this instruction. A specific example for this instruction could be:

add $1,$2,$3

Which would mean "write the sum of specific cpu registers $1 and $2 into $3".

Branch prediction is a microarchitecture technique for improving the performance of pipelined processors.

I know 3 ways a person can design a processor with branch prediction to handle mis-prediction: instruction cancellation, register renaming, or delay slots. (Are there any other ways?)

delay slots

The MIPS and the SHARC DSP and several other processors use delay slots. Delay slots can be seen as a very simple kind of branch prediction -- one that always predicts that a branch will never be taken. If there is a branch misprediction -- if the branch is actually taken -- then instructions in the delay slot are unconditionally executed anyway. This is an inherent problem with delay slots.

However, it is not an inherent problem with branch prediction.

instruction set compatibility

Most CPUs are designed to be binary-compatible with some previous CPU. Since many early CPUs completely finished executing one instruction before going on to the next, many modern CPUs try to maintain the illusion. Most processors act "as if" it executes one instruction completely before going on to the next, effectively acting "as if" it did not actually execute any of those wrong-way instruction on the wrong side of the branch. (Some people find delay slots "illogical" because delay slots break the illusion of executing one instruction completely before going on to the next).

In a pipelined processor, the results are not actually written (committed) to the register file or to memory until the last stage of the pipeline -- the write-back stage.

instruction cancellation

With instruction cancellation, when there is a branch mis-prediction, a feedback wire from the branch resolution stage to all the previous stages indicates that there was a mis-prediction. On the next clock tick, when every instruction in the pipeline moves forward to the next stage, all the instructions in the pipeline "behind" the branch are simultaneously transformed into a "bubble", the equivalent of a NOP instruction. Meanwhile, the instruction fetcher begins loading the pipeline with instructions from the "right-way branch". One at a time, each instructions reaches the write-back stage. Instructions that have been cancelled (transformed into a bubble) do not write anything to the register file or memory. That prevents the wrong values from ever showing up in the register file or memory. After the bubbles have all drained out, instructions from the right-way branch start hitting the write-back stage and writing the correct values to the register file or memory.

register renaming

I hear rumors that some superscalar processors with out-of-order execution use register renaming to enable eager execution -- to fetch instructions from both sides of the branch. As the instructions are loaded into the pipeline, the instruction decoder expands/renames short logical register names in the instruction into to longer physical names. The same register name in two different instructions on two sides of the branch is expanded to two different physical register names.

When the branch instruction gets to the resolution stage that finally resolves which direction it will really go, all the memory STORE instructions in the wrong branch are cancelled. Meanwhile, the instruction fetcher stops pulling instructions from the wrong branch and focuses on only the right branch.

As each instruction reaches the write-back stage, those that were from the wrong branch may (in some designs) write to a physical register, but the wrong-way data in those physical registers never actually influences any STORE instructions that are actually executed -- any STORE instruction with any direct or indirect dependency on that wrong-way data will be turned into a bubble that does nothing by the time it hits the write-back stage. All STOREs in the right-way branch will execute correctly, because they only use physical registers influenced by instructions from the right-way branch. Those physical registers are never overwritten by any instruction in the wrong-way branch.