Branch prediction pipelines

This is not complete page.

---

Introduction

Three branch types

As it was mentioned in previous manual, BPU model tries to guess a direction of a branch. It enables the Fetch stage to continue fetching instructions without stalling the pipeline. Predicted instructions are fetched and enter the pipeline. Of course, BPU is not able to provide us with 100% legit information, that’s why there is a need in verifying its predictions. In case of detection of wrongly fetched instruction we have to flush from the pipeline this instruction and younger ones.

Pipeline modeling

Fetch

To fetch some instruction, microprocessor has to know its Program Counter ( PC). Simply, if previous instruction hadn’t been a branch, then instruction with PC incremented by 4 would have been fetched. But type of previous instruction is known just when it is at decode stage. And, in addition, sometimes PC of next instruction to fetch could be known only after previous instruction passed execute stage, e.g, conditional branch. So in order not to wait till previous instruction reaches some certain stage, BPU is used. It predicts target, i.e., next instruction’s PC.

Decode

At this stage we know type of the instruction which proceeds. Also here we can detect some mispredictions made by BPU, e.g. microprocessor fetched instruction with PC incremented by 4 after j PC + 48 instruction. If misprediction is uncovered at this stage, then wrongly fetched instruction is flushed from pipeline. This situation is called short flush.

Execute

At this stage the instruction is executed and all the relevant calculations are made. After this stage we know for sure next instruction’s PC. And, in case of detected misprediction, wrongly fetched instruction and all the younger instructions are flushed from pipeline. This situation is called flush.

What are the 3 branch types

Type	When do we know the direction	When do we know the target
Unconditional direct ( J, JAL)	Always taken	At Decode stage
Conditional direct ( BEQ, BNE etc.)	At Execute stage	At Decode stage
Unconditional indirect ( JR, JALR)	Always taken	At Execute stage

Implementation

I've chosen the idea of deductive method of explanation, i.e., I'll describe pipeline from tail to head. In my opinion, this will be clearer for readers.

Unconditional direct jumps

Decode stage

Here I will write that decode module sends actual information about the instruction to fetch module so that it could update BPU. Also I will write about actions performed in case of mispredioction.

Fetch stage

Here I will write about obtaining the target from decode module or from BPU respectively to their priority.

Conditional direct branches

Same as for unconditional direct jumps.

Execute stage

Decode stage

Fetch stage

Unconditional indirect jumps

Same

---

Conclusion

Branch Prediction Unit tries to guess instruction which should be fetched next. This unit can have faults, and we need to detect them as soon as it’s possible. Some mispredictions are detected at Execute stage and cause flushes, others – at Decode stage and cause short flushes with less penalty.