Pipeline Problems: Branch Instructions

Branch instructions are those that tell the processor to choose the next instruction to be executed - based on the results of another instruction.

Branch instructions can be troublesome in a pipeline if a branch is conditional on the results of an instruction which has not yet finished its path through the pipeline.

For example:

Loop :

add $r3, $r2, $r1
sub $r6, $r5, $r4
beq $r3, $r6, Loop

The example above instructs the processor to add r1 and r2 and put the result in r3, then subtract r4 from r5, storing the difference in r6

In the third instruction, beq stands for branch if equal.

If the contents of r3 and r6 are equal, the processor should execute the instruction labeled "Loop." Otherwise, it should continue to the next instruction.

In this example, the processor cannot make a decision about which branch to take because neither the value of r3 or r6 have yet been written into the registers.

The processor could stall, but a more sophisticated method of dealing with branch instructions is branch prediction.

The processor 'makes a guess' about which path to take:

If the guess is wrong, anything written into the registers must be cleared, and the pipeline must be started again with the correct instruction.

Some methods of branch prediction depend on stereotypical behavior.

Branches pointing backward are taken about 90% of the time since backward-pointing branches are often found at the bottom of loops.
Branches pointing forward, are only taken approximately 50% of the time.

Thus, it would be logical for processors to always follow the branch when it points backward, but not when it points forward.

Other methods of branch prediction are less static: processors that use dynamic prediction keep a history for each branch and uses it to predict future branches.

These processors are correct in their predictions 90% of the time.

Still other processors forgo the entire branch prediction ordeal. The RISC System/6000 fetches and starts decoding instructions from both sides of the branch. When it determines which branch should be followed, it then sends the correct instructions down the pipeline to be executed.