%======================================================================
\section{ Message Passing on the Memory Bus }
\label{sec:mp-on-mbus}
%======================================================================

The message passing abstraction covers a wide range of application
needs.  As a foundation to the rest of the paper, a short overview of
our assumed message passing software model is presented. A similar
short overview is then presented of the hardware considerations for
message passing implementations.  A final short overview of
straight-forward implementations for messages concludes this section.

We focus on the software model in which there is a set of ports in the
system with a transmit and receive queue associated with each port.  A
message space consists of a set of (dynamically) connected ports.  The
two basic message passing operations, send and receive, each consist
of three steps: get a buffer, process, then release the buffer.  For a
send operation, the buffer, once acquired, is filled with the message
data, and the release of the buffer indicates that the message is
ready to be sent. Once a nonempty buffer is acquired from a receive
queue by some application, the message data in the buffer is examined.
The release allows the buffer to be used by another message.  If
several threads are concurrently sharing a message queue, mutual
exclusion is needed to ensure correct operation.

%----------------------------------------------------------------------
\subsection{Assumptions}
\label{sec:design-sp}
%----------------------------------------------------------------------

This paper focuses on hardware consisting of a cluster of symmetric
multiprocessor (SMP) workstations, connected with a high-bandwidth,
low-latency, multi-staged interconnection network.  A network endpoint
subsystem (NES) interfaces the network to the {\em memory} bus of each
SMP.  The design of a low-latency, low processor overhead, high
bandwidth message passing system requires exploiting the strengths of
the commodity hardware and avoiding the weaknesses inherent in the
microprocessor's design.  The following is a list of key SMP
characteristics to consider.  (Examples are drawn from a PowerPCs 604
based SMP to provide concrete illustrations.)
%
\begin{enumerate}
\item{ 
Off-chip accesses are expensive.  Bus transactions require multiple bus
clock cycles and a processor clock cycle is typically three or more
times faster, so any off chip access translates to tens of processor
clock cycles.  }
\item{ 
If sufficient data is involved, burst transfers are more efficient than
uncached accesses.  }
\item{
Main memory has long access times -- \eg/ for a typical
PC-class machine, read latency is about 10 bus clock cycles 
and write latency is half of that.}
\item{ 
The weak memory model, found increasingly among today's processors,
often demands the use of memory barrier instructions. These can be
expensive \eg/ SYNC on the PowerPC 604 was measured to require 15 to 20
processor clocks.  }
\item{
Cache management instructions, when available in user mode, are
expensive.  On the PowerPC 604, a single cache-line Flush takes around
20 processor clocks.  }
\item{
Coherent bus protocol details, such as whether cache-to-cache transfer
is supported, are important to low level network interface unit design
choices.  }
\item{
Atomicity primitives for dealing with races between concurrent or
parallel threads are not cheap; a pair of
load-reserve/store-conditional instructions, commonly used in modern
microprocessor for taking a lock, takes over 30 processor cycles on
the 604 even under the no contention situation.  }
\end{enumerate}
%

\subsection{A Basic Message Passing Implementation}
 
A basic implementation of message passing support within a network
interface unit connected to the memory bus of an SMP exploits the
above architectural assumptions.  Thus, transmit and receive queues
consist of a {\em cacheable} message buffer region, and {\em uncached}
producer and consumer pointers.  The message buffer region is arranged
as a circular FIFO with the whole queue visible to application
software.  Message data is thus efficiently transferred over the bus.
The producer and consumer pointers are needed to indicate when a
message is ready to be transferred.  They are uncached so that a
pointer update immediately triggers processing, thereby avoiding the
need for full coherence.  A cache-line can either be actively flushed
from processor or externally fetched by the network interface unit;
the exact mechanism depends on the processor architecture.  Message
data cache-lines may be eagerly fetched before the length field in the
message header is read.

Although clever implementations of uncached pointers may imply atomic
updates, the above scheme is not thread safe due to the circular FIFO
management.  In a multi-threaded environment, the entire ``get buffer,
process, release buffer'' sequence may need to be executed within a
critical section.

 
%---------------------------------------------------------------------
\subsection{Implementation of Long Messages: DMA }
\label{sec: dma}
%---------------------------------------------------------------------


DMA is an efficient mechanism for moving contiguously located data
between the memory of one site and that of another.  Most of the
packetization and formatization of blocks of data required for
transmission across the interconnection network can be done by simple
hardware within the network interface.  All that is needed is a
mechanism for the processor to communicate the request to the network
interface unit.  A mechanism similar to the basic message passing one
outlined above is sufficient.

%----------------------------------------------------------------------
%                                 END
%----------------------------------------------------------------------