[MUSIC PLAYING]
On behalf of the MIT summer session,
let me indicate how happy we are to be participating
in this edition of the University Video Communications
Distinguished Lecture Series.
Our speaker tonight is Danny Hillis, a founder
and chief guru of Thinking Machines Corporation.
He received his PhD from MIT in 1988,
but in 1981, he was already becoming interested
in the physical limitations of computation
and the possibility of constructing
highly parallel computers.
This work culminated in 1985 with the design
of the Connection Machine, which became the foundation
of his very successful company.
His topic tonight is Connection Machine architectures.
Danny--
I'm interested in designing computers
for the very largest problems.
And I got interested in this kind of computer design
originally as a user, because I had some problems
that I was studying in artificial intelligence that
required much, much faster computers than I could buy--
like 100,000 times faster.
And it didn't look like anybody else was going to build them,
and so I got interested in the problem of building them.
And as it turned out, fortunately,
a lot of other people were interested in such computers
too.
A typical application is-- for example,
in designing an airplane, people want
to simulate the shape of the airplane wing
and the air flying over it so that they can figure out
how the airplane is going to fly before they build it
and before they have to test it in a wind tunnel.
Or another example as the scientist
might use it to model a system that they
have no hope of really physically
modeling-- for example, the formation of a galaxy
or the folding of a protein.
And all of these problems require a tremendous amount
of computation-- much, much more than we can really do today
to do the problems accurately.
So it's great for computer designer,
because as soon as you build a faster machine,
the users of this kind of problem want to get faster one.
And there's really no end in sight for that.
They seem to want computers that are certainly
thousands of times faster than what we can give them today.
Now, another great thing about this set of big users
is, because they're solving problems
that people haven't solved before, they're generally
writing their programs from scratch.
And they're very often willing to write their programs
in a different way to run them on your machine, which
is very important, because it frees up
what's one of the biggest constraints
for a normal computer architect, which
is to run existing programs.
So the computers that I'll be talking about today, which
are called it a parallel computers,
use a somewhat different formalism
in programming them, some very different primitives,
different programming languages, and things like that.
But the users are willing to adopt that different formalism,
because that's the only way that they can solve their problem.
And in fact, as it turns out, it's
a very natural formalism for a wide class of problems.
So what I'm going to be talking about today
is this kind of architecture, which is called a data parallel
architecture, of which the connection machine is
an example.
And I will, I hope, convince you that this
is the most natural kind of architecture
for very large problems.
I'm certainly convince of that.
I'm going to start by explaining why conventional Von Neumann
machines are a poor fit to very large problems,
and why data parallel machines are
a much more natural approach.
I'm then going to talk about some of the design issues
in designing data parallel machines,
and specifically, how do you achieve
a balance between processing and communications
in I/O, which turns out to be some of the hardest engineering
issues.
And then finally, I'm going to talk just a little bit
about where we stand today and where this technology is
likely to lead in the future.
So let me start by talking about Von Neumann machines, which
are the kind of machines that we're all used to,
and represent almost all of the computers in the world today.
And the basic idea of a Von Neumann machine
is that you have two pieces.
One of them is a processor, which operates on data--
does arithmetic, for example--
and another one is the memory, which holds data and doesn't
operate on it.
And so to operate on data, you leave it stored in the memory.
You move it across.
You add two things together.
You put it back in the memory, and so on.
And typically, you move one word or a few words
across at a time.
This is the single operation model
that's sort of implicit in all of the programming languages
that most of you are used to programming in.
Now, from an engineer standpoint,
the Von Neumann machine was a solution to a technological
opportunity-- or a technological problem,
depending on how you look at it--
which is that, when those machines were designed,
the switching components were very, very fast
and very expensive, and the memory components
were relatively slow and relatively cheap.
So it made sense to build a machine that,
on one side of the room, had these big slow things
like mercury [INAUDIBLE] and another side of the room
had these very fast expensive things, like vacuum tubes,
or relays, or something like that.
And the vacuum tubes switched lots and lots
of times for every memory reference,
and it worked out very well.
In fact, it worked out so well that, as we improved
the components in that kind of machine,
we kept that same basic design.
And so if you look on a modern one-chip computer,
you'll see on one side of the chip is the memory,
and on the other side [INAUDIBLE]
of the chip, the switching elements, which
are the processors-- only today, it's all
made of the same kind of stuff, so it doesn't quite
make sense to separate them.
And in fact, there's a tremendous inefficiency
in separating them out, which comes from the use of silicon
and the activity of the silicon.
So if I take a very, very large machine--
remember, those are the ones I'm interested in--
like a Cray or a big [INAUDIBLE],,
or something like that, or a Connection Machine--
and look at what's inside of it, it's all made of silicon chips.
And if I lay out the silicon chips,
it probably has something on the order of a squaring meter
of silicon in it.
Actually, these days, it's going to be a little bit more--
but something like that.
So imagine that I laid out all the silicon, looked
at it like that.
Now, I would notice that these days, about this much of it
is in the processor itself and about this much of it
is in the memory system--
mostly in the bits of the memory, and the memory
decoding, and things like that.
So if I were able to look at this
under some kind of imaginary microscope
that showed the activity of the chips
and showed where useful things were happening,
I would see that, when this machine was operating,
this part of it was very, very busy most of the time
and this part of it would have one memory location
being referenced at once.
Or maybe, if it was a [INAUDIBLE] pipeline machine,
it might have four, or five, or something like that.
Well, there's a terribly inefficient design,
because we're-- in effect, we're optimizing the activity of this
and leaving all this silicon sitting there doing nothing,
just holding bits.
And in fact, the time that the machine has taken
is mostly information traveling from here to there
and back again, which is what Backus called the Von Neumann
bottleneck.
The terrible thing about this inefficiency
is the bigger that you build a computer, the worse it gets,
because the easiest way to build it bigger
is the memory system becomes larger,
and this proportion of processing to memory
gets even more and more out of whack.
And that waiting for data to move back and forth
between memory becomes more and more
the bottleneck of the machine.
So it's tolerable when you build a little machine, which
has a closer balance of memory and processing,
but it becomes kind of intolerable
when you build a big machine for these kinds of problems.
Now, obviously, the answer is you
want to put in more processing somehow.
And the general answer is somehow,
you want to distribute that processing through the memory,
and you want to mix up in here processors and memory.
And the trick is, how do you do that efficiently?
How does it change the programming model,
and how do you get it to work?
So the Von Neumann machine is basically
good for the big problems, and the potential answer
is parallelism of getting a lot of things to happen at once.
And that will get the efficiency of your machine up.
Now, just because parallelism is the only answer doesn't mean
it's an answer.
And it could be that the problems, in fact,
don't allow for parallelism.
So that's the real question-- is, is there
something fundamental about our problems that requires things
to be done one at a time, or can,
in fact, they be done in parallel all at once?
And if they can be done in parallel,
where is the big source of the parallelism?
Now, if I take a physical simulation example,
it's sort of obvious where the parallelism is--
because for example, imagine that airplane--
you're flowing air over the wing.
Well, when the airplane's flying,
the real air is computing that in parallel.
The air over here is deciding what
to do completely independently of the air over here deciding
what to do.
And so in some sense, the physical situation
is fundamentally parallel, but the question is,
is that reflected in the algorithms?
And it turns out that people solve that same problem
by a variety of different algorithms.
For example, one kind of algorithm--
they do it just like the physics does it-- they
model a whole bunch of particles and model the interaction
of the particles as they bump into the wing
and bump into each other.
And for example, those are called either particle
algorithms or cellular automata algorithms.
Another completely different kind of algorithm
is you model the space as a whole bunch of-- there's
a grid of cells, and you model the behavior
of each of the cells by a set of equations that says how
the air flows through the cell.
Another kind of algorithm is you transform that problem--
that physical problem to a different problem, where
you have to solve a system of equations.
And you solve those equations, and then
you transform the solutions back to the physical problem.
So there are a whole lot of different algorithms
for solving that same physical problem.
It turns out every single one of them
has a tremendous amount of parallelism.
And the good news is [INAUDIBLE] parallelism that grows
with the size of the problem.
So the bigger the problem, the more parallelism there is.
So that looks good for the side of parallelism.
It looks like maybe it's fundamentally there,
when you look at the algorithm.
But there used to be this thing that would bother people
about that argument, which was put most crisply
by Gene Amdahl in Amdahl's law.
And he made the argument that parallel computers will never
really work that much.
They'll never get you more than about a factor of 10.
And here was the argument.
The argument was imagine that I represent the total amount
of computation to be done.
So that's the line, and here's the total amount
of computation.
Now, imagine that some of it is fundamentally sequential
and has to be done a bit at a time, and the rest of it
is parallel and can be done all at once.
So let's be generous and assume 90% of it is parallel
and only 10% of it is sequential.
This would represent how much time
it would take on a sequential machine,
because we'll do all of it in sequence.
But imagine I put 10 processors to work on that same problem.
Well, I get to divide this part of the problem by 10,
so this becomes a tenth the size.
And now the parallel and the sequential [INAUDIBLE]
the same time, because the 10 processors
don't help me on the sequential part.
So I've made the problem a lot faster--
almost 10 times as fast.
But now let's say I put 100 processors on the same problem.
So I now divide this by 100.
Well, if I divide that by 100, then I
get something which is almost entirely dominated
by the sequential part, so I'm getting diminishing returns now
as I put more processors on it.
So this is a very compelling argument [INAUDIBLE] very
intuitive that parallelism--
even if it works on a lot of the problem,
as long as there's a sequential part of the problem there,
the machines are going to become increasingly inefficient.
It used to bother me a lot, but then I started noticing--
and I noticed, in my problem, it didn't really seem to come up.
In my application, it didn't really seem to come up,
and I started noticing, in a lot of other people's applications,
it didn't come up.
I think a lot of people have noticed this
these days, that, in fact, Amdahl's doesn't
seem to be hurting us.
And why not?
And I believe that the best answer is one that was--
I'm going to give a version of an answer that was published by
[INAUDIBLE],, and it has to do with scaling.
The answer is people are not trying
to solve the same problem on the parallel machine
that they solved on the serial machine.
They don't want to solve the same problem faster.
They want to solve a much bigger problem
in the same amount of time.
If we break up the parallel processing part
of the problem-- take something like that airflow--
if we look at an algorithm for airflow,
we'll find that some parts of the airflow problem are--
the amount of computation we have to do
are independent of the size of the problem.
So let me call that using order notation.
That part is order 1.
It's some constant part of the problem.
Then there's a part that, if I double the linear dimension,
I go to twice the resolution, then
there's a part of the computation that doubles.
So if I parameterize the problem in terms of the number of grid
points, for example, and I call that n,
then there's a part of the problem that grows as order n.
Then there's another part of the problem that
depends on the boundary conditions and
so on that grows as order n squared, and so on.
And in fact, there's a big chunk of the problem, which
is the relaxation of the interior of the problem, which
takes more--
not only does it--
the number of points grow up as n cubed, but also
the amount of time that you have to relax it grows up
as another factor of n.
So this keeps on going up, and there's
a part of the problem that grows is [? n ?] to the fourth.
So we've got a lot of different parts of the problem like this.
Well, what happens if somebody comes along and says,
I want a problem that's twice as big,
I want twice the resolution?
Well, this part of the problem doesn't change at all.
This part doubles, this quadruples,
and so on, and this multiplies by 16.
I end up with a much bigger problem,
which goes right off the top of the board.
But if I renormalize that and draw it again,
it looks like almost all of it is
the end of the fourth part of the problem.
And this stuff is tiny.
And if I want it to double yet again,
I can make that even more extreme.
So it turns out, in practice, when you look at this--
and I'm not certain why this should be true,
and I'm certainly not certain it's always true--
but in practice, these higher order terms
are always things that can be done in parallel.
So in fact, it's not like there's
a fixed percentage of the problem
that can be done in parallel, but in fact, the percentage
grows as the problem gets bigger.
Since I'm interested in the biggest problems,
I can always pick a problem that's
big enough, where it's not--
where, in fact, that's not a factor.
In fact, the customers pick that problem,
because the customers will pick a problem where it's big enough
that that's not a factor.
So as it turns out, Amdahl's law doesn't end up biting us--
I think much to everybody's surprise.
I was even surprised, and I'm an optimist.
So I guess the lesson to learn from this
is that the bigger the problem is, the bigger the opportunity
of parallelism.
This is one of the differences between designing a machine
for the center of the market--
so the workstation on your desk--
versus designing a machine for these super applications,
because they're very skewed in the types of opportunities
for parallelism that you have.
The problems that I'm designing for typically
have the opportunity for parallelism
on the order of hundreds of thousands,
or millions of things happening at once,
and very, very little of the problem
is in this fundamentally sequential part.
OK, so the obvious answer then is
I can use lots of processors.
And VLSI technology lets us stamp out
processes relatively inexpensively,
and we can interleave them with memory,
and we can build a machine that's all
mixed up processors and memory.
So what are the design issues for designing a machine
like so that it works efficiently?
Well, first of all, notice that the big source
of the parallelism is in the data.
It's because the data is getting bigger.
The size of the problem, I keep talking about,
is really a data size.
And so the big opportunity is somehow
operating on all of that data at once.
And that's also a very different than a lot of other kinds
of parallel machines.
A much more normal way of getting parallelism
in a machine is to split up the program
into several programs which run it once, each of which
operates on its own data, or some show data,
or something like that.
But the normal effort involved in making
a parallel programming is an effort
of splitting up the program and looking
for control parallelism.
And basically, I think that that's a perfectly good kind
of effort, and I think it makes sense,
and it probably gets you factors of eight or something like
that, but it won't get factors of 100,000,
because you can't break up a 10,000-line program
into 100,000 things running all at once that are all different.
In fact, the data is growing much, much faster
than the program.
The programs are pretty much fixed in length.
So the opportunity for the parallelism
is, in fact, in the loops of that program.
And so for example, take the airplane
wing example, the airflow example.
A sequential computer has a big loop
that calculates what the air does here,
then calculates what the air does here,
and so on, and so on, and so on.
And after it finishes that whole line,
it starts the next line, and the next line, and the next line,
and so on--
whereas the physical fluid calculates all of that
simultaneously.
So the big opportunity is in calculating all of that
simultaneously.
So I'm not so much interested in programs
that can be split so that you can
run several programs at once.
I'm interested in really just running one program,
but what I want to do in that one program is I
want to take out the loop and do all
of the iterations of the loop at once.
That turns out to have some great advantages
for programming, but I'm going to concentrate mostly
on the hardware right now.
It also has some nice advantages of hardware.
So having done that--
so when I do that, that's what I call a data parallel machine.
It's a little bit different issue--
you hear people talk about single instruction machines--
single instruction, multiple data,
versus multiple instruction, multiple data.
It's a related issue, but it's a little bit different,
because really, SIMD versus MIMD is kind of an implementation
issue that, once you've picked a programming model,
you figure out, what's the cheapest way
to implement that model?
This is really an issue of what programming model
you want to support.
And in fact, then you have a choice
of whether you want to put some of the control down
in the processors or keep it centralized.
And that's a kind of engineering issue
that just depends on the relative cost of wires
and silicon, and it probably changes from year to year.
I think a lot of people expect me
to defend SIMD machines just because I
designed machines that way.
I think that was the right way to design machines in 1990,
and it maybe won't be in 1995, and maybe it
will be again in 2000.
It's a small issue.
That's not really what I believe in.
What I believe in is presenting this data parallel model
to the user, and doing that in the most efficient way.
So how do you do that?
Well, most obvious issue is arithmetic and processing.
And that also turns out to be about the easiest problem
to solve.
So for example, in the CM2 Connection Machine,
it has two kinds of arithmetic.
It has 64,000 bit-serial arithmetic units
that are distributed through the memory,
and it has 2,000 floating point units,
which are 64-bit wide words which are also
distributed to the memory.
And it has some 32-bit data paths
for doing indirect addressing and referencing data.
So it's a mixture of different kinds of arithmetic units
that are sprinkled through the memory, evenly distributed
to prevent moving data around any more than you have to.
And of course, the big issue is not so much building
all these [INAUDIBLE],, but it's building a memory systems
to support them and has sufficient memory bandwidth
to keep them busy.
Of course, that works out very naturally
in a parallel machine, because you put each one of these LAUs
right next to its own little piece of memory,
and so you can read out 64,000 memory bits in parallel
and get a tremendous amount of memory bandwidth
to keep all these LAUs busy.
So it turns out that the peak floating point performance--
it's a good way of measuring it--
of the machine is on the order of something like 20
gigaflops, which is 20,000 megaflops, which
is millions of floating point operations per second.
So that's fast, but it's not-- that's not really
a very relevant number, because who cares
what the megaflop number is?
It's turns out that, if I look at this problem,
only about a third of the problem
is, in fact, doing that kind of operation.
What is the rest of the time spent doing?
Well, the rest of the time is spent
doing two other major things.
One of them is moving data around in communications,
and the other one is input/output-- things
like writing to disks.
So I guess one of the points that I'd like to make
is that, if you're going to achieve this kind of speed
up that the revised Amdahl's law promises,
you have to do all of the things that you
can do in parallel in parallel.
So if I only did the floating point operations in parallel,
then I'm going to get killed by Amdahl's again,
because I can only speed it up by 30%,
no matter how fast I can do those.
And in fact, one of the critical things that you have to do,
which is much harder than the floating point,
is the data motion, because it's all very nice for the hardware
designer to say I'm going to divide up
the memories into lots of little memories,
each which talk to their own processor,
but unfortunately, the algorithm doesn't work that way.
The algorithm-- data has to move all over,
and data here has to be added to data here, and so on.
So it goes in arbitrary patterns.
Now, sometimes those patterns have some locality
and some regularity.
So for example, if I solve the fluid flow problem over
the airplane by dividing up the space into a nice,
regular three-dimensional grid then,
that would work very nicely and neatly if I connect it up
my processors into a nice three-dimensional grid--
as long as it was the same shape as whatever
I wanted to solve for that particular airplane.
In fact, there's a lot of parallel machines
that work that way, and they work very well
on that class of problems.
The problem is that most of the algorithms are not that neat.
And in fact, if I take the implicit algorithms there,
where basically, I'm working with systems of equations which
have some communications patterns that
are kind of all their own, that are not--
don't map directly into this three-dimensional space.
Or for example, I might use an algorithm
called the free Lagrange method, where
I model each chunk of stuff as it flows around.
In effect, I'm re-drawing that grid
at every time cycle, dependent on where
the stuff is that's flowing.
And there, I really can't even decide beforehand
until I run the problem what my communications
pattern is going to be.
So I need a way of arbitrarily allowing
the processors to communicate.
And that turns out to be one of the most
difficult technical problems in the design of the machine.
And there's a lot of different ways of doing it,
but typically, what you do is you
build a physical interconnection network.
And on the CM2, the physical interconnection network
is every 16 processors is connected by a crossbar switch
so they can all talk to each other.
So that's a reasonable number.
And then every one of those clusters of 16 processors
is on the corner of a hypercube, and they all
talk to each other.
So that means they each have neighbors in hyperspace.
And it's a particular way of wiring them.
I won't stop and explain what a hypercube is.
It doesn't matter.
The point is the programmer never really knows
what a hypercube is.
And I might design it differently next year,
and you shouldn't care--
because basically, the hardware engineer
comes up with some neat wiring pattern
that they convinced themselves is the best in the world,
and then the programmer wants to see a model of totally
arbitrary communications.
So the programmer just wants to say,
this processor, get that memory location.
How do you do that?
Well, in the Connection Machine, the way that you do that
is, one, that physical pattern.
You have a bunch of autonomous switches
that root messages through that network.
And there's different ways of doing that.
One way is circuit switching, kind of like the telephone
system works, where you call up and you
establish a connection between two things that
want to talk to each other.
Another one is packet switching, like local area networks work,
where you put together a bunch of bits with an address on them
and steer them to the right place.
Well, it turns out that the Connection Machine
is sort of a combination of those two methods.
It actually send out little packets with addresses on them,
but it starts sending the beginning of them
before it's got the end of them.
So they sort of thread through the network like little snakes.
And in fact, sometimes the beginning of it
is actually being delivered before the end of it
has even been sent yet, so they're
sort of snaking through.
And that method of routing, which
is used in the Connection Machine
and several other machines these days,
is called wormhole routing.
And it's a solution that is a very neat solution for hardware
designers today.
Again, it's one of these things that probably won't matter
a few years from now as you get better ways of building
switching networks.
It may be that a few years from now,
for instance, we'll build things with optical technology,
and the messages will just jump from one part of the machine
to another.
But the trick is to be able to put in things like that
and provide the user with a level
of architectural abstraction so that they don't
need to know about the details.
So the programmer of the Connection Machine
doesn't know anything about wormhole routing, or packet
switching, or single-bit ALUs, and 64-bit ALUs, or even really
the number of processors that are on the machine.
There are levels of abstraction built into the machine, which
are the equivalent things, like virtual memory, which
provide the programmer with a much clearer model.
And part of the trick of being a computer architect
is to be able to put in all these kind of messy things
that take advantage of what technology you can buy in
a given year without providing that messiness at a level
that the programmer sees it--
so to be able to take advantage of the quirks of technology
without messing up the programmer's model.
So I think that the data parallel programming
model and the data parallel abstraction in the machine
is something that transcends various applications
of the machine.
So I don't think you should get too hung up
with the particular details of how the CM2 is implemented.
OK, I've talked about arithmetic,
memory bandwidth, I/O--
no, I haven't talked about I/O.
I/O is probably the most neglected part
of this equation, because fundamentally, most computer
designers kind of think of it as not their problem.
It' somebody else's.
The problem is that the users are not content just
to sit there and compute.
They want to write down the answer someplace.
They want to read in things to compete on.
And that means that the machine has to stop and talk
to some external device.
And typically, computer designers
treat that as kind of an afterthought about how
to deal with that, because they don't
know exactly what the device is going to be,
and it's very application-dependent,
and so on.
The problem is, in this kind of case,
where the I/O is actually increasing
with the size of the problem, that would kill you
if you took that attitude.
So you really have to think of I/O as an integral part
of the machine.
So just as you're distributing processing through there,
and just as you distribute communications--
that wormhole routing scheme is a way
of effectively distributing communications function
to the machine--
you have to distribute I/O. So I/O
has to come out of that machine, that square meter of silicon
all over it in order to get it out fast enough.
The problem isn't just getting out of the memory
fast enough or into the memory fast enough.
That's relatively easy, because you can just
use a lot of wires.
And in fact, the Connection Machine--
for example, the CM2 has eight I/O channels
of 100 megabytes each--
sounds like a lot of I/O. But what do you plug it into?
And I would love to just say, well,
that's somebody else's problem, but in fact,
when you start selling these machines--
becomes your problem, because the customer
needs to get it done fast.
So for that reason, we started solving the problem of building
our own peripheral devices--
and specifically, disk arrays.
And so in the Connection Machine,
for example, in every one of these I/O channels,
you use a parallel disk array, which does achieve speed
by doing a lot of slow things in parallel,
just like the machine does.
So you put 40 disk drives in parallel,
and all that goes on one I/O channel.
And when you write a 32-bit word,
you write the 32 data bits each to its independent disk drive,
and you write eight check bits--
you compute an error-correcting code
and write eight check bits to eight other drives.
Actually, you only need seven check bits.
The other one's a spare.
The advantage of those check bits
is that, when a driver crashes--
which, it inevitably does you still have all of the data,
because--
because you wrote this check bit,
you can reconstruct the entire data,
even though you're missing any one of the data bits.
And the advantage of it is you get a tremendously fast
transfer [INAUDIBLE].
When we designed that, I thought,
well, that'll be plenty to keep everybody happy--
40 disk drives at once-- but in fact,
very quickly, the customer said, we want faster.
So in fact, the CM2 today supports, in addition,
an idea of disk striping.
So in fact, you can run eight of these data vaults all at once.
And so you're using 320 disk drives
that you're writing out to at once.
And it's very clear, in another year or two,
they're not going to be happy with that either.
So the I/O problem becomes part of the problem
that you have to solve, whether you want to or not.
And it becomes one of the biggest bottleneck
problems in designing a very large-scale computer.
And I'm just touching on the bandwidth issues of it.
There's a lot of other issues as to how
it fits into the operating system,
and protection, and error tolerance,
and things like that.
So I talked about arithmetic, communication, input/output.
What about control?
That's the SIMD/MIMD issue.
It turns out that, if I look at the control
portions of the program, they don't
grow with the amount of data.
In other words, they remain relatively fixed
as the problem size increases.
So that means that the control portions of the program
are really down in the sequential part.
They're not in this parallel part,
which means that there's really no need
to be able to handle those in parallel-- for the most part.
It helps a little bit [INAUDIBLE] in places,
but for the most part, it's not like the control explodes,
because the control is basically dependent on how
long your program is.
And the program doesn't get longer just because you
had more data to operate on.
So that allows the hardware designer
to get some efficiencies by taking advantage of that shared
control.
So the reason that I think that SIMD machines are
the most efficient machines in 1989,
1990 time frame is because the cost
of distributing that control and putting it out is too high.
It becomes too high a cost.
And it's much cheaper to do that control in one place
and distribute out the information to the places
where it's needed, because you really
are only running one program.
Now, that doesn't mean that that's the only way
to support the data parallel programming model, though.
And if, in the future, [? at ?] [? some ?] [? times, ?] you
begin to get more and more of the costs of the machine is
in the communications, rather than in the silicon--
because silicon's getting cheaper every year,
so it may be after a while that the piece of wire to send
the data is much more expensive than just putting a whole other
computer at the other end of the wire.
At that point, I think it'll make sense
to implement the data parallel programming
model by putting more control out at the [INAUDIBLE]..
And in fact, the CM2 adopts a kind of compromised approach.
It actually has four streams in instructions
to go through that.
So I think that's really the SIMD/MIMD issue.
I don't think it's a philosophical issue.
And I think, in any case, even if you had all this control
out there, you really still want to present to the user
the model of a single thread of control,
because their parallelism is, in fact, not in the control.
Their parallelism is in the data.
So that's the control issue.
So my conclusion from all of that
is, to achieve a balanced design, what you need to do
is make sure that all of the parts that
can be done in parallel are done in parallel in the hardware.
That means, specifically, you have to do processing,
you have to do communication, and you
have to do I/O in parallel.
And control you get to do whatever way you think
is cheapest.
It's just a matter of efficiency.
So all of that sort of theories about designing
this kind of machine-- how well does it actually
work out in practice?
Well, for many problems today, the Connection Machine
is the fastest machine in the world.
And it depends on if the problem is of this sort.
There are also many problems for which
it's not the fastest in the world--
probably many problems for which a [? Cray ?] is the fastest.
But an interesting question is, on the fastest problems
and the biggest problems, what's the fastest
machine in the world?
And the answer is the Connection Machine.
Gordon Bell was kind enough to hold a contest where
what you did is you clocked machines
on doing any real problem, a real application,
to see how fast they were-- how many floating point operations
per second.
And the Connection Machine won that--
the prize this year by a large margin.
And in fact, another Connection Machine program came in second
and won the cost performance prize.
So it's clear that, for the biggest problems and the most
data-intensive problems, this kind of machine
is the fastest right now.
So now, what about for the future?
How is it going to compare to the competition, which
is, by the way, vector machines, like Crays?
Well, if you look at the basic technologies that
are in the Connection Machine, they're
basically technologies that are improving
in cost performance by a factor of two or three
every two years.
If you look at the technologies that
are in the vector machines, which are things like bipolar
integrated circuits, high-performance cooling
technologies, their improvement in cost performance,
while substantial, is more like a factor of two
every two years.
So it's not as fast.
So I'm convinced that not only are these data parallel
machines fastest today, but as we look out in the future,
they become more and more the fastest machines.
So somebody who has a pile of money, like $30 million or $100
million make it up, will always do much better
if they're solving a big problem to spend that on a data
parallel machine because of this increasing spread in the cost
performance of the components.
So I think the future of these machines
looks extremely bright.
And in fact, I believe that, over the next few years,
we'll see machines of this sort--
commercial machines of the sort that are performing regularly
in the 100 gigaflop range.
Today they perform in the 5 gigaflop range,
maybe getting up to the 10 gigaflop range.
But I think that we'll see on good problems performing at 100
gigaflops in a few years--
and by the mid-1990s, I think that we'll
be talking teraflops.
And that's trillions of floating point operations per second.
That's a factor of 1,000 over what
you do on a conventional supercomputer today.
And so I don't think we yet comprehend how to use it,
[? but a ?] factor of 1,000-- one level sounds like an awful
lot, but then, if I've got one of these problems that grows
like n cubed, that's really only less than--
that's only a factor of 10 for a problem like that.
And if it [INAUDIBLE] only a factor of about five
or something like that.
So if I went five times the resolution,
I really want to look at turbulence.
I can use up that factor of 1,000 very fast.
Or if I want a more accurate model of how a molecule falls,
or if I want to really understand
how that spiral arm of the galaxy forms,
there's lots and lots of problems
that use that up very quickly.
And in fact, we're beginning to get hints
that we'll be able to begin approaching some
of the problems in artificial intelligence
that I originally was interested in quite a few years ago,
when I started getting interested
in this type of machine.
So we're beginning to see the light at the end of the tunnel,
that we can get machines that are really fast enough approach
these problems.
So it looks like it's going to be an interesting decade.
So let me summarize.
The conventional Von Neumann machine,
the [? word ?] [? at ?] [? a ?] [? time ?] machine,
is fundamentally inefficient for very,
very large-scale problems, and it becomes more inefficient
as the problem grows greater because of this Von Neumann
bottleneck.
The natural solution is to distribute processing
through the machine.
In order to maintain a balanced design,
we have to distribute not only processing,
but we have to distribute I/O and communications so that we
can do all of it in parallel.
If we do that, then, for the biggest problems,
we'll be able to do arbitrary amounts of it in parallel.
So we'll be able to get very, very good speedups.
In fact, we can always pick a version of the problems
big enough so that we can get them--
we have enough parallelism to keep it busy.
And finally, the result of all of this
is that data parallel machines today
are, in fact, the fastest computers in the world
for a class of problems.
And it looks like that's becoming more and more
true in the future.
So in conclusion, I'd like to say
that I think this is the natural solution to very
large problems, and I hope I've convinced you all of it is too.
Thank you very much.
I'm Frank Morris from Pennie and Edmonds New York City.
Can you explain to us what advances
you foresee in the next few years that will enable you
to increase the performance of the Connection Machine
from about 10 gigaflops to a teraflop?
Yeah.
I'll speak in very general terms,
because obviously, we're getting into what
we're developing in some of our next products here.
But fundamentally, there are three sources
of speed improvement in the machine.
One of them is that the basic technology in the machine
is improving.
So that's that factor of two or three
a year I was talking about.
As we fit more and more onto a VLSI chip,
we can get things closer together,
actually operate them faster.
Clock speeds become faster.
Data paths become lighter for the same cost.
So there's some things that, in a sense,
come for you for free just from the technology.
Another big source of--
is that we understand much more of what we're doing now.
So we now have a lot of machines out in the field--
probably about 10% or 20% of the supercomputers
that are out there right now are Connection Machines,
and so we're beginning to get a lot of experience
and how users actually use the machine
and how the machine works in certain cases, where
it doesn't work, where the time is being spent, and so on.
So another big source is optimizing the machine,
because we now know what to optimize for.
And we were kind of shooting in the dark for the first time
around.
There's probably almost an order of magnitude
to be gained by that.
And then the other source of improvement in speed
is just plain we'll build machines bigger.
And when we first built the Connection Machine, $5 million
seemed like a lot to solve one of these problems,
but in fact, these days people are
used to spending as much as $20 or $30 million
for a very, very large computer.
And so you can just plain old build bigger machines,
and that's another source of the power.
So if you multiply all of those together,
it really is very plausible to get to that teraflops number
in the mid-'90s.
How much bigger do you see the machines becoming?
I believe that, with the way that we understand designing
machines now, we can see the next factor of 100
after the teraflop.
So the designs change.
The way that you build the communication networks change.
The way that you build the processing elements change.
But fundamentally, I think the same kind of architecture
and the same kind of model presented to the user
will follow through for that kind of speed improvement.
We're talking over the next decade, really, for that.
After that, I think even that model begins to fall apart,
and it needs something else to come along-- some other way
of thinking about the problem.
Users will have to change all of their programs
to get beyond the--
I don't even know what's after a teraflop,
but I'm not going to worry about it.
I'm worrying about up to about 100.
I'm [INAUDIBLE] Howard University in Washington DC.
Thanks for your presentation, especially as
you addressed the problem of time saving
for large computation problems.
For some of the activities in numerical analysis,
we spend a lot of time in I/Os.
And I'm looking forward to hear from you what your thoughts are
in terms of making the I/O devices more intelligent.
Certainly, people have been talking about,
for years, putting processors down into the I/O devices,
in the same sense that, in a data parallel machine,
you put the processors into the memory.
I question in a parallel machine how much is really
to be gained from that, because the limitation is really
not the data motion between the I/O device
and the memory of the machine in a parallel machine.
It's easy to build I/O channels to keep up with that capacity.
The limitation really is much more in the physical storage
medium itself of the I/O device.
So today, even the very, very fastest,
very most sophisticated computer still use the Stone Age
technology of disks spinning around,
and that's the thing that's really going to have to change,
and what's the technology that's going
to replace that is kind of the $64,000 question.
Optical technology is mostly--
what's out there now is still disks spinning around.
You're writing things on it with optics, instead of
with magnetics, but it's still that kind of mechanical motion
determines the speed of the system.
I think we're eventually going to have to get away from that.
Some of the possibilities are things
like storing three-dimensionally in crystal lattices.
Magnetic bubbles is another thing people have talked about.
None of them seem really quite there enough
to be able to predict them, but it's clear
that we're going to need something like that.
I know that, when you do error analysis
on serial machine in terms of different outputs, you have--
[INAUDIBLE] to compare the advantage
in terms of troubleshooting program [INAUDIBLE]
in parallel processing, more or less [? architecture. ?]
OK.
Fundamentally, writing a program on a data parallel machine
is no more difficult than writing a program
on a sequential machine, because you only
have one thread of control.
So you don't have to worry about issues like synchronization
or data consistency between processes and things like that.
It's things like that, where you have
multiple threads of control, that
makes some kinds of parallel programming very difficult.
But debugging a data parallel program
is really very much like debugging a sequential program,
and uses essentially the same tools.
Now, of course, if the program's doing the wrong thing,
then it can do the wrong thing a lot faster,
so it can make a lot more mistakes,
but the truth of the matter is that it can already
make mistakes a lot faster than you can keep up with it anyway.
So that difference really doesn't make a difference.
Now, that's to do with software errors.
Another question, which you might have been asking,
is about hardware errors.
And one topic that I neglected in the talk, which
is a very big issue for designing these machines,
is the problem of fault tolerance.
And in fact, the machines that we're
designing in the future all have very high degree
of fault tolerance, so that one part of the hardware can break
and the program continues running, and runs--
the user sees no error, even though the hardware--
the individual hardware elements are making errors.
And that becomes a necessity when you design very, very
large-scale machines.
And that will become increasingly a problem
in designing machines, and increasingly
a place for architectural creativity.
I'm Mark Tuttle from the [INAUDIBLE] Lab.
I felt, during the talk, you were
trying to convince me that the data parallel model was
the best and most natural model for parallel computation,
and I'd like to press you on that a little more.
It seems like, in discrediting the other models,
you're taking a lot of--
you're taking advantage of the parallelism that's inherent--
the data parallelism that's inherent in the data
that you're using, like the airflow
over the wing and stuff like that.
But it seems like there are a lot of problems where that's
not really the case, like chasing links
through a semantic net, where you can, of course, formulate
that is taking the transitive closure of a graph.
And I just wanted to ask you about that.
Well, I certainly believe that other kinds of parallelism
are legitimate and useful.
The problem with most kinds of parallelism
based on control flow is that they
don't get you the factors of tens of thousands
or hundreds of thousands that you
need to really do these very, very large-scale problems.
So I guess I feel that data parallelism is
the only way that you'll get the speed in very, very
large problems.
And in fact, the problems that you mentioned,
which were database query, computing
the transitive closure of a graph,
are very, very natural expressions
in data parallel algorithms, and in fact, work very,
very well on a machine like this when the problem is large.
So it's not that I think that the other kinds of problems
are no good.
In fact, I think they're very good.
I think multitasking, forking parallelism
is very useful in many cases.
I think pipelining is useful in many cases.
I think that those make a lot of sense,
but they're not going to get you the factors of hundreds
of thousands, so they're really not what
you have to focus on when designing a machine that's
going to operate in that performance range.
It sounds like you're talking about--
that's an argument that the architecture that you're
interested in is a superior architecture,
because you can make these chips small enough
that you can make these machines much, much bigger.
It's more cost effective to make these kinds of machines bigger,
but that doesn't seem like it's a convincing argument
that the model--
the programming model itself is the most natural model.
Well, maybe a more--
better way to convince you that the programming model is
the right model is to say that even somebody who
builds hardware for a completely different model
almost always ends up programming it
in the data parallel model.
So typically, if you have a machine that
has more than a few dozen processors, even if it wasn't
designed to support the data parallel programming model,
you'll see that the way that people program that machine
is to sort of make that machine pretend like it's
a data parallel machine.
And in fact, they only write one program,
and they run it all on all the processors at once.
So they hide all of that flexibility
that they put into the architecture,
because they don't know how to deal with [INAUDIBLE] software.
So I think that's a very convincing argument
that this is the most natural way of expressing
those algorithms.
I'm Karen Matthews from UVC, but Danny,
this question is from [? Gordon ?] [? Bell. ?] To
what extent can we expect a language for expressing
parallel computation to span a range of types of machines
so that programmers don't have to be retrained?
I think that it's realistic for programming languages
that support machines with roughly the same numbers
of processors to have the same kind of programming language.
So I believe that all machines with tens of thousands
of processors will be programmed in the same way
by exactly the same programming languages.
I believe that machines that have dozens of processors
will be programmed in a pretty different way, because there it
makes sense to use this kind of fork joint kind of parallelism.
And it may be that there are some intermediate stages where
machines with a few processors can be programmed in a message
passing way, but I think that all machines that are massively
parallel will run exactly the same programming languages.
And interestingly enough, they're
probably the same programming languages
that the sequential machines will run,
and that was a big surprise to me.
[MUSIC PLAYING]