How can instruction fetch and decode pipeline stages run simultaneously in a CPU with dynamic branch prediction?

Question

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?

Answer 1

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

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):

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.

Answer 2

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.