%======================================================================
\section{ Introduction }
\label{sec:intro}
%======================================================================

% \comment{Missing: the context of this work: NES for a cluster of SMPs.}

Highly efficient support for interprocessor communication on a general
purpose system requires mechanisms that adequately address the \3m/ of
message passing: {\em multi-granularity, multi-threading and
multi-tasking}.  While the performance of certain aspects of message
passing has improved with the introduction of direct user-level access
to network interface\cite{cm-5,Joerg92,Scott96} and the exploitation
of host system capabilities such as coherence on the memory
bus\cite{Mukherjee96}, architectural support for the \3m/ remains
inadequate.

% multi-granularity


Parallel and distributed applications exhibit a multitude of
communication granularity.  At one extreme, a control message that
conveys a simple request or an acknowledgment often amounts to no more
than a few bytes.  At the other extreme, block data transfers of many
kilobytes of data are common among coarse-grain parallel applications.
In general, the data of the smallest sized messages are transferred
between processor registers.  As message size increases, caches are
the source and desired destination and for really large messages, main
memory becomes the most likely repository.  The most efficient data
transfer mechanism depends on the message size and data location, \eg/
uncached write and read for very small messages, burst transfer on the
memory bus for cache-line sizes, and processor-external DMA for the
largest messages.

% When does multi-threading come into play?
% Why multi-threading environment needs special MP support. 
%  Get buffer, process, free buffer
%   ^--     and	      ---^ needs to be atomic
%  Arbitrary interleaving of these actions from different threads
%   to the same queue has to work.  

Multi-threaded execution environments are increasingly common and
message passing is a critical part of such environments.  Under the
common message-passing model of associating a transmit and a receive
queue to each process, the basic operations of send and receive each
consist of three steps: get a buffer, process, then release the
buffer.  When simultaneously executing threads share a common message
queue, the get buffer and free buffer actions must each be atomic.  At
the same time, arbitrary interleaving of such actions from different
threads should work correctly, and the action or inaction of one
thread must not block another thread.  Proper design of the hardware
network interface can efficiently handle these requirements, which
otherwise may require expensive software safe-guards such as locking
and message copying.

% Why time and space sharing important
% Why MP needs to provide support for it.  

If the use of high performance message-passing causes a dramatic
increase in context-switch overhead such as draining of the network
between context switches, then it is a poor design.  To move parallel
machines out of their niche as special purpose machines for ``Grand
Challenge'' problems to cost effective workhorses, flexible, efficient
support for multi-tasking is needed.


While few will disagree that the \3m/ are desirable in a message
passing system, most available parallel machines today fall short in
some aspects.  Machines usually provide only a single message passing
mechanism, have little hardware support for multithreaded access to
message passing primitives, and require a large overhead for context
switching (when it is available at all).

This paper argues that it is possible to build a cost-effective {\em
and high performance} parallel processing system from a cluster of SMP
workstations, a high-performance interconnection network, and a simple
well designed network interface unit.  A particular implementation
supporting the \3m/ is described in this paper and serves as the
proof of concept.  Subsequent sections describe how, within an
integrated message passing framework, multiple data transfer
mechanisms are utilized to efficiently support a diversity of
communication granularities.  The handshake between the application
code and the network interface unit is limited to atomic, independent
operations which are compatible with multi-threaded sharing.
Multi-tasking is supported with a multitude of hardware supported
message passing queues, and virtual destination queue names.

The contributions of this work are: 
\begin{itemize}
\item{
a memory-bus based message-passing interface supporting several 
data-transfer mechanisms, each suitable to different
message granularity, data location, and programming model.
}
\item{
the use of inherently atomic single uncached read or write at the
``commit points'' of message passing operations to achieve a
thread-safe interface.   
}
\item{
the use of hardware-enforced, private, virtual message destination
name space as a general, flexible means for enforcing protection and
facilitating job migration in a multi-tasking environment.  }
\item{
Direct support for a large number of message queues, all of which are
always active.  Efficient use of expensive resources through the use
of a queue hierarchy comprised of a small number of fast
resident message queues and a large number of slower non-resident
resources, with transparent, dynamic migration of a virtual queue
between them.  }
\item{
A low-overhead one-poll mechanism that returns the highest priority
message from a set of message queues.}
\end{itemize}

The organization of the paper is as follows.  Foundational material
related to message passing support by a memory-bus attached network
interface unit is presented in Section~\ref{sec:mp-on-mbus}.
Foundational material continues with an overview of \start/ Network
Endpoint Subsystem (NES) in Section~\ref{sec: arch}.  The heart of the
paper then follows in the next two sections.  In
Section~\ref{sec:voy-mech} the message queue organization describes
the virtual message queues, the translation mechanism, and
message-space protection.  The implementation of the two novel message
passing mechanisms, Express and Tag-on are then described in
Section~\ref{sec:exp-tagon}.  Estimated performance of the \start/
NES, obtained with a cycle-level accurate C simulator that has been
validated against the Verilog RTL model of the NES implementation, is
presented in Section~\ref{sec:performance}.  The timing demonstrates
that no single mechanism adequately addresses the range of message
sizes and execution model.  Related work is discussed in
Section~\ref{sec:rl-wk} before we conclude in
Section~\ref{sec:conclusion}.


%======================================================================
%                                 END
%======================================================================