So we will see now that, another benefit of loop unrolling it that is allows us
also to reduce the CPI in addition, to reducing the number of instructions.
To get some idea for how the CPI changes, we need to have a processor. So let's
assume we have a, 4-issue in-order processor, meaning it's only able to look at
the next four instructions to see what can be executed together. Meaning it can
only look at the next four instructions, to see what it can execute together.
And let's assume that the processor has perfect branch prediction. So first,
let's look at what happens when we try to execute the original loop.
So to see what happens with this loop in this processor, let's look cycle by
cycle at which instructions can execute. In the very first cycle,
we will try to do this load and then we will try to see whether we can execute
the next instruction in order in the same cycle, but we cannot because it
depends on the load. So, this instruction has to be done here. Now, we will look
at the next instruction, and try to execute it in order in the same cycle, but
we cannot because it depends on R2 again, so we move here. The next instruction,
however, does not depend on the previous one, so we can do this add here. But
then, for the branch, it does depend on R1 so it can be only done here.
Because we have perfect branch prediction, this load has also been fetched from
the next iteration and it doesn't depend on the branch that was done here so
we will actually do the load for the next iteration. And then, we will,
again, not be able to do the add. So the add happens in the next cycle. And
then, in this cycle, these two happen and so on. So overall, after this initial
load that had to be done by itself just because, there was no branch before it,
it takes us three cycles to do all five of the instructions in the loop.
So the CPI here, is 3 cycles for 5 instructions. But
remember that, we can do scheduling of this loop to try to improve the CPI. So
before we get into what's the CPI of the unrolled loop,
let's see what the CPI is if we schedule this loop body.
Our scheduling will start out with this loop body, and then try to maximize
the CPI that we can get, by reordering the instructions. So, clearly,
here, this load could, not be done in parallel with the next instruction,
because there is a dependence there. So we need to find something, and
it cannot be the branch, because it needs to stay at the end of the iteration.
That we can put here, and that this ADDI can move there.
So our scheduling algorithm will move the ADDI here. So
now that we are subtracting 4 from R1 here, we need to adjust the store so that
it adds back the 4 that we decremented here. Because, this store was supposed to
store to the same element as the load. Now, however, we have moved R1, so
to access the same element as the load, we need to add 4 here. Note that
moving the ADDI it really the only scheduling freedom we have here because.
We need to do the load, and the ADD, and the store in that order so
they cannot be re-ordered, the branch needs to stay at the end of the loop, so
pretty much the only freedom we have is where is the ADDI going to happen.
So now let's look at what happens cycle-by-cycle. We can do the load in
the first cycle. The ADDI can be done, together with the load. But
the ADD to what we loaded still has to be done in the next cycle. The store
cannot be done until this ADD is complete. The branch can still proceed
in parallel with the store. And now, because of perfect branch prediction,
we're going to move here, and we can try to do the load for the next iteration.
Note that R1 has been updated here in the previous iteration, so all the way
through here we really did not modify R1, so pretty much the store of the branch
didn't modify R1. That's the only registered dependence that this load has, so
the load can be done here. And then we can also do the R1 update here,
because this ADDI only depends on R1, and the R1 has been updated here.
So we can do this. So as you can see, now it takes two cycles,
to do these five instructions. So the CPI we get is now 2 over 5.
It took us two cycles to do the five instructions. This is significantly better,
than without scheduling so, scheduling did help