In this course, you will learn to design the computer architecture of complex modern microprocessors.
VLIW Compiler Optimizations
Loading...
Из курса от партнера Princeton University
Computer Architecture
286 оценки
Из урока
VLIW 1
This lecture covers the basic concept of very long instruction word (VLIW) processors.
Познакомьтесь с преподавателями
David WentzlaffAssociate Professor
Electrical Engineering
Okay so, very long instruction words, processors.
Still wanna have high performance and we took all this hardware that was in a, out
of our superscalar reserve through it out. Well, something's got to make up for it.
And what makes up for it, is a very, very, very smart compiler.
So, we put a lot of emphasis on the compiler, in these sorts of architectures.
And, the compiler really has to do the scheduling.
It has to do all of the dependency checking.
It probably to avoid all the different data hazards, and this is just we're just
getting started. We're gonna talk mostly next lecture about
all of the different optimizations a compiler can do to try to approximate what
a on-board superscalar can do, but by doing it statically.
So it's a pretty cool trick if you take all that hardware, you put in the
compiler, you run it once. And then, every time you go to execute the
code, you don't have to go and recalculate all the dependencies.
Sounds good. Okay.
So let's see how we execute some code here and what is the sort of performance
aspects to executing loop code on a very long instruction word processor.
So here we have a very basic array increments.
We're gonna take every element of this array.
We're gonna increment it by the value C. [clears throat] And our, we run through
aour compiler and here's the sequential code sequence.
This has not been scheduled yet for VLIWs or for our VLIW architecture over here.
So, we load some, we, we load the value. We increment our counters.
We actually do the floating points, add. We store the value back.
We increments the array index, and then we, we loop.
Seems simple enough. Let's see how this gets scheduled here.
Well, because the architecture and because the compiler knows about latencies here
Let's say tthis load here has a few cycles of latency..
So it's gonna actually schedule this ad later.
And the add, it's a floating-point add, this has a couple of cycles of latency
also, so it schedules the consumer of that results here, this F2.
Later. And, yeah, I don't know, you can sprinkle
in the array additions and then the counter additions, kind of somewhere free,
has lots of open slots. But let's say it schedules at the same
time as the load in the store. So this is pretty cool.
We are actually executing two wide parallels in here.
And we didn't need all the extra overhead of in [inaudible] super scour.
Oh, and we can just go to the branch somewhere.
Okay. So, first question here how many floating
point operations are we doing per cycle are we doing very well here?
So, it looks, looks, looks pretty poor. We have one floating point operation here,
just this ad. And we have one, two, three, four, five,
six, seven, eight cycles? Yeah.
So we're having 0.18 or 0.125 floating, like floating point operations per cycle.
It's not that great. [inaudible[.
You know we're actually having three instructions here.
It's better than nothing but we're not really using the machine very well.
Out of our superscalar, we'll probably try to take connstructions that are below here
maybe intermix them, try to reorder a bunch of things and try to run faster.
So what's a technique to go faster? Well, one of the big comply, as I said we
have a lot of emphasis on compilers in this unit.
One of the things the compiler can do, is it can actually unroll the loop.
So here we have our loop, we unroll it, four times, and, now, we're going to sort
of take the loop overhead, and we're gonna factor it out, so that it only happens
once every four times. That sounds good.
We're gonna do some more work here, per each [inaudible] loop.
But things are a little more complicated. What happens here if N, big, upper case N
here are terminating value is not a multiple of four.
Well, we need to do something about that. We probably need to check sorta before we
go to execute here whether we're, we're doing okay or whether we're actually are
[inaudible] for convenient leaf and it's big enough and probably can run as
multiple four for a long period of time and so is the last iteration you'll have
to clean up. But we need to generate some clean up code
and compiler is responsible to do this. So these compiler optimizations do take
some effort. Okay, so let's look at the scheduling now
of our loop unrolled code. We can do a bunch of loads upfront here.
So we've inter, intermingled these loops. And what's kinda cool is because you pull
out the loads and are thrown to the top and the stores been pushed into the
bottom. And then put all the ads sort of in the
middle. And maybe sprinkle the array update
somewhere else. And we go to actually schedule that, we're
going to do something similar. We're going to have the loads [inaudible]
first, execute the floating point ads of the floating points stores and have the
result. But what you could noticed here is we're
actually starting to get some overlap, because we've unrolled, we can overlap
this load and the first floating points addition 'cause we've effectively covered
the latency of our functional units by putting other loop iterations during that
time. So if you look at this schedule versus the
schedule back here. We're just sort taking these dead cycles
and we've put the other loop iterations in those dead cycles.
In this loop unrolled case, we're incrementing this counters and the indexes
not by four anymore. We're incrementing by however many times
we've loop unrolled times the offset, so we're incrementing it by sixteen now.
Does that make sense? 'Cause in, in this code here we were
incrementing R2 by four, because that's the size of a single value is four bytes.
So we have to sort of move our array index over by four.
But now, because we're batching up all this work together.
[clears throat] We actually have to move the, the index by a, a bigger value.
So we're moving it by four 'cause we've unrolled four times, times the size of the
data value, which was four. So we're moving it by sixteen.
And, and, one of the nice things here if we look is in both the loads in the
stores, we're using our register indirect addressing mode here to add in some
offsets. So, we're actually offsetting, let's say,
twelve plus this base register of R1 to figure out where we're actually doing the
load from. But it's just, a convenient way that we
don't have to compute a bunch of addresses [clears throat].
Okay, so going back here, we can see we're starting to overlap actual operations with
other loop iterations. Well, that's really cool.
So we're starting to get some performance here.
So, let's, let's look at the performance. So, I ask the same question here.
How many floating point operations per cycle?
Hopefully, hopefully it's higher, one, two, three, four divided by one, two,
three, four, five, six, seven, eight, nine, ten, eleven cycles Okay, so that's
0.36 is a lot better than 0.125. This is good.
Loop unrolling is helping us. But is this, is this everything?
Or could we do more in our compiler? So these four compiler people came up even
fancier idea, which is called software pipelining.
So uses, uses a term we've seen before, pipelining, but does it in software.
So the idea here is that instead of. Just having one loop, unrolling the loop,
and then overlapping the iterations. We're actually going to take multiple of
these schedules, and interleave them. And try to fill some of these empty spots.
So let's, let's look at this. We're going to have the code unrolled four
times. It's the same piece of code we had on the
previous slide. And we're gonna draw our schedule that we
had before. So here is the schedule we had before in
purple. Okay, that doesn't look so bad.
But now, we're going to schedule it with another iteration of the exact same four
time unrolled loop shown here in green. So we've just overlapped this with, this
other iterational loop. Well are we, are we done here?
Well, not quite. We still have some open spots here.
So let's try to overlap even another iteration, as shown here in red.
Now the fix-up code that you need to have to do this correctly gets more complex
'cause all of a sudden now you're overlapping multiple iterations, but as
long as you don't modify some value, as long as you don't do a store,
speculatively, or a store, you're probably okay, 'cause always just doing
[inaudible]. Doing extra loads, doing extra work.
You're doing extra work and you're filling slots thinking that you're not gonna have
anything go wrong or thinking that the index variable N if you will, is a
multiple of four and large, and you're not at the end.
So let's, let's put some names to these things.
[clears throat].. So we call the, beginning here the run up,
the prologue. Here, we actually have our sort of actual
iteration. You can see that the, sorry this is in
green, that doesn't show up very well there are instructions here.
There's ads. It's pretty full.
We're actually doing a lot of work on our machine here.
And then the epilog here is the, is when we're done.
This when we're falling out. We're sort of at the last loop iteration
of the outer loop, if you will. So let's, let's do some math and look at
the performance of this. Okay, so let's ask the same question here.
How many, floating point operations, per cycle?
Well, we go look over here. We have one, two, three, four.
And we have four cycles in our, in our tight loop case.
That looks pretty good. That's cool.
We just got a bunch of performance. But we have to do a lot of compiler
optimization to make this work before we're able to use the [inaudible] machine,
and we're able to overlap three different iterations of this of this loop, that we
also did a software transform to unroll it twice.
So this is called a software pipeline, pipelining.
And have the nice picture in here to sort of show what's going on visually.
So we're gonna have time on the horizontal axis, and we'll have sort of activity of
how many instructions are executing or something like that on the vertical axis
or, or shown here as performance. When you run multiple loop unroll
iterations, you have, starts from start up, you have the actual you are in the
loop, and then you come down from that. And that's, that's better than having lots
of start up and sort of come down with small loop iteration portion here in the
middle. [clears throat] But when we go look at the
software pipelined, we can overlap, basically one iterational loops execution
with or one loop start up or, a, a with loop iteration of another loop Now we can
actually execute sort of our prologue, execute multiple iterations, very tight,
and then have our epilogue here. Yeah, so.
Our software pipelining [inaudible] start up and wind down costs.
Once for the execution of the loop and not every iteration of the loop.
So that's, that's, that's fun. That's cool.
We're getting performance. If only the world was dense loops, life
would be easy. Alas, the world is not all loops.
If we just had a processor, which just did enter array calculations and all of our
problems in the world were just dense array computations life would be really
easy. But they're not.
A lot a time code has lots of branches. It has if than else clauses.
And here so graphically show something like a if than else.
So we have some piece a code that makes a decision and executes the code on the left
or executes the code on the right, based on an if statement.
So this is the if true statement and this is the ELF's clause.
[clears throat] and data dependent branches are a problem typically for very
long instruction word processors. Now, why is that?
Hm. Well in a, out of word processor, you can
try to execute, code sort of around the branches and move instructions above the
branch and below the branch. But if you're doing static scheduling when
you hit this branch, and let's say it's a hard to predict branch.
You can't really do anything because you packed a bunch of instructions next to
each other and they need to execute atomically.
So, thinking measure of move code up and down across that branch.
Superscalar can do that, 'cause it has its instruction window, it has a bunch of
techniques a bunch of hardware to be able to do that.
But in our VLIW processor, that's a problem.
So I wanted to introduce a, a compiler, an important compiler nomenclature here,
which is important for this class, it's called a basic block.
So what is a basic block? A basic block is a piece of code which has
a single entry and a single exit. So this is a basic block, it has one
entry, and one exit. And why is single entry important?
Well, if you can jump into the middle of this piece of code, the compiler cannot
necessary reorder the instructions inside this block.
If you have multiple exits, let's say you exit here, the compiler can't push
instructions below that exit point. But if you have a basic block, the
compiler basically knows that these, this instruction sequence is going to execute
effectively, effectively atomic, but not actually atomic.
I mean that you can have other things going on inside there.
But from a compiler perspective it can reorder the instructions around in here to
get better performance. Hm, okay.
So loops, loops are easy. We can solve for pipeline.
We can unroll. Squirrelly code if and else spaghetti code
are hard. So compiler guys came up with some fancy
tricks to make VLIWs work better and take advantage of some of the code motion that
out of a force superscalar does but in the compiler and not in dynamically in
hardware. And one of the more famous ways to do this
is something called [inaudible] scheduling, which was John Ellis' who was
one of Jon Fishers' student's thesis work. This was in the Bulldog compiler out of
[inaudible] So, what you do is you profile the code and, you compare the
probabilities that these branches go the one way or the other way.
So, let's say profiling, this is not a something hardware is doing at run time,
this is something that you do with the program while you are sort of still back
in the compiler stage. You take the program, the compiler goes
and runs it on some input given, given input set and comes up with the
probabilities of which way things go. And then what you do is, you come up, you
take this profile information and you come up with some guess at what is the most
probable one. And we're going to circle that here.
And say. These darkened edges are the most probable
sort of path through the squirrelly piece of code given this is the entry point.
Now, this doesn't mean that you can't have branches that sort of branch out of this,
but if you do you need to have some fix-up code 'cause what we're about to do is
we're gonna take this entire sort of, big [inaudible] of code here.
We're gonna remove all of the branches and we're gonna schedule for our VLIW
processor as one big monolithic piece of chunk code.
And by doing this we can move instructions, let's say, that are down
here, which this opens last to executing your early portion of this codes sequence,
we can move them up. And likewise we can move things that use
the resolve of long latency instructions up here and push it down across branches.
So our out-of-order superscalar does this with branch speculation, but our compiler
can do this on our VLIW processor using trace schedule.
But when do this, which be careful because there's always a possibility that while
unlikely you can still branch the other way.
So typically, the way this is done is you have some form of fix-up code that you
branch away, you have to sort of fix up anything that was after the branch that
made a committed change if you will, to the, the processor state.
And you sort of roll that back somehow. So, we're basically in software, doing the
rollback case from number our out-of-order superscalar.
So instead of taking the, architectural register file and copying it to the
physical register file on branch mispredict, instead our compiler generates
a code sequence which does that same operation if you were to branch away
there. And we'll roll back, only the only the
certain register that needs to be rolled back and only the memory state that needs
to be rolled back. So, that's pretty cool, so we can
basically take all the functionality that was dawn in our out-of-order superscalar
and put it in the software using trace scheduling.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
