%% This section covers all aspects of messaging passing on *T-ng. 
%%   - what sort of service does this network provide?  
%%     * can basically regard it as lossless.  Hardware will detect
%%       most errors, but not able to correct them?   
%%     * no end-to-end flow control in hardware, only link level. 
%%       (if needed, further services can be provided in software by
%%        processor at the end-point)
%%     * if possible, relate to ISO/OSI level 2-3?  
%%     * some provision for multi-user environment.  
%%   - brief paragraph on organization of the router, latency, and
%%     throughput. 
%%   - description of NIU organization and services. 
%%     * where it sits and why. 
%%     * protection.
%%     * buffering in the NIU.  
%%   - intended modes of operation:
%%     * directly by compiled code.
%%     * dedicated network processor, implementing FUNi style source
%%       buffering and acknowledgement. 
%%     * implementing TCP/IP and more traditional form of
%%       communication. 
%%   - comparison with other styles of providing network support.  
%%     * I/O bus (micro-channel, PCI, etc.)
%%     * memory bus
%%     * also put in context of 88110MP design 
%%------------------------------------------------------------------------
\section{Messaging Support}
%%------------------------------------------------------------------------
\label{sec:msg-support}
%%------------------------------------------------------------------------

\start/'s user-mode message-passing capabilities are provided through a
tightly-coupled hardware network interface directly attached to each 620
processor's L2 cache interface.  Each NIU connects the 620 processor to an
Arctic\cite{Boughton94} packet-switched fat-tree network.  The NIU's
packet buffers can be memory-mapped into an applications address space.
Thus, user programs can send and receive messages, without kernel
intervention, by directly manipulating the NIU's packet buffers.  In
addition to standard networking protocols such as TCP/IP, other popular
message-passing layers such as PVM, MPI and Active Messages can be
implemented over \start/'s networking facilities, allowing \start/ to run
existing parallel programs that use standard protocols.

This section summarizes the Arctic switch fabric and describes the
NIU.  The Arctic network router chip and the modular fat-tree switch
fabric board is being developed at MIT.  while the functional design
of the NIU is a joint effort of MIT and Motorola.  However, the
detailed design and final implementation of the NIU are being carried
out by Motorola.

\subsection{Arctic Switch Fabric}

The Arctic routing chip, a successor to PaRC\cite{Joerg90} from the Monsoon
project, has been described in other documents\cite{Boughton94} and thus
will only be summarized here.  Its salient features follow.

\begin{itemize}
\item 4-by-4 packet-switched router capable of implementing a variety of
staged networks.
\item 320~{MByte/sec/full-duplex-link} 
\item Latency of 6 Arctic cycles per hop.
\item Up to 96 byte messages with a maximum payload of 88 bytes per packet.
\item Support for two virtual prioritized networks, allowing the
implementation of two-priority deadlock-free protocols on a single
network. 
\item Support for secure space partitioning.
\item Sophisticated buffer management, allowing it to sustain close to
its peak bandwidth.
\item Commercial-quality set of test, control and error handling
features.
\item 16-bit CRC for data and Manchester encoding for flow-control links to
detect errors.
\item Error rates low enough to ignore under normal operating conditions.
\item Hardware router-to-router flow control.
\end{itemize}

\subsection{Network Interface Unit}

To fully utilize the Arctic network, a high performance Network
Interface Unit (NIU) is required.  The \start/ NIU is situated on the
620's L2 interface to provide a low-latency, high-bandwidth path
between the processor and the Arctic network.  The NIU is optimized to
support short, frequent messages, common to most fine-grain parallel
computation.  Using the \start/ NIU, the overhead of receiving or
transmitting a message by a user-level process to/from the 620
general-purpose registers is conservatively estimated at 100 processor
cycles for an 88 byte message and lower for smaller messages, yielding
a bandwidth of roughly {120 MByte/sec}.  These numbers include some
synchronization instructions that may possibly be eliminated,
potentially doubling the maximum bandwidth and halving the minimum
latency.

\begin{figure}
\illustrationpercent{niuconfig}{80}
\caption{NIU/620 Configuration}\label{fig: niuconfig}
\end{figure}

The NIU design incorporates a dual-ported buffer connected directly to the
L2 interface of the 620 processor.  (see Figure~\ref{fig: niuconfig}.)  The
other port of the dual-ported buffer connects to the NIU's control logic
and datalink transceivers.  The 620 interacts with the NIU by reading and
writing to specific regions in the buffer.  As shown in Figure~\ref{fig:
niu interface}, the dual-ported buffer space is logically partitioned into
four data regions and one status/control region.  The four data regions are
as follows: transmit high priority, transmit low priority, receive high
priority, and receive low priority.  They are used to transmit and receive
two priorities of messages.  Each data region occupies two memory pages (8
KBytes) and can thus be individually protected by memory mapping.

The status/control region, located on a separate page, contains a
32-bit control word and a 32-bit status word.  The control word allows
the 620 to set or query the NIU state, while the status word contains
the NIU transmitter and receiver status bits, the ACD service request
signal and any state requested by the 620 through the control word.
Since the user does not need to access the control region of the NIU
for user-level messaging, this region of the NIU interface will be
mapped to a kernel page, protecting the NIU from user corruption.  All
relevant NIU internal states can be read and written by the kernel
through the control interface, allowing the network to be
context-switched.


\begin{figure}
\illustrationpercent{niuinterface}{80}
\caption{NIU/620 Interface Buffers}\label{fig: niu interface}
\end{figure}

Each transmit or receive data region is further subdivided into 64 packet
cells.  Each packet cell is 128 bytes large (two 620 cache-lines), enough
to hold a maximum sized (96 byte) Arctic packet.  Each data region is
jointly managed by the 620 processor and the NIU as a circular queue.  For
the two transmit buffers, the 620 processor acts as the producer of the
queue while the NIU serves as the consumer.  For the receive buffers, the
620 processor and the NIU reverse their roles as consumer and producer.

Each packet cell contains a v-bit to indicate whether it contains a
valid message.  Prior to storing a new message into the queue, the
producer must first poll the v-bit at the tail of the circular queue
to ensure the cell is not still holding a valid message.  If the v-bit
is invalid, the producer stores the message.  After storing the
message, the producer then marks the v-bit {\em valid} to indicate to
the consumer that the cell now holds valid data.  From the other side,
the consumer polls the v-bit from the head of the circular queue.
When the v-bit becomes {\em valid}, the consumer can proceed to
retrieve the message from the cell.  After retrieving the message, the
consumer needs to reset the v-bit to {\em invalid} to free the cell
for reuse.  With the use of the v-bit, there is no explicit exchange
of queue indices between the 620 processor and the NIU to manage the
circular queues.

For receiving a message, aside from polling on the v-bit at the head
of the receive queue, the user process also has the option of
configuring the NIU to interrupt the 620 based on various conditions
such as the arrival of a certain class of message.  This feature
allows the user program to avoid the overhead of polling the network
if it is known that messages arrive very infrequently.  If the high
priority network is devoted to the kernel, enabling the high-priority
arrival interrupt would be an easy way to signal a kernel message has
arrived.

The transmit cells takes on a rather awkward format (see
Figure~\ref{fig: transmit buffer}) due to the order in which
cache-line-writes go to the L2 interface.  Since the L2 interface is
only 128-bits wide (a quad-word) and cache-lines are 512 bits big,
cache-line-writes occur in four quad-word writes and always occur from
the first quad-word to the last quad-word.  In order to avoid any race
conditions, the v-bit is located in the fourth quad-word of a transmit
packet cell.  The packet header (including length and route), plus the
first 64-bit data of the outbound message occupy the rest of the
fourth quad-word.  The remainder of the outbound message data fills
the cell successively starting from the first quad-word of the cell,
skipping over the fourth.  In other words, the second through the
seventh 64-bit message words will occupy the first three quad-words of
the cell, while the eighth and successive data words will start on the
fifth quad-word of the cell.

\begin{figure}
\illustrationpercent{transmitbufconfig}{40}
\caption{Transmit Cell Packet Format}\label{fig: transmit buffer}
\end{figure}

The v-bit, packet status plus header, and the first 64-bit data word
of an inbound message is packed into the first 128-bit quad-word of a
receive packet cell (see Figure~\ref{fig: receive buffer}), rather
than follow the transmit format.  The remainder of the inbound message
data are stored contiguously on the successive word locations.  The
placement of the v-bit in the first quad-word is dictated by the way
reads are done on the 620 L2 interface.\footnote{The NIU and the 620
have to agree on the order in which the quad-words are written and
read, to ensure that the v-bit is valid only when the data in a cell
is valid.}

\begin{figure}
\illustrationpercent{receivebufconfig}{40}
\caption{Receive Cell Packet Format}\label{fig: receive buffer}
\end{figure}


