3
\$\begingroup\$

We are just learning about branch prediction so I might not totally understand how they work, but as I understand it, the branches are set to predict either taken or not taken. The pipeline will start processing the next instruction or two before the branch is decided. Once the branch is decided, if the prediction was correct nothing happens but if the prediction was wrong, the pipeline simply switches to processing the correct instruction at the next clock.

This leads me to my question.

Say I had some assembly like this:

loop: addi r1 r1 1
sub r2 $0 r3
...
...(other random things)
...
bne r1 $0 loop
sw r2 0(r1)

If the branch were predicted as taken, the values of r1 and r2 would be overwritten before the branch was resolved and then sw would have the wrong values. How does one deal with this? Is this just an inherent problem in branch prediction or is there a protocol for storing those values until the branch has been decided?

Thank you!!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd be interested in the source of your rumors. My understanding what that eager execution was not used because its yield is a sure 50% (well as a first estimate) while branch prediction allowed you to have higher yield in practice. \$\endgroup\$ – AProgrammer Dec 13 '15 at 12:36
  • \$\begingroup\$ @AProgrammer: If you really want to know the source, you might consider clicking on the links in the answer in the "register renaming" section. In particular, you might want to click on the "eager execution", and on that page, click on the link to the book "Processor architecture: from dataflow to superscalar and beyond", and start reading the "Eager execution" section beginning near the bottom of page 148. \$\endgroup\$ – davidcary Dec 15 '15 at 7:50
  • \$\begingroup\$ Your "50%" number may be true on a limited CPU where the predicted branch completely saturates every execution unit. However, some superscalar processors have 8 or more execution units and rarely find enough runnable instructions in the predicted branch to keep all 8 execution units working. Rather than let the remaining execution units sit idle, if we instead allow the otherwise-idle execution units to work on the not-predicted branch, it doesn't slow anything down when the prediction is correct, and it speeds things up when the prediction is incorrect, improving benchmark scores. \$\endgroup\$ – davidcary Dec 15 '15 at 8:33
  • \$\begingroup\$ @davidcary - How can we implement instruction cancellation by hardware? or int other terms how can we force NOP just by using harware? \$\endgroup\$ – Mayank Jain Sep 19 '16 at 0:48
  • 1
    \$\begingroup\$ @MayankJain: Consider re-asking that question as a new top-level question, as recommended by "Asked question, then had a related new question". \$\endgroup\$ – davidcary Sep 19 '16 at 2:23
2
\$\begingroup\$

It's very possible that the instruction will be executed, since your question refers specifically to MIPS in the tags. It lies in what is called a branch delay slot, and it is executed without regard to the result of the immediately-preceding branch. This could be considered a primitive branch predictor with side effects, where the prediction is to not branch, and the side effect is for the pipeline to not be fully flushed and all actions "undone". Compilers will generally be aware of this for a given architecture and reorder instructions (or insert a nop) appropriately.

On the other side of the coin, there are processors that actually have hazards of overwriting necessary registers when a branch is mispredicted. This can be handled using a form of register renaming, in which one of two things happen:

  • Values written get written to a different set of registers with speculative data; that set of registers is then used if the branch prediction was correct (Future File)
  • Old values are written to a history buffer to be restored if the branch prediction happened to mis-predict the path to be taken.

Of course, register renaming of registers to either speculative or history buffers can be combined with more advanced register renaming techniques that eliminate the risk of value overwrites and enhance performance in some other way by removing serialization of instructions using a register, one after another.

\$\endgroup\$
  • \$\begingroup\$ You may want to finish your answer! \$\endgroup\$ – magmastonealex Dec 10 '15 at 0:40
  • \$\begingroup\$ @magmastonealex My bad, that should have been deleted before I can complete it. I realized there was a flaw in my logic (I was writing about a mechanism for handling cache misses and not branch mispredictions and I didn't delete it fully). I'll look for a more correct behavior for that portion. \$\endgroup\$ – ζ-- Dec 10 '15 at 0:41
  • \$\begingroup\$ @magmastonealex Fixed \$\endgroup\$ – ζ-- Dec 10 '15 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.