So, now let's look at the process of pipeline stalls and
how they can happen. Let's say we have a five stage pipeline and
this is where we fetch the instruction, then we decode it and read registers,
then we use the ALU to compute the result of the instruction, then we access
memory. This is a loaded store instruction. And then we write the result of
the instruction to a register. This is what happens in cycle one, cycle two,
cycle three, etc. Supposed we have a load instruction here in our pipeline. And
it's going in to R1 something from memory. While this load is in
the ALU stage here computing the address. So it hasn't accessed memory yet.
Suppose we have an add instruction that needs to use the R1 and
this instruction is already reading registers here so it can compute the result
in the next stage, and we have a subsequence instruction here, let's say,
another add that adds our 2 to 1 and produces our 3.
So now the problem is that this ADD here,
is reading the wrong value of the register. So, if we let it proceed further,
because in the next cycle, this load will be here and
now, it's actually accessing memory. But by then, it's too late. This ADD,
if it moves here will use the value of R1 that is the wrong one.
It's the value of the R1 before the load actually produced a value and
this is where we get a processor stall. Pretty much what needs to happen is,
the add needs to stay here until it gets the correct value of R1 from the load.
Because the add is stuck here, the next instruction also needs to
stay where it is, because it cannot move here. That means that in our pipeline,
now we have a bubble, just like we did in the production line. We can have
more than one bubble because of a single dependence between instructions. So
in this example, next cycle, the load has loaded the value
from memory into R1 and is now writing that value to a register.
The ADD needs to repeat the read of R1 because in this cycle here,
it still didn't get the correct value of R1.
Although the load was now loading that value from memory the R1 was not
written yet. So, now the load is writing, the ADD repeats the read and
because the ADD is still here, the next instruction is still stuck here and
that means that we have two cycles worth of stall. In this cycle it could be
that for example the load is writing to R1 in the first half of the cycle and
this ADD is reading R1 in the second half of the cycle. So next cycle,
the ADD can move on. But it could be that the load actually takes a full
cycle to write the result, in which case we will have another cycle stalling.
So let's suppose that we can do this,
that we can write R1 and then read it in the same cycle. If that is the case,
the next cycle, which is cycle four, we will have the load leaves the pipeline.
The pipeline bubble here moves forward in the pipeline, this pipeline bubble
moves forward in the pipeline and now the ad finally moves on. So the next
instruction after this side can move on. We can fetch the next instruction, and
so on. So as you can see here. A processor pipeline stall creates
a problem because normally every cycle after the load leaves, every cycle will
have the next instruction leave, but in this case after the load leaves, there
are two cycles worth of pipeline bubble that finish before the next instruction.
So, really instead of having just one cycle for the load, one cycle for
the add and so on to finish, we now have one cycle for the load,
2 cycles worth of not finishing anything and then the ADD and so on and
that causes our pipeline to have a CPI of more than 1.
If we count the 3 instructions, 1, 2, 3 instructions we'll finish over 5 cycles.
Three cycles for them and 2 cycles for the bubble. So really, our CPI is
significantly larger than one. A processor pipeline may also need to be flushed.
This is an example that we didn't have in our car assembly line.