And let's start taking about exceptions and interrupts.
And then we're going to start talking about superscalar two.
So we'll start talking about out of order superscalars.
So how do you actually start to execute instructions when they're not in
programmatic order? And when you first hear about this, you're
gonna say, well how is that possible? You know, you shouldn't be able to execute
instructions out of order. But it's very, it's relatively easy.
You can actually, just, you know, execute them out of order.
Maybe you want to commit them in order. That may even be optional.
But let's, let's all start off by talking about interrupts.
So what's, what's an interrupt? So an interrupt is typically some external
or internal event that happens. And it may be synchronous to an
instruction or it may just be some external thing that happens.
That is going to redirect your control flow somewhere else for a little bit of
time and then it will come back to the instruction that you were asked before.
So here's our program. It's executing, happily executing
structure mean. I - one, then it's going to execute
instruction i. Instruction i doesn't actually commit
instead we vector over to interrupt handler which is also some sequence of
instructions that process some problem let's say with instruction i.
And then when it's done it'll come back, re-execute instruction one, or instruction
i. Maybe, maybe not, we'll see why there's
some cases that you may not actually go to re-execute this instruction, if it had a
fatal fault. And then continue on.
Typically, I wanted to point out that, a lot of times, this is done, sort of, for
system level code, or operating system level code or a hypervisor level code that
you'll jump someplace else. So, a good example of this is a timer
interrupt on a processor. It goes off.
It'll re-vector you to someplace else where you have to sort of update the
internal time of the machine and then, you go back to the instruction sequence that
you were executing before. So let's, let's look at some of these
causes. So.
We'll name the, first set of interrupts here asynchronous interrupts, or, some
people call these excep, external events or external interrupts.
And, some good examples, as I said before, are, devices cause interrupts.
So something like the programmable interrupt timer on, X86 processor will
cause a timer tick every once in a while, or every 100 times a second, is, is
pretty, you probable other devices, You know, your network card gets a packet
in on it. And the packet needs to be processed, so
it needs to be read of the network and be put into ram somewhere.
Hardware failures. So things like EEC memory errors.
So its error correcting code memory errors in your main memory will sometimes cause
interrupts to happen or asynchronous events to happen.
Synchronous things sometimes people call these exceptions or traps.
I'm actually calling all of these interrupts because from a naming
perspective you read different architectural manuals they all rename
these things slightly different and there is no sort of common utilization of the
terms. But if you're, you're using something like
x86 a synchronis interrupt is usually called either a trap or an exception.
But that is not common across all other architectures are not x86.
So some good examples of this is if you, try to execute an instruction, which is
not in the ISA manual. It's a garbley, gobbledygook of bits on,
on the disc. So it was an error code, effectively, or
some non-valid instruction, you get an illegal instruction, exception.
Or if you're trying to execute, let's say an operating system-level instruction.
We haven't talked about this in great detail, we'll touch on this later in the
course. But if you're trying to execute some
instruction that only the operating system should be able to execute but you're
executing it from your user program. Then, you're trying to execute something
like a privilege instruction. That's a good way to have this happen.
Earth medic overflow. Some architectures have it when the,
precision of your numbers falls outside the scope of what you can actually
accurately represent, you'll get an overflow exception, or an underflow
exception. Similar sorts of things can happen in a
floating point unit. So, great example of this is if you end up
with what are called denormalized numbers, so in floating point numbers this means
you basically have also lost precision in your floating point unit, so you, you fall
out of the range of numbers that they can represent very well, and you end up in
this other space that are called denormalized numbers.
You get an exception usually. Sometimes other sorts of things that fall
into this case are things like divide by zero.
You try to divide by zero, you'll sometimes get exceptions.
And you can do that. That's a great way, if you on your x86, if
you guys want to write a program, Write a simple C program,
Take some number, Divide it by zero.
And then build a number program. You'll get a printout.
The operating system will, you'll get an exception.
The OS will print out divide by zero fault.
And the program will stop. It will kill your program.
Unaligned memory. Some architectures don't allow you to
access memory in a unaligned manner. Some architectures do.
So something like MIPS, the MIPS instruction set, if you go to try to
execute a unaligned instruction sequence or unaligned load, will say, on the
earlier versions of MIPS, you'll actually get a unaligned memory access.
Later, actually, later MIPS have it as a option.
You can either have a, have it take a trap or not take a trap.
Common thing page faults. So we talk about paging later in this
course. But, if you go try to access some piece of
memory and the memory's not mapped in correctly.
So you, you just can't, the machine physically can't go find memory.
You'll take a, a trap. And then finally, the things like system
calls or interrupts on x86. There's an instruction called int, which
actually causes a, just an interrupt to occur.
And then it takes as a parameter a number. So that's how system calls have
traditionally worked on x86. They later replaced it with actually, an
instruction called sys enter which, does a similar sort of thing with a little bit
cleaner semantics. So I think we, oh actually there's one
point I wanted to talk about asynchronous interrupts.
With asynchronous interrupts, it's hard to know when to deliver the interrupt.
Cuz it's not pegged to a specific instruction.
If the instructions are going down the pipeline, you don't necessarily know
whether to attack it to the first instruction that's in the pipe.
I think it's at the sort of a fetch stage. I think it's at the execute stage.
I think it's at the write back stage. So that's, that's a, that's a challenge.
Another important thing to think about with, asynchronous interrupts is,
sometimes multiple of them go off at the same time.
So let's say your timer interrupt goes off at, at, time t0.
= zero, your, network card gets a packet in and someone hits the keyboard exactly
at the same time. Well, which, which should happen?
Which should you actually go handle? Typically machines have a prioritized
inner-request mechanism. So there would be some sort of priority
encoder there which will determine which is the highest priority.
Some of them, some machines will actually have re-programmable priority interrupt
encoders effectively which will allow you, allow the system software, the operating
system to decide what is the highest priority interrupt to go take in that
case. Sometimes machines will just sort of make
a decision, or the objects of the, of the machine will sort of make a decision, and
say these classes of interrupts are not ver, or asynchronous interrupts are not
very easy to handle so we'll sort of put those in these of low priority bucket, and
then some small set you'll actually be alter sort of re, re-prioritize if you
will. Oh.
Oh, yeah. So, I wanted to talk about this.
What actually happens, when you take a interrupt, from a hardware mechanism
perspective. So the, this is a very idealized view, but
from a mechanical perspective things need to happen in a machine.
There's some state that needs to be updated.
The first thing that needs to happen is, you should basically stop the program at
some point. And you should try to save the program
counter somewhere. Cuz if we want to come back to, let's say,
the instruction that took the interrupt, We need to know where to come back to.
But we're going to go and execute some other piece of code in the meantime.
So our, we can't just save it in the program counter.
We need to save it off. And that's typically called either an
exceptional PC. So EPC that's, what its called on, on a
MIPS, MIPS processor. On x86, I'm trying to remember what it
does. I think it actually gets, pushed onto a
systems stack. So it gets put into memory somewhere.
And if you had something like MIPS, one of the tricky things here is all of your
registers. Are still live from the previous
instruction sequence here. So all of a sudden you, you jump into a
new piece of code and all of your instructions are still, or all of your
registers are still live, They have values you can't throw away.
And you're in the interrupt exception handler.
What do you do? Well there's, there's different,
mechanisms to this, to, to have this happen.
Some architectures, something like MIPS actually reserves two registers that are
only allowed to be used by interrupt handlers.
This is actually a pretty poor solution in my opinion.
So they, they save off two registers. I believe it is, it's somewhere high, it's
like, maybe like 28 and 29. Registers 28 and 29, are not allowed to be
used by the, basically operating system, or the user code and it's only used by
interrupt handlers, in the operating system to save off state.
And what happens in that case is you could use those registers to basically take the
other registers, Compute some addresses and do a store.
Cuz if you recall on, on MIPS, you need to have an address to do the store to.
So you compose the address into, let's say, register 28, and then use that as the
store address. And you can store off all of the other
registers into memory somewhere. And then you can unwind that back when
you're, when you're going to return from the interrupt.
So it's a, a complicated dance. Something like x86, there is some power
mechanisms they are which actually take it and take a lot of your registers and put
them on to a in memory stock for you. So, it's typically, well it's either a
push A which is, push, pushes all of the register state onto the stack and, and pop
A which pops it off. It is not actually required though.
There's other, some operating systems don't actually do push A and pop A, better
operating systems, or more modern operating system will actually only save
off what is strictly needed. That's something, something to think
about. One other important thing here.
Typically when an interrupt occurs, you probably want to mask other interrupts
from happening. So this is, this is a really hard problem
to solve, is you have interrupts inside the interrupt handler.
Ooh. Yeah, that doesn't sound like a, like a
happy day for, for anyone. Cuz what if you're in interrupt handle and
another external interrupt comes in? What do you, what do you do?
You can't save the exceptional PC into the exceptional PC state now.
Because you've already saved the, the old program counter into there.
You can't take that second interrupt inside that.
So you can't necessarily nest interrupts very easily.
So what, what people do for this is, one solution, actually, is to take the
exceptional PC, and put it into memory somewhere.
And once you've done that, Then you can turn interrupts back on
inside the interpender. You can take more interrupts inside the
interpender. Alternatively, if you know that the
interrupts going resolve itself very quickly, you can just return, you can just
leave interrupts masks the whole time the interrupt handler is happening, and when
it's done just the return from interrupt construction usually turns off the
interrupt. Or, or, excuse me, turns back on the
interrupts, if you will. So it'll, it'll re-enable interrupts.
So it's, you got to be a little careful there, there's with interrupts inside of
interrupts happening. So, so that's, that's a great question, so
what do you save in the exceptional PC. On a interrupt.
Oops. So yeah.
That's, that's, that's there. So if you're, have instructions that are
marching down the pipe in a two way in order superscalar we'll say.
You're, you're gonna save the PC of the instruction that took the interrupt.
Some architectures define this differently.
If you go look at something like x86 typically what gets saved in the
exceptional pc is the next instruction to execute.
So it's, it's really dependent on architectures.
Some architectures will save the address in the exceptional pc of the next
instruction of program order to execute. Some things will save the address of the
instruction that actually took the trap and as far as or took the exception or the
interrupt. So it's a little bit of a, a, a tradeoff
there. One of, one of the things that's actually
hard is, you have a branch that takes an exception.
Do you store the target of the branch location in the exceptional PC?
Or do you, yeah. You have to sort of resolve the branch
first. So that's one reason, actually, why lots
of architectures favor just storing the PC of the, instruction that took the trap and
not the, sort of next" instruction." So, I, I actually favor storing the PC of
the instruction that took the, the trap, and not the destination of that.
Asynchronous interrupts similiar sort of thing, Sometimes the handler wants to
resume after sort of an instruction, where someone might have to add PC plus four if
you have a architecture exceptional PC plus four if you need to jump over the
instruction, for instance. Something I didn't want so here this is
the expression that I came up was, what does this look like in a pipeline?
And when do you note actually process the interrupt.
So here we have a five stage pipe. So this is a little bit easier pipeline.
And we can see, this, these bubbles here are actually different types of interrupts
or exceptions that can come out of the pipe at different locations.
So out in front here we can have maybe, a PC address exception.
What do I mean by that? Well, some architectures won't allow you
to execute, let's say, code out of, certain regions of memory.
So an example of this is actually in the 64 bit extension of x86.
The 64 bit extension of x86 there's what they call a memory hole.
So between hope you'll call positive memory and negative memory, so the top
that, being such. There's a big chunk of memory which no
one's allowed to execute out of, or it's not math, it's not real memory.
So they have a 64 bit address space, but they only use 42 bits of that 64 bit
address space. So if you've any bits in the middle which
are not, set correctly, you're basically going to be executing out of the memory
hole, and that's an example of something that can cause a PC address exception.
So your PC sort of falls off the end of math to memory.
What do you do? You're in some piece of memory, you're in
some address which by definition is not a valid address.
Decode. Illegal, illegal op code.
So it doesn't, it isn't in your ISA manual.
Lots of, lots of op coding, coding space. Usually most architectures purposely leave
some space in there just for legal instructions, or future expansion, if you
will, and you want that to, to interrupt, overflows and underflows out of your ALU.
There's a whole host, if you have a floating point unit here, of floating
point exceptions. Overflows, underflows, and denormalized
sorts of instructions. Data address exceptions.
Well this would be if you're, let's say, you have an unmapped memory address.
Or you do a underlined mode or store. So basically, every stage of your pipe
here can be generating, some form of interrupt.
And then there's also asynchronous interrupts, which we haven't drawn yet.
Okay, so, good first question here is, how do we handle multiple simultaneous
interrupts in different pipeline stages, happening all at the same time?
Agree we should prioritize them. So, what is the oldest instruction in the
pipeline here? So this is going to be the oldest
instruction in the pipe. So, let's, let's think about that.
So that means it's probably going to want to kill everything behind it.
If, if there is an exception, that has happened here.
So if we were sort of, multiple things generating exceptions here at one time.
The oldest thing, the oldest instruction in the pipe, the instruction that's been
in the pipe the longest, is going to want to kill all of the rest of the things.
Going forward, though, so from a priority perspective,
Which of these things are probably the highest priority?
So, do you think we should be computing overflow errors if the instruction op code
is illegal? Should be even decoding the instruction if
the address that we try to fetch from our instruction memory doesn't make any sense.
So the priority of sort of the, when you go to figure out where or which exception
or which interrupt is the cause of the exception should go this way, from left to
right and then the you're going to, want to actually kill going, going backwards.
So let's, let's, let's skip that question for a second and look at the, at this
drawing. So what you'll see here is we're actually
going to just remember that we took some exception for a particular instruction and
just pipe it forward. And then what we're going to do, is we're
basically going to say, at the ends of the pipe, once we know everything that's
happened. We're gonna call this the commit point.
And that's going to feedback the other way killing everything.
Now, Why do we put the commit point here?
Could we put the commit point, let's say, in this stage of the pipe?
In the execute stage. So, let's, let's define the commit point.
The commit point is the point at which architectural state of the machine is
committed to the is committed, and, now that may not be in the register file yet.
Because by definition, in this point here, it's not in the register file.
It doesn't get there till the write back stage.
But nothing can change. We're not, we can't read, we can't take a
branch, we can't redirect, we can't take any more exceptions.
Well, by that definition we can't put the commit point here, because further
exceptions can happen after the commit point, if we pull the commit point back.
There are machines which do pull the commit point back.
You will see, when we start talking about super, or out of order superscalars, we
typically like to have the commit point at the end.
Cuz, or near the ends. Because then you can sort of see if
everything's resolved. You can handle your interrupts, exceptions
and have exceptions going out on the pipe as long as possible.
And if you try to pull your commit point early, that forces you to actually resolve
whatever exception is going to happen for a particular instruction relatively early
in the pipe. So if we want to full this forward a
stage, we would have to basically check whether the address of a load or a store
is valid in this pipe stage. That may be possible because we finished
the, calculation of the address right here.
But we haven't necessarily let's stay done the TOB lookup.
But we can pull the TOB lookup earlier or something like that.
That is possible. And, and we'll see that some architectures
try to pull that early. Some architectures try to have, imprecise
exceptions. This is a, a scary, scary place.
We're not going to be talking about this very much.
We're going to be talking about precise exceptions mostly in this class.
But an imprecise exception is one where instructions are going down the pipe.
You basically let the instruction sort of pass the commit point and you tag the
exception to the wrong instruction effectively.
It's not, not precise. You can't stop on a dime.
Architecture is, there are some embedded processes that do things like that.
And it's probably not the wisest thing to do if you want to write a real operating
system. But like I said, yes.
So the commit point being close to the end is probably a good place.
So at least after all your exceptions are done.
So by the time we get to this red dashed line here,
So we're after the computation of the exceptional PC and everything, we know
that we're going to be committing. Or we, or at least we have a thumbs up or
a thumbs down. And if it's a thumbs down we kill
everything behind here. One thing I did want to say is, cause.
What does that register do? Well that register tells us, why did we
take the exception. So it's a priority encoder, which
priority, prioritizes, as we said, this direction.
And we'll determine the cause of the, of the exception.
Asynchronous interrupts. Hm.
There's different places to wire this in. You just sort of have to tag it to
something, but you have to make sure that you actually take it.
So the simplest thing to do is just to put it into this big log at the end of the
pipe here at the commit point. And have the asynchronous interrupt show
up at the end of the pipe. Not all pipes do this.
Some pipes will actually inject asynchronous interrupt at the beginning of
the pipe, allow it to go down the end, and arbitrate like everything else here at the
end stage of the pipe. The simplest thing to do is to have it
come in here, and that's because otherwise you might drop this asynchronous interrupt
on the ground, or not actually take the asynchronous interrupt.
You want to make sure you actually have a chance to take it.
Exceptional PC. Takes the PC and, and pipes it forward and
saves that in a register. But this only gets loaded on a exception
or interrupt happening. Okay, so that's, that's commit points.
That's, that's important for out of order superscalars.
Because we're going to have to start thinking about, where is the commit point
of a processor? And it may not be where we want it.
Or it's possible that we will not be able to put the commit point anywhere in the
processor, and actually have the processor work.
So today, we're going to actually look at a processor where it's not possible to
have precise exceptions. So there is no line we can cut and say,
this is the commit point. Let see, so we, we covered all this.
Speculation. This is going back to like, our example of
PC plus four. Do we want to assume the exception's going
to happen? Or the interrupt is going to happen, or
not? So we're calling it an exception for a
reason. It is the exceptional case.
It is not the common case. So we want to somehow predict what our
branch vector tells us or PC4 plus four or fall through or PC, you know, the next
instruction. We do not want to just have we don't have
to wait till the end of the pipe to know whether an exception is taken or not
before we try to go get the next instruction.
One other thing When we start to go to out of order pipelines, we're going to start
to need some, recovery mechanism here. We're going to be processing instructions
out of order. So if they, we might be taking the
interrupt for, in instruction after it, it's let's say, subsequent instructions
have either committed or sort of started to go down the pipe.
And you sort of get some out of order time questions.
So we're going to look at a few different solutions for this, for recovery.
In our, in our simple cases, we just basically flush the pipe,
And kill everything behind us. In more complicated things.
We're actually going to have extra register files that are basically going to
be shadow register files. We're going to keep track of everything
that's going on in the processor, of what should have happened.
And then we're gonna dump that into our true architectural.
Excuse me. Into our physical register file, and we'll
look at that, maybe today, or next class. We should bypass.
Bypassing is good. You should not have to wait to the end of
the pipe. Okay so let's look at a time diagram here,
of an add that takes an overflow. Instruction one here is an add and we
speculate that it does not take a, any sort of exception.
So we fetch the next instruction. We start sticking ads on the pipe.
In the except in the execute stage of the pipe, we determine that there isn't
overflow. Well as we said, as we said, we don't
actually try to do something about this until the commit stage at the pipe.
So in, in our simple pipe our commit stage is at the end of this memory stage.
So we actually pipe it forward one stage. At that point, we restart the front of the
pipe, and we start fetching, the, handler code.
The exceptional handler code. And we're going to basically kill behind
us, turn everything behind us into a no-op.
So. We'll saying we're bypassing out of ex1
here, into the Well, okay, let's say we go to this one instead.
Or we, we can come out here, you'll see we're bypassing out of the memory stage,
or the, the memory stage, back to the register fetch stage of instruction three.
I think that's what you just asked about. What's going to happen is, we're going to
let that bypass happen, we're going to let that data come around, through the bypass
network. But what's going to happen is, we're, at
that same time, we're sending the kill, kill signal behind us in the pipe.
Or instruction one is going to be killing everything behind it in, in the pipe.
So we're going to bypass the data around. It's going to get bypassed.
It's going to end up, in, in the pipeline register in the cycle.
But it's going to be killed basically at the end of that cycle.
A better example is actually here. Let's say,
It bypasses to instruction two from the execute stage to the decode stage of the
pipe. That's actually gonna going to loaded into
the pipeline register of the fetched, operand.
And then it's going to go forward into the execute stage, ex2 here, for instruction
two. So we bypassed it.
We started executing that instruction. Everything was going fine.
But then, we just come along, and we kill it.
So, we're speculatively executing, it's called.
So we're, it's a speculative execution pipeline.
We are assuming, we're predicting that everything is going fine.
And then we're going to be killing behind us when something goes wrong.