2
$\begingroup$

I have recently been investigating CPU pipelining and branch prediction and have a question about how exactly these fit together.

If, for example, instructions are meant to be fetched in one stage of the pipeline and decoded in the next while the next instruction is fetched simultaneously, how is it possible for the pipeline to proceed without a stall when dynamic branch prediction is in operation?

As an instruction must be decoded before branch prediction can occur or be deemed unneeded, and as any prediction must be made before the next instruction can be fetched, how can an instruction be decoded while the next instruction is fetched in the same clock cycle?

$\endgroup$
2
$\begingroup$

As an instruction must be decoded before branch prediction can occur or be deemed unneeded,

That can be avoided. The fetch stage can do prediction based purely on the current PC, without looking at the instruction. Branch Target Prediction also enters the picture here, otherwise without decoding the branch target would be unavailable. Accidentally applying branch prediction to an instruction that turns out not to be a branch is not a disaster, just something to detect and signal a misprediction if necessary.

So this can be done with no bubble.

As an example, here is a diagram of the pipeline of the RISC-V BOOM processor (source), showing PC going to next-line predictor and the I\$ in parallel

enter image description here

any prediction must be made before the next instruction can be fetched

Why stop? Just keep predicting, it doesn't matter that the next instruction(s) have been fetched, flush them out if one of the later predictions "changes its mind". This gives you a lot of time to run slow but high quality predictors after the fast predictors. You could even do away with the fast predictors, but then there really would be a bubble for every "taken" prediction - an unconditional stall is overkill though, there's no reason to not at least fetch the next address (effectively predicting "not-taken").

As a practical example, AMD Bobcat takes several shots at branch prediction, some in parallel with decoding (Fetch3 through Fetch5):

enter image description here

In the BOOM diagram there are also several forms of branch prediction, but the Backing Predictor (the more complex predictor with higher accuracy) there is before decode rather than parallel with it.

$\endgroup$
0
$\begingroup$

It is called branch prediction. The whole point is that you can predict whether a branch will be taken or not before you actually know. Sometimes you are wrong.

So the processor reads and decodes the instruction that it predicts will be executed. If the prediction is found to be wrong, the processor has to start all over again, this time reading and decoding the right instructions.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I'm aware that branch prediction obviously occurs before the branch instruction is completed, but I was unsure whether instructions had to be decoded and identified as a branch instruction before prediction could occur. I hadn't considered that prediction could occur in the fetch stage using the instruction address $\endgroup$ – Connor Claypool Jul 4 at 16:26

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.