[MUSIC PLAYING]
To perform a task in parallel is to have
multiple entities working together toward a single goal.
Likewise, parallel computing is the use of multiple processors
together in a single machine to solve a single problem.
Vital application areas, which would immediately
benefit from the availability of parallel computing devices,
include superconductor physics, atmospheric research,
weather modeling, defense, astronomy, genetics,
oil exploration, and aerospace.
Such machines could improve current computational
capabilities by several orders of magnitude.
However, today's parallel processors
remain in the domain of sophisticated specialists
and are extremely difficult to use
by scientists and engineers who want
to solve routine yet time-consuming problems.
The ultimate challenge is to bring parallel computing
into the mainstream.
The MONSOON Project is rising to meet this challenge.
MONSOON is a joint research effort
by the Motorola Computer Group in Cambridge, Massachusetts
and Tempe Arizona and the Massachusetts
Institute of Technology Laboratory for Computer
Science.
The project is funded by DARPA and Motorola.
The goal of the project is to demonstrate the feasibility
of dataflow multiple processors using implicitly
parallel programming languages.
Professor Arvind of MIT'S Laboratory for Computer Science
computation structures group and a leader in the dataflow
research effort.
Why is it that we don't have more parallel machines?
The economics of it is not in the way.
I think there is a fairly strong agreement
that software is the problem to making parallel systems more
readily available.
Small multiprocessors available today
have had economic success, only limited application areas.
Applications with each processor can be dedicated easily
to a specific task.
However, such machines can't be exploited
from volumes of software available on uniprocessors.
This says something about the state of languages in use
and the compilers in use.
So users have to resort to some sort
of explicit parallel programming to get the job done.
It turns out that explicit parallel programming
is quite difficult. People are reluctant to do it
not only because it's difficult, because there
is no guarantee of portability.
It's not clear if program you have
put some effort into making parallel
will port to a machine with more processors,
or somebody else's machine, or for that matter,
even to the next generation of the same machine.
And all of this puts a big damper
on trying to parallelize a program.
Dr. Ken Traub of the Motorola Cambridge Research Center.
Another kind of problem with explicit parallel programming,
which is even more serious, is that these kinds of programs
don't have very good compositionality properties.
We're used to writing subroutines,
and then calling subroutines from all
over the place having subroutine libraries, and so on.
But any experienced program will tell you,
that when you're working with parallel subroutine libraries,
you can't count on how well they'll work
under different circumstances.
And this is especially true of the data parallel model.
If you look at the other extreme, which is massively
parallel machines, it's obvious that there is some success.
We read about these machines in newspapers all the time.
People are actually using these machines
to solve some very important problems.
This is in spite of extreme difficulty in programming
massively parallel machines.
Right now, these machines are being used to solve problems
which cannot be solved any other way.
Working on parallel machines has its own sex appeal.
The difficulty becomes the challenge.
But the point is, if parallel machines remain
so difficult to program, then it's
obvious that they will remain on the fringes.
They can never become mainline computing engines
that we use every day in our offices, in our homes.
So the key issue here is the ease
of programming and the languages we
use to program these machines.
Computer languages play a pivotal role
in the degree to which the parallelism of a problem
is exposed or obscured.
To illustrate, consider the following simple problem,
known as "wavefront."
The problem is to construct an n by n matrix, such
that the top row and leftmost column contain 1s,
and each of the other elements in the matrix
is defined in terms of its neighbors to the north
and west as shown.
It is not difficult to see that after the elements in one
diagonal have been computed, the elements
in the following diagonal can be computed in parallel,
and so on, until the matrix is full.
The number of operations that can be performed simultaneously
at each time step is displayed by a graph,
called a parallelism profile.
Clearly, the number of operations
that can be performed in parallel increases
until the middle diagonal is computed and then decreases.
Now, consider this Fortran program to solve wavefront.
It consists of an initialization step,
doubling [? S ?] to-do loops, and the computation
for each element X, I, J. The semantics of Fortran
dictates the precise order in which
the elements of the matrix are computed, namely,
top row to bottom row and left to right in each row.
The difficulty of performing the required analysis
to determine what can be done in parallel,
even for this simple program, is beyond the capability of almost
all commercial compilers.
Let's examine the steps we have taken to execute the Fortran
wavefront program in parallel.
We have started out with a specification
of a problem in which the parallelism is evident, encoded
it in a sequential language, Fortran in this case,
and then are forced to rely on a sophisticated compiler
to produce parallel code from the sequential program.
It seems to me to be far more effective to use
a language in which we can encode are algorithms, such
that the parallelism in the original problem
is not obscured, but is actually preserved by the code.
The language Id, developed by Professor Arvind
and his colleagues, is such a language.
As an example, here is an Id program for wavefront.
First, the dimensions of the matrix are defined.
Then the boundary elements of the matrix
are defined as well as the remaining elements.
Note, that this is a declarative specification of the problem.
Nothing is implied about the order of computation,
so that whatever can be computed in parallel,
subject to data dependencies, will be computed in parallel.
To illustrate the value of compositionality,
consider an extension of wavefront
in which the value of element X, I,
J is a function of neighbors to the north and west
and its own previous value.
This is to be iterated multiple times.
At first glance, the parallelism profile of this program
would appear to be that of a series of wavefronts laid end
to end.
This would be the parallelism obtained in Fortran
by simply composing the earlier program in a loop.
However, the parallelism that is actually
present in this problem is far greater
than what might be expected, leading to a much
shorter execution time.
This parallelism profile is what is
obtained in Id when the original Id
program is enclosed in a loop.
Plus the power of implicit parallel programming
leads to programs which are both high level
and exhibit a degree of parallelism, which
would be almost unthinkable to express
in languages like Fortran.
I believe that implicit parallel programming
will be able to jump over the final hurdle
to make parallel machines really commonplace.
It can bring down the programming difficulty
to a level where users would as happily program
parallel machines as they would program sequential machines.
Compilers for implicitly parallel languages, such as Id,
are likely to generate a multitude of threads
of computation, reflecting the large amounts of parallelism
which can be exposed in programs.
Therefore, it is essential that the hardware architecture
for the system be designed with this in mind.
[MUSIC PLAYING]
In the MONSOON architecture, the state of the computation
is represented as a tree of activation frames, which
are similar to stack frames in conventional machines.
However, instead of only having the most recent frame
active at any time, in the MONSOON architecture,
multiple procedures are active simultaneously.
In addition, the control state is virtualized,
so that within activation frames are
multiple threads of control, which
may be simultaneously active.
In any machine architecture which
supports a parallel model of computation,
there are certain fundamental issues
which must be addressed in order to achieve efficient process
or utilization.
The first of these issues is memory latency.
Let's look at a computing node in any multinode system.
There is a processor component with an on-chip memory
cache, typically some local memory,
and an interface to the communication network.
A reference by a processor to local memory
may be five times slower than a reference which hits
the processor's local cache.
And even in a well-designed machine,
the latency incurred by a reference
to a different node in the machine may be many times
slower yet.
Professor Greg Papadopoulos of MIT's computation structures
group.
When you're looking at how you're going to run programs
on this machine, you have to ask yourself the question,
how often am I going to require communication
with another node?
And what will the penalty of such communication be?
For example, will I just sit there, and wait,
and idle while I wait for the response
to request that I'm given?
Or can I be more creative and do something else--
try to amortize or minimize the latency?
One natural way to tolerate communication
latency is to issue many remote requests into the network.
Although each request experiences the latency
of the network, the processor which originates the requests
is kept busy by the multiple responses,
which ultimately return.
In order to successfully generate
sufficient remote memory requests to keep
the communication network full and the processor busy,
there must be sufficient parallelism available,
and the processor must also be able to perform
rapid context switching across multiple threads of control,
each of which can generate requests into the network.
Remote requests, which are made by a processor,
will produce responses which return in a different order
than they were issued.
To impose an ordering requirement on the network
is practically unmanageable.
Well, as they say, talk is cheap.
It's listening that's an art.
It's easy if you assume that you have
lots of threads to generate as many outgoing messages
as you want.
The really hard part is, when you
think about a message coming back in the processor,
how are you going to relate it to the waiting
threads of control?
And is this really the only datum
that's required to continue the computation?
In order to relate a response to a waiting
activity within a processor, the processor
must have the ability to perform efficient synchronization.
In general, multiple responses may be
required to activate a thread.
What's interesting is that if you just
tackle this latency problem, you end up
with a machine that looks like this.
You would imagine a few contacts that you could rapidly
switch among in each processor, and then some synchronization
capabilities in the memory.
But that hardware in and of itself
doesn't quite get you to the point that's
expected by the compiler.
And the key difference is, while the machine needs
only enough context to keep the communication network filled,
the compiler must be able to name
enough activities in the machine to support the fully
parallel model.
So the dataflow approach is, rather
than buying the number of threads
that we can name at a time to physical resources,
like the number of registers in a processor,
we instead virtualize this and come up with a very lightweight
multithreaded model.
So threads in MONSOON look like these lightweight computation
descriptors, which we can switch amongst very rapidly.
In fact, on any processor, there can
be thousands of thread descriptors awaiting execution
at any given time.
The thread descriptors consist of a pointer
to an instruction in memory, a pointer to the activation frame
the thread is associated with, and a few registers.
Two independent thread descriptors
may synchronize by using the presence bits found
on every word of frame memory.
So the hardware design of MONSOON
emphasizes very rapid switching across threads.
In fact, it is possible to join two threads of computation
with one cycle of overhead, and a new thread
can be formed from a currently executing thread
with zero cycles of overhead.
To summarize, the MONSOON approach to parallel processing
brings together and implicitly parallel programming language,
Id, which preserves the parallelism which
is present in algorithms, and an architecture which supports
the compiling model for the language,
as well as addressing the fundamental problems
of latency and synchronization.
Certainly, we oftentimes write programs
where we don't know where the parallelism is,
but the gut feeling is there must be some.
The original algorithm for these codes,
even though no intention may have been paid to parallelism,
perhaps do have sufficient parallelism.
If you just took the same algorithm
and included it in Id, there is a good chance
that you would give significant speedups of your program,
regardless of how unstructured the code is.
The rule of Id, or implicit parallel programming,
is to make sure that the good properties, the parallelism
of your algorithm, is not obscured, that language is not
in the way.
So the role of the machine has got
to be to efficiently exploit all sorts of parallelism,
which are exposed by these wonderful languages.
It seems to me that the sky is the limit.
[MUSIC PLAYING]