So before we discuss branch station, let's have a reminder of what a branch does
in a pipeline. A branch instruction like this will compare registers R1 and
R2. And if they are equal, jump to the label.
This is usually implemented by having, in the immediate part of
the instruction field, the difference between the next instructions PC and
the PC that should be at the label. So that the branch effectively, if R1 and
R2 are equal, would just add the immediate operand to its current PC.
So that the branch, if R1 and R2 are equal, will add the immediate
operand to the PC that it computed for the next instruction. Now the problem
with branches is that if the branch condition is not met, just increment the PC.
For example, if the size of the branch instruction is four, then the PC
will just move by 4 bytes. However, if the branch condition is satisfied,
in this case if R2 and R1 are equal, then the branch will increment the PC and
also add the immediate to it, so the next instruction we fetch will be
at this label. Now let's look at what happens when a branch goes to a pipeline.
Let's say we have a classical pipeline with a Fetch, Read, ALU, Memory and
Write stages. And let's say that towards the end of the ALU stage is,
we actually figure out if a branch is taken or not. In the first cycle,
we fetched this branch. In the second cycle, the branch moves here,
where it reads the operand. So it's reading R1 and R2 but
we have no chance of telling whether the branch will be taken or not.
So it's no telling whether the branch will be taken or not.
So we either don't fetch anything here or we fetch something here. Let's say we
fetch some sort of a green instruction here. At the end of this cycle,
we still don't know whether the branch will be taken. We have now read R1 and
R2, but we haven't compared them yet. So when the branch is in the ALU stage,
the green instruction we have fetched after the branch moves here, and
we fetch another instruction, let's say that is a purple instruction.
At the end of this cycle, we finally know whether the branch is taken.
Now there are two possibilities. Either we
have fetched the correct instructions, for example, the branch is not taken, and
we have taken the instructions that follow the branch. The branch is not taken,
that means the PC just gets incremented and we fetched the right instructions.
In which case, we have no bubble in our pipeline. We can just proceed. We just
fetched the right instructions. The second possibility is that the branch for
example is taken and we fetched the next instructions. In which case,
we have to cancel these instructions. In the next cycle,
these two cancelled instructions move on through the pipeline. And
we finally fetch the instruction that we know is correctly fetched. So
what happens is if we correctly guessed what should be fetched after the branch,
then there is no penalty. The branch finishes and then the next instruction will
finish right after the branch. However, if we mispredicted what will happen
during the branch and refreshed the wrong things, then the branch effectively
took three cycles to execute because the branch actually finishes in one cycle.
But then there are two empty cycles when we don't finish anything. So, overall,
the cost of the branch was really three cycles instead of one inner pipeline.
Meaning, the branch cost us one cycle, which is normal for
every instruction, plus two cycles because of a misprediction.
Now you also see why it never pays to not fetch something after the branch.
If we don't fetch anything after the branch until we are sure what to fetch,
then we are guaranteed to have two empty slots after the branch. So,
somehow, in that case, regardless of whether we would have guessed correctly or
not, we have a two-cycle penalty. So we'd rather have the two-cycle penalty some
of the time than all of the time. Another thing that is important to
note is that at the end of the fetch cycle where we fetch the branch,
we don't really know anything about this instruction yet.
We have just obtained the instruction word, meaning, the 4 bytes that
present an instruction. But we haven't even begun decoding the branch. So
what happens is next cycle we have to fetch something based only on
the knowledge of the branch address. We don't even know whether its a branch or
not. So when we are fetching an instruction, we don't it is a branch but
we already have to make a prediction of whether it's a taken branch.