%---------------------------------------------------------------------
\subsection{Express Messages}
\label{sec: short-msg}
%---------------------------------------------------------------------

% motivation: 
%    no weak memory problem
%    implicit handshake
%   -> low per-message processor overhead
%   -> low end-to-end latency
%   * automatic adding of source address. 

The Express message mechanism provides the ability to atomically
send/receive a message in a multi-threaded environment {\em without}
synchronization instructions, dramatically reducing the cost of
sharing network hardware between multiple threads and/or multiple SMP
processors.  It does so by enabling an entire message send/receive to
be performed using a single inherently atomic uncached write or read.
In order to maximize the data sent by an Express message, low-order
address bits are used for the logical destination address and
additional data, permitting almost 5 bytes of data to be sent with a
single uncached 4 byte write.  Such address bit stealing has been
proposed before\cite{Joerg92}, but we are familiar with only one other
machine (Cray T3E) that uses it.

A major challenge of the Express message design is to maximize the
amount of data transported by a message while keeping each compose and
launch to a single, uncached memory access.  The Express message
mechanism assumes that the (i) message send queue specifier, (ii)
message destination, and (iii) 5 bits of data are packed into the {\em
address} of an uncached write.  The NES automatically transforms the
logical destination into a message header and appends the 5 bits of
data in the address to the 32b of written data to complete the \arctic/
message.  A diagram showing a simplified format for sending and
receiving Express messages is given Figure~\ref{fig:
expressmsg-simple-format}.  Additional address bits can be used to
convey more information but consumes a larger (virtual and physical)
address space which can negatively impact TLB's if the information
encoded into the address bits do not exhibit ``good locality''.
Alternate translation mechanisms such as PowerPC's block-address
translation mechanism\cite{ppc-arch94} can mitigate this problem, but
such mechanisms are highly dependent on both the processor
architecture and OS support.

\begin{figure}
\illustrationpercent{shmsg-simple-format}{35}
\caption{Express Message Formats} 
\label{fig: expressmsg-simple-format}
\end{figure}

% Squeezing information into the message: encoding of information in
%  address bits; 

To reduce the data read by a receive handler, the NES reformats a
received Express message packet into a 64 bit value as illustrated in
Figure~\ref{fig: expressmsg-simple-format}.  A receive can be
accomplished with a 64 bit uncached read into an FPR.  The data is
subsequently moved into GPRs via (cache) memory\footnote{PowerPC does
not support 8 Byte load into a pair of GPRs nor direct data transfer
between a FPR and a GPR.}.  Alternatively, two 32 bit loads into GPRs
can be issued to receive the message.

The addresses for accessing Express message queues do not specify
specific queue entries.  Instead, the NES provides a FIFO push/pop
interface to transmit and receive Express messages.  When a processor
performs a write to enqueue the message, the NES provides the
necessary buffer address to put that message into NES SRAM.
Likewise, when the processor performs a read to receive a message; the
NES provides the necessary SRAM address from which to read the
message.  Speculative loads from Express message receive regions are
disabled by setting the page attributes appropriately\footnote{In the
PowerPC architecture, disabling speculative loads is done by asserting
the guarded bit.}.  When an application attempts to receive a message
from an empty receive queue, a special Empty Express message, whose
content is programmable by system code, is returned.  If message
handler information is encoded in the message, such as in Active
messages\cite{vonEicken92}, the Empty message can be treated as a
legitimate message with a ``no action'' message handler.

%Unlike for receiving, the use of producer and consumer pointers is
%required for transmit queues to ensure that they do not overflow.

Because interaction between application code and the NES occurs only
through single uncached accesses, the actions are inherently atomic.
The Express message interface is thus thread-safe, and multiple
threads of a single job running simultaneously on an SMP can shared an
Express message queue without extensive mutual exclusion locking.

%---------------------------------------------------------------------
\subsection{\tagon/ Messages}
\label{sec: tagon-msg}
%---------------------------------------------------------------------

% motivation:
%    CCDSM transportation of data 
%    non-contiguous msg data source; possibly different SRAM bank
%    similar savings as short message, with additional payload
%   -> low per-message processor overhead
%   -> low end-to-end latency

The \tagon/ message mechanism extends the Express message mechanism to
allow additional data from NES SRAM to be appended to an out-going
message.  The \tagon/ message mechanism was designed to eliminate a
copy if message data was already in the NES's SRAM.  It is especially
useful for implementing coherent shared memory protocols, and for
multi-casting a medium sized message.  It is also thread-safe.  As
composed by an application, a \tagon/ message looks similar to an
Express message with the addition that several previously unused
address bits now specify the SRAM location where the additional 1.5
cache-lines or 2.5 cache-lines of message data can be found.  The
address field is kept small by specifying only an offset from a
programmable base address known to the NES, so that it will fit within
the limited size of an Express message.

At the destination NES, a \tagon/ message is partitioned into two
parts that are placed into two separate queues.  The first part is its
header which is delivered like an Express message, via a queue that
appears to be a hardware FIFO.  The second part, made up of the data
that is ``tagged on'', is placed in a separate buffer similar to
a Basic message receive queue in that it utilizes explicit buffer
deallocation.

\tagon/ messages have the advantage of decoupling the header from the
message data, allowing them to be located in non-contiguous addresses.
This is useful in coherence protocols when shipping a cache-line of
data from one site to another.  Suppose the sP is responding to
another site's request for data.  In \start/, this is achieved by the
sP first issuing a command to move the data from aP-DRAM into aSRAM,
followed by a \tagon/ message that ships the data to the requester.
In addition to the cache-line of data, a \tagon/ message inherits the
37 bit payload of Express messages which can be used in this instance
to identify the message type and the address of the cache-line that is
shipped.  Cache-line data may also be brought into the NES without the
sP asking for it, \eg/ the aP's cache may initiated a write-back of
dirty data.  In such cases, \tagon/ message's ability to decouple
message header and data allows the data to be shipped out without
further copying.

\tagon/ messages are also useful for ``specialized'' multi-casting.
To multi-cast some data, an application first moves it into NES SRAM.
Once that is done, the application can economically send it to
multiple destinations using a \tagon/ message for each one.  Thus,
data is moved over the system memory bus only once at the source site,
and the incremental cost for each destination is an uncached write to
indicate a \tagon/ message.

\subsection{OnePoll Implementation}

By extending the Express message receive mechanism slightly, \start/
provides the OnePoll mechanism, the ability to poll from multiple
queues {\em simultaneously}.  The NES implements the Express message
polling mechanism with internal pointers that generate the SRAM
address from where to read an Express message.  Empty message is thus
implemented with a dedicated buffer in the SRAM containing the Empty
message.  It is straight forward to extend this to choose an SRAM
address from among those of several queues, based on whether they are
empty/non-empty, and their relative priority.  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.
