%%------------------------------------------------------------------------
\section{Shared Memory Support on \start/}
%%------------------------------------------------------------------------
\label{sec:sm-support}
%%------------------------------------------------------------------------

In order to fully utilize the large, well-supported caches in the 620
and to explore new grounds in architecture, compilation and
scheduling, we added coherent cache-line shared memory support to
\start/\footnote{The decision to incorporate support for globally
coherent caches after switching from the 88110MP to the PowerPC 620 is
a fundamental difference between the original *T project and
\start/\cite{StarTNG94}.}.  A design requiring minimal hardware,
however, was desired to reduce design and implementation time.  An
ideal design would allow the use of a 620 processor on each site to
support shared memory cache-coherence protocols and additional
features such as an L3 software cache.  Coherent shared memory
implemented using a 620 would be flexible, since the 620 could be
arbitrarily programmed, already has access to system resources such as
the network and DRAM, and would add no cost to the system.

Unfortunately, the 620 or, for that matter, any commercial processor,
does not allow software to observe and respond to bus transactions
directly.  It was noted, however, that if some device captured bus
transactions and propagated responses, a 620 processor could read
those transactions and respond to them through that device.  Hardware
with this functionality, the ACD, is incorporated into \start/ to
provide the necessary infrastructure to experiment with shared memory.

The \sp/ provides most of the services necessary to implement shared
memory.  It provides processing power to run coherency protocols,
access to the network, and access to site resources such as DRAM.  The
ACD is simply a way for the service processor to observe and respond
to bus transactions and perform necessary coherency operations.  This
model relies on the fact that the 620 bus is split-phased.  The
split-phase bus allows the \sp/ to service the ACD over the same
memory bus that other processors use to access memory, even though
outstanding requests are pending.

The ACD acts as a memory device for the global region of memory.  It
``captures'', that is, buffers and acknowledges, all bus transactions
destined for the global memory area.  Two capture buffers are
provided, one to capture read operations, the other to capture write
operations.  Having two buffers is necessary to avoid deadlock.  One
data buffer is provided for reply cache-lines and one address buffer
is provided for flushes.  The \sp/ needs the capability to issue
flushes through the ACD to avoid deadlocks.  The reply and flush
buffers are written by the \sp/ to initiate a response or invalidation
operation respectively\footnote{Other ACD features, specific to the
620, are not discussed in this paper.}.  The ACD hardware was designed
to be simple to implement and fits easily into 35,000 gates.

Using a standard processor to support global memory has obvious tradeoffs.
Clearly, the performance of such a scheme is not as good as if there were
special-purpose hardware dedicated to the task.  As discussed in
Section~\ref{sec:acd-performance}, the expected latency of a cache-miss is
a factor of four worse than that of Stanford's FLASH, an aggressive
shared-memory machine.  It is important to note, however, that this penalty
is only paid when there is a cache-miss --- if miss rates are low, the
amortized penalty is also low.

The advantage of \start/'s approach, however, lies in its flexibility
and ease of implementation.  The \sp/ runs arbitrary software,
allowing us to experiment with cache-coherency protocols very easily.
It can implement such features as a software cache, which improves
sharing of remote data among the different processors at a site and
which allows features such as update-based protocols, variable-sized
cache-line fetches, and other sophisticated streaming techniques.  The
\sp/ could treat different areas of global memory differently --- it's
possible to support uncached global memory in this fashion.  Even a
cache-only memory architecture\cite{Hagersten92} could be implemented.
Also, if shared memory support is not needed for a program, the \sp/
becomes a normal computation processor.  The possibilities for
experimentation are endless.  By coupling the simple ACD with a 620 on
an SMP system, we implement shared memory in a very low-cost and
flexible way, allowing us to experiment with it and tune it for our
purposes.

Since global memory accesses that go through the ACD are slow, the ACD
is avoided whenever possible.  \ap/'s see two regions of memory, their
normal local memory, which is handled in the way normal SMP memory is
handled, and global, which is mapped to the ACD.  The service
processor also sees two regions of memory, local and the ACD command
interface.  The \ap/ and \sp/ local memory is completely disjoint ---
the DRAM backing the \ap/ and \sp/ local memory is partitioned.  One
cannot access the other's memory directly.  All global address space
handled through the ACD is eventually mapped to some \sp/'s local
space\footnote{In this paper, we assume the \sp/ also acts as the home
site protocol processor.}.

\begin{figure}
\illustrationpercent{memory}{40}
\caption{Memory Organization}
\label{fig: memory}
\end{figure}

In the rest of this section, we first elaborate on the global shared
memory implementation on \start/ in Section~\ref{sec:acd-design}.
This is followed in Section~\ref{sec:acd-performance} by a discussion
of the expected performance of this implementation.  


%%--------------------------------------------------------------------
\subsection{How Shared Memory Works on \start/}
%%%--------------------------------------------------------------------
\label{sec:acd-design}
%%%--------------------------------------------------------------------

We will illustrate how global cache-coherency is maintained through a
general example.  The ACD captures an L3 memory operation on a global
address by storing away all relevant details, and then notifies the
service processor that the outstanding request has been captured by
raising an ``external event'' line on the service processor's NIU,
causing a bit to be raised in the NIU status word.  Alternatives to
the \sp/ polling the NIU are interrupts and polling the ACD over the
L3.

The service processor handles the captured request by reading the
captured information from the ACD over the L3 bus.  After the service
processor has read the outstanding request, it frees the capture
buffer then performs the actions proscribed by the protocol such as
checking the L3 cache, sending a message to the home site, and so on.
This sequence of actions is illustrated in
Figure~\ref{fig:acd-read-eg}.  Eventually, the requested data is
returned to the requesting service processor, which then writes the
data to the ACD which puts the data on the L3 bus completing the bus
operation.

%% Removed: extraneous -- Jamey
%%  The alternative of
%%putting an interface between the ACD and the service processor on the
%%L2 interface is possible, and will dramatically increase performance,
%%but will not be explored in this phase of the project due to time
%%constraints.

\begin{figure}
\illustrationpercent{acd-read-eg}{40}
\caption{A simple global cache miss}
\label{fig:acd-read-eg}
\end{figure}

Deadlocks are possible in any shared memory system.  Simple SMP
systems solve the problem by having a single point of
sequentialization (the address bus), carefully allocating buffers for
specific functions and providing ``retry'' mechanisms to force
transactions to back-off if necessary.  Distributed schemes have no
efficient single point of sequentialization and often cannot know to
retry transactions until it is too late to do so.  The \start/ scheme
is even more complicated than a normal distributed scheme since it
uses a peer to the application processors, sitting on the same memory
bus and using the same MESI protocols and buffering, to run the
protocols and service the ACD.  Avoiding deadlocks in \start/'s shared
memory system has been examined in detail in another
paper\cite{CCDSM94}.

%%--------------------------------------------------------------------
\subsection{Expected Performance of \start/'s Shared Memory System}
%%--------------------------------------------------------------------
\label{sec:acd-performance}
%%--------------------------------------------------------------------

Since \start/'s support for cache-coherent shared memory involves a
lot of software, a cache miss incurs a significant penalty.  In this
section, we will assess that penalty and analyze whether that penalty
is tolerable for more than just experimentation.

The cache miss penalty depends on whether the desired cache-line hits
in the L3 cache.  Since the L3 cache is managed by software, we expect
that aggressive prefetching techniques, such as bringing over an
entire object at a time, can be employed.  Also, if prefetching from
the processor is done at the correct time, much of the desired data
that is being prefetched could wind up in the \sp/'s L1 or L2 cache,
speeding up the software access time.

\begin{figure}
\begin{center}
\begin{tabular}{|l|c||c|}
\hline
Type of Miss            & \start/      & \flash/ \\
                        & (proc cycles) & (proc cycles) \\ \hline
\hline
L3 Hit                  & 157              & 54 \\\hline
Local Clean             & 199              & 54 \\\hline
Local Dirty Remote      & 825              & 286 \\\hline
Remote Clean            & 770              & 222 \\\hline
Remote Dirty at Home    & 825              & 290 \\\hline
Remote Dirty Remote     & 1455             & 382 \\\hline
\end{tabular}
\end{center}
\caption{Miss penalties in processor cycles.  The numbers for \flash/
are taken from~\protect\cite{Heinrich94}.}
\label{fig: miss penalties}
\end{figure}

The penalties of cache-misses are shown in Figure~\ref{fig: miss
penalties}.  The times are given in processor cycles and are very
approximate and conservative.  The penalties assume that a remote home
location is 7 network hops away and that a remote dirty location is 5
network hops away.  The corresponding penalties for the Stanford
\flash/, as reported in~\cite{Heinrich94} are given for comparison.
To the first order, the miss penalties for \start/, assuming the
blocking case, are roughly 4 times longer.

To consider the actual impact on performance, one has to take into
consideration miss rates and the percentage of memory operations in a
program.  First, let us consider miss rates.  In the same \flash/
paper, the miss rates for selected SPLASH programs are obtained from a
simulator for \flash/ which assumes a 1 MByte cache.  The miss rates,
except for MP3D, range from 0.06\% to 1.00\%.  

In terms of overall performance, it is clear that unless the miss rate
is under 1\%, the performance of \start/'s shared memory system is
quite poor.  If the miss rate is less than 0.1\%, which occurs for 3
of the 7 benchmarks with a 1 MByte cache, our performance is quite good.
We believe that integrating network virtual memory to reduce miss
rates and using split-phase caching techniques to bound miss penalties
will dramatically drop the miss penalty, allowing \start/ to run many
more applications efficiently.

\subsection{Improving \start/'s Shared Memory Performance}
\label{sec: improving performance}

Since most of the shared memory support is built in software, the
options for performance enhancement are limitless.  The software L3
cache has already been mentioned.  Here are a couple more
possibilities.

\subsubsection{Integrating Network Virtual Memory into \start/:}

In order to fully exploit the large amount of compiler research aimed
at automatically placing \localglobal/ data, the path to access
\localglobal/ data should be made faster.  One way to do that is to
introduce temporary ``localization'' of a global page via the virtual
memory system by using network virtual memory\cite{Li89a,Dwarkadas93}.
This technique is however inadequate when there is finer grain
sharing, where the ownership is better divided among different sites
at the cache line level.  For pages that fall within this category, we
will rely on the cache line level cache coherency mechanism provided
by the ACD and \sp/.  Schemes to dynamically switch a page between
coherency granularities will be investigated.

\subsubsection{Reducing Application Processor Idle Time through
Multithreading:}

Another way to avoid the long delays incurred by servicing a global
cache-miss is to switch threads when a cache-miss occurs.  When the
cache-line is returned, the thread is restarted where it left off.  Such a
scheme is also required to cache memory locations with synchronizing
semantics such as I-structures\cite{arvind90}.  In such a scheme, the
penalty of a cache-miss is simply the time to context switch out the thread
and switch it back in later.  There is also a potential cost of checking to
see if there was a cache-miss.  With special hardware support, this last
cost can be eliminated.

Unfortunately, \start/ does not have special hardware support to
detect and handle cache-misses.  In order to implement this scheme, an
efficient method to detect a cache-miss needs to be implemented in
software.  Our proposed scheme uses a {\em miss pattern}, that is, a
pattern which is very unlikely to occur in real data.  When a
cache-miss occurs and the request is propagated to the memory bus, the
ACD captures it and passes it to the service processor.  If the
desired cache-line is not in the L3 cache, the service processor
returns a cache-line filled with the miss pattern through the ACD to
the requesting processor.  All accesses to memory where a miss pattern
can be returned must be checked against the miss pattern.  If the miss
pattern is encountered, the thread must be swapped out pending the
arrival of the desired data.  Speculation and superscalar execution
can probably remove most, if not all of the cycle overhead involved in
this check.

When the requesting processor sees the miss pattern, it sends a
request for the cache-line.  The request includes information on how
to restart the thread, save its current thread state away and schedule
the next thread.  Switching threads will be performed by code
generated by the compiler.  An upper bound on the amount of time to
access global memory would be around 300 cycles.  The request will
generate 2 reply messages.  The \sp/ will receive the cache-line to
insert into the L3 cache while the requesting processor gets back the
exact word that was requested.


%%------------------------------------------------------------------------
%%                             Section End
%%------------------------------------------------------------------------

