In-order fetch. So, we have an in-order frontend and we
have an out-of-order issue, writeback and commit.
So, what this is going to try and do is we're going to try and fix some of the
problems that we saw, oops, here, where we'll actually had, let's say this
instruction here, this add is waiting to issue because our issue was in order.
So, that instruction could issue. All of its inputs are ready.
R11 was written right there, or something like that.
So, R11 is ready. It's ready to issue.
But because we have in-order issue, by definition, we can't issue out-of-order.
So, now let's look at a machine where we can issue out-of-order.
So, we actually move it to the execute units, do our register fetch,
out-of-order. So, to do that, we actually have to add
another data structure, and this data structure we're going to call the issue
queue. And this is going to be something like an
associative FIFO, but it's not going to be FIFO, we're going to basically going to
store instructions into it, and then we're going to, we're going to put instructions
into it in order, because our fetch is in order, or frontend is in order.
But we're going to pull out of it out of order.
And, but we have to be a little careful, because when we go to pull out of that
data structure, we have to make sure that the.
All of the appropriate registers are, are ready.
So, all of our dependencies are ready or at least somewhere in the bypass or we can
go pick it off the bypass by the time it actually needs the value.
Or in our, in our bypass stage. Let's take a look here.
We still have architectural register file. We got rid of all that complex reorder
buffer stuff on this example. So, we don't have a reorder buffer.
We don't have a store buffer. We have out-of-order commit.
So, we're going to have the same problems we had before with precise exceptions in
this pipe but we, it's going to give us sort of easy introduction to understanding
what the issue queue looks like. So, the issue queue gets written when
instructions enter it. Sort of at the decode stage.
This is, itself is a register structure. So, it's like, flip flops in here and a
bunch of logic and stuff. So, you can just go from this stage to
this stage in the pipe without having any, registers.
So it gets read in there and things are basically going to update into this.
So, when things actually end up in the architecture register file, we're going to
mark bits in the issue queue, saying, oh, that register you were waiting on, it's
now ready. And if you get, let's say, two registers
that are ready and you're dependent on two registers, you can issue.
And we can issue out-of-order. Okay.
So, I have read and write here in the, the issue stage.
Why do I, why do I have that? Well, when you actually go to issue it you
basically want to mark that instruction as, oh, yeah, I actually did issue this
instruction. You want to, sometimes people build this
as actually remove the instruction from the issue queue.
In this basic case, we're gonna leave it in the issue queue until the end of the
pipe because we need some way to track the, the liveness of the instruction.
But the, the next processor we're basically gonna think of it as sort of a.
I, I won't say FIFO, because it's not strictly first in first out, but it's,
it's a data structure where you can put stuff in and then remove stuff out of.
So, it's a buffer or a multi entry buffer. Okay, let's, let's take a look inside the
issue queue. And this is assuming something like MIPS.
So, in our issue queue here we're going to have.
First of all, we're going to actually going to have the Opcode, because we're
going to have multiple instructions sort of ganging up in here.
So, it's possible it could be like, I don't know, in this case one, two, three,
four, five. There's five instructions just sort of
sitting in this, in this data structure. So, just sort of slacking.
There's a buffer and a slack in the front of your pipe, effectively.
You might need the immediate's values, because that's sort of part of the Opcode,
or part of the instruction, and then, then we're going to basically have things for
the three different registers. And what were going to put in here is we
are going to put the register identifiers, so.
Here let's look, let's look at the sources first, because that makes a little more
sense. The V bit is going to say that this
instruction needs the source. So, it's possible that, as we said, you
know, there's some like an immediate instructions don't read both source
operands. So, for an immediate, only one, probably
this valid bit is going to be set and this one is going to be zero.
The P bit is pending. So, what that means is somewhere, later in
the pipe there is a in-flight instruction that writes to that register.
So, we're going to basically track that with a bit here saying that it, that iis
still pending. Now, the reason we actually have to keep
that pending information and the validity informations are separate and why need to
keep both of them is it's possible that multiple instructions could light up
simultaneously as being ready to go. So, if you have, let's say, two
instructions that are both dependent only on register five and register five is not
ready, it's, it's the destination of a multiply.
But then register five gets ridden. It's going to actually clear the pending
bits. So, it's no longer pending and it might be
in multiple places. So, it might be like here and here or
maybe even there. It's going to clear the pending bits, and
whoever is trying to read register five, and then, because we're only let's say
going to have single issue on this processor.
You can only pull one thing out at a time. So, you need to sort of pull one thing out
and you need someway to leave the other instruction in the issue queue having all
of it's operands ready. So, that's how you do that.
Okay, so how do we figure out if an instruction is ready?
Well, we see if the if the, if it actually uses it, that the operand, uses the,
excuse me, the, particular upper and identifier and we see if it's pending.
And then we have to check the other, other for, for two inputs.
We need to check the two inputs, and then we also have to make sure there's no
structural hazard somewhere else in the pipe, like if we're trying to schedule
write, write ports. And we're going to use the scoreboard to
do that. The other thing is if we want high
performance, we probably don't want to have to wait for values to get to the end
of the pipe. So, in reality, this, this, this is even
going to get more complicated because it's going to be, these things plus information
coming from the scoreboard which is when, when a particular register identifier is
ready or when a particular register is ready.
Let's talk about the destination here. This just tracks whether an instruction
writes a destination or not. And like I said, in these, in these basic
pipelines, we're going to leave instructions in the instruction queue
until they get to the end of the pipe. And when it gets to the end of the pipe,
this is where we go to check to see, what other locations we need to, sort of, clear
out. So, if there's an instruction, let's say,
sitting here, which has the valid bits set, and its range of register five is the
destination. When that instruction commits, we're going
to clear it out of, the issue queue. And, we're going to say, oh well it wrote
register five. Let's scan through all these other places
and look for places that say register five.
And if they say register five, we are going to flip the pending bid from pending
to not pending anymore and we're going to remove the instruction from the issue
queue. Okay, so, centralized versus distributed
issue queues. In a, in a, in a sort of logical sense, in
a perfect world it's probably nice to have a big centralized issue queue.
You can scan over all the instructions. You don't have to sort of look around, but
this can sometimes be harder to implement, because you have to put all of your
instructions in one location. And sometimes they don't necessarily sort
of cross communicate very well. Like floating points units.
They have floating point registers versus integer register files is one type.
They don't necessarily need a whole lot of communication.
So, you could have distributed instruction queues where you sort of steer let's say
here the execute or ALU and memory ops to one of these for these functional units.
They have a different instruction queue just for, multiplies or something like
that. I'm going to, put a paper on the website
for you guys all to read. It's Tomasulo algorithm.
It's a very famous paper, and in that they talk about distributed instruction queues.
Strangely enough, sort of, the first place in literature that these instruction
queues showed up was around that time, or in that paper, and they actually go
straight to the distributed version and kind of skip the centralized version,
which I always found a little bit odd but lots of people build centralized ones
today. One of the, one of the reasons that the I
think the Tomasulo algorithm people went for this distributing one first is because
they were actually implementing it in multiple discreet chips.
So they had a issue cube per chip. So, they had a floating point chip and a
integer chip and they steered the instructions.
They didn't wanna have to have one data structure that cross, cross two chips.
Today we have, you know, lots of integration.
So, we don't have to worry about that as much.
Okay, so, I just wanted to briefly say, this is a question that came up last time,
and scoreboards. If you have to worry about
write-after-write hazards in the pipe. The things we are talking about today, we
didn't have to really worry about that. But this is something to talk about next
time, we're gonna have to think about better scoreboards.
It looks the same as the previous scoreboard, but you might need to keep the
functional unit, or you need to keep the functional unit number, or some bits that
represent the functional unit, and then those march down the pipe versus 1s
marching down the pipe. You have, let's say, different numbers,
like one, two, three, or you have other things marching down the pipe.
But that's only if you have to track write-after-write hazards.
Okay. So.
That was a quick aside. Let's look at this in order, fetch,
out-of-order issue, out-of-order, writeback and out-of-order commit
processor in a pipeline diagram. And I'm going to show a new little thing
in our pipeline diagram here, we have a lowercase i.
Which means the instruction enters the issue queue.
And then, when it exits the issue queue, it, it just starts going down into the
issue stage of the pipe. And, trying to think where at, where am I?
This is not that complicated of a drawing. Here I'm actually showing the, the issue
queue. What is in the issue queue.
So I have two, or excuse me, three issue queue slots.
Because, this is a relatively simplistic pipe.
The, this first instruction which goes to execute register two and register three
are just already ready, so we don't have to worry about it.
But an example of something that's more interesting, let's say, is, I don't know.
Where is it going. Here we go.
This will enter the issue queue. But register twelve does not become ready
until late. So, once that becomes, comes ready, we can
basically start pulling things out of the issue queue, and, and issue that
instruction. So that, that shows up.
Let's see if we can show that here, register, what is this, fourteen, twelve?
Okay. So this one here, we're waiting for, that
to happen. Let's see.
Yeah, we're waiting for no, where is it twelve, just add.
[inaudible] this long. Wrong.
Yes. That is actually is what I want to show
here. This is interesting.
That value actually becomes ready, early. But.
Is that what's actually happening here, the value becomes ready at the end of this
execute stage. But it can't go to issue.
At that cycle because there's something else issuing.
So, it has to be pushed out. So, we're only doing a single issue per
cycle. If we had multiple issues, you could think
of something more interesting happening here.
Yeah, so this is actually a really complicated case because if we pull this
back let's say to here we get a writeback hazard.
The W would conflict with the other W. If we try to issue here, sorry, that was a
reissue here. If we try to issue, here we get a
structural hazard on the issue. So, it actually gets pushed way out there.
So, it's kind of a, kind of a bummer. So, sometimes you just lose.
Okay, so, here's a interesting case. So, let's assume that all the instructions
are preloaded into the issue queue. So, showing this, we have fetch, decode,
issue, issue, issue, and basically this thing's just sort of sitting in the issue
queue and then we start looking. What happens?
Those the performance get better than the previous example?
So, interesting enough, even you if you sort of issue everything into the pipe
early and then just sort of fill up your issue queue.
Pulling out of the issue queue can still be limiter and the number of ALUs can
still be a limiter. So, there is other structural hazards.
The performance of this code in this pipeline does not actually get any better
which is sort of interesting. You think, Oh, well, I don't have to wait
for things to dribble into my instruction queue.
I just sort of preload my instruction queue.
But the performance really, really doesn't end up being better.
So this motivates us going to both out of order mixed with duplication of
structures. Like, maybe we can issue two instructions
at the same time. And maybe we can have two ALUs.
So this is, motivates us having a superscalar.