Distributed Shared Memory

INTRODUCTION & THISIS

Chapter Review

o Introduction
o What is Shared Memory
o Bus-Based Multiprocessors
o Ring Based Multiprocessors
o Switched Multiprocessors
o NUMA
o Comparison of shared Memory System
 Distributed Shared Memory

Distributed Shared
Memory
INTRODUCTION & THISIS

A distributed shared memory is a mechanism allowing

end-users' processes to access shared data without using
inter-process communications. In other words, the goal of
a DSM system is to make inter-process communications
transparent to end-users. Both hardware and software
implementations have been proposed in the literature. In any case, implementing a DSM system implies to
From a programming point of view, two approaches have address problems of data location, data access, sharing
been studied: and locking of data, data coherence. Such problems are
not specific to parallelism but have connections with
 Shared virtual memory: This notion is very distributed or replicated databases management systems
similar to the well-known concept of paged (transactional model), networks (data migrations),
virtual memory implemented in mono-processor uniprocessor operating systems (concurrent
systems. The basic idea is to group all distributed programming), distributed systems.
memories together into a single wide address
space. Drawbacks: such systems do not allow to Shared memory machines
consider the semantics of shared data: the data
are composed of a set of processors accessing to a single
granularity is arbitrarily fixed to some page size
memory. The main advantage of these machines lies in
whatever the type and the actual size of the
their easy programmability since there are no
shared data might be. The programmer has no
communications between the processors. However,
means to provide information about these data.
contentions and collisions (due to concurrent accesses to
 Object DSM: in that class of approaches, shared the shared memory) prevent applications to be scalable.
data are objects i.e. variables with access Therefore, in spite of some attempts, most of shared-
functions. In his applications, the user has only to memory machines are limited to a small number of
define which data (objects) are shared. The whole processors (< 32).
management of the shared objects (creation,
Distributed memory machines,
access, modification) is handled by the DSM
system. In opposite of SVM systems which work on the contrary, can integrate a large number of
at operating system layer, objects DSM systems processors (> 1000). Applications using these
propose a programming model alternative to the architectures can be scalable (if the programmer is good
classical message-passing. enough!). The communication model usually used is
message passing, which can allow considerable speedups.
However, its programming remains difficult since end-
users have to handle all communication operations.

 Page 1
 Distributed Shared Memory

 Page 1
  Distributed Shared Memory

Bus-Based Multiprocessors

Fig. 1-1. (a) A multiprocessor. (b) A multiprocessor with caching.

Bus based multiprocessor consists of some number of difficult to program. One of the solutions for it is to
CPUs all connected to a common bus, along with a implement write-through cache and snoopy cache. In
memory module. A simple configuration is to have a write-through cache, cache memories are designed so
high-speed backplane or motherboard into which CPU or that whenever a word is written to the cache, it is written
memory cards can be inserted. A typical bus has 32 or 64 through to memory as well. In addition, all caches
address lines, 32 or 64 data lines, and perhaps 32 or more constantly monitor the bus. Whenever a cache sees a
control lines, all of which operate in parallel. The problem write occurring to a memory address present in its cache,
with this scheme is that with as few as 4 or 5 CPUs, the it either removes that entry from its cache or updates the
bus will usually be overloaded, and performance will drop cache entry with the new value. Such a cache is called
drastically. The solution is to add the high-speed cache snoopy cache. because it is always snooping on the bus.
memory between the CPUs and the bus as shown in the
One particularly simple and common protocol is
fig. The cache holds the most recently accessed words. All
called write through. When a CPU first reads a word
memory requests go through the cache. If the word
from memory, that word is fetched over the bus and is
requested is in the cache, the cache itself responds to the
stored in the cache of the CPU making the request. If that
CPU and no bus request is made. If the cache is large
word is needed again later, the CPU can take it from the
enough, the probability of success, called the hit rate, will
cache without making a memory request, thus reducing
be high and the amount of bus traffic per CPU will drop
bus traffic. These two cases read miss (word not cached)
dramatically, allowing many more CPUs in the system.
and read hit (word cached) are shown in Fig. 1-2 as the
However, the introduction of cache also brings the
first two lines in the table. In simple systems, only the
serious problem with it suppose that two CPUs A and B
word requested is cached, but in most, a block of words
each read the same word into their respective caches.
of say, 16 or 32 words, is transferred and cached on the
Then A overwrites the word. When B next reads that
initial access and kept for possible future use.
word, it gets the old value from its cache, not the value A
just wrote. The memory is now incoherent, and the
system is

 Page 2
 Event Action taken by a cache in response to its own CPU's Action taken by a cache in response to a remote CPU's
operation operation

Read miss Fetch data from memory and store in cache (No action)

Read hit Fetch data from local cache (No action)

Write Update data in memory and store in cache (No action)

miss

Write hit Update memory and cache Invalidate cache entry

Fig. 1-2. The write-through cache consistency protocol. The entries for hit in the third column mean that the snooping CPU has
the word in its cache, not that the requesting CPU has it.

Our protocol manages cache blocks, each of which can be state is changed to DIRTY, as shown in Fig. 1-3(c). The
in one of the following three states: DIRTY state means that A has the only cached copy
1. INVALID — This cache block does not contain valid of W and that memory is out-of-date for W.
data.
At this point, A overwrites the word again, as shown in
2. CLEAN — Memory is up-to-date; the block may be in Fig. 1-3(d). The write is done locally, in the cache, with no
other caches.
bus traffic. All subsequent writes also avoid updating
3. DIRTY — Memory is incorrect; no other cache holds the memory.
block.
Sooner or later, some other CPU, C in Fig. 1-3(e), accesses
The basic idea is that a word that is being read by
the word. A sees the request on the bus and asserts a
multiple CPUs is allowed to be present in all their caches.
signal that inhibits memory from responding.
A word that is being heavily written by only one machine
is kept in its cache and not written back to memory on Instead, A provides the needed word and invalidates its
every write to reduce bus traffic. own entry. C sees that the word is coming from another
cache, not from memory, and that it is in DIRTY state, so it
The operation of the protocol can best be illustrated by
an example. For simplicity in this example, we will assume marks the entry accordingly. C is now the owner, which
that each cache block consists of a single word. means that it can now read and write the word without
Initially, B has a cached copy of the word at address W, as making bus requests. However, it also has the
illustrated in Fig. 1-3(a). The value is W1. The memory responsibility of watching out for other CPUs that request
also has a valid copy. In Fig. 1-3(b), A requests and gets a the word and servicing them itself. The word remains in
copy of W from the memory. Although B sees the read
DIRTY state until it is purged from the cache it is currently
request go by, it does not respond to it.
residing in for lack of space. At that time, it disappears
Now A writes a new value, W2 to W. B sees the write from all caches and is written back to memory.
request and responds by invalidating its cache entry. A's
 Distributed Shared Memory

Fig. 1-3. An example of how a cache ownership protocol works.

Many small multiprocessors use a cache consistency protocol similar to this one, often with small variations. It has three
important properties:

1. Consistency is achieved by having all the caches do bus snooping.

2. The protocol is built into the memory management unit.

2. 3. The entire algorithm is performed in well under a memory cycle.

3. As we will see later, some of these do not hold for larger (switched) multiprocessors, and none of them hold
for distributed shared memory.

 Page 1
 Ring-Based Multiprocessors
The next step along the path toward distributed shared memory is divided into 32-byte blocks, which is the
memory systems are ring-based multiprocessors, unit in which transfers between machines take place.
exemplified by Memnet (Delp, 1988; Delp et al., 1991;
All the machines in Memnet are connected together in
and Tarn et al., 1990). In Memnet, a single address
a modified token-passing ring. The ring consists of 20
space is divided into a private part and a shared part.
parallel wires, which together allow 16 data bits and 4
The private part is divided up into regions so that each
control bits to be sent every 100 nsec, for a data rate
machine has a piece for its stacks and other unshared
of 160 Mbps. The ring is illustrated in Fig. 1-4(a). The
data and code. The shared part is common to all
ring interface, MMU (Memory Management Unit),
machines (and distributed over them) and is kept
cache, and part of the memory are integrated together
consistent by a hardware protocol roughly similar to
in the Memnet device, which is shown in the top third
those used on bus-based multiprocessors. Shared
of Fig. 1-4(b).

Fig. 1-4. (a) The Memnet ring. (b) A single machine. (c) The block table.

Unlike the bus-based multiprocessors of Fig. 1-1, in is always reserved for it, in the Home memory field of
Memnet there is no centralized global memory. Fig. 1-4(b). A block may be cached on a machine other
Instead, each 32-byte block in the shared address than its home machine. (The cache and home memory
space has a home machine on which physical memory areas share the same buffer pool, but since they are
 Distributed Shared Memory

used slightly differently, we treat them here as A problem arises if the requesting machine has no free
separate entities.) A read-only block may be present space in its cache to hold the incoming block. To make
on multiple machines; a read-write block may be space, it picks a cached block at random and sends it
present on only one machine. In both cases, a block home, thus freeing up a cache slot. Blocks
need not be present on its home machine. All the whose Home bit are set are never chosen since they
home machine does is provide a guaranteed place to are already home.
store the block if no other machine wants to cache it.
Writes work slightly differently than reads. Three cases
This feature is needed because there is no global
have to be distinguished. If the block containing the
memory. In effect, the global memory has been spread
word to be written is present and is the only copy in
out over all the machines.
the system (i.e., the Exclusive bit is set), the word is just
The Memnet device on each machine contains a table, written locally.
shown in Fig. 1-4(c), which contains an entry for each
If the needed block is present but it is not the only
block in the shared address space, indexed by block
copy, an invalidation packet is first sent around the
number. Each entry contains a Valid bit telling whether
ring to force all other machines to discard their copies
the block is present in the cache and up to date,
of the block about to be written. When the invalidation
an Exclusive bit, specifying whether the local copy, if
packet arrives back at the sender, the Exclusive bit is
any, is the only one, a Home bit, which is set only if this
set for that block and the write proceeds locally.
is the block's home machine, an Interrupt bit, used for
forcing interrupts, and a Location field that tells where If the block is not present, a packet is sent out that
the block is located in the cache if it is present and combines a read request and an invalidation request.
valid. The first machine that has the block copies it into the
packet and discards its own copy. All subsequent
Having looked at the architecture of Memnet, let us
machines just discard the block from their caches.
now examine the protocols it uses. When the CPU
When the packet comes back to the sender, it is stored
wants to read a word from shared memory, the
there and written.
memory address to be read is passed to the Memnet
device, which checks the block table to see if the block Memnet is similar to a bus-based multiprocessor in
is present. If so, the request is satisfied immediately. If most ways. In both cases, read operations always
not, the Memnet device waits until it captures the return the value most recently written. Also, in both
circulating token, then puts a request packet onto the designs, a block may be absent from a cache, present
ring and suspends the CPU. The request packet in multiple caches for reading, or present in a single
contains the desired address and a 32-byte dummy cache for writing. The protocols are similar, too;
field. however, Memnet has no centralized global memory.
As the packet passes around the ring, each Memnet The biggest difference between bus-based
device along the way checks to see if it has the block multiprocessors and ring-based multiprocessors such
needed. If so, it puts the block in the dummy field and as Memnet is that the former are tightly coupled, with
modifies the packet header to inhibit subsequent the CPUs normally being in a single rack. In contrast,
machines from doing so. If the block's Exclusive bit is the machines in a ring-based multiprocessor can be
set, it is cleared. Because the block has to be much more loosely coupled, potentially even on
somewhere, when the packet comes back to the desktops spread around a building, like machines on a
sender, it is guaranteed to contain the block requested. LAN, although this loose coupling can adversely effect
The CPU sending the request then stores the block, performance. Furthermore, unlike a bus-based
satisfies the request, and releases the CPU. multiprocessor, a ring-based multiprocessor like
Memnet has no separate global memory. The caches
are all there is. In both respects, ring-based

 Page 1
 Distributed Shared Memory

multiprocessors are almost a hardware implementation exclusive (multiprocessors and distributed shared
of distributed shared memory. memory machines; mammals and birds, respectively).
Nevertheless, it does exist, and shows that the two
One is tempted to say that a ring-based
categories are not quite so distinct as one might think.
multiprocessor is like a duck-billed platypus —
theoretically it ought not exist because it combines the
properties of two categories said to be mutually

Switched Multiprocessors

Although bus-based multiprocessors and ring-based bandwidth left. The only way out is to add more bus
multiprocessors work fine for small systems (up to around bandwidth. One approach is to change the topology,
64 CPUs), they do not scale well to systems with hundreds going, for example, from one bus to two buses or to a
or thousands of CPUs. As CPUs are added, at some point tree or grid. By changing the topology of the
the bus or ring bandwidth saturates. Adding additional interconnection network, it is possible to add additional
CPUs does not improve the system performance. communication capacity.

Two approaches can be taken to attack the problem of A different method is to build the system as a hierarchy.
not enough bandwidth: Continue to put some number of CPUs on a single bus,
but now regard this entire unit (CPUs plus bus) as a
1. Reduce the amount of communication.
cluster. Build the system as multiple clusters and connect

2. Increase the communication capacity. the clusters using an intercluster bus, as shown in Fig. 1-
5(a). As long as most CPUs communicate primarily within
We have already seen an example of an attempt to their own cluster, there will be relatively little intercluster
reduce the amount of communication by using caching. traffic. If one intercluster bus proves to be inadequate,
Additional work in this area might center on improving add a second intercluster bus, or arrange the clusters in a
the caching protocol, optimizing the block size, tree or grid. If still more bandwidth is needed, collect a
reorganizing the program to increase locality of memory bus, tree, or grid of clusters together into a super-cluster,
references, and so on. and break the system into multiple superclusters. The
superclusters can be connected by a bus, tree, or grid,
Nevertheless, eventually there comes a time when every
and so on. Fig. 1-5(b) shows a system with three levels of
trick in the book has been used, but the insatiable
buses.
designers still want to add more CPUs and there is no bus

 Page 1
 Fig. 1-5. (a) Three clusters connected by an intercluster bus to form one supercluster. (b) Two superclusters connected by a
supercluster bus.

In this section we will look at a hierarchical design based blocks, so each cluster has 1M memory blocks within its
on a grid of clusters. The machine, called Dash, was built address space.
as a research project at stanford university (Lenoski et al.,
1992). Although many other researchers are doing similar Directories
work, this one is a typical example. In the remainder of Each cluster has a directory that keeps track of which
this section we with focus on the 64-CPU prototype that clusters currently have copies of its blocks. Since each
was actually constructed, but the design principles have cluster owns 1M memory blocks, it has 1M entries in its
been chosen carefully so that one could equally well build directory, one per block. Each entry holds a bit map with
a much larger version. The description given below has one bit per cluster telling whether or not that cluster has
been simplified slightly in a few places to avoid going the block currently cached. The entry also has a 2-bit field
into unnecessary detail. telling the state of the block. The directories are essential
to the operation of Dash, as we shall see. In fact, the
A simplified diagram of the Dash prototype is presented
name Dash comes from "Directory Architecture for
in Fig. 1-6(a). It consists of 16 clusters, each cluster
Shared memory."
containing a bus, four CPUs, 16M of the global memory,
and some I/O equipment (disks, etc.). To avoid clutter in Having 1M entries of 18 bits each means that the total
the figure, the I/O equipment and two of the CPUs have size of each directory is over 2M bytes. With 16 clusters,
been omitted from each cluster. Each CPU is able to the total directory memory is just over 36M, or about 14
snoop on its local bus, as in Fig. 1-1(b), but not on other percent of the 256M. If the number of CPUs per cluster is
buses. increased, the amount of directory memory is not
changed. Thus, having more CPUs per cluster allows the
The total address space available in the prototype is
directory cost to be amortized over a larger number of
256M, divided up into 16 regions of 16M each. The global
CPUs, reducing the cost per CPU. Also, the cost of the
memory of cluster 0 holds addresses 0 to 16M. The global
directory and bus controllers per CPU are reduced. In
memory of cluster 1 holds addresses 16M to 32M, and so
theory, the design works fine with one CPU per cluster,
on. Memory is cached and transferred in units of 16-byte
 Distributed Shared Memory

but the cost of the directory and bus hardware per CPU hop. Although not shown in the figure, there are actually
then becomes larger. two sets of intercluster links, one for request packets and
one for reply packets. The intercluster links cannot be
A bit map is not the only way to keep track of which
snooped upon.
cluster holds which cache block. An alternative approach
is to organize each directory entry as an explicit list telling Caching
which clusters hold the corresponding cache block. If
Caching is done on two levels: a first-level cache and a
there is little sharing, the list approach will require fewer
larger second-level cache. The first-level cache is a subset
bits, but if there is substantial sharing, it will require more
of the second-level cache, so only the latter will concern
bits. Lists also have the disadvantage of being variable-
us here. Each (second-level) cache monitors the local bus
length data structures, but these problems can be solved.
using a protocol somewhat similar to the cache
The M.I.T. Alewife multiprocessor (Agarwal et al., 1991;
ownership protocol of Fig. 1-3.
and Kranz et al., 1993), for example, is similar to Dash in
many respects, although it uses lists instead of bit maps Each cache block can be in one of the following three
in its directories and handles directory overflows in states:
software.
1. UNCACHED — The only copy of the block is in this
Each cluster in Dash is connected to an interface that memory.
allows the cluster to communicate with other clusters. The
interfaces are connected by intercluster links (primitive 2. CLEAN — Memory is up-to-date; the block may be in
buses) in a rectangular grid, as shown in Fig. 1-6(a). As several caches.
more clusters are added to the system, more intercluster
3. DIRTY — Memory is incorrect; only one cache holds the
links are added, too, so the bandwidth increases and the
block.
system scales. The intercluster link system
uses wormhole routing, which means that the first part The state of each cache block is stored in the State field
of a packet can be forwarded even before the entire of its directory entry, as shown in Fig. 1-6(b
packet has been received, thus reducing the delay at each

 Page 1
 If the
block
is not

present in any of the cluster's caches, a request packet is sent to

Protocols
the block's home cluster, which can be determined by
The Dash protocols are based on ownership and examining the upper 4 bits of the memory address. The home
invalidation. At every instant, each cache block has a cluster might well be the requester's cluster, in which case the
unique owner. For UNCACHED or CLEAN blocks, the message is not sent physically. The directory management
hardware at the home cluster examines its tables to see what
block's home cluster is the owner. For dirty blocks, the
state the block is in. If it is UNCACHED or CLEAN, the
cluster holding the one and only copy is the owner.
hardware fetches the block from its global memory and sends it
Writing on a CLEAN block requires first finding and back to the requesting cluster. It then updates its directory,
invalidating all existing copies. This is where the marking the block as cached in the requester's cluster (if it was
directories come in. not already so marked).

To see how this mechanism works, let us first consider If, however, the needed block is DIRTY, the directory
hardware looks up the identity of the cluster holding the block
how a CPU reads a memory word. It first checks its own
and forwards the request there. The cluster holding the dirty
caches. If neither cache has the word, a request is issued on the
block then sends it to the requesting cluster and marks its own
local cluster bus to see if another CPU in the cluster the block
copy as CLEAN because it is now shared. It also sends a copy
has containing it. If one does, a cache-to-cache transfer of the
back to the home cluster so that memory can be updated, and
block is executed to place the block in the requesting CPU's
the block state changed to CLEAN. All these cases are
cache. If the block is CLEAN, a copy is made; if it is DIRTY,
summarized in Fig. 1-7(a). Where a block is marked as being in
the home directory is informed that the block is now CLEAN
a new state, it is the home directory that is changed, as it is the
and shared. Either way, a hit from one of the caches satisfies
home directory that keeps track of the state.
the instruction but does not affect any directory's bit map.
 Distributed Shared Memory

If the requesting CPU does not have the cache block, it issues a cases can be distinguished here. If the block is UNCACHED, it
request on the local bus to see if any of the neighbors have it. If is marked dirty and sent to the requester. If it is CLEAN, all
so, a cache-to-cache (or memory-to-cache) transfer is done. If copies are invalidated and then the procedure for UNCACHED
the block is CLEAN, all other copies, if any, must be is followed. If it is DIRTY, the request is forwarded to the
invalidated by the home cluster. remote cluster currently owning the block (if needed). This
cluster invalidates its own copy and satisfies the request. The
If the local broadcast fails to turn up a copy and the block is various cases are shown in Fig. 1-7(b
homed elsewhere, a packet is sent to the home cluster. Three
(a)

Location where the block was found

Block state R's Neighbor's cache Home cluster's Some cluster's cache
cache memory

UNCACHED Send block to R; mark

as CLEAN and cached
only in R's cluster

CLEAN Use Copy block to R's cache Copy block from

block memory to R; mark as
also cached in R's
cluster

DIRTY Use Send block to R and to home Send block to R and to home cluster (if
block cluster; tell home to mark it as cached elsewhere}; tell home to mark it
CLEAN and cached in R's cluster as CLEAN and also cached in R's cluster

(b)

Location where the block was found

Block state R's cache Neighbor's cache Home cluster's memory Some cluster's cache

UNCACHED Send block to R; mark

as DIRTY and cached
only in R's cluster

CLEAN Send message to home Copy and invalidate block; Send block to R;
asking for exclusive send message to home invalidate all cached

 Page 1
 Distributed Shared Memory

ownership in DIRTY asking for exclusive copies; mark it as

state; if granted, use ownership in DIRTY state DIRTY and cached only
block in R's cluster

DIRTY Use block Cache-to-cache transfer Send block directly to R;

to R; invalidate neighbor's invalidate cached copy;
copy home marks it as DIRTY
and cached only in R's
cluster

Fig. 1-7. Dash protocols. The columns show where the block was found. The rows show the state it was in. The
contents of the boxes show the action taken. R refers to the requesting CPU. An empty box indicates an impossible
situation. (a) Reads. (b) Writes.

Obviously, maintaining memory consistency in Dash

(or any large multiprocessor) is nothing at all like the
simple model of Fig. 6-1(b). A single memory access
may require a substantial number of packets to be
sent. Furthermore, to keep memory consistent, the
access usually cannot be completed until all the
packets have been acknowledged, which can have a
serious effect on performance. To get around these
problems, Dash uses a variety of special techniques,
such as two sets of intercluster links, pipelined writes,
and different memory semantics than one might
expect. We will discuss some of these issues later. For
the time being, the bottom line is that this
implementation of "shared memory" requires a large
data base (the directories), a considerable amount of
computing power (the directory management
hardware), and a potentially large number of packets

that must be sent and acknowledged. We will see later

that implementing distributed shared memory has
precisely the same properties. The difference between
the two lies much more in the implementation
technique than in the ideas, architecture, or algorithms.

 Page 1
 Distributed Shared Memory

NUMA Multiprocessors
If nothing else, it should be abundantly clear by now that
hardware caching in large multiprocessors is not simple. Examples of NUMA Multiprocessors
Complex data structures must be maintained by the
To make the concept of a NUMA machine clearer,
hardware and intricate protocols, such as those of Fig. 1-
consider the example of Fig. 1-8(a), Cm*, the first NUMA
7, must be built into the cache controller or MMU. The machine (Jones et al., 1977). The machine consisted of a
inevitable consequence is that large multiprocessors are number of clusters, each consisting of a CPU, a
expensive and not in widespread use. microprogram-Mable MMU, a memory module, and
possibly some I/O devices, all connected by a bus. No
However, researchers have spent a considerable amount caches were present, and no bus snooping occurred. The
of effort looking at alternative designs that do not require clusters were connected by intercluster buses, one of
elaborate caching schemes. One such architecture is which is shown in the figure.
the NUMA (Nonuniform Memory When a CPU made a memory reference, the request went
Access) multiprocessor. Like a traditional UMA (Uniform to the CPU's MMU, which then examined the upper bits
Memory Access) multiprocessor, a numa machine has a of the address to see which memory was needed. If the
single virtual address space that is visible to all CPUs. address was local, the MMU just issued a request on the
When any CPU writes a value to location a, a subsequent local bus. If it was to a distant memory, the MMU built a
read of a by a different processor will return the value just request packet containing the address (and for a write,
written. the data word to be written), and sent it to the
destination cluster over an intercluster bus. Upon
The difference between UMA and NUMA machines lies
receiving the packet, the destination MMU carried out the
not in the semantics but in the performance. On a NUMA
operation and returned the word (for a read) or an
machine, access to a remote memory is much slower than
acknowledgement (for a write). Although it was possible
access to a local memory, and no attempt is made to hide
for a CPU to run entirely from a remote memory, sending
this fact by hardware caching. The ratio of a remote
a packet for each word read and each word written
access to a local access is typically 10:1, with a factor of
slowed down operation by an order of magnitude.
two variation either way not being unusual. Thus, a CPU
can directly execute a program that resides in a remote
memory, but the program may run an order of
magnitude slower than it would have had it been in local
memory.

 Page 1
Fig. 1-8. (a) A simplified view of the Cm* system. (b) The BBN Butterfly. The CPUs on the right are the same as those on the left
(i.e., the architecture is really a cylinder)

Figure 1-8(b) shows another NUMA machine, the BBN 3. Remote access times are not hidden by caching.
Butterfly. In this design, each CPU is coupled directly to
The first two points are self-explanatory. The third may
one memory. Each of the small squares in Fig. 1-8(b)
require some clarification. In Dash and most other
represents a CPU plus memory pair. The CPUs on the
modern UMA multiprocessors, remote access is slower
right-hand side of the figure are the same as those on the
than local access as well. What makes this property
left. The CPUs are wired up via eight switches, each
bearable is the presence of caching. When a remote word
having four input ports and four output ports. Local
is touched, a block of memory around it is fetched to the
memory requests are handled directly; remote requests
requesting processor's cache, so that subsequent
are turned into request packets and sent to the
references go at full speed. Although there is a slight
appropriate memory via the switching network. Here, too,
delay to handle the cache fault, running out of remote
programs can run remotely, but at a tremendous penalty
memory can be only fractionally more expensive than
in performance.
running out of local memory. The consequence of this
Although neither of these examples has any global observation is that it does not matter so much which
memory, NUMA machines can be equipped with memory pages live in which memory: code and data are
that is not attached to any CPU. automatically moved by the hardware to wherever they
are needed (although a bad choice of the home cluster
Bolosky et al. (1989), for example, describe a bus-based
for each page in Dash adds extra overhead).
NUMA machine that has a global memory that does not
belong to any CPU but can be accessed by all of them (in NUMA machines do not have this property, so it matters
addition to the local memories). a great deal which page is located in which memory (i.e.,
on which machine). The key issue in NUMA software is
the decision of where to place each page to maximize
Properties of NUMA Multiprocessors performance. Below we will briefly summarize some ideas
NUMA machines have three key properties that are of due to LaRowe and Ellis (1991). Other work is described in
concern to us: (Cox and Fowler, 1989; LaRowe et al., 1991; and
Ramanathan and Ni, 1991).
1. Access to remote memory is possible.
When a program on a NUMA machine starts up, pages
2. Accessing remote memory is slower than accessing may or may not be manually prepositioned on certain
local memory. processors' machines (their home processors). In either
case, when a CPU tries to access a page that is not
 Distributed Shared Memory

currently mapped into its address space, it causes a page system has to guess if the page will be heavily used in the
fault. The operating system catches the fault and has to future. If it guesses wrong, a performance penalty will be
make a decision. If the page is read-only, the choice is to extracted.
replicate the page (i.e., make a local copy without
Whichever decision is made, the page is mapped in,
disturbing the original) or to map the virtual page onto
either local or remote, and the faulting instruction
the remote memory, thus forcing a remote access for all
restarted. Subsequent references to that page are done in
addresses on that page. If the page is read-write, the
hardware, with no software intervention. If no other
choice is to migrate the page to the faulting processor
action were taken, then a wrong decision once made
(invalidating the original page) or to map the virtual page
could never be reverse
onto the remote memory.

The trade-offs involved here are simple. If a local copy is

Comparison of Shared Memory
made (replication or migration) and the page is not
reused much, considerable time will have been wasted Systems
fetching it for nothing. On the other hand, if no copy is
made, the page is mapped remote, and many accesses
follow, they will all be slow. In essence, the operating

Shared memory systems cover a broad spectrum, from shared memory). In Fig. 1-9 the spectrum is shown
systems that maintain consistency entirely in hardware to explicitly.
those that do it entirely in software. We have studied the
On the left-hand side of Fig. 1-9 we have the single-bus
hardware end of the spectrum in some detail and have
multiprocessors that have hardware caches and keep
given a brief summary of the software end (page-based
them consistent by snooping
on the bus. These are the
simplest shared-memory
machines and operate
entirely in hardware. Various
machines made by Sequent
and other vendors and the
experimental DEC Firefly
workstation (five VAXes on a
common bus) fall into this
category. This design works
fine for a small or medium
number of CPUs, but
degrades rapidly when the
distributed shared memory and object-based distributed
bus saturates.

Fig. 1-9. The spectrum of shared memory machines. On the left-hand side of Fig. 1-9 we have the single-bus
multiprocessors that have hardware caches and keep
them consistent by snooping on the bus. These are the

 Page 1
 Distributed Shared Memory

simplest shared-memory machines and operate entirely writing it. Unlike in a multiprocessor, however, caching
in hardware. Various machines made by Sequent and (i.e., page placement and migration) is controlled by
other vendors and the experimental DEC Firefly software (the operating system), not by hardware (the
workstation (five VAXes on a common bus) fall into this MMUs). Cm* (Jones et al., 1977) and the BBN Butterfly are
category. This design works fine for a small or medium examples of NUMA machines.
number of CPUs, but degrades rapidly when the bus
Continuing along the spectrum, we come to the machines
saturates.
running a page-based distributed shared memory system
Next come the switched multiprocessors, such as the such as IVY (Li, 1986) and Mirage (Fleisch and Popek,
Stanford Dash machine and the M.I.T. Alewife machine. 1989). Each of the CPUs in such a system has its own
These also have hardware caching but use directories and private memory and, unlike the NUMA machines and
other data structures to keep track of which CPUs or UMA multiprocessors, cannot reference remote memory
clusters have which cache blocks. Complex algorithms are directly. When a CPU addresses a word in the address
used to maintain consistency, but since they are stored space that is backed by a page currently located on a
primarily in MMU microcode (with exceptions potentially different machine, a trap to the operating system occurs
handled in software), they count as mostly "hardware" and the required page must be fetched by software. The
implementations. operating system acquires the necessary page by sending
a message to the machine where the page is currently
Next come the NUMA machines. These are hybrids
residing and asking for it. Thus both placement and
between hardware and software control. As in a
access are done in software here.
multiprocessor, each NUMA CPU can access each word of
the common virtual address space just by reading or

Then we come to machines that share only a selected help maintain consistency. Everything is done in software
portion of their address spaces, namely shared variables here, with no hardware support at all. Orca (Bal, 1991) is
and other data structures. The Munin (Bennett et al., an example of this design, and Linda (Carriero and
1990) and Midway (Bershad et al., 1990) systems work Gelernter, 1989) is similar to it in some important ways.
this way. User-supplied information is required to
The differences between these six types of systems are
determine which variables are shared and which are not.
summarized in Fig. 1-10, which shows them from tightly
In these systems, the focus changes from trying to
coupled hardware on the left to loosely coupled software
pretend that there is a single common memory to how to
on the right. The first four types offer a memory model
maintain a set of replicated distributed data structures
consisting of a standard, paged, linear virtual address
consistent in the face of updates, potentially from all the
space. The first two are regular multiprocessors and the
machines using the shared data. In some cases the
next two do their best to simulate them. Since the first
paging hardware detects writes, which may help maintain
four types act like multiprocessors, the only operations
consistency efficiently. In other cases, the paging
possible are reading and writing memory words. In the
hardware is not used for consistency management.
fifth column, the shared variables are special, but they are
Finally, we have systems running object-based distributed still accessed only by normal reads and writes. The object-
shared memory. Unlike all the others, programs here based systems, with their encapsulated data and
cannot just access the shared data. They have to go methods, can offer more general operations and
through protected methods, which means that the represent a higher level of abstraction than raw memory.
runtime system can always get control on every access to

 Page 1
 ? MuItiprocessors ? ? DSM ?

Item Single Switched NUMA Page Shared Object based

bus based variable

Linear, shared virtual address Yes Yes Yes Yes No No

space?

Possible operations R/W R/W R/W R/W R/W General

Encapsulation and methods? No No No No No Yes

Is remote access possible in Yes Yes Yes No No No

hardware?

Is unattached memory Yes Yes Yes No No No

possible?

Who converts remote memory MMU MMU MMU OS Runtime Runtime

accesses to messages? system system

Transfer medium Bus Bus Bus Network Network Network

Data migration done by Hardware Hardware Software Software Software Software

Transfer unit Block Block Page Page Shared Object

variable

Fig. 1-10. Comparison of six kinds of shared memory systems.

The real difference between the multiprocessors and the operating system or runtime system. The medium used is
DSM systems is whether or not remote data can be also different, being a high-speed bus (or collection of
accessed just by referring to their addresses. On all the buses) for the multiprocessors and a conventional LAN
multiprocessors the answer is yes. On the DSM systems it (usually) for the DSM systems (although sometimes the
is no: software intervention is always needed. Similarly, difference between a "bus" and a "network" is arguable,
unattached global memory, that is, memory not having mainly to do with the number of wires).
associated with any particular CPU, is possible on the
The next point relates to who does data migration when
multiprocessors but not on the DSM systems (because
it is needed. Here the NUMA machines are like the DSM
the latter are collections of separate computers
systems: in both cases it is the software, not the
connected by a network).
hardware, which is responsible for moving data around
In the multiprocessors, when a remote access is detected, from machine to machine. Finally, the unit of data transfer
a message is sent to the remote memory by the cache differs for the six systems, being a cache block for the
controller or MMU. In the DSM systems it is sent by the UMA multiprocessors, a page for the NUMA machines
 Distributed Shared Memory

and page-based DSM systems, and a variable or object

for the last two.

 Page 1