\renewcommand{\editdate}{Nov 24 04:08 1997}
\renewcommand{\mytitle}{base.tex}
\renewcommand{\useredit}{rudolph}
%\markboth{Draft File: \mytitle \ \ \ \  Last Edit: \editdate(\useredit)}{Draft File: \mytitle \ \ \ \ Last Edit: \editdate (\useredit) }
%==================================
\section{A Base NIU Design}
\label{sec:minimal}
%~~~~~~~

This section describes a simple NIU design that supports the full set
of capabilities outlined above.  It provides a base design, upon which
hardware enhancements can be added systematically to improve
performance while maintaining the same interfaces to the network, and
to the SMP memory bus.  Before describing the design it is important
to understand why a pure software approach is insufficient. Given
direct access to the network, low level message passing libraries
easily implement user-level message passing.  Distributed shared
memory can also be handled in software through the use of
sophisticated compilation tools such as Shasta \cite{Scales96} that
also directly interface to the network communication.  But these
schemes become less attractive in multiuser, multiprocessor, SMP
environments where many processes wish to communicate over the network
concurrently.  Either processes are trusted to correctly handle
packets belonging to other processes, thereby compromising protection,
or the operating system must mediate network access, thereby
compromising performance.

\subsection{Assumptions: SMP Memory Bus and the Network}
%~~~~~~~~~~

For our design, the SMP must be capable of supporting multiple bus
{\em masters} and {\em slaves} as well as bus {\em snoopers}.  A bus
master can initiate all bus operations, including cache management
operations such as flush.  It is assumed that the SMP systems support
{\em intervention} in which there are two slave devices associated
with the same address range -- a primary, \eg/ the memory controller,
and a secondary, \eg/ the NIU bus slave unit.  The secondary unit can
dynamically intervene preventing the primary from satisfying a bus
transaction and itself responding to the transaction.  Traditional
look-aside caches require such intervention support.

Finally, it is assumed that the NIU is able to delay committing to a
bus transaction.  In particular, consider the case of a processor
requesting exclusive access to a cache line.  In most SMP's, once a
slave has committed to such a bus transaction, it is assumed that the
initiator has ownership of the cache line.  Further transactions to
the same address are disallowed until the first transaction has been
satisfied.  We require that a slave can cause a transaction to be {\em
retried} at a later time rather than having to commit to it.  In some
systems, the transaction will be continually retried, while in others
it will only be {\em rerun} when the slave indicates it is ready.
Still other systems allow a slave to {\em take back} or undo its
commitment.

There are fewer assumptions on the interconnection network.  We assume
reliable transmission, and support for at least two message priorities
in the network.  The latter is desirable to help avoid deadlocks in
cache coherence protocols.  A FIFO network is convenient for cache
coherence protocols, though not an absolute necessity.

\subsection{Message Passing with Virtualized Queues}


To provide protection, flexibility, and efficient use of resources,
message passing communication is implemented with operations on {\em
virtual transmit} and {\em receive queues}. The sender enqueues a
message into a local {\em transmit queue} (TxQ) and the receiver
dequeues a message from a local {\em receive queue} (RxQ).  Messages
in the TxQ specify virtual destination RxQ's (see Figure
\ref{fig:pipes}).  Virtualization of message queue names enables migration of virtual 
receive queues, and permits a queue to be locally mapped to local
hardware resources.  Virtual receive queue names go through
translation twice: once before being launched into the network and
once upon arrival at the destination NIU.  A
{\em conversion table} is used to give the physical destination NIU
site number required by a network packet for routing, and associates a
virtual RxQ name used at the destination site.

\begin{figure}
\illustrationpercent{pipes}{50}
\caption{Messages are sent from TxQ's to RxQ's without any a priori
restrictions. A TxQ at SMP A can send to two different RxQ's located
at SMP C, and a TxQ at SMP B can also send to two different RxQ's but
located at separate SMPs.  Notice that the bottom TxQ (at SMP D) can send
to an RxQ at SMP A, although the reverse is not true.
}
\label{fig:pipes}
\end{figure}





\begin{figure}
\begin{center}
\begin{tabular}{c||l|l|l|l|}
TxQ	& \multicolumn{1}{|c|}{Logical Dest 0}	
	& \multicolumn{1}{|c|}{Logical Dest 1}
	& ...	
	& \multicolumn{1}{|c|}{Logical Dest $n$} \\\hline
0	& $\langle$site$_A$, RxQ$_\beta$, source$_i$$\rangle$
	& $\langle$site$_B$, RxQ$_\delta$, source$_j$$\rangle$ 
	& ...	
	& $\langle$site$_C$, RxQ$_\zeta$, source$_k$$\rangle$ \\
\hline
1	& $\langle$site$_A$, RxQ$_\theta$, source$_l$$\rangle$ 
	& $\langle$site$_E$, RxQ$_\iota$, source$_m$$\rangle$ 
	& ...	
	& $\langle$site$_F$, RxQ$_\lambda$, source$_n$$\rangle$ \\
\hline
$\vdots$& $\vdots$
	& \multicolumn{1}{|c|}{$\vdots$}
	& \multicolumn{1}{|c|}{$\vdots$}
	& \multicolumn{1}{|c|}{$\vdots$}
\\
\hline
$n$	& $\langle$site$_G$, RxQ$_\nu$, source$_o$$\rangle$ 
	& $\langle$site$_H$, RxQ$_\pi$, source$_p$$\rangle$ 
	& ...	
	& $\langle$site$_I$, RxQ$_\sigma$, source$_q$$\rangle$ \\\hline
\end{tabular}
\end{center}
\caption{Conversion Table: each row contains the 
logical destination to $\langle$site, RxQ, source$\rangle$ mapping for
a transmit queue.}
\label{fig:logical-destination-mappings}
\end{figure}

To enforce flexible protection, applications refer to destination
RxQ's queues using short logical names associated with a local TxQ
(Figure \ref{fig:logical-destination-mappings}).  Messages can only be
sent to destinations with valid entries in the table.  Protection is
enforced by restricting who can modify the conversion table.  A
virtual source field, which is also read from the conversion table, is
automatically included in each message so that the receiver can
communicate back with the sender, while still allowing the sending
site to locally map its receive queues.

Our scheme provides greater flexibility than common schemes such as
attaching to every outgoing message a Parallel Job Identifier (PJID)
which is subsequently verified at the
destination\cite{Papadopoulos93}.  In particular, it allows
non-monolithic and non-symmetric communication domains to be set up
over the same physical network.  The former recognizes that not all
parties in a communication network are equal: some entities are more
trusted and are allowed to communicate with both trusted and untrusted
parties.  

\subsection{An Overview of the NIU Architecture}
%~~~~~~~~~

\begin{figure}
\illustrationpercent{minimal}{50}
\caption{
A minimal NIU Design. It interfaces with the SMP bus both as a slave
and master on one side and with the network on the other side. The
embedded service processor does all the work and provides flexibility.
\label{fig:baseDesign}
}
\end{figure}

With these assumptions, our minimal or base NIU design consists of
four parts (see Figure \ref{fig:baseDesign}):
%
(i) an embedded service processor (\sp/); 
(ii) a pair of transmit and receive queues that interface to the
interconnection network; 
(iii) an interface to the SMP bus, consisting of master, slave, and
snoop units,  along with a special ``approval''
register and \textem{HAL} bits for S-COMA CCDSM support;
and 
(iv) a scratch memory or buffers accessible by all three major
components. 
%

\begin{figure}
\illustrationpercent{addressSpace}{50}
\caption{
The virtual memory is divided into various spaces each with different
semantics.  The operating system, through the page table mechanism,
can control access to these spaces.  The implementation may require
the OS to conform to certain mapping restrictions of these spaces.
\label{fig:addressSpace}
}
\end{figure}

The NIU presents a memory-mapped interface with memory operations on
specific regions of memory invoking different operations (see Figure
\ref{fig:addressSpace}).  These memory operations are interpreted by 
the \sp/, which performs most of the functionality of the NIU.
Messages to and from the network are mediated by the \sp/ forming and
deciphering network packets and enforcing protection.  The hardware
network transmit and receive queues are necessary since the \sp/
speed may not match the network's.

The interface to the SMP bus is more involved.  Via the bus master,
the \sp/ can issue commands to move data between the scratch memory
and the SMP's DRAM or it can invalidate cache lines in the SMP
processors.  The bus slave captures memory accesses from any
application processor (\ap/) in the SMP and eventually satisfies them
using the scratch memory to buffer data.  Unlike I/O bus interfaces,
the NIU can maintain cache coherence with the SMP processors.

Since we retry operations to avoid committing, some mechanism is
required to avoid sending the same request to the
\sp/ repeatedly.  Our solution is to employ an {\em Approval
register}.  When a transaction is to be processed by the NIU, it is
recorded in the approval register and requested to be retried.  At the
same time, the NIU begins processing the transaction.  The transaction
will continue to be retried by the SMP while being processed by the
\sp/.  When the \sp/ completes its
actions, the bus slave then commits and satisfies the transaction.

When the slave unit services a cache line write action, it stores the
data in the next free location of the scratch memory.  It then informs
the \sp/ of the bus address and action.  The \sp/ knows implicitly
where to find the cache line.  Similarly, when the slave unit services
a cache line read action, the \sp/ will inform the slave where the
data is located in the scratch memory.

These are all the mechanisms needed to meet our requirements.
The distributed shared memory is implemented on top of message
passing, and so the latter is described first.

\subsection{Meeting the Message Passing Requirements}
%~~~~~~~~~~
\label{sec:mp-requirements}
Latency and processor overhead times that are proportional to the
message length can be achieved through a spectrum of message
semantics, two of which, \basic/ and DMA, are fairly standard while
two others, \express/ and \tagon/, are novel.  Each is optimized for
its own usage pattern and has its own advantages, see Figure
\ref{fig:msg-advantages}.  Since \basic/ messages form the foundation
upon which the remaining three are build, we begin with its
description.
%
%
\newcommand{\mca}[1]{\multicolumn{1}{c|}{#1}}
\begin{figure} 
\footnotesize
\begin{center}
\begin{tabular}{| l || c c c c || l |}
\hline
       &   Size &   \ap/     & Lat-         & Band-  &  \\
Type   & (words)&  Ovrhd & ency  & width  &  \mca{Comments} \\ \hline \hline
Express & 1+    & low       & low  & low & Synchronization, Bookkeeping \\
Tagon  &  10+   & low       & med & med  & Cache Coherent Shared Memory Protocols\\
Basic  & 100+   & med       & med & med  & Generic  message passing\\
DMA    & 1000+  & low       & high & high & Page Migration, Coarse Grained Apps \\ \hline
\end{tabular}
\end{center}
\caption{\label{fig:msg-advantages}
Each \start/ message type has different fields and is optimized for
its own usage pattern in terms of processor overhead, latency, and
bandwidth.  }
\end{figure}
%
%
\begin{figure}
\illustrationpercent{basic}{35}
\caption{Sending a Basic Message.
From software's
point-of-view, a message is sent as follows.
The consumer and producer pointers are compared
to ensure there is free buffer space (Step 1).  
A message consisting of a destination, size, and data, is stored into the next
free buffer location, which is cached  (Step 2). 
Finally, the producer pointer is then updated usually after a ``sync''
or ``fence'' command to ensure that the update occurs after the
message store completes (Step 3).  A receive operation occurs in an
analogous fashion, with an update to the producer pointer signalling
that the message has already been read.
} 
\label{fig:basictx}
\end{figure}
%

\bigskip
\noindent
{\bf \basic/ Messages:} The \basic/ message mechanism provides support for
variable length messages up to a few cache-lines long.  It transmits
and receives through FIFO buffers which are emulated by a continuous
region of cachable memory and producer/consumer pointers which are
uncached.  Figure \ref{fig:basictx} shows the software steps involved
for transmitting a message.


The NIU bus slave services transactions to the pointer
regions. 
Buffers are allocated to DRAM.
An update to a producer pointer of the TxQ causes
the \sp/ to begin preparing to launch the message.  The \sp/ issues
bus transactions to fetch the buffer data from the \ap/'s cache or DRAM.
After checking for message validity, the \sp/ formats a network packet
for the message information into the transmit queue and launches it
into the network.
At the receiving site, the \sp/ removes and  reformats the packet, 
places it into DRAM and updates the consumer
pointer.  Queue overflow is handled by writing the data in some
scratch DRAM space and sending a high priority message to the source
advising it to hold back forwarding additional messages.


\bigskip
\noindent{\bf \dma/ messages:} 
The \dma/ message mechanism provides support for memory-to-memory,
long messages.  Latency is sacrificed for bandwidth.  The source \sp/
communicates with the destination \sp/ to agree on validity and DRAM
locations.  The source \sp/ issues a series of NIU bus master commands
to fetch data from the local DRAM, formats a network packet, and then
commands the network transmit queue to launch the message.  Reception
handling is analogous.


\bigskip\noindent{\bf \express/ messages:}
The \express/ message mechanism provides support for very small
messages (a few bits more than a word) which originate and arrive in
registers.  Bandwidth is sacrificed for low processor overhead and low latency.
\express/ messages provide the ability to atomically launch a message 
in a multi-threaded environment {\em without} synchronization
instructions, dramatically reducing the cost of sharing network queues
between multiple threads and multiple SMP processors.  To increase the
usefulness of \express/ messages, a tag field in addition to a data
word is communicated.  An entire message can be sent by using a single
inherently atomic uncached write as explained below.

An \express/ message can be thought of as a \basic/ message in which
the buffer plus producer/consumer pointers emulating a FIFO are
replaced with a real hardware FIFO.  In reality, the producer pointer
is automatically updated when the message body is written.  The user
repeatedly writes into the same address and, if the NIU is fast enough
to avoid the message buffer overflows, he is freed from having to
manage the buffer pointers.  Even if the NIU is not fast enough, the
user can reduce the pointer checking overhead by periodically
determing the amount of buffer space available and sending fewer
messages than that.

The single uncached write operation is captured by the NIU
bus slave and the address and data lines are forwarded to the \sp/.
The address carries much information about the message, specifying the
particular \express/ message queue, the destination, and the tag.  The
data word is also included in the message.  A large address range is
allocated to each \express/ message queue -- the size of the range is
a function of the number of destinations and the number of tag bits
(See Figure \ref{fig:expressmsg-simple-format}).

\begin{figure}
\illustrationpercent{express-tx-format}{35}
\caption{Express Message Transmit Format. A destination, priority,
five bit tag field, plus 32 bits of data are specified with a single
uncached write operation.} 
\label{fig:expressmsg-simple-format}
\end{figure}

Message reception works in a similar way.  A load instruction to an
\express/  RxQ address,  automatically causes the consumer pointer to
be incremented and the message source, tag, data to be returned.
An empty queue causes a
special (configurable) empty message to be returned.
Microprocessors that
support a doubleword read with a single atomic load instructions are
also threadsafe for message reception.  In other machines, two load
instructions are required.

\bigskip\noindent{\bf \tagon/ messages:} 
The \tagon/ message mechanism extends the \express/ message mechanism
to allow additional data to be appended to an out-going message.
Additional address bits are used to specify an offset into the message
space that contains one or two cache lines of data to be appended to
the express message.  Once again, the \sp/ may have to reclaim these
cache lines for launching the packet into the network.  The
decoupling of the header from the message data, allows message data to
be located in non-contiguous addresses.  This is useful in coherence
protocols when sending a cache-line of data between sites as well as
for multi-casting.


\subsubsection*{Multiple Message Regions and OnePoll}
%~~~~~~~~~~~~

Finally we note that {\em multiple message queues} can be supported
just by allocating different ranges of physical memory addresses to
different queues. The appropriate semantics for each type of queue is
implemented under the control of the \sp/.  Some control
over the virtual to physical page mapping in the \ap/ is required.  In
particular, when a process is assigned a transmit or receive queue and
allocated a region of virtual memory, the OS must ensure that this
region is mapped to the appropriate region of physical memory with the
correct semantics.

Often there is need to poll several queues, and service messages from
them according to some priority. This can be a fairly expensive
operation without hardware support. 
A small extension of the \express/
message receive mechanism, the {\em OnePoll} mechanism, is provided
for this purpose.
Specifically, an application registers a set of queues in
priority order to the OnePoll unit.  A load from the ``one poll'' address
causes the \sp/ to examine each queue for non-empty status. As soon as one
is found, it is used to supply the data to the load.  If all are
empty, a special programmable empty message is enabled.
Basic messages can also be included in the OnePoll, by returning a
special \express/ message that identifies the chosen Basic message
queue that is non-empty, and the values of its status pointers.


\subsection{Meeting the Shared Memory Requirements}
%~~~~~~~~~~

The cache coherent distributed shared memory implementation requires
cooperation with the local operating system.  When the OS maps virtual
memory addresses corresponding to system-wide global shared memory
addresses to physical page frames, the NIU must be informed of the
correspondence in order to maintain its inverse map from physical
memory to system-wide memory.  Some frames correspond to NIU slave
space, while others correspond to DRAM locations that are snooped by
the NIU.

A large, sparsely accessed shared memory is best implemented as NUMA,
which is mapped to slave space.  A cache line miss or eviction by an
\ap/ is serviced by the \sp/.  The \sp/ may access local DRAM if it
is the home site or make a request to a remote site for a cache line
to satisfy a transaction.

When there is sufficient DRAM to support local copies of active shared
memory pages, it is efficient to treat the DRAM as a level 3 cache
using an S-COMA implementation \cite{stenstrom92}.  The coherence
protocol is divided into a hardware part that specifies the agent
responsible for the transaction and a firmware part that executes on
the \sp/.  For each cache line, the NIU maintains its state, {\em
shared}, {\em exlusive}, {\em invalid}, or {\em other protocol}.  The
latter cache-line state satisfies the requirement for multiple
protocols in which all transactions are captured and forwarded to the
\sp/ for processing.  A function of the state and bus transaction
determines if the memory controller or the NIU is to respond to the
transaction.




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







