\renewcommand{\editdate}{Nov 24 04:18 1997}
\renewcommand{\mytitle}{enhancements.tex}
%\markboth{Draft: \mytitle \ \ \ \  Last Edit: \editdate }{Draft: \mytitle \ \ \ \ Last Edit: \editdate }
%==================================
\section{Enhancements}
\label{sec:enhancements}
%~~~~~~~

In the base NIU design the \sp/ is involved in almost every action.
Two performance problems can arise: (i) the latency of going through
the sP may be unacceptable for latency sensitive operations; (ii) as
the network becomes faster and the number of \ap/'s per site
increases, the \sp/ {\em occupancy} becomes a serious performance
bottleneck.  Our solution is to use specialized hardware functional
units within the NIU to handle common case scenarios, taking the
\sp/ ``out of the loop''. We describe how to eliminate the
\sp/ from most message passing operations, then discuss some
further hardware enhancements to ease system-level issues as well as
to support multiple cache coherence protocols.

\subsection{Improved Message Passing Performance}
%~~~~~~~~~~
% ----------
% basic
% - ptrs
% - permission check
% - transmit engine
% - translation
% - reclaim

In order to handle \basic/ messages without invoking the \sp/,
hardware assistance is needed for three functions: (i) FIFO message
queue management; (ii) message formatting; and (iii) queue name
translation.

First, each \basic/ message TxQ and RxQ buffer are mapped to some
known place in the scratch pad memory.  Hardware support for FIFO
queues then consists of registers and logic for manipulating the
producer and consumer pointers, allowing the bus slave unit to satisfy
operations on the message queues.  The addition of transmit and
receive hardware units takes care of reformatting messages in the
hardware TxQ's for transmission into the network, and steering of the
receive messages into RxQ's.  When protection is enabled, queue name
translations occur during transmission via hardware table lookup.  To
support multiple hardware queues, TxQ and RxQ states are organized
into ``queue state register files''.  The \sp/ is still used to handle
exceptional situations.  For example, if the validity check of the
destination fails, or a message arrives for a full RxQ, the \sp/ is
invoked to take the appropriate action.

\express/ and \tagon/ messages are implemented on top of the
\basic/ implementation, with hardware ``wrappers''.  The slave unit's
processing of an \express/ transmits uncached write automatically
updates the producer or consumer pointer, and then invokes the \basic/
engine.

Three composable, simple hardware units implements DMA: a reader, a
sender and a receiver.  The reader performs block bus operations and
the sender performs block transmits with data and bus operations to
execute on the receiving site.  They can be coupled to run in a
pipelined fashion, moving data through a queue in scratch memory or
used separately to provide block bus operations or multicast of blocks
of data.  The receiver decomposes the message into data and bus op
parts, and issues the bus operations with the provided data.  The DMA
receiver uses remotely settable counters to determine when to notify
its \sp/ of completion.

\subsection{Resident and Non-resident Message Spaces}
%~~~~~~~~~~

In order to support a large number of message queues without the
expense of a large scratch memory, the design should retain the
ability for the \sp/ to service message passing operations.  We refer
to queues that have dedicated hardware state as {\em Resident} and all
other queues as {\em Non-resident}.  Because both are accessed via
memory-mapped interface, application code is not directly aware of
whether its queue is mapped to NIU slave space (Resident) or to DRAM
(Non-resident).  This mapping can thus be changed dynamically and
transparently by the system software.  In essence, Resident queues are
used as a firmware controlled message queue cache.

All non-resident queues share a single hardware queue with the
overflow queue and are handled by the \sp/.  Other required hardware
includes a lookup table to allow dynamic, local mapping of receive
queues into Resident resources.  Packet arrival results in a table
lookup (similar to cache-tag matching) to determine if the packet's
destination queue is one of those mapped to the hardware.  If not, or
if that destination queue is already full, the message is routed via a
special queue to the \sp/ for processing as explained in Section
\ref{sec:minimal}.

Since all queues are active, where resident or not, more flexible
scheduling policies are possible.  Swapping out a parallel process
requires no global coordination to ensure correctness.  The OS can
locally decide the best use of the resident message buffer space. This
is in contrast to MPP's such as the CM-5\cite{Leiserson92} which
supports only a single set of network queues, forcing the queues as
well as the network state to be entirely swapped out at the time of
context switch. The liberation from globally synchronous gang
scheduling opens up the possibility of implementing novel
co-scheduling approaches\cite{Sobalvarro95}.

\subsection{Multiple CCDSM Protocol Support}
%~~~~~~~~~
\label{sec:enhancedHAL}

\begin{figure}
\footnotesize
\begin{center}
\begin{tabular}{c | c c | c c | c c | c c}
                  & \mco{8}{Bus Transaction Type} \\
Cache Line State  & \mcc{Read}  & \mcc{Read Atomic} & \mcc{Rd w/ Modify} & \mcc{Write} \\ 
                  & Cntl & NIU  & Cntl & NIU        & Cntl & NIU     & Cntl & NIU \\ \hline
Invalid           & \n & \y     & \n & \y       & \n & \y          & \n & \y \\
Exclusive         & \y & \n     & \y & \n       & \y & \n          & \y & \n \\
Shared            & \y & \n     & \y & \y       & \n & \y          & \n & \y \\ \hline
Update Exclusive  & \y & \n     & \y & \n       & \y & \n          & \y & \y \\
Update Shared     & \y & \n     & \y & \y       & \n & \y          & \y & \y \\ \hline
\end{tabular}
\end{center}
\caption{
Each cache line has up to eight states.  The table has been extended to
provide for the
simultaneous support for multiple protocols on a cache
line basis.}
\label{fig:newhal}
\end{figure}

A single cache coherence protocol such as MESI cannot efficiently
support all memory access patterns.  For example, false sharing can be
alleviated by multiple-writer protocols.  One way to implement
multiple protocols would be to mark such cache lines as special and
let the \sp/ handle accesses to them.  Such an implementation,
however, is likely to perform poorly.

%HAL bits allow bus transactions to continue immediately if the
%accessed cache-line is in the correct state.  The
%\sp/ is only invoked if HAL bits need to be changed or communication
%with other \sp/~s is needed. There is a finite state machine (FSM)
%that takes the HAL bits and bus transaction type as inputs and
%generates the appropriate response (\ie/, retry, proceed,
%retry\&invoke-\sp/, no-action).  The power of this scheme can be
%extended gracefully by providing more HAL bits per line and by making
%the FSM reconfigurable by the \sp/. As before, only the \sp/ can
%change the state of a cache line, but this is presumed to happen
%infrequently.

HAL bits allow hardware to automatically handle bus operations that do
not require additional action, without intervention by the \sp/.  By
providing additional HAL bits, we can directly support multiple
protocols (which may wind up being a single large protocol).  A
possible encoding for three HAL bits per cache line is shown in Figure
\ref{fig:newhal}. The first three states can behave with the usual
semantics while the remaining five states can have a different action
mapping for each transaction type.  With the additional bits and
without further modifications, however, the \sp/ is the only entity
capable of changing the HAL bits.

%%%%%%%%%%%%%%%%%%%
%  End of Section %
%%%%%%%%%%%%%%%%%%%







