So before we go into how exactly Tomasulo's Algorithm works,
let's kind of see an overview picture of what's going on in there.
Just like what the helper instruction looks like. So
first, there is an instruction queue which I labeled here IQ. Instructions come
from the fetch unit in the order in which they were fetched and again,
these are only floating point instruction and then they're queued up here. So
this is basically like this is the kind of, all this instruction, the next one,
the next one, the next one and we will be kind of,
you know, dropping these instructions into the Tomasulo's algorithm machine in
the order in which they came. We always grab the next available instruction from
the instruction queue. And we want to put it into a reservation station.
There are a number of reservation stations that basically,
when one becomes available, we will put an instruction into one of those.
And the reservation stations are where instructions basically sit for
their parameters to become ready. There is a floating point register file.
So this is where your floating point registers are. And when an instruction is
inserted into the reservation station, the values that are already in registers,
meaning the values that are actually already present and ready for
execution, are going to be simply entered into the reservation station from
the register file. Once an instruction is actually ready to execute, it goes to
an execution unit. And you can have different types of execution units.
So for example this a adder, and this is a multiplier. So
simple floating point instructions will be done in the kind of adder unit, and
the more complicated like multiply and divide would be done in the multiplier
unit. Each of these units really have separate reservation stations,
where unit instructions that are going to that unit would wait.
Once such a unit has produced a result, the result will be broadcast on a bus.
So of course, the result would go to the register file. So pretty much all
the results that are ready would be available in the register file, so
that instructions that come in would simply grab them from there and
we don't have to worry where those values are going to come from.
But these results would also be broadcast to the reservation stations. Why?
Well, because there are instructions here that are waiting for
values that they need to be produced and
as values are produced, we need to tell these instructions that, you know,
now your value has been produced so that it need to also go here. So
pretty much here, you have some values that you already have in an interaction.
Some values that you, you're waiting for and you know what you're waiting for.
And then, when the value is finally broadcast, you check for
each of the value that is broadcast, whether this is the one we are waiting for
or not. Now, I have two of these for reservation station,
because a typical instruction will actually have two inputs. Like for
example, you're adding two numbers. And when you broadcast the result,
either of the two or both of them might need that result. For example,
if you're doing something like add R1, R1 and the instructions is producing R1
is currently in the multiply. When it broadcasts the resultant says this is R1.
We want to latch it into maybe both of the operands for this instruction. So we
need to compare basically what's being broadcast. Its name needs to be compared
with both of the inputs that you are waiting for, and then you select the one or
both of them or, none of them if this is not the value you are waiting for.
And finally, if the instruction is not an arithmetic instruction it's
actually a load into the floating point register file or
a store from it. Then the instruction would go to the address generation unit,
that's an integer operation so it's not going,
not going to through that, so basically we just compute the address. And
then we insert the instruction into the load buffer or a store buffer,
where the instructions are going to be queued up for going to memory.
And the load buffer only provides the data that I ask, the store buffer provides
both the address and the data to memory. When the load comes back from memory,
its value is also broadcasted on the CDB and goes to the appropriate register.
And also, all the values that are broadcast from the bus, are going to go here,
so that stores can get their values when they become available. So,
our store instruction needs to put a value in memory, is going to wait for
its floating point value that needs to be placed in memory.
Until it becomes available and only then be sent to the memory.
Unlike, arithmetic instructions which can execute out of order.
Basically, the only way for inputs to become available and
then they can go for loads and stores. They were done in order.
So basically, they didn't reorder loads and stores. And it will later,
consider how to do that. Modern processors will actually reorder loads and
stores too. So this is a lot simpler than in modern processors, but
this here is pretty much the way it's done now. Modulo some small adjustments.
So before we go into kind of the details of Tomasulo's algorithm,
let's just kind of give names to some things on this picture, and
then we will kind of discuss what each of these things really needs to do.
So, this part here, where we send the instruction from the instruction queue
into the reservation station, then the load store unit is called issue.
When the instruction is finally sent to execution from a reservation station,
it's called dispatch. And when the instruction is ready to broadcast its result,
we call that write result, or simply broadcast. So basically,
every instruction will be issued,. Meaning, get to the res station.
Eventually it gets to dispatch, because all of its inputs are at the end it's,
kind of gets to go to the unit. Once it's done, it's going to write
the result and that is when we consider the instruction completed. So now let's
see what happens when you issue, when you dispatch, and when you write result.