Today, I want to talk about the DASH project with you
and our research at Stanford involved
in the building of scalable shared memory machines.
We'll start by talking about some of the general challenges
as well as some of the advantages
of a scalable shared memory machine
And then in the second half of the talk
move into actually discussing the dash
architecture and the concepts behind that architecture.
Before starting, let's discuss a little bit the goals
in designing a parallel machine.
I think probably the first goal is the obvious one, namely
one with high performance out of a parallel machine, faster
than available unit processors.
Second goal, which we think is quite important,
is that the cost performance of a multiprocessor
be competitive with the cost performance of workstations
that use the microprocessor technology available.
Obviously, scalability has been something
that people in parallel processing
have talked about extensively and one
would like to have scalable performance
in a multiprocessor, as well as scalable cost performance.
Finally, a goal that we've considered very important
in our research is to design machines,
which are general-purpose, which have wide applicability
to a range of applications.
We think each one of these points
is important in trying to make parallel processors
pervasive in getting to the point where
we all as a computing community choose
to use parallel processors because they're
a better and faster way to solve our problems.
The term scalability has been used
to mean a whole variety of things.
And I think it's helpful to mention
what some of those definitions are
and to say what we mean by scalability.
One definition of scalability is what I would
call an impractical definition.
It states that scalability is either speed-up
on a constant size problem across a range of machines
or even speed-up on scale problems,
which for practical machines, machines that can be
implemented, is unattainable.
A second definition for scalability
would be realistic in the sense that we could asymptotically
approach that performance but might disregard cost
and might disregard constant factors, which
in practice would make the machine perhaps
scalable but uninteresting from a cost viewpoint.
What we mean by scalability, and the definition
we've used in our project, is a very pragmatic definition
of scalability.
Our interest is in good speed-up and good scalable
cost across a range of parameters for a machine.
In particular, what I'm going to talk about today, or I do,
which are interesting in the range of tens
to low thousands of processors.
What's required to build a scalable multiprocessor?
Well, obviously, we must scale both bandwidth
and do something about the scaling of latency.
We'll return to this topic of latency shortly.
Let's just focus on bandwidth for now.
When we say we must scale bandwidth,
that means that we have to be able to scale the local memory
bandwidth, the bandwidth that each processor demands
linearly, and we also have to have a way
to scale the communication bandwidth between processors
as we scale the size of the machine.
An important observation is that scaling
the memory bandwidth requires the use of physically
distributed memories.
It's inherent.
There's no cost-efficient way to scale up a machine
and scale up the memory bandwidth without physically
distributing the memory.
I also want to point out that if you
want to achieve scalable cost performance,
you've got to take advantage of the best price performance
available in processors.
That means using state of the art microprocessors,
and I think we can see this trend evidenced
in various recently announced machines-- the CM5,
for example, that chose to use off-the-shelf microprocessor
rather than build a custom processor for the machine.
Once one has decided to use a distributed
memory, a physically distributed memory,
there are two interesting architectural alternatives.
One is a message-passing machine, where the memories are
private, and communication between processors
is done by explicitly passing messages.
A second alternative, and the one
we're going to discuss in some detail in this talk,
is a machine that has physically separated memories
but has a single address space across all those memories.
It's important to observe that either approach requires
you to deal with locality of access.
Because the memories are physically distributed,
people have to pay attention-- programmers have
to pay attention to the locality of access.
Both these approaches also require
a scalable interconnection technology,
which allows us to scale up the bandwidth
between the processors.
Given that, why do we find a single address-based approach
attractive?
Well, there are both functional and performance advantages.
The functional advantages-- one of the most important
is that a single address space is easier to program in
and easier to build compilers for.
It's easier to program for because it's a better
understood programming model, and it's easier
to build compilers for it because the compilers
can treat the single address space and the memory--
the physical, distributed memory as an optimization problem.
There's also, as we'll see in this talk, the opportunity
to create an incremental program development methodology whereby
a programmer can relatively easily port
a program to this machine and can regard
the process of enhancing performance
as an incremental process whereby the issues of locality
of access are addressed as an optimization problem--
a performance enhancement problem,
as opposed to a correctness or fundamental problem getting
the program working.
With a little bit of hardware help,
a single address-based machine can also
efficiently simulate other models.
There are also performance advantages
associated with a single address space approach.
One of the most important of these
is that small data objects can be communicated
more efficiently between processors,
and that's because that communication is
integrated in the memory model.
A second advantage is that it's easier to exploit caching,
and we'll see that this is the backbone of much of the work
that we've done at Stanford.
As one scales up the machine size,
the latency to access remote memories increases.
This increase is unavoidable.
For example, if we were to look at how that latency scales up
in machines today, we'd see as typical numbers the local cash
access time might typically on a processor today take one cycle.
Accessing local memory might take anywhere
from 10 to 40 cycles.
Accessing a remote memory having to go across an interconnection
network might take anywhere from 50 to 200 cycles.
And remote access that might have to actually require
trapping to the operating system or some other software library
might take as many as 1,000, or in fact, up to 10,000 cycles.
This remote access time scaling is unavoidable
if we want to allow the machine to scale up
to large numbers of processors.
How do we deal with this long latency?
There are three fundamental ways in which we can deal with it.
The first is we can lower the frequency of long latency
events.
By using better parallel algorithms
or better implementations of parallel algorithms,
we can actually have the programmer lower
the frequency of long latency events
and thereby improve the performance of a program.
A second approach is to try to reduce the latency by the use
of hardware techniques.
For example, we try and make the access to remote objects
cheaper.
A third approach is to tolerate latency,
that is find some way to overlap computation and communication
so that the impact of latency on performance is minimized.
Let's talk about reducing latency.
One of the most important methods
for trying to reduce latency is to eliminate the long latency
accesses by the use of caching.
Caching is a time-honored idea that
has been used in architecture for a long time
and been extremely useful in trying to reduce latency.
When we introduce caching, we can introduce it
either as a hardware technique or as a software technique.
And, of course, the static versus dynamic behavior
of the application affects the suitability
of using a software technique, which
might be more appropriate in a static environment,
or a hardware technique, which might
be more appropriate in a dynamic environment.
We can also reduce the communication latency
by the use of low latency, high bandwidth protocols, those
who both avoid contention and reduce latency.
This is an area where there's been dramatic progress
and where it appears that there will
continue to be important progress in interconnection
networks.
As we said earlier, we can also tolerate latency.
One obvious way to tolerate latency
is in a message-passing machine, where
the programmer has the task of overlapping
computation and communication.
Another way to tolerate latency is
by changing the memory model.
The memory model specifies when a processor can continue
after doing a load or a store, for example,
and when it can assume that access is completed.
By relaxing the memory model, we allow the processor
to continue earlier, allowing it to ignore
the fact that a store, for example,
may take quite a long time to propagate
across an entire machine.
Two other ways to tolerate latency
are through prefetching and multiple context.
In prefetching the program or the compiler actually
inserts instructions into the program,
which have the effect of bringing data
from a remote location to a nearby location,
thereby reducing its access time.
In multiple contexts we actually designed the machine
so that when a long latency event occurs,
the processor contexts switch to another thread of execution,
thereby overlapping that long latency
event with the other thread of execution.
It's important to observe that all latency tolerating
techniques require extra parallelism to be
available in the program because they
overlap these long latency events
with that extra parallelism.
They also generate extra bandwidth demands
on the machine by doing prefetching or multiple
contexts, we increase the bandwidth
demands that the process requires
on that particular program.
Let's return to the topic of caching and cache coherency.
There are several alternatives we
could look at in a single address space with respect
to the use of caching and whether or not
the caches should be kept coherent
with hardware assistance.
One approach would be to say, let's not cache share data,
and as we'll see that will make the accesses
to remote data very expensive.
A second related alternative is that we cache share data
but under software control.
In that case, we're limited by the ability of the software
to do the job perfectly.
By that we mean that if the software cannot be certain that
it can cache a local copy and still retain a consistent
programming model and a consistent memory model
for the programmer, then the software must be conservative,
must not choose to make a cache copy,
and must use the remote copy.
And that becomes the limiting factor
in trying to cache in software.
What would an architecture with private caches
that did not attempt to cache share data look like?
Well, that architecture might well have caches,
but the caches would contain only private data therefore
accesses to remote data would have
to go through the caches over the interconnection network
and to the remote memory.
Some examples of these kinds of machines
are the IBM RP3 and the BBM Butterfly.
These machines feature, as we see here, a distributed memory,
and they even use caches.
There's also a single address space across this distributed
memories.
They also need to make use of a scalable interconnection
network.
This slide shows why this approach
runs into difficulties.
The frequency of shared accesses--
that is, what percentage of the memory accesses
made by the processor are to share data--
is quite large, often in the range of 35% to 40%
of the accesses made by the program.
That means, for example, in a machine
with caches that cache only private data, that 35% to 40%
of the memory accesses are going to take
on the order of 100 cycles.
Obviously, the penalty for this and the effect on speed-up
would be quite dramatic.
Now, there's actually good news in these sorts of measurements.
And one element of good news is that the shared read frequency
tends to be much higher than the shared right frequency.
That's good news because from the point
of view of a cache designer, that means the caching will
probably work quite well.
So, a third alternative to designing a machine
with a single address space is to design cache coherency
into the hardware.
The key question is, can that cache mechanism--
can that coherency mechanism-- be made to scale?
This chart shows how conventional cache coherency
has traditionally been implemented using what's
typically called a Snoopy Bus.
In this scheme the processors are
connected onto the single bus.
When a cache miss occurs, that miss is placed on the bus,
and the cache is snooped to try to determine whether or not
they might contain the data required by the processor.
If one of those caches contains the data,
then it places the data on the bus
and the processor, which generated
the initial cache miss, finds the data present there.
When a processor writes a shared data item,
that data item is placed on the bus, the address of that data
item, and an invalidation is generated on the bus
so that the copies of the data resident in the other caches
are eliminated by that validation.
A good way to think about this is
that what a Snoopy Bus protocol presents
is a solution to the multiple readers single writer problem.
We allow multiple people to read and copy
the data item into their cache.
When we want to write the data item,
we invalidate all those caches so
that there's only a single copy that
can be written and updated.
Now, if we try and ask what's the problem
with a snoopy-based protocol, the major problem
is that when a cache miss occurs,
we must broadcast that address on the bus
and require all the caches to snoop
to see whether or not they have that particular address.
An important observation here is that this
is an inherent feature of this protocol.
It is not a property that can be eliminated
just by making the bus faster or by even putting two buses in.
Because the limitation that will occur
will be that the bandwidth of the caches that
is used for snooping will quickly saturate.
And therefore, we can't extend the machine purely
by increasing the amount of bus family.
Let me talk about an alternative to this snoopy-based approach
that enables us to have a cache coherency
scheme that will scale.
This alternative is a cash coherency scheme
called directories.
In a directory-based scheme we have an object
called a directory, which keeps track of all the shared
copies of a data item.
It keeps track of it with the use of presence bits, which
denote which caches have a shared
copy of a particular block or line in the cache.
Each block and memory has a corresponding line
in the directory, which keeps track
of that particular block of memory
and which caches have a copy.
There's also a dirty bit to indicate
when the single copy is the only copy of a particular block
anywhere in the machine.
So one of two situations exists.
Either there are one or more presence bits
on indicating if there's more than one
that the copy is shared by multiple readers
and exists in multiple caches, or the dirty bit is on,
and there is a single copy with one presence bit indicating
the location of that copy.
Now, how do these directories maintain coherency?
Well, the next two slides will tell us about that.
When a location is red, the reader--
the processor doing the reading--
causes the directory to be updated to indicate
that that processor has a copy of that particular cache line.
That basically tracks the readers.
Then, when a location is written,
the directory does two things.
First, it grants ownership to the writer,
that is, it determines which of all the
processes that they want to write get priority in trying
to write this data item.
It grants the ownership, and then using the presence bits
contained in the directory, it causes
the other copies to be invalidated and eliminated
from the cache.
The advantages of this approach are
that it has no unnecessary broadcasts,
and it imposes no restrictions on the topology or the ordering
of messages sent around the interconnection network.
Directory schemes actually predate snoopy-based schemes,
but they were passed over.
They were passed over because the Snoopy schemes are simpler
and because for most multiprocessors built,
scaling hasn't been an issue.
People have been interested in smaller scale multiprocessors.
In order to explore larger scale machines with cache coherency
directories and the interest in directories has been revived.
In order to scale these directories,
two important things have to be done.
One is that we have to distribute
the directories with the memories, that is,
when we have multiple memories, we
have to have multiple corresponding directories.
If we didn't, then the single directory in the machine
would become the bottleneck, and it
would be no different from then having
a single memory in the machine.
We also have to use a scalable directory scheme, one
that allows the total size of the machine and processor
count and memory to scale up without making
the directory overly costly.
I'm not going to talk about scalable directory
schemes in detail in this talk, although there
are several papers that have been written on this topic.
These distributed directory protocols
have now been adopted by a wide variety
of machines looking at trying to build scalable cache coherency.
The Stanford machine that we're talking about is one of these.
But the scalable coherent interface
is another example that's proposed as an IEEE standard
for interconnecting multiple processors.
The MIT Alewife machine uses a scalable directory scheme,
as does the Kendall Square KSR one.
Now that we've discussed some of the background issues
in building scalable single address machines,
I want to talk about the DASH architecture
and design in particular.
DASH is built around the concept of a distributed directory.
It uses individual processors connected
to their caches, a memory and directory,
which forms a cluster.
That cluster is interconnected with the communication network
based on the Caltech Mesh and using a high bandwidth
version of that mesh.
A single address space is implemented
across the entire machine even though the physical memories
are distributed.
For example, the high order bits of every address
specify the cluster in which that particular address or word
will live.
The individual clusters are, in fact,
multiprocessors based on Silicon Graphics 4D-340s.
And the coherency protocol that's
implemented as a Snoopy protocol on that bus
is used as part of the overall architecture.
Let me give you an idea of what the DASH memory hierarchy looks
like and define some terminology so we can talk about how
the coherency protocol works.
At the top level, we have the processor and its two level
cache system.
That's part of the Silicon Graphics 4D.
The next level of hierarchy is provided
by the other caches in the same cluster, which
act as super caches via the snooping protocol.
If the data is not found for particular access
either in the processes caches or the other caches
of the processors in that cluster,
we go to the home cluster of that particular address.
The home cluster, remember, is given by the upper order
bits in the address.
There are two possible situations here.
One is that the home cluster is the same as the cluster that's
generating the request, that is, the address is
the address of a word in the local memory of that cluster,
in which case, of course, we don't
need to go across the interconnection network.
The other case is that that address belongs
to a remote cluster, and we have to actually send a request
across the interconnection network
to that home cluster where the address lives.
In fact, there's even another possible level in the hierarchy
here.
Consider the situation when the only copy of a particular word
that a processor has requested lives in yet another cluster,
neither the local cluster, which requested the data,
nor the home directory but a third remote cluster,
in which case, we may have to cross the interconnection
network again to go and get that data.
Let's look at how this protocol operates
when we try to read a cache line, which is held dirty
in a remote cluster.
The access will begin with the local cluster generating a read
request.
That read request will miss in the local caches
and cause a message to be sent across the interconnection
network, requesting the data from the home cluster.
When that message arrives in the home cluster,
we'll do a directory lookup to determine
where that particular word currently
resides in the machine.
We'll find out that the word is dirty and resides
in a remote cluster.
That will cause the home cluster to forward the request
to that dirty remote cluster.
So a message is actually created,
and the address of the data object is forwarded.
When it arrives at the dirty remote cluster,
that cluster will do a lookup, using the Snoopy Bus
protocols to access the caches in the remote cluster.
It will find the data word and transmit it
directly back to the original requesting local cluster.
This forwarding directly back of the request
eliminates the need to keep state in the home cluster
and keep track of that message.
It also reduces the latency.
At the same time the dirty cluster
will also write the data back and generate a write
back so that the home cluster will be updated.
This will mean that future requests don't
need to be forwarded to the dirty cluster
but can just be accessed directly in the home cluster
and then the data can be returned
to the requesting cluster.
Now, let's look at the case of a write
and see how cache coherency is maintained
with a write to a shared data item.
When the local cluster sees a write to a shared data
item that it does not currently have exclusive access to,
it will generate a read exclusive request, which
is sent to the home directory.
The home directory ACKs is the point of arbitration.
If two clusters try to do a right to the same word
in a cache or the same cache line at once,
those requests will both be forwarded
to the home directory, and they'll be serialized there.
When the home directory gets the request,
it replies directly to the local requesting cluster,
granting it exclusive access.
The cluster can then proceed to do the write.
In parallel with granting access,
the home cluster also will cause an validations
to be sent out to all the objects, which
are sharing the data.
It uses the presence bits of the directories
to determine which clusters have shared copies of the data.
Those shared objects will then do invalidations
in their individual caches and send acknowledgments
back to the local cluster when the invalidations have
completed.
These acknowledgments allow us to use a more relaxed memory
model, as well as increase the resiliency of the machine
in the face of failure.
In addition to the basic mechanism
of caches in cache coherency, there
are several other features in DASH, which
are used to reduce latency.
I've mentioned the notion of a relaxed memory model.
What actually happens in DASH, when a write occurs,
the cluster gets the read exclusive acknowledgment
and immediately continues.
That allows it to actually overlap its execution
with the actual process of doing the invalidation
to the remote clusters.
The writes are then pipelined basically,
and we obtain improved performance from that.
By going to a relaxed memory model,
we don't need to actually halt the processor until we
reach a synchronization point.
This also allows the compiler more freedom
in reordering shared accesses between two synchronization
points.
The DASH architecture also supports prefetching.
It does this by actually including the ability
to generate a request to an address, which
will cause a local copy of that cache line
to be brought into the cluster.
Then, rather than see the long latency of an entire cluster
reference, it's just obtained locally.
One of the important innovations in the DASH fetching mechanism
is that the prefetching is what we sometimes call non-binding,
that is, even though a data item is brought locally,
its coherency is maintained so that if it's
prefetched early and somebody updates the data item,
the semantics are correct and the prefetch
purely acts as an optimization.
This is quite critical in allowing
the compiler or the programmer freedom
in place and prefetches.
It means you can place a prefetch anywhere you want,
and you will not change the correct behavior
of the program.
DASH includes features to reduce the latency of synchronization
operations and also to reduce the bandwidth
demands of those synchronization operations.
Two examples of that are the queuing locks,
which allow us to get improved low latency access to highly
contended locks and fetch an increment operation, which
gives us the ability to reduce the contention on things
like queue indices and loop indices.
Let me actually show you a diagram of what the DASH
hardware looks like here.
In this figure, we can see the clusters organized
with the multiple processors and the directory in the cluster,
as well as I/O and the portion of the memory.
The interconnection network is actually a pair of meshes.
One of these is used for requests,
and the other is used for replies.
What actually happens in the machine is when a request is
generated, the directory, recognizing
that the request is for a remote address,
creates a message, which it transmits over the request
network.
That message is routed through the network,
to the appropriate cluster, where
the directory at that cluster sees the message
as an incoming request.
That directory in the target cluster
then takes the message off the network,
does whatever accesses are required on the bus,
and creates a new message containing the data.
That message is then sent back out on the reply network, where
it is routed through the reply network
and back to the original requesting cluster, where
again the directory puts that back on the bus.
Let's look one level deeper into how the directory controller
actually functions.
We see here on the bottom the two buses, which
are the backbone of the cluster, the Silicon Graphics
multiprocessor bus.
The directory controller actually
acts like another snoop on that bus,
sitting there watching the bus activity.
When the directory controller sees the remote request,
it generates a message, which it sends out
through the message routing chip and through the request
network.
That message goes around the machine
and comes in the request network of the remote cluster.
The message then is routed to what we call the Pseudo-CPU.
The Pseudo-CPU is a piece of logic,
which acts on behalf of a remote requester,
as if it were a demon sitting on the bus.
It generates the necessary bus control
signals to get the data either from memory
or from the cache of one of the processors on that bus.
When the access is completed, the directory controller
picks up the data from the bus and sends the message
containing the requested data back out through the message
routing chip on the reply network.
A piece of logic in the original requesting cluster
called the reply controller keeps track
of all outstanding requests.
When the outstanding request returns to the cluster,
the reply controller places the data back on the network
and tells the processor that it can now proceed with execution.
What's important is that this entire process
is totally transparent.
A program issues a load instruction,
and the hardware does this entire mechanism, including
the creation of messages, routing them
through the network, getting the data,
and providing the data back to the processor.
The DASH design also includes a rather substantial performance
monitor to try to monitor and watch the behavior of programs.
This allows us not only to have a machine which
can execute parallel programs, but to actually
have an environment for studying parallel programs
and watching how they behave.
Overall, in terms of gate count, this coherency mechanism
adds about 10% in the gate count to the individual cluster.
So, the overhead is actually quite modest.
Now, let me show you a picture of what
the DASH prototype looks like.
We've implemented this using state-of-the-art academic
packaging.
We've actually removed the board supports
that we use in this figure, which
normally consist of old phone books and TTL catalogs.
The design is actually done so that the directory
logic slips right into the Silicon Graphics backplane.
With the help of Silicon Graphics,
we were able to make a number of small but critical
modifications to their processor environment
so that the processor can correctly
operate with the directory board and its backplane.
The message network is actually implemented
over the ribbon cables that are visible in this picture.
Now, let me say something about the performance
of these remote accesses in this machine.
This figure shows you the breakdown of the time
to do a local fill of a cache, that is, to fill a cache miss,
which is occurred on the local bus,
a two cluster fill that is the time to do a cache miss,
which has to go to one remote cluster,
and finally a three cluster fill,
the time to do a cache miss that has
to go to two remote clusters.
A local fill takes just over 20 processor clocks.
And you can see the breakdown with that time
almost evenly divided between memory access time and bus
overhead.
One of the surprising things you'll
see in both the two and three cluster fill,
which take respectively about 100 and 130 processor clocks,
is that a substantial amount of the time
is devoted to getting through the memory
hierarchy onto the bus and in and out of clusters.
A rather small amount of the time
overall is devoted to actually getting through the network.
This actually has some important advantages.
It means that in larger scale machines,
the network time will still not be the major bottleneck
in the design.
Let me also observe that although one might think
that these times of 100 processor
clocks to go to a remote cluster or 130
to go through two remote clusters sound large,
that, in fact, we expect that next generation
versions of this architecture, we will be hard pressed
to maintain those processor clock
ratios given the rapid improvement in CPU performance.
So, we believe that these are realistic numbers and numbers
that real designs and programs have to live with.
So, given that, one might ask the question,
if remote accesses can take 100 to 130 processor clocks, what's
the performance of this machine going
to look like on real interesting applications?
Well, I guess I wouldn't be here today
if the performance wasn't interesting.
So, on this slide, I'm going to show you
some numbers that have been captured on the 16 processor
prototype for DASH.
These numbers are for a wide range of applications, varying
from things that do radiosity calculations for graphics
to a variety of scientific programs
that do galaxy evolution, fluid flow, the classic matrix
multiply, as well as more scientific,
more engineering-oriented programs that
do things like placement and wrap by simulated annealing.
You'll notice the speed-up for a wide range of these problems
is actually quite good, and what I'd
like to do is show you some reason why
the performance on one of these programs is particularly good
and why on one of them, namely the one
on the bottom of the chart, MP3D,
the performance is not so good.
This next photograph shows a picture
of our real-time monitoring system, which actually enables
us to watch what's happening on the machine in real time,
using the performance monitor to capture data.
On the left hand side of the screen,
you can see four windows, which correspond to the four clusters
and tell you what the remote access latency in those four
clusters looks like.
And you can see that the times are quite tightly packed
together, indicating that not very much contention is
occurring in the machine.
On the right hand side, you can see four windows
that tell you how much idle time exists
in each one of the processors, with the large green bar
indicating that the processors are busy most
of the time, roughly 90% to 95% of the time
in this application.
So this application, which is simulating molecular dynamics
in a water molecule, actually gets quite good speed-up.
Let's look at what this kind of performance monitor
tells us about the program, which doesn't
get good speed-up, MP3D.
If we look at this shot of the screen, we'll see two things.
On the left-hand side, we can see
that there is quite a lot of contention in the machine,
and rather than have a sharply focused remote access time,
we've got a remote access time, which is smoothed out
and blurred out.
And we see that the average remote access
times are considerably larger than what the minimum latency
is, indicating that there's a lot of contention
in the machine.
We also can see on the right-hand side
that three of the four clusters are idle almost 50%
of the time, that is, the process of utilization
is only about 60%.
And hence, that's why we're not getting very good speed-up
on this application.
Now, let me return to this performance chart for a second
and say something about this.
The MP3D application was originally
written for a vector supercomputer,
and it actually effectively streams its entire memory
image, a three-dimensional representation of space,
through the processor.
One of the things we did was to rewrite this application,
and the version of it that's been rewritten is called PSIM4.
PSIM4 is actually a more sophisticated version
of this application in that it includes
more complicated chemistry of the upper atmosphere.
However, it obtained substantially better
performance as we can see on this chart,
and it does that because PSIM4 pays more attention to locality
of access and uses a more sophisticated data
structure to improve its locality of access.
So, we see that with some work, we can even obtain performance
on a program whose performance was initially quite dismal.
Let me say something about the software strategy, which we are
developing for this machine.
One focus of that software strategy
is compiler-directed parallelism and hierarchy-- memory
hierarchy management, whereby the compiler analyzes
scientifically oriented programs consisting primarily
of loop intensive programs and both decomposes the parallelism
to run in parallel and manages the memory hierarchy,
aggressively tries to improve the locality of memory access.
We're also developing languages, which
are aimed at parallel programs, which have a larger grain size
and which also have a more complicated model of memory
locality.
These languages, Jade and COOL, both have
ways for users to talk about data dependencies
between parallel tasks, as well as
to deal with the issue of locality.
One of the nice things about a machine like DASH
that has a single address space is
that there's a fairly straightforward strategy
for getting an operating system on it.
We took a version of the Silicon Graphics IRIX operating system
and ported it quite easily to DASH.
Some small performance tuning was done in order
to enable the machine to operate more effectively
with multiple clusters.
But the important thing is that it runs UNIX
in a multi-threaded environment in a way that most of us like.
We've also focused quite heavily on trying
to build tools to help people tune their programs
and make them run effectively on a machine like DASH.
This is particularly important because the memory
hierarchy, as we've seen earlier,
is quite sophisticated, and explaining this
to a programmer who hasn't had several courses in computer
architecture can be quite difficult.
In order to assist them, one of the tools we built
is a tool called Mtool.
Mtool actually tracks the behavior of a program
and keeps track of where the performance bottlenecks are.
So, it can tell you, in a particular procedure,
for example, that there's a memory
bottleneck or a synchronization bottleneck,
which is preventing you from obtaining good speed-up.
Mtool not only can do that, but it
can isolate the actual lines in the source code,
and it has a fully windowed interface
to enable you to go directly from the memory bottleneck
to the particular set of lines and source code,
which are the source of that bottleneck.
This allows users to quickly focus in
on what the problem in their program
is and allows them to tune it.
Now, let me say a little bit about what
we see for future opportunities, future versions of the DASH
architecture.
One thing we've been looking at is
a much more highly integrated version
of this architecture that would use newer processors.
One could use modern packaging technology to design
a four-processor cluster, which with ASICs and type packaging
technology, could put the four processors with their first
and second level caches, 128 megabytes of memory,
and ASIC-based directory controller,
new state-of-the-art interconnection network using
new mesh routing chips all together onto a single board.
Using processors that are available in 1992,
you could obtain a peak performance
of 600 MIPS out of that cluster and about 400 megaflops.
If you took this highly integrated cluster
and placed it into a tightly packed system environment,
you could place a thousand processor machine, that is,
a 16 by 16 grid with four processors per cluster,
into four large racks.
With today's processors, that might give you
a peak performance of about 600 GIPS and about 400 gigaflops.
But what's perhaps even more exciting is that if you took
processors, which we expect to be available
in the '93/'94 time frame, you could obtain a machine,
which would have about 1.6 teraflops of peak performance.
Let me now make some concluding remarks about the DASH design.
What DASH tries to do is combine some
of the scalability advantages that have been demonstrated
and associated with message-passing machines
together with the programming advantages
that we know from a single address space machine.
It does that with the use of a distributed directory protocol.
We see that DASH looks like the beginning of a convergence
between these two approaches, the message-based approach
and the single address space approach
and hopefully has some of the advantages of both.
Let me say, though, that a single address space, while it
eases the programming effort, does not
allow the programmer to ignore and forget about locality.
So that to really use these machines,
we'll need new algorithms that have scalable parallelism, that
pay attention to locality, that help us make use of latency
tolerating support, and help us minimize
global synchronization.
The DASH project has been a large project for us
by academic standards and wouldn't
have been possible without the help of a lot of people.
My colleagues at Stanford have played a big role
in making this machine work, professors
Gupta, Horowitz, and Lam have all
made invaluable contributions.
Dave Nakahira, our staff engineer,
has actually helped keep the hardware together and make
it really run.
A large number of PhD students have
contributed to both the hardware and software system.
Dan Lenoski and Jim Laudon were key designers on this project.
And finally, I want to thank Silicon Graphics, without whose
help we could have never built a working prototype of this scale
and demonstrated the viability of these ideas.
Thank you.