Eventually this load does complete, and let's say brings us a value of 700, and
it's marked as done. Now we're going to do the branch and the add. Meanwhile,
we are going to be checking whether we can commit this instruction and
we can, because it's marked as done, and it's the next instruction to commit.
So we'll commit this instruction. Which will result in moving the commit pointer
here, and writing this value of 700 to register R1 and also,
making the RAT, now point here. Now, let's suppose that a branch takes longer to
figure out than the ADD. So this ADD completes, produces a value of let's say 3,
and is done. And that's all that happens here.
Again, this result would have been written to the registers, thus permanently
changing R2. And that's all that happens. Now, know that this result of 3 would
not have been written to the registers even with Thomas [UNKNOWN] algorithm,
because the renaming for R2, is pointing not to this instruction.
Meaning that we would have kept in the registers the value of 2, that we would
have written, for the divide because that's the latest R2. But in this case,
we don't do any of that. We just keep the values in the ROB as is. Eventually,
we get to resolve this branch and figure out that it's been mispredicted. So
now, the branch, will be marked as done.
We will now start fetching from the correct instructions but the question is,
how do we get rid of the ones, that we had wrong? Well what we
do is we annotate here that there has been a misprediction of this branch, and
that's all that happens as a result of its, execution. And we don't really fix
the misprediction. We continue fetching the wrong instructions because we don't
know how to get rid of this, until the commit reaches the point of the branch.
So when we commit this branch we realize that, after this branch, we were
fetching the wrong instructions. The PC that the branch should have created,
is different from the PC we have actually used. At that point what we do is,
we commit the branch normally. It doesn't write to any registers so
the commit just moves this. But if it's been mispredicted and
it was, what we do is we do the recovery before we restart the fetch from
the correct place. How do we do this recovery? Well with a raw based processor.
At the point where the commit has reached the branch, the registers,
contain exactly the values they need to contain, at the point of the branch.
All of the instructions prior to the branch have been committed,
which means that their updates have been reflected in the registers. And
none of the instructions after the branch, have updated the registers.
So the registers contain exactly the correct value at the point of the branch.
To undo these instructions, what we need to do, is two things.
One is, reverse the issuing of these instructions by simply making the ROB
empty at these points. So after we have committed the branch,
we make the ROB empty by simply putting the issue point in the same place.
So we will issue instructions again into these slots. We of course, as we issue
them unmark this done bit. Also the RAT now contains the wrong values. But
the questions, what are the right values for the RAT? Well because,
the registers contain exactly the correct values as of this point. Undoing
the damage in the RAT, simply consists of, rewriting whatever is in the RAT so
that each RAT entry points directly, to it's corresponding register. So now.
It looks like these instructions have never executed or issued for that matter.
And, we can begin fetching from the correct place, updating the renaming
as a result of that, and updating the issue pointed as a result of that.
As you can see, with the ROB based processor, we can do instructions out of
order, but we still can't figure out what the correct. Or that should have been,
if we did the right thing at the point of the branch. So as you can see,
here we have executed these instructions before we figured out the branch, but
we are still able to undo this damage. Overall, the recovery with
the ROB based processor consists of, making the right entries point to their
corresponding register so can, erase all of the renaming. Emptying out whatever
is in the ROB after we commit the offending branch instruction. And of course,
getting rid of whatever is leftover in the reservation stations and the ALU so,
basically free all the reservation stations and stop the ALUs from broadcasting
results in the future. So if, one of these instructions is still in the ALUs or
reservation stations. It's going to be, just dropped.