[MUSIC PLAYING]
Hi, I'm Josh Fisher from HP Labs.
I'm glad to be here today.
I'll be talking about instruction level parallelism.
ILP is very different from parallel processing
that we hear so much about.
Rather than having separate processors getting
separate chunks of a program that's
been programmed to do that, ILP is an architectural technique
that lies at the bottom end of the CPU
and allows the overlap of the ordinary risk level operations
so that you might be doing a multiply and an add
at the same time.
The same multiply and add that appear in the user's program,
only now they're issued one after the other
without the second one waiting for the first to finish,
for example.
Or they might be issued at the same time.
Instruction level parallelism is something that
is meant to be transparent.
That is, the user should not see any of it.
We take ordinary programs and make them go a lot faster using
this technique.
It's an old technique.
It's been around for over 30 years in the fastest computers.
And after a 30 year history in which it really
didn't do an awful lot, particularly
for the last 20 of those years, in the '80s,
it started really taking off.
And it's become very much the hot topic
in architecture conferences.
And you just don't build a fast microprocessor these days
without using instruction level parallelism.
It's a very simple concept.
If you look at a small chunk of code.
And here we have just eight operations
that are doing some multiplies, adding
the result, two more multiplies, adding the result,
and a couple of adds.
And I just took this random chunk
of code out of an application.
Using instruction level parallelism,
you might issue the first multiply in the first cycle.
But rather than just stopping there,
you might at the same time notice
that this add down at the bottom doesn't depend upon anything
that came earlier.
These other adds do have to wait for the multiplies that
are producing their data.
But this add is data independent.
And you certainly could start executing it right away.
An ordinary computer typically has a separate floating point
and integer unit.
And that integer unit isn't doing anything.
So you might somehow get the bright idea
of issuing the integer operation at the same time
as the floating operation rather than waiting for it to stop.
And that way you're overlapping operations,
and you're able to get a speed up.
In this little expression, if you
did each of these operations one at a time,
you'd find it took 12 cycles, say, if the multiply took
two and the adds took one.
There are eight operations.
Four of them are multiplies.
If you look at what might happen down here,
we're able to complete the same work in six cycles.
So we'd get a factor of two speed up.
That's a typical sort of thing you
can do using this kind of hardware arrangement.
The hardware you pretty much already have
and the ability now suddenly to be able to
overlap a lot of the operations.
Now, notice I haven't said anything
at all about how you go from getting handed this stuff
and coming down to this, getting this record of execution
of what actually happened when that went twice as fast.
The technology of instruction level parallelism
is getting somehow the ability to go from a sequential program
automatically to this kind of speed up or a good deal
more, as we'll see.
If we look at the history of instruction level parallelism,
it turns out that it's been tremendously influenced
by the question of how much ILP there
is in typical programs and people's belief about that.
And in fact, that's still, as we'll
see later, a very controversial question.
People really don't have a good handle on the answer to that.
But if you look historically at what
happened with machines like this, in the late '50s,
there were some experimental machines being built.
And then in the early '60s, CDC delivered the 6600,
the fastest scientific computer of its time,
sort of the supercomputer of its day.
And it had eight functional units.
They built extra functional units
so that you could attempt to start
a new operation every single cycle
whether or not the previous ones had finished.
That was a very successful machine.
There were a lot of them used for a lot
of important applications.
At the same time, IBM was building the 360 91,
which had a lot of instruction level parallelism
as well, a rather different kind underneath.
And we'll talk about that in a few minutes.
It was not a commercial success, but then there
were follow ons to that machine that
used the same kind of CPU design and were very successful.
So in the early '60s, this was the way
to make computers go faster.
If you talked about parallel processing, then
you meant this kind of stuff.
Nobody called it instruction level parallelism.
It was just what people did to make computers go faster.
It was a topic that got some academic interest
and certainly a lot of design interest.
And people started asking this very natural question
of how much parallelism there is in typical programs.
And several groups set out to answer that question.
There were three that I know of, and I
believe there were probably others as well.
The three I know for sure.
And they all got the same answer when they
tried to answer this question.
The way they tried to answer this question was as follows.
They said imagine you have a bunch of ordinary programs,
but imagine that you also have infinitely much hardware
to run these programs on trying to get as much
of instruction level parallelism as you possibly could.
So you have 5,000 integer adders,
or as many as you'd like, as many floating point units
as you'd like, as much memory bandwidth
and registers as you need, and the ability
to issue as many operations on the tick of a clock
as you possibly could.
And then the question is, how much
of this kind of parallelism would you
get running ordinary programs on machines of that ability?
And the answer was very uniform.
And people still either on purpose or not even
knowing this history repeat these experiments today.
And you always get pretty much the same range.
About one and a half to two and a half or so
is the kind of number you get.
That was not considered a very wonderful result.
People were pretty pessimistic about all
of this when they heard it.
And in fact, the interest in instruction level parallelism
died out at the same time these experiments came out.
And I can't know for sure if this was a huge factor,
but talking to people who were in the computer
architecture and compiler worlds at the time,
I've heard very often, oh yeah, this was a big factor.
We just thought this technology had run out
of steam right there.
And I remember very clearly as a young university professor
going off to Washington to get my first grants working
in this area.
And I wanted to do something about getting
more parallelism for this and I had ways of doing it.
And I remember the people in Washington
telling me very clearly, oh, don't bother with this.
This is the Flynn bottleneck.
It even had a name, like Flynn had
done some of these experiments.
And you can't get that kind of parallelism.
It's just not there to be had.
Go do something else.
And fortunately, I had read these papers
and I had a ready answer.
But it was very striking how clear that perception was.
Well, it turns out that this belief
that there's only that much parallelism is really wrong.
And it's sort of wrong for a big general reason.
And it's wrong because they really
missed one specific, narrow thing
right away that makes the results not quite what you want
to know when you measure this.
The general thing is the question
of code transformations.
A compiler can do things to code that
will expose more of this instruction level parallelism.
And there's no way to predict just what the compiler will
do that will give you more of this parallelism.
There are lots of tricks similar, for example,
to the vectorizing tricks that give you
more and more of this instruction level parallelism
compared to the way the program is originally
expressed by the programmer.
If you think about it, in fact, there's
a silly argument that's a little less silly than it seems
at first that says that these limit studies really can't make
sense as far as giving a flat statement of how
much parallelism there is.
After all, you could reduce a computation to a table lookup
by computing ahead all the possible answers
for all the possible ranges of data
and then doing a one cycle table lookup in order
to get that computation done in a single cycle.
So you take a big matrix of programs and data
sets and just look up your answer
for the program and data set at hand and do it in one cycle.
Now, that's silly.
Of course, nothing wildly like that is practical.
But in fact, a lot of speedups that one does
reduce to that trick.
And there are even ways in which compilers,
not to mention hand coders, will substitute table lookups
for more complex, longer computations.
So really, this is a real problem
in trying to make a flat statement about how
much parallelism there is.
A more accurate statement is much narrower.
It's conditioned on the compiler technology
available to the experimenter at the time.
And very rarely do they even have state of the art compiling
techniques when they do these experiments,
never mind compiling techniques comparable to what
we'll have in the future.
So in some sense, these limit studies,
they're very interesting.
They're very informative.
But people should not be taking them
as this is some absolute that we'll never get beyond.
But there was a much bigger problem right away,
and that concerned conditional branches.
When these limit studies were done in the early '70s,
people said, well, in an ordinary program,
we have tests and branches.
So if something is true, go this way, otherwise go that way.
And you might want to raise an operation up
from beyond one of these branches up into the place
that you're right now considering
how much you can issue.
So here you are.
You're issuing operations, pulling them up from below,
but you now have run into a conditional branch.
And you'd like to pull one up from one side or the other.
Well, they reasoned you can't do that because after all,
if you pull an operation up, it's
bound to have side effects.
Must be a reason you're doing it.
And suppose the branch goes the other way.
Then you'll have done something that's
affected your computation and you didn't mean to do it.
And that would be bad.
And of course, you can think of some little special cases
where it isn't so bad and you get away with it.
But people basically felt that this was not
a source of big speed for instruction level parallelism.
What's interesting is that one of the groups that
did this experiment, which was Reisman and Foster at UMass
Amherst, did a second experiment in which they suggested
that there is a way around this conditional branch problem.
And they looked at that and measured what could happen.
And it really was a very interesting result
that they got.
They termed this differently, but I
think this is the way you can look at it
and understand it best.
They said, suppose you take the program in advance
and unwind every possible path of computation.
So write down every path through the code
that the code could take when it runs.
So at each conditional jump, you now
would write down two ways, the one leading up
to here going that way and then the one leading up to here
and then going that way.
So now you've written every single path through the code.
Now, it's an awful lot of those.
But just imagine for a second you had done that.
Don't forget the hypothesis of this experiment
is infinite hardware.
All you need.
So you have a big piece of paper.
You write all this stuff down.
And then you build a processor for each one of these paths.
And you hand that path to that processor.
And now you start computing.
Now, a processor that's been given a path
doesn't have to worry about these conditional jumps
anymore.
OK some processor was told to go this way and then this way.
And so if it wants to start up here,
if it wants to pull this operation up
above these jumps, no problem.
It knows for its world the jumps are going this way.
The branches are going that way.
So no problem.
So it would pull it up.
Each processor in turn stops worrying
about the branches and starts pulling up
all the code that's data ready.
Now, every time a branch resolves,
you have a whole lot of processors to throw away.
All the ones that had been sent some way inconsistent
with the branch resolving in the direction that it did.
So you just throw those away.
No problem.
Infinite hardware.
Eventually some processor will have
been handed exactly the right path through the code,
and that processor will have gotten instruction level
parallelism without having to worry
about the conditional jumps.
And it's going to get more parallelism than you'd
get if you stopped at branches.
Well, how much more?
Huge amount more, as it turned out.
The kinds of numbers they were getting,
I think the programs and data they looked at averaged
54 or 55 factor speed up.
And there were some where they said, look, this is silly.
This is just dependent on the data set size.
You can get any number you want with some of these,
and that's certainly true.
Huge order of magnitude and more speed up available
if you could somehow go past conditional branches.
So then they actually set out to see how crazy an idea this was.
And what they measured was that if you even
wanted a factor of 10 speed up, then at the worst
place, the place that was densest with machines still
running of the program, you had to have 16
unresolved conditional jumps.
And that meant you had to have 2 to the 16th
or 64,000 copies of your machine.
And that's just to get a factor of 10 speed up.
And that doesn't even speak to all the machines
you had to throw out for the whole rest
of the program, which is probably a good deal more
than that.
So they reasoned this is ludicrous.
This is a preposterous amount of hardware
you'd have to throw at the problem
in order to get this speed up.
And wrote a summary, and these were very good experimenters,
good computer scientists have gone on
to do good work in computer science besides this,
and a very imaginative experiment.
But I think sort of as a prisoner
of their time, the conclusion that they
wrote was not the conclusion one would like
in retrospect to have seen.
Here's the conclusion you'd like to see.
You'd like it to have said, boy, there's
a lot of this instruction level parallelism.
But the crazy way we thought of trying to tap into it
doesn't work.
Sorry.
Maybe somebody can come along with a better way.
Instead they basically wrote it off and people reading it
basically wrote it off.
And the message wasn't what they wrote,
which was there's a lot of instruction level parallelism,
but it's impractical.
Bad enough, people basically came away
with the feeling there wasn't much instruction level
parallelism.
So that's all wrong.
It really is the first thing I said
that's the correct conclusion.
And it turns out that there is a practical embodiment
of this idea.
I've spent a lot of time on this one sort of obscure experiment,
but a lot more people know about it now.
Because the idea that comes out of it,
this idea of unwinding all the possible execution
paths in order to get more parallelism by going
past branches is very central to an awful lot
of the technology that's here.
We're going to learn about something
called speculative execution in a minute.
And that really is the way you can
tap into huge amounts of instruction level parallelism.
But you have to make this idea of going down
paths speculatively practical.
And you're not going to do it the way these guys set out
to measure it.
But there is something you can see
right away that does kind of bring some practicality to it.
And here's the idea.
Take a single CPU and start filling it up from below
with things to be done.
The way we were doing on that first example.
But now when you get to a conditional branch,
pick one of the directions, say.
So just pick taken and start pulling things up from taken.
But when you do it, make sure that you do it in such a way
that you don't destroy so much of the state of computation
of a computation that if it turns out
that untaken was the right answer,
you have no ability to recover.
So make sure that when you pull operations up
and they're clobbering things, they're
changing the state of the computation, that you've
somehow arranged in the hardware or software
to leave around enough stuff so that when untaken turns out
to be the right answer, you can still not
get the advantage of having pulled these things up,
but at least the semantics of the program are still correct.
That idea, again, is called speculative execution.
It allows you to go past a branch, pull things up.
You're sort of in a danger zone here because you're
doing things that you're not quite sure whether you want
the results of them or the old stuff back
or you want to ignore them, which
is usually what you end up just having to do.
And then at some point, the branch resolves
and you can continue with the correct computation.
Now, in fact, you can go up from both sides, not just one.
So that when you look down at this branch, whatever
it is you're going to do on the taken
side you can simultaneously do on the untaken side
and pull up operations from both.
Make sure that you're preserving the semantics
of the program both ways.
But now what's happened is we've gotten back
to this Reisman and Foster situation.
Now instead of having 64,000 computers running this program,
instead what we have is one computer with 64,000 operations
to do in order to get a factor of 10 speed up.
Doesn't feel like we've improved things very much.
However, if when you get to a branch
that branch is very predictable, that is it
tends to go in one direction most of the time
and you can figure out what that direction is, then
it makes sense to just gamble, a very common trade
off in computer systems, gamble on the more likely event,
get a big speed up there, and then make sure
you do the right computation when the less likely event
occurs.
That's what's behind caches after all.
And that really makes sense if branches are predictable.
Well, it turns out, these are some recent numbers
we've gotten here at HP, it turns out
that branches are a lot more predictable
than a lot of people think.
Now, people working in instruction level parallelism
are pretty well aware of this.
But I remember very often being told by people
that this is not the way it is.
And so it was interesting to measure it and see
just what it is.
If you consider a given source branch,
maybe it's executed a million times,
if in a run of the program it's taken 800,000 times
and not taken 200,000 times, then you would say it
goes in its majority direction 80% of the time.
And you would count that as a million branches
that go in their majority direction 80% of the time.
And now take a wide range of programs
over a very wide and varied data set.
We have the spec marks here with a lot
of added data sets and a lot of other particular C integer
codes, which we're most interested in.
And we took all of the branches.
This is around 7 billion branches, something like that
were measured to get these numbers,
out of real programs running real data.
And these were systems and scientific codes.
And what we found is that 40% of the branches you execute
come from a source branch that's predictable more than 99
and 1/2 percent of the time.
And if you sort of cut off at some reasonable place
where you'd like your predictions to be right
in order to get a payoff from your speculative execution,
you get a huge preponderance of the branches
where going one way seems like the thing to do.
And in fact, very few branches dynamically are unpredictable.
Now, you can always find a program where that's not true.
But I'm actually surprised.
I haven't been able to find non-pathological programs.
I'm sure they're out there, but I just haven't run into them.
I sort of looked at some programs
that I thought would be.
Even some of the spec marks.
I think most people would predict
that the LISP interpreter, for example, would have very 50-50
behavior.
They very much fit into this pattern.
And there's sometimes a little more weight down here
but very little more.
And sometimes the scientific code,
there's a lot more weight up at the top.
So branches are very predictable.
And this gives us a technique for dealing
with this problem of going past conditional branches.
And it really puts some validity to the limit studies that
don't stop at conditional branches
but say if you want to know what's available,
here's what's available.
Now you need tricks to get it.
You need architectural techniques
that will allow you to go past those conditional jumps.
So that's sort of a little bit of narrow history.
I'll say much more about the recent history
at the end of the talk.
But a little narrow history and some perspective
that I have always found very valuable
in understanding the hardware and software techniques that
go into instruction level parallelism, which I'd
like to start looking at now.
So if you think back to that example we did at the beginning
where we took a section of straight line code,
there were no conditional branches there,
and we tried to schedule it to see
what would be fired when in the instruction level parallel
hardware, we really did two different tasks.
And you heard me doing those out loud,
though I didn't separate them at the time.
The first task was can I issue this operation now?
That is, is it independent of all the operations
that I'm issuing now or that are in between where
we are and now?
In other words, is its data ready?
Have the things it has to wait for already
completed their execution?
So that's called recognizing the independence of operations
or dependence analysis is the typical word used for it.
And that's a job that you have to do in order
to find out whether an operation is ready to be fired.
If its data isn't ready, it doesn't make any sense
to start the add.
So that's one job.
Then having done that, you get a handful of things
that you would like to fire right now.
You have to ask the question, where in this hardware
am I going to do it?
Can I do it this cycle and using what resources?
So the second question, then, is how do you
schedule the operation?
So the way you can think of this is if you sort of fix
the endpoints here, here's the source code that we're
starting with and here's the execution
we're trying to get the execution
pattern at the end of instruction level parallelism,
and those are sort of fixed independent of how
you do this stuff, the steps along the way
are, well, you want to run your compiler
and turn it into low level operations.
You might not want to run it all the way into the final version
because, for example, you may not
have chosen what functional units or what registers to use.
You may do that as part of scheduling.
But you do most of the compiling job.
And then you want to have some thing, whatever it is,
and we'll talk about that in the next slide, whatever
it is that will do the dependence analysis.
And then you want to do something that will schedule
the operations on the hardware.
Now, I've gone on and on about some thing on purpose
to emphasize one of the most important things
that I hope you can get out of this talk.
And that is that if you think in terms of the source code
and the record of execution as fixed, the desired
kind of execution and the desired source code,
then you have a spectrum here of jobs
to do where you can draw the line of which
to do in software before the program runs
and which to do in hardware as the program runs
in lots of different places.
There are two extremes of this.
The one is to simply take ordinary risk operations here,
hand them to the hardware.
So now on this side of this boundary,
everything is hardware.
Ask the hardware to do the independence recognition.
Ask the hardware to schedule the operations
on the functional units using the registers, whatever.
In that case, you have what people now call a super scalar.
Alternatively, in the other extreme,
and there are intermediate points between these two,
in the other extreme, you could say
I'm going to allow the dependence
analysis and the scheduling to all occur kind of as
part of the compiling process, to all occur in the software
before the program runs.
And then finally, the hardware has nothing
left to do but execute that code that you've already scheduled.
If you do that, then the hardware you're talking about
is called a VLIW, a Very Long Instruction Word machine.
So we're going to look at these two kinds of machines
in a little more detail, and we're
going to discuss this trade off.
This trade off is very, very similar
to the kinds of hardware, software trade
offs one is always making in systems design.
But I guess before going on, it's
worth saying that these are the popular things people
talk about.
There are clever ideas that try to embody the best
of both kinds of processors.
That is, they try to not apply the hardware software trade off
in one extreme or the other but try
to look at all the individual pieces of the jobs in here
and figure out which ones to parcel to the software
and which ones to parcel to the hardware.
One of the most clever ideas, just
to give you an example of this, is
something that appears in the horizon processor, which
I first saw at the Supercomputer Research Center
I guess is now being built by Tera Computer in Washington
state, I think.
That idea is to draw the boundary here, basically.
That's an obvious idea if you look at this picture.
But the way they did it was very clever.
The idea is to do the dependence analysis and the compiler
and then encode the statements of what an operation is
dependent upon into the code in the form of hints
so that the hardware can simply run that program
step after step without looking at the hints at all.
So you know the program can run correctly without anybody
having to do anything.
But then if the hardware wants to use
the hints to do more clever scheduling
and get some instruction level parallelism, it can do that.
And the hints are very simple.
It's just a number attached to each instruction.
And it says how many instructions straight
before this one this instruction is guaranteed
to be independent of.
So if there is a 10 in that field that
goes with that instruction, then the hardware
is guaranteed by the compiler that the previous 10
instructions in the instruction stream
are all independent of this one.
And the hardware just has to look and see if anything older
than that is still in flight.
And if nothing is, then it knows it can issue this operation.
If something is, then it has to play safe and wait,
not knowing for certain whether that's a data
predecessor of this one or not.
But it's within that window.
That's called horizon.
Clever idea.
Nice name for it.
So that's one example.
And I guess I went through that just
to make sure that you understand that this really
is a continuum.
And people often talk about the VLIWs and superscalars
as being sort of opposites.
But really they're two approaches
to trying to get the exact same thing.
It's just where you draw that boundary.
And practitioners in the field are always discovering this
and are always glad to discover it.
It's one of those nice things that you suddenly
see what's underlying everything in that sense.
OK.
Now, if you look at how these things work,
let's consider first a superscalar.
It's pretty intuitive.
You build some extra hardware.
You feed in the instruction stream.
And it's just an ordinary stream,
one operation at a time.
Could be the same stream you would
have been running on a non-superscalar processor
implementing the same architecture.
And this hardware starts fetching the operations,
looking at them, figuring out if they're data ready or not,
doing the independence recognition.
And if they are, figuring out where
to send them in the system.
Now, there is every imaginable level of sophistication that
can be applied to this job.
The very simplest thing you can do is get an operation,
figure out whether the registers it's going to use
are reserved by somebody.
And if they are, just stop.
Reserved in the sense that somebody
is planning on writing the results into that register.
Or instead of just stopping, you can stick the operation aside
and look at the next one.
Now, when I said stop, I mean stop issuing
and allow the ones that were already in flight to complete.
Instead of stopping issuing, you can put that one aside
in a special buffer and look at the next operation and ask,
can this one now go?
And then you need to periodically, like each cycle,
look at the ones that you've delayed
and see whether they can fire.
Or you might be even more sophisticated
and when you put something aside arrange to have the hardware
notify you when that operation is now data ready.
So they're starting with the more modest superscalar
algorithm in the 6600.
And the rather more ambitious one,
it's called Tomasulo algorithm in the 360 in the early '60s.
Those sorts of things have been used in several processors.
And as we'll see later, they are very
much what we find in the highest performance processors today.
The algorithms that were used in the CDC and IBM machines
lived for quite a long time.
The CDC method evolved into something considerably more
ambitious as the superscalar unit of the Cray supercomputer.
Seymour Cray was at CDC and took that same philosophy
when he built the Cray-1.
And in one form or another, these ideas
have lived on in that line of computers.
And the same thing with IBM mainframes
that lived on in a lot of the most powerful models
and the RS/6000 and so on.
So that's what you do with a superscalar.
And real question is, as we'll see later,
how does this hardware scale?
How big can it grow before it starts getting impractical?
And we'll talk about that in a while.
An alternative to that is to throw out that control hardware
completely.
Instead let the compiler do the whole job
and do it in such a way that it schedules
exactly the record of execution that it wants to have happen.
So that rather than giving a sequential chunk of operations
in, it gives the exact outcome, the record of execution
mapped exactly into the code that the compiler
expects to happen.
And then the hardware doesn't have
to do anything in the way of sophisticated scheduling.
It simply takes the first operation
and assigns each-- it takes the first instruction.
People tend to call these long things instructions.
And the constituent risk operations
are called operations, just to distinguish between the two.
Take the first instruction, parcel
each operation out to the functional unit
it registers and says it uses.
Bang, execute them in one cycle.
Grab the next one and so on.
So that's the idea of the VLIW.
It's very simple.
It requires very much less hardware,
because this is quite complex hardware
that you can now throw out.
In fact, you tend to very often throw out
a little bit of the control hardware in a VLIW
that you would have built in an ordinary sequential machine,
simply because you have such a sophisticated compiler in order
to do that at all that there are a few other things that
sometimes control hardware has to do that you can maybe
arrange to do a little more efficiently in the software.
Now, I've been saying consistently issue
the next instruction on the next cycle,
issue the next instruction on the next cycle.
And a lot of these operations, for example,
you'd expect a floating multiply and a floating add and a load,
take more than one cycle to operate.
Well, in all instruction level parallel machines,
independent of the kind of machine
it is, you like to build pipelined functional units
and pipelined memory when you have the need
to start a new operation before the old one finishes.
Whenever you have a longer than one cycle latency operation,
it makes sense to build a pipeline unit.
And your goal is to be able to start a new operation
in that unit each cycle.
After all, you have all this mechanism
for firing operations before the old one stops.
Why not build hardware that allows you to fire more of them
with basically the same hardware dollar?
So you tend to see any long latency
operation in instruction level parallel
machine being pipelined.
Now, not all of them are.
That's not always the case, but it is certainly the rule.
And the example I've written here
certainly would count on the fact
that these longer latency operations aren't holding you
up when you issue the next instruction.
Now, I've shown this a issuing a bunch at the same time.
And when we saw the record of execution
at the very beginning for either superscalar or VLIW machines,
we saw it written as a bunch of operations
that fired at the same time.
So it was sort of multi issue.
Another idea that's very similar but just a little bit different
is what's come to be called super pipelined or deeply
pipelined or highly pipelined machines in which you increase
the issue rate tremendously as far as the clock of the issue.
But you issue more than one operator.
I'm sorry.
You don't issue more than one operation per clock.
So that, for example, you might even
have an issue rate a lot faster than an integer add,
which is sort of what we tend to think
of as the atomic unit in the user visible clock in a system.
Instead, you might start an integer add and then issue
more operations before it completes
but at a very, very fast clip.
Now, that's an important hardware trade off
and has lots of implications for how you build your system.
But really in concept.
It's not very different from this kind
of record of execution.
It's just finding the available instruction level parallelism
and scheduling it is going to be a pretty similar job.
And it's likely to be similarly effective,
give or take the advantages and disadvantages of the hardware
trade offs that you get.
And it applies just as well to superscalar and VLIW machines.
It's a little more attractive for a superscalar machine
because you can build a more simple issue unit
and just make it very fast rather than trying to issue
a lot at the same time.
So perhaps that's an advantage there.
But in any case, that's an idea that people often
think of as being more different than in my opinion
it really is.
So one last thing about VLIWs.
I thought you'd enjoy seeing some code that
is an example of when you're doing incredibly well
on a VLIW.
Now, you very rarely will do this well.
This is two instructions, two clock ticks,
of compiled code for the Multiflow Trace 28/300
that I happen to have around.
And it's for a dense solver.
And dense solvers are things that
are very easy to get parallelism out of.
Almost any form of parallelism works great on a dense solver.
And this is two clock ticks.
First clock tick, you issue all of these operations.
If you look at, if you can read the op codes from a distance,
there's a lot of floating point multiplies integer ALUs,
a lot of loads and stores.
Actually, I guess I grabbed two that
don't have loads and stores now that I look at it.
Oh yes they do.
Lots of loads in stores as well.
And a bunch of branches, because when
you do that many operations at once,
you better not be limited to doing one branch per cycle
or that will really make your code very sparse again.
So in here is the second instruction filled
with all these operations.
Obviously if you issue this much on the first clock tick
and then don't even wait for it to stop before issuing
that much on the second clock tick,
this machine is going to scream.
And sure, a code like this goes incredibly well
on this machine.
If you measure the performance per clock tick of code
like this on a machine like that, it's just tremendous.
Of course, most of the time it's not
going to look anything like that.
But interesting nonetheless.
So now that we've seen the kinds of machines
that there are, and of course in the scope of the time
of this talk I can't really go into a lot
of the architectural details that
are very interesting about this machine,
at the end I'll point you at some references
if you want to learn some more about this.
I'd like to talk about two big problems, two
or three big problems in instruction level parallelism.
And the first one is speculative execution.
Speculative execution is an interesting topic.
You hardly heard anybody talk about it just a couple of years
ago.
And now when you look at, let's see,
I was at the ASPLOS conference recently,
which is a good systems conference,
there were three or four papers on speculative execution,
good papers.
So people are really working on the problems here.
And here's the thing about speculative execution.
There really are two sets of problems.
There's how you implement it and then
there's the big problem you get when you do.
The how you implement it is actually simpler
than you'd think.
Here you are with a program.
And looking ahead, you might decide because of the way
you think these branches will go that you'd
like to grab this operation and issue it ahead of these two
branches, because you think they're going to go this way.
And so you speculate that that'll be true.
Well, now the first job you have to do
is what happens when it was an unprofitable speculative
operation?
How do you clean up after it?
And there's a series of techniques you can use.
One technique you can use is in the hardware,
you can arrange to sort of shadow the work you're doing
and have the old state sitting around and the new state.
For example, you can have a shadow set of registers.
And this is an idea that people have
kicked around several times.
And now I've seen there was a paper at ASPLOS
by Mike Smith at Stanford, who was advocating the use of this.
That you grab an operation, do it, but write its results
in a set of special registers.
And you don't sort of commit these registers
as the real results until the branches
resolve in that direction.
So I'm paraphrasing a harder thing.
But this idea has been kicked around.
There was a little bit of something
like that in the multiflow VLIW computer
and it's something people have talked about a lot.
So that's one idea that you could do.
Second idea is to use renaming.
That is when you write the results of your operation.
Suppose the operation that you're pulling up
writes a variable x.
Suppose somebody down here reads the old value of x.
Then you can give this new result a different name.
And when you get down here, when the jumps resolve
in the direction that you had planned,
you can put in code that names that result back to x
if it happens that this value of x and the new value of x
reach some place in common.
Then they have to have the same name.
Those of you who are familiar with compilers, that's
a typical kind of problem.
You would just use compiler renaming, putting
a new sort of move to rename the new value to x down here so
that the same value gets read down both branches.
This is the typical thing you would do, especially in a VLIW,
where you're setting up the world,
that we'll see in a superscalar as well, where you're setting
up the world to do speculative execution without destroying
the state of the old values.
And instead of having to do moves and all of the stuff
and renaming, one thing you can do very often
is simply do operations that don't hurt anything
down this branch.
And then just ignore them when you go down there.
So if over here you're writing a value x
but there's no interest in the old value of x down here,
you can just move it up and not worry about it.
Forget about it when it goes that way.
So x has some value.
You don't care.
So those are the sorts of techniques you can use.
This is all perfectly tractable.
It's been implemented.
The Multiflow Trace did speculative execution
like this.
And people have done the sort of moving things up
that you can ignore for many years
in various different architectures.
So this has been found around, and it seems
like a reasonable thing.
There's a big gotcha with speculative execution though.
And that is what happens when there's an exception?
So it's easiest if we look at it in terms of loads.
So suppose you have a while loop here.
And what we're doing is while the index
I is below some upper limit, we're
going around and doing some computation.
And the computation involves loading A of I. Now,
you might want to look down further iterations
of this computation and bring some loads further up.
That's a typical thing people like to do, because loads very
often, especially array loads if the array is large enough
and you're bypassing a cache, say,
can have a very long latency.
So you want to bring those loads up.
But at some point, you're going to bring a load up that you
wouldn't have wanted to do because of having
gone past the upper limit.
So now you've loaded off the end of the array.
Well, I'm not a big fan of sports sayings,
which are typically trite.
And there's one in particular that
makes me totally crazy whenever I hear a color person in an NFL
game doing.
They'll very often say, I don't know if any of you
have ever noticed this, they'll say when you throw a pass,
three things can happen and two of them
are bad, being an incompletion and an interception.
And the implication is you shouldn't throw passes.
You should run a lot.
So for those of you who know football,
that makes some sense.
That's of course, patently crazy,
because it doesn't weigh the probabilities of the bad things
and good things happening and the cost and benefit
of the good and bad things.
But you're always hearing them say, if you throw a pass,
three things can happen, two of them are bad.
Well, speculative loads are just like that.
If you do a speculative load, three things can happen
and two of them are bad.
The good thing that happens is you
do the load, everything's fine.
You fetch the data.
Nobody seems to have a complaint.
If it turns out that you don't want
to use the data, then great.
You ignore it.
I mean, you just did a load.
What's the harm of doing a load?
You can certainly ignore it if it turns out
that you don't go the direction that would have required
the use of that load.
Second thing that can happen, though, and this is bad,
is that you might have a miss in your memory hierarchy
somewhere.
And now you've got to figure out whether to service that miss.
Now, you might have no choice.
Somebody might have built the system in that way.
But for the system designer, maybe you
want to build in some ability to allow you to not have to stop.
Particularly, I mean, OK, if it's a cache miss.
But suppose the page fault.
Do you really want to stop and service
the page fault, which takes an awfully long time, if you start
getting a lot of them because you've
run off the end of an array?
And now you're really getting into the area of data
that you're not interested in.
Worse than that, imagine you're chasing pointers.
And now you start loading from some useless address
because you're going off into some place
that the pointer structure never meant
you to be because your test for the end
would have stopped you before you got there.
And now you've got some address that's
an address you're not even slightly interested in.
So you have a policy question of whether,
if you build the hardware, whether to allow yourself
to not service page fault. So that's the first bad thing that
can happen.
Second bad thing that can happen,
which is maybe less bad, is that you
might get an actual exception.
So you might try to access an address that's
not only off the end of the array
but out of your user space.
Or it might be on Mars.
There might be some address that doesn't even make any sense.
So that's easy.
The hardware raises its hand and says, oops, sorry, bad address.
Well, now what?
Chances are you've only gotten that because you've
done something speculatively.
The only other alternative is that it's a user error.
And those are pretty infrequent compared to,
as it turns out when you measure,
compared to exceptions raised from speculative operations.
The multiflow compiler, which I have some experience with,
Stefan Freudenberger, and I've been
looking at these properties at HP of the multiflow compiler.
And we've been finding that, in fact, some programs
have hundreds of thousands of fake exceptions.
That is, exceptions raised by unprofitable speculative loads.
And if you have to stop and report each of those
or take some kind of trap during each of those, that's misery.
But what can you do?
If you just ignore them, which is what you're tempted to do,
what do you do when the user actually has an error and does
a speculative load near your compiler or hardware has marked
it is speculative, and now your system says, oh look,
here's an exception on the speculative load.
Ha ha, they're not fooling me.
Well, what if it turns out it's actually a user error?
Planes fall out of the sky.
Bridges collapse.
So you have to report them or you're in trouble there.
So now what?
You've got 200,000 of these things in some program.
You don't want to report them except if it's user error,
and then you do want to report it.
So that's a piece of engineering that people
have been working very hard on the last couple of years.
And the basic idea that you'll see in several papers
that people have written up is sort
of to mimic the IEEE floating point idea,
which is to produce some invalid value, set a bit somewhere that
says, of course, integers, unfortunately,
addresses, things like that, don't
have this nice extra representation
that floating point numbers have that makes no sense
that you can use.
You can call not a number.
And then for those of about that, and then
get this for free.
You have to build some hardware to take
care of this, some extra bits somewhere,
that allow you to tag something you've
done as having been speculative and raised an exception.
And then somehow, you arrange, and this
is where the engineering comes in,
somehow you arrange to find out when the branches resolve
in such a way that you know for a fact
that it was a profitable speculative operation.
That is, the flow of control eventually did go that way.
And so you shouldn't have gotten an exception.
It wasn't that didn't mean to do that operation
in the first place.
You did.
It's a real user error.
You better stop and report it.
So you have to somehow leave around
in that spot when you finally get
to where the branches resolve the right way the ability
to report this user error.
So that's the idea.
Hardware delays the report until the branch resolves.
And you'll see people building systems
that do this in the future.
Nothing like this has been built yet.
Again, the machine that I've had a lot of experience with
is probably the most ambitious by
far in terms of doing this step.
The Multiflow Trace VLIWs did do speculative loads.
It marked them as speculative.
But in the end, would just throw away
exceptions on speculative loads, and that's
a pretty dangerous policy and not the sort of thing
you'd want to be doing.
Second huge area concerns the two real big disadvantages
of superscalars and VLIWs.
And I'm going to talk about the VLIW disadvantage is
what the next slide will say.
But in the course of doing it, then I'll
compare it to superscalars.
And I'll talk about what the big disadvantages for superscalars.
The big disadvantage for VLIWs is object code compatibility.
This is really the Achilles heel of these architectures.
And it is a big problem.
And I'm personally dying to know just how all of this
is going to turn out.
I certainly have my guesses.
But right now VLIWs pose a very big engineering problem
for computer manufacturers.
This is not a technical problem in terms of building systems
that work correctly and go fast.
It's the problem that when you build a VLIW
and you're a computer manufacturer,
you have the problem that when you
want to ship your next VLIW, it's
unlikely to run the code that was
running on your previous VLIW.
Let me explain why that is.
If what you've done in a VLIW is written
the actual record of execution that you're expecting to get,
then what happens when you've put a multiply here
and an add that uses its data three cycles later
and you build a new machine in which the multiply takes
five cycles instead of three?
This old code will not have the right answer waiting for it
after three cycles.
Now, you can put in a way of stopping and waiting, spinning
for a couple of cycles, and that happens.
But now you're going to throw away
a lot of the advantage of your new system
when it runs the old code.
That's pretty unacceptable, and even that's
hard to engineer in some aspects.
So the problem is that when you have your old code
and you want to run it on your new VLIW,
unless you've just scaled the clock, then it's OK.
If everything is in the same relation to each other,
if all the latencies are the same relative to each other,
that's fine.
Same number of clock signals.
But if you've done anything else about changing the latencies,
you have a real problem in this.
Now, there are a lot of hardware and software tricks
that people have talked about playing for a VLIWs.
And there's a lot of energy being put toward really solving
this problem in the system by sort
of importing a little bit of superscalerness
into the machines.
And the machines that have been built, both the Multiflow
machine and the Cydrome machine, for example,
which were the two most ambitious VLIWs that
were built in the 1980s.
Both had some mechanism whereby you could do loads
and in case the load had to delay
for one reason or the other, the machine
could take care of that.
It could sort of stop and wait.
But you don't want to push that idea too far,
or you're throwing away all of the performance that the VLIW
is supposed to be giving you.
Now, there's a second approach to solving this,
and that is to distribute something different from fully
bound object code.
This is a period in a few experimental systems.
Even some little bit of extra work
is done in linkers in some commercial systems as well.
So what you distribute is not quite fully bound object code.
Well, you might want to take that idea to a much
greater extreme in a VLIW.
And what you might want to do instead
is to ship something in which the final scheduling
step hasn't been done.
The dependence analysis has been done.
Some amount of the scheduling perhaps has been done.
But the linker, basically, or what looks to the user
like the linker does this final scheduling
at install time for the code.
So that's distributing some sort of raised objects
beyond the thing you'd expect.
So those are the directions that people
have been using for solving this object code compatibility
problem.
Now, of course, there's another solution to the object code
compatibility problem, and that is build a superscalar.
And at first glance, and in reality
in the systems we ship today, this problem
is completely solved by shipping a superscalar.
A superscalar, after all, gets the sequential code
in the hardware.
The thing that you send to the user
is the stuff that comes out after the squiggly line
way over here, not the squiggly line right over there,
if you remember that slide.
And all the rest of the stuff that's
changing according to the latencies
and so on of the hardware is being done in the hardware.
So you just build different control hardware
as part of the implementation of the superscalar.
It's going to run the sequential code.
As far as the user's concerned, distribute the sequential code,
it'll run correctly on every system.
No problem.
There is a problem with it.
For systems with the amount of ILP
that we see today, the problem really is solved just fine,
I believe.
But what I'm not convinced of is that the problem is solved
for large amounts more ILP.
And I'd like to explain why and what the problem is.
Now, this is all conjecture.
People have never built a superscalar
that goes beyond the superscalars we have today.
We finally, in fact, have gotten up
just sort of to the level of the big machines
that people were building dozens of years ago.
And it's going to be very interesting to see
what direction this goes in now that we
have machines that have finally gotten up to that boundary.
But here's the problem with large amounts of instruction
level parallelism.
First of all, you might want to ask
whether that amount of instruction level parallelism
is there.
Before the end of this talk, I'm going
to talk about how much instruction level
parallelism I think is available in different kinds of codes.
But one quick answer before I talk
about this problem with superscalars
is to say, well, maybe this is all the ILP
there really is in most programs except for scientific programs.
Scientific programs, you give them
a vector unit along with your modest superscalar
and then you're just doing fine.
And if that's all there is, then this is no problem.
Then we can go on from there.
So that's one simple answer.
I don't believe it's going to be true in the end,
and I certainly hope it's not true in the end.
But it's always possible.
There's no way to know for sure right now.
But what happens when you have large amounts of ILP?
One negative answer is you can't even
build a superscalar like that.
After all, if you have large amounts of instruction level
parallelism, then you have to be looking
at a lot of operations at once.
And to do the independence recognition,
you have to look at these operations
basically pairwise and ask, are they independent of each other?
Whatever algorithm you're going to use
is going to seem to grow exponentially
in the number of operations you want to consider.
If you have a large amount of operations
that you're trying to fire every cycle,
you better be considering a huge amount more than that.
And having this control hardware grow exponentially
in so many operations is likely to be really bad news
for the hardware designer.
I think if you talk to the people who've
built today's most ambitious superscalars, most of them
maybe are more plucky and public,
but they're not really excited about the next steps.
It really seems hard to go much beyond where we are now.
So this is a real problem.
Totally unknown.
It might turn out that there are nice hardware algorithms you
can use that will make this problem fine
and then everything is fine.
But question one is, can you really scale superscalars
much beyond where we are today?
It's not a problem for VLIWs.
You have to scale the compiling time, which unfortunately
in this tape there isn't enough time for me to really go
into that subject.
But I don't think compiling time is
going to be a very big barrier in the end to using VLIWs.
I think compiling is going to end up
being very fast, even very sophisticated compiling
for VLIWs.
That's something I'm very confident about.
But scaling these superscalars, so VLIWs scale very nicely.
You just add more functionality.
It's a pretty linear design, and it's not a huge problem
to grow it.
But growing the superscalar, you've
got the central control unit more or less all
in one place that has to do this exponentially growing job.
It's kind of scary, actually.
Next question is, what about the register
architecture of the machine?
Once you fix your architecture, you
have to fix the number of registers.
If you have a lot more instruction level parallelism,
you have a lot more operations in flight at the same time.
There's a natural pressure that starts
going on the number of registers you have.
Unless you start with a very large number of registers,
enough to supply data for your most ambitious superscalar,
then you're going to find yourself
starved as you go from the inexpensive model
to the expensive model.
They all have to have the same register architecture.
So that's a bit of a limit in scaling superscalars that
really is a problem if you want to stay object code compatible.
You can't, after all, send instructions
that refer to register 39 in a machine that
only has 32 registers.
And then the bigger question.
And here's a real unknown, and I'm
really curious about what the answer to this is.
That is, suppose you build two different superscalar
implementations of the same architecture.
Now, they're both going to run the code correctly.
That's not an issue.
But what happens if the latencies
are dramatically different?
For example, you might have one expensive one and one
low cost model.
And if you look at those two, it's
very likely going to be that the ratio
of the long latency operations, like memory
operations and floating point operations,
compared to integer operations is going to be very much
greater in the low cost model than it will in the highest
performance model.
Because that's sort of where you put your speed
in the high performance model.
You engineer those systems, multi-level caches and fast,
fast floating point into the hardware.
And that's where you put your dollar.
So now you have these tremendously different ratios
of latencies of operations between the two
implementations.
Can you really distribute the same object code to both
and not give up tremendous performance on one of them
compared to what you could have if you distributed two
separate sets of object code?
Big unknown.
If it turns out that on, for example, the low cost model
your performance suffers terribly
because you ship the expensive model's object code,
third party software vendors are probably
going to be very reluctant to do that.
They're going to want their best performance on the machine
that you sold zillions of, not on the machine
that you sold a very few of.
But then what happens is you're losing your advantage
on the expensive machine.
If they have to ship two different versions,
there goes object code compatibility.
The whole point of this is to only
have one set of object code.
And that's just unknown.
It could well be that all you have to do
is get the things that are independent near each other.
That's good enough and will get you
close to the best performance you
can get on either kind of machine,
on either implementation of the superscalar.
But that's a really big unknown for us in this field.
Now, there's one other thing.
And that is that you very often hear
people say that what they don't like about VLIW
and that they do like about superscalars is
that the compiling effort is so bad on VLIWs
and superscalars aren't like that.
And really, I have my beliefs about these subjects,
and maybe they come through, but I've
tried to really say what I think is known and what's not known.
This is not known either.
But I just feel so strongly about it,
I have a lot of trouble believing that the statement
could possibly be true.
To me the effort in compiling--
and not the statement.
The statement that you don't have
to compile very ambitiously for superscalars.
What I believe is that this statement really is true.
And that is that the effort in compiling
is a function of the ILP that you want to get.
It's not a function of whether the machine is
a VLIW or a superscalar.
And my argument is as follows.
The argument that it's easier for a superscalar
is that the superscalar looks down the instruction stream
and it does the data dependence analysis
and it does the scheduling and it predicts the branches.
And you can do branch prediction dynamically
while the program is running and even do it more
accurately as a result. It does all of the stuff
that you've talked about doing in the compiler,
does it while the program's running.
Why on Earth would you do it in the compiler as well?
So you don't need an ambitious compiler.
Well, most of that argument is true,
but it turns out a crucial piece isn't.
Yes, the superscalar can look down a long ways
by predicting branches dynamically.
And yes, a superscalar probably can do the scheduling.
Scheduling is a pretty linear job
and it's probably practical to build
a fair amount of scheduling into the hardware.
The problem is in the data dependence analysis.
And if a superscalar is going to get a lot of instruction level
parallelism, it's going to have to look very far down,
hundreds of operations down the instruction stream to get that.
Well, the superscalar is going to have something that could be
called a window of opportunity.
It's going to have sort of a sliding window
ahead of where we're executing.
Where it's looking in order to pull things up,
there's going to be some finite number of operations
that it can look down.
And the operations that are data independent
are going to be peppered through the code down there.
They're not going to be all clumped together.
In fact, the opposite effect tends to happen.
Usually operations are data dependent upon the ones written
right before them, because that's
the way programs are written.
So do some stream of computation and then some more or less
independent stream of computation
later and then finally collect those results
and do something else.
So you have to look way down the stream to do that.
That's going to get a huge window of opportunity that's
not going to be practical to build superscalar.
Too much of this exponentially growing dependence analysis.
And so the solution is that you need
to have a compiler which does the dependence
analysis in the beginning, does code rearrangement.
Probably you want the compiler to arrange
for speculative execution then.
That's probably easier than trying to decide
to do that on the fly.
And it's hard to see how you're going
to avoid doing this work in the compiler, virtually
the same work you have to do to compile for a VLIW.
The two really do seem very much equivalent to me.
So I don't believe the argument that a superscalar
is going to buy you compiling speed at all.
Now, there's one other thing I want
to mention on the subject of object code compatibility,
and that is the VLIW disadvantage
of having a new implementation have changed latencies.
And thus having the inability to run
the old code on the new machine has another aspect to it.
And that is within a given implementation, a given VLIW,
certain operations that you want to do
might have variable latency depending upon the data.
So I mentioned, for example, that the Multiflow and Cydrome
machines both had the property that the designers built
in the ability for a long, long load
to occur, longer than the schedule expected,
and then the machine would stall in order
to get the correct answer when that happened.
So in that case, we've seen another disadvantage of VLIWs.
And that is that a super scalar can dynamically
arrange the schedule on the fly to only issue the things that
are data ready, looking at what's data already
at that moment.
So it can adjust to longer and shorter variable latencies.
A VLIW, you have to decide in advance.
So that's another advantage of superscalars.
I'm not really convinced that's an important advantage.
And I was at the same conference,
the VLIW conference.
Butler Lampson gave the keynote speech.
And he mentioned something in a totally unrelated area that
really reminded me of this.
And that is in communications, you have the same problem.
You have asynchronous versus synchronous communications.
And the trade off is that asynchronous communications
can adjust to changed latencies and communications.
And thus, you don't have to do a worst case analysis in order
to set up the communications.
Synchronous communications, you have
to be sure the data is getting there.
So you have to do a worst case analysis.
And it's been everyone's intuition
that asynchronous communications would be faster because you
didn't have to allow for the worst that could possibly
happen.
Of course, there's the overhead of figuring out
whether everything was OK or not.
That's what's wrong with asynchronous communications.
That's a lot like superscalars.
And synchronous communications are a lot like VLIWs.
And Butler's comment was everybody
always expects asynchronous communications to be faster.
Synchronous communications is always faster, as it turns out.
And I was very much reminded of this trade off.
So I really do believe that that problem
of changing latencies of functioning, it's
just not a big deal.
People often cited as one of the real advantages
of superscalars.
There's another real advantage, and this
is another part of the hardware software trade off.
The typical classical trade off you
have in system design when you're
doing hardware versus software choices
is that in the software--
I'm sorry, in the hardware, you have perfect knowledge.
That is, you're making your decisions
while the program is running.
And so you can see all the values of everything.
Whereas in the software, you have incomplete knowledge.
You're analyzing a program that hasn't yet run.
You don't know what the data is.
You don't know which way the flow of control has gone.
You're missing an awful lot of information.
The good news is you have all the time in the world
to do your analysis.
Of course, if your compiler is that slow,
then you're not going to have a very viable product.
But even within the bounds of what people expect,
you have a lot more than the four nanoseconds
the hardware is going to have to make its decisions.
So in the software, you can do a much more sophisticated
analysis.
In the hardware, you're really stuck
with doing something a lot more shallow but with better
information.
So that is another trade off here between these two systems.
But it's really more than anything
a trade off of sophisticated compiling versus less
sophisticated compiling.
Now, it's often cited as an advantage for superscalars
that they have this runtime information.
And so they can do a better job of scheduling
and a better job of dependence analysis.
But I just have trouble believing
that that adds very much, given the amount of time
you have to do it.
But that is something that does distinguish a superscalar
from a system that isn't a superscalar
and can't do that kind of dynamic analysis.
One important kind of analysis is something
called memory disambiguation.
And there's certainly no time in this talk
to go into that subject.
But the basic problem is if you have two operations, one
of which reads an array value and the other of which
writes some array value, is it permissible to do them
in the other order to get more instruction level parallelism?
Well, you have to know whether they're reading and writing
the same value or not.
And of course at runtime, you can tell.
You just look at the address that's in the hardware.
At compile time, sometimes that's
a tremendously sophisticated analysis.
When it comes to arrays, people have gotten very good
at that analysis, at solving the equation of whether these two
indices are the same.
That's called array disambiguation.
For pointers, where now you have two references to memory
where the references came through pointers,
that's a wide open subject.
People have looked at that in several different contexts
of system design.
And I think it's one of the big frontiers in instruction level
parallelism.
I think that real progress is going to be
made in pointer disambiguation.
It is an incredibly hard problem.
It may involve some slight change of programming paradigm
in a way that we've learned good programming.
I'm not talking about adding wild new constructs
to languages.
But the way we've learned new programming practices
about aliasing and things and Fortran programming,
for example, over the decades.
I think that may in decades happen
with pointer disambiguation.
But in my opinion, nobody's going
to do sophisticated pointer disambiguation any time real
soon.
OK.
Now, what I certainly don't have time to do in this talk
is go into the slightest amount of detail
about code generation techniques.
Code generation techniques are one of the reasons
that instruction level parallelism has really
taken off in the last 10 years.
People are a lot more confident of their ability
to do the kind of code generation
that you have to do in order to use these machines effectively.
One of the techniques is called trace scheduling.
And it's a technique that came along
around 12 or 13 years ago.
It was something I was involved in.
And it's a way of taking this idea of looking down
the instruction stream and speculating
in the most likely direction and doing the code generation
in advance in order to build correct code that
gets the advantages of going past conditional jumps.
And the basic way it works, this is incredibly superficial,
but there are references that come with this tape
that if you're interested, you can learn more about it.
Basic way it works is that the compiler takes the code
and picks a path through the code that it thinks of as being
one of the more likely paths.
And sometimes it will unroll loops and in line subroutines
and unwind rejoins and so on to make these paths longer.
And then it just makes the assumption
that this is the way the code is going to go.
Builds a big data precedence graph
that it does the independent analysis.
Schedules this into these wide instruction words
if you're scheduling for a VLIW or schedules
the independent operations clump next to each other
so the superscalar can find them without having to have
a huge window of opportunity.
Schedules them.
Some of them will be speculative.
And then schedules whatever code is
necessary to do renaming and so on at the boundaries
of this trace.
Now, when the code goes this way, you do very well.
You get a lot of performance because you
speculated ahead a lot and exposed
a lot of the instruction level parallelism.
When it doesn't go this way, you've set it up in such a way
that the semantics are right.
Now, you're not going to pick every trace and compile it.
That's too many, remember.
But what you do is having compiled one,
you take the code that hasn't been compiled yet,
and you pick the most likely path
from what's remaining and so on.
Now, there's a lot of techniques for doing
this kind of scalar code generation for instruction
level parallel machines.
Some of them are variants on traced scheduling.
Some of them depart quite a bit more than that.
But basically, they all follow the same idea
of trying to take advantage of predicting in advance the most
likely path and scheduling the entire path at once
rather than just scheduling little pieces of it.
Now, for loops, there's another important technique.
It's called software pipelining.
And software pipelining is--
I'm going to show you how it works very, very
informally on a very, very simple type of example.
But I just want you to get the idea of what it's about.
It's actually quite a large technology and quite
a sophisticated technology, still in its infancy
and still with a lot of research being done.
But the basic idea is suppose you have a tight loop of just
these five operations A through E.
And you have hardware that operates in such a way
that functional unit one can do A,
functional unit two can do B, and so on.
Our goal is to come up with a schedule for this loop that
instead of doing A, waiting for it to finish,
doing B, waiting for it to finish,
these might be data dependent on each other, for example.
Instead of doing that, we can start later iterations next
to these and do pieces of all the different iterations
at the same time in one cycle or in a handful of cycles
that we repeat over and over again.
So the basic way you can think of it, even
though the technique for generating code
is very different from this, basic way you can think of it
is first cycle, start the first iteration.
Now, as time goes by, you're going
to do the following operations from that iteration
on the different functional units,
starting them each on successive cycles.
Because they depend upon this one.
Second cycle, start the second iteration.
And then in following cycles, continue that.
And then keep going after that.
And what you find is that eventually, you sort of filled
your machine with some repeating pattern
where each functional unit is doing
the same thing in the simple example over and over again.
And then this repeating pattern can be just considered
a single tight loop.
So now you pull the repeating pattern out.
This is, again, how you think of it.
It's not necessarily how you would implement the code
generator.
You pull this repeating pattern out,
and it becomes your tight loop in the center.
And you set it up with something called
the prologue that starts all the iterations necessary to get
into the tight loop in the center.
And you finish it with a post log that
finishes the iterations that have been started
and have been completed.
Again, there's more in the references about this
if you're interested in finding out more about it.
So finally, let me sum up here.
What we've seen is that in the last few years,
microprocessor designs from the major manufacturers
for their fastest workstations have all
embodied a fair amount of instruction level parallelism.
The HP PA-RISC 7100, the IBM RS/6000, the announced DEC
Alpha are all superscalar machines
with varying degrees but a fair amount
in each case of instruction level parallelism.
These are incredibly fast machines.
They're fast cycle time machines,
but they get a lot more advantage
out of the instruction level parallelism
than you might imagine.
So these are machines that are very much the state of the art.
And these days, if you're building high performance
processors, if you're not doing instruction level parallelism,
you're just not there.
In the '80s, we had the phenomenon
of startups that were building many supercomputers that
embodied instruction level parallelism.
There were some superscalar ones and there
were a couple of VLIW ones.
The Multiflow Trace machine I was associated with,
the Cydrome that Bob Rau also at HP was associated with,
and the Color, for example.
For one reason or another, virtually all
of these mini supercomputer startups
failed, whether they had very ambitious architectures
or very humdrum architectures.
Mostly these were not strongly related, in my opinion,
to the technology that was there.
Certainly the Multiflow machine had tremendous price
performance and ease of use in its time
and had a lot of commercial acceptance.
I think a total of 120 pretty big machines
sold over the years.
But the company finally couldn't make it.
But what did happen is that a lot of the technology
got purchased by a lot of large companies.
And I believe, for example, that the Fujitsu supercomputer that
was just announced a couple of weeks ago that
has as each of its nodes a long instruction word machine.
And I believe they're using multiflow technology, compiling
technology, and so on in that product.
I know several large companies have released the multiflow
compiler as a compiler for their products.
And I know that it's underdeveloped.
It's being used in development efforts
in a lot of large companies and in some of these products.
And other startup technologies have found their way in.
But in fairness, no VLIW has been commercially successful.
There were the array processors of the '70s that
were really difficult beasts to use
but had tremendous price performance
but never really made it as general purpose computers.
And what's going to be interesting
is that now that we're pushing the boundary of instruction
level parallelism and what's available,
it really will be an exciting time
to see which way this thing goes,
whether we're going to be able to make superscalars practical
and whether that's the right answer
or whether VLIWs are going to have to come in
to have the simpler hardware.
Very big questions do remain unknown.
The biggest question is how much instruction level parallelism
is there.
And I'd like to just close by giving you
my quick summary of how I read the limit
studies and the practical experience people have had
so far.
For scientific codes, technical codes, it's no question.
There's a lot of instruction level parallelism.
Most of these vectorize.
There's a lot of other ways to get this advantage,
but VLIWs certainly are a very effective way of getting it
and superscalars run very well in these codes also.
Those numbers are huge and doesn't even
make sense as the same.
It's a function of how much hardware
you throw at the problem.
So that's easy, the sort of vectorizable array oriented
codes.
For scientific codes that aren't quite so easy
but are still sort of a pipeline floating
point, memory intensive array codes that you see around,
probably a factor of five is not a question.
We can probably easily do that in time.
And I suspect it'll go a lot farther than that,
but you can't really make a strong case for it yet.
For the scientific technical integer codes that are around,
it's probably around there also, but it's not so clear
that you can go much further.
But that would be my take on what the studies have said.
A lot of people certainly are far more pessimistic than that.
Some people are more optimistic.
Certainly time will tell.
And finally, for the systems codes maybe
it's a factor of two or three that you
can get from the studies that have been there today.
And I think there things like pointer disambiguation and code
generation techniques are going to make a very big difference
in what we're able to do.
And it'll be very interesting to see
what the future holds for that.
Finally, the commercial codes, I don't think anybody
knows anything.
I've heard some anecdotal evidence
that for a lot of the more business data
processing oriented codes, there is
a lot of instruction level parallelism that's
available to us.
But I don't know of any studies that people
have done and published that have told us just
what those codes look like.
So if you are interested in knowing more about the subject,
Bob Rau and I have a paper that was in Science Magazine
last year that's a survey.
Not quite on the level of this talk, but in some
places goes into a lot more detail
and has a very good reference list.
In fact, it's conversations with Bob over the last few years
that have really given me a lot of the perspective you've heard
in the course of this talk.
So thank you very much for coming.
I've enjoyed this talk a lot.
So let's open it up for some questions.
Yes?
Josh, could you tell us more about software pipelining
in commercial systems?
Sure.
Thanks.
Well, the software pipelining is a really interesting
technology.
It's a lot more mathematical in nature
than some of the other code generation techniques
and so has gotten a lot of interest
from a lot of different groups who
tried to formulate different ways of doing it.
It was used in the floating point systems early on.
Floating point built these array processors that eventually
had the ROM be substituted-- have RAM substituted
for the ROM that was in there.
And there were a lot of the algorithms that
went very well on that, went very fast on that system
because they use software pipelining.
Cydrome got started because of Bob Rau's software pipelining
experience and algorithms and particularly because he
had a lot of good ideas about how
to build hardware that made it easier to software pipeline.
We've actually done a lot of that at HP.
First the Apollo systems, the people in the DN 10,000
had written a software pipeline for that machine.
But now, in fact, the commercial compiler
you get with the PA risk products you buy today
does software pipeline right in it.
And there's a lot of research going on at HP Labs,
Bob Rau's group, and a lot of other places
where people are looking at software pipeline.
So it's really become an important topic.
It even makes ordinary sequential machines
that have a little bit of sort of subtle instruction level
parallelism in them go faster when you do that.
So it's a pretty valuable technique.
Yes?
Could you tell us how high level transformations
like loop unrolling or inlining effects do ILP [INAUDIBLE]??
Absolutely.
They turn out to be critical effects.
If you have a subroutine call in the middle of a tight loop,
you're not going to get anywhere if that subroutine calls
a boundary beyond which your ILP won't go.
So the typical thing people will do
is insert a text copy of the subroutine into that.
Now of course, that is a source control problem.
You have to make sure that when you modify that subroutine,
you catch every place that it was in line later
in your [INAUDIBLE] control system.
So that's one technique that's used all the time.
Similarly, loop unrolling.
Unless your software are pipelining, in which case
you want the tightest copy of the loop you can get,
loop unrolling, which used to be used for compiler optimization
to eliminate the test between iterations,
if you could predict that you'd go around
a certain number of times.
For ILP, you're happy enough to leave the test in.
That tends to be a very predictable branch
at the end of the loop.
But what you want is to get rather
than a small body of text, you want a very large body of text.
And in fact, when people complain about the compile time
for these what Bill Wolf calls heroic compilers that
do this sort of thing, the compile time more than anything
comes about because of the expansion
in the code size due to loop unrolling
and subroutine inlining.
That's really been the biggest factor.
Yes?
How does dataflow machines merge into your characterization?
Is this [INAUDIBLE] superscalar or are there some differences?
Yes, that's a great question.
Dataflow machines I really left out,
even though they are very much instruction
level parallel machines.
Right now the emphasis on data flow
has gotten more off to the multiple thread
world and MIMD processors.
So it hasn't been such a practical thing
as superscalars and VLIWs.
People haven't really built one that
would be in any way commercially competitive
to do just instructional level parallelism.
But in a sense, they're the purest kind
of instruction level parallelism when running a single thread.
What you have is the code itself specifying exactly
the dependence relationship as part of the way
the code is written.
And the hardware simply is notified.
It has operations which are notified that it's
time for them to fire.
And it's very much an instruction level parallelism
idea.
And it's a little bit in between superscalars and VLIWs
in a way, because VLIWs, and again, you
can read more about in this paper
where we do discuss dataflow machines in this context.
VLIWs require the independence between operations
to be specified.
And superscalars don't specify anything in advance.
The hardware figures it out.
Dataflow machines have the dependence relationship
and still have to figure out what's independent
and what can be scheduled.
So they really are in some sense one
of these intermediate solutions.
They're a wonderfully alluring idea.
Somebody said they've been the greatest
idea and the next coming thing in architecture
for 25 years now.
So they just haven't made it for this purpose.
But they seem a lot more promising
for multithread applications.
Yes?
You talked about the predictability of branches.
And one of the things when compilers
is that compilers don't know which way branches will go.
Are you suggesting the use of feedback
as a compiler mechanism to get optimal use
of the architecture?
Yeah.
That's also a great question.
I wish there had been time for me
to talk a lot more about profile based optimization
in general, which is an interesting subject area even
independent of this.
There are a lot of other profile based optimizations you can do.
What I mean by profile based is just what it sounds like.
The compiler has access to some quote "representative data"
and then runs it to get an estimate of which way the jumps
go and then does optimisations, or in this case
does its scheduling, based on which way those estimates
from previous runs tell you.
They're sort of three ways.
You can either ask the programmer, which is not
a very acceptable way to tell which way jumps go,
or you can use heuristics.
And the jury's out on heuristics.
Experiments so far have failed.
But I've been hearing a lot of underground swell
that really sophisticated heuristics maybe
do almost as well as profiling.
And then there's profiling.
Profiling has the disadvantage that it involves the user.
And we've yet to see really well engineered systems that
make this very transparent to the user
but still allow the compiler to gain access to profiling
information from these codes.
Has to involve the users some.
And I'm, again, interested to see how that works out.
It certainly is the best way to get data.
And it turns out you can come very close
to the best possible.
[INAUDIBLE] and I, the reason I had those branch statistics
is that we just did a study that was in this last ASPLOS.
And we showed that you really can use very unrelated data
and do very well most of the time in predicting branches.
Yes?
To get more ILP, you have to look deeper
in the instructions stream.
And I was wondering if there's any idea how much of a trade
offs there is between the gains from the ILP
and the loss of perhaps data locality.
Yes, that's a very good question.
And I think one can generalize it to just
say, how does ILP play with data locality in general?
Is it really a good thing or a bad thing?
And my take on it is that for the kinds of systems
we're talking about today and the sizes of caches we
have today, and the ones we'll have in the future,
which will be even better from this respect,
that that's not just not a big issue.
Just looking at code and getting a feeling for it.
But time will really tell.
The most ambitious ILP machine there's ever been, I believe,
was the Multiflow Trace, which could fire off
28 operations at a time and keep maybe 80 of them
going in flight at once.
And it didn't have a data cache.
So locality was just not an issue particularly,
though some forms of locality were for that machine.
So there really isn't that kind of experience.
But my guess is that that's not going
to be a big problem at all.
But who knows?
I'm always an optimist.
So well, I'd really like to thank you for coming today.
I've enjoyed giving this talk a lot.
[MUSIC PLAYING]