
%======================================================================
\section{Related Work}
\label{sec:rl-wk}
%======================================================================

The network interface unit in a parallel system can be located at one
of four places, each at a different distance from the processor: (i)
in the processor core; (ii) on a cache interface; (iii) on the
cache-coherent memory bus; or (iv) on the I/O bus.  

Though good for small to medium size messages, none of the on-chip (in
the processor core) network interfaces provide special bulk transfer
hardware.  Almost all these machines are proof-of-concept experimental
platforms where multi-tasking is rarely addressed.  Multi-threaded
sharing of message queue is not addressed except among the Dataflow
machines; these machines support only small messages sent and
(implicitly) received with individual instructions.  Examples of
processors with integrated network interfaces include
transputers\cite{Whitby-Strevens85}, the iWarp systolic
processor\cite{Borkar88,Borkar90}, dataflow processors like
Monsoon\cite{Culler90} and the EMC-R\cite{sakai89}, and hybrid
processors such as the MDP\cite{Dally92}, M-machine\cite{Fillo95}, and
the MIT/Motorola 88110MP\cite{Papadopoulos93}.

The Alewife\cite{Agarwal95} is an example of a network interface on
the L1 cache interface.  Alewife supports multi-part message
specification and its Sparcle processor provides hardware
multi-threading.  Race conditions during access to network interface
is prevented by disabling multi-threading during each message
interface access critical section.  
%Not much attention is paid to
%multi-tasking in Alewife.  
The design for StarT-NG\cite{Chiou95} proposed a network interface to
the L2 cache interface but only one message type is
supported.

Placing the network interfaces on I/O buses designed to accommodate
third party devices, is currently a popular approach.  Commercial
examples include machines like the IBM SP-1\cite{ibm-sp1} and
SP-2\cite{Agerwala95,Stunkel95}, and plug-in extensions like Myricom's
Myrinet\cite{Boden95} and DEC's Memory Channel\cite{Gillett96}, while
research efforts include Princeton's SHRIMP\cite{Blumrich94a} and
StarT-Jr\cite{Hoe94}.  Most I/O bus-based message passing support
utilizes main memory DRAM to house user-level message queues.  The NIU
delivers message between such queues on different nodes.  In some
designs, messages are sent out by writing directly across the I/O
bridge chip to the NIU.  Although these projects would like to provide
support for the three Ms, research efforts have so far been more
concerned about overcoming the challenge of traversing at least two
buses, and crossing one or more bridge chips before even reaching the
network interface.  With multiple user-level message queues housed in
main memory, most I/O bus based NIUs support multi-tasking fairly
well.  Multi-threaded access to the same message queue generally has
no special support.

%\comment{Say something about Utah Avalanche\cite{Swanson96}}

Our work is focused on network interface connected to the memory bus.
Many of the machines that support distributed shared memory locate
their network interface unit (NIU) on the memory bus.  Among them,
DASH\cite{Lenoski92}, Exemplar\cite{Exemplar93,Brewer95}, and
NUMA-Q\cite{Numa-q} do not directly support message passing.  Message
passing on the T3D\cite{Kessler93} is implemented with its remote
memory access and atomic fetch-and-add capabilities, the latter for
remote message queue space acquisition.  Message data is transfered
using the machine's shared memory capability.  Multi-granularity
support includes a bulk transfer engine, and special support for
barrier and Eureka synchronizations.  Its successor, the
T3E\cite{Scott96} provides more traditional form of message passing --
messages are launched from special off-chip E registers, and received
from buffers in main memory.  Support for multiple receive queues
facilitates multi-tasking in both the T3D and T3E.
FLASH\cite{Kuskin94} has a programmable memory controller, which can
be harnessed to implement a virtual memory mapped NIU.  Just about any
form of NIU can be implemented in firmware.  Thus far, their planned
message passing support appears to be the memory to memory bulk copy
form.  Typhoon\cite{Reinhardt94}, while having some hardware support
for message passing, is primarily a shared memory machine.

The {CM-5}\cite{cm-5} is a message passing machine with very
respectable performance for its time.  However, it does not handle
larger messages (messages bigger than a few words) efficiently, and
multi-tasking support, though present, is not flexible.  The
Paragon\cite{Paragon-91} uses a second processor at each node to copy
messages between the otherwise unprotected hardware network interface
and software message queues in main memory.  This provides protection
in a multi-tasking environment but introduces the overhead of
copying.
% -- a message can
%traverse the memory bus as many as three times on its way out of the
%sending node, and another three times on its way in.  It also requires
%polling by the coprocessor which introduces delays and extra bus
%occupancy.  
The Meiko CS-2\cite{Barton94} also has a message
coprocessor, and operates in a similar way as the Paragon, though its
design is more efficient in that the coprocessor connects directly to
the network.

More recent work by Mukherjee et. al.\cite{Mukherjee96} on Coherent
Network Interface (CNI), presents a nice and efficient network
interface.  The design however does not address the issue of sharing a
message queue among several concurrent threads.  It also does not
adapt the data transfer mechanism as communication granularity
changes.  Multi-tasking, though briefly mentioned, was not discussed
in detail.

Figure~\ref{tab: mp-machines-cp} provides a {\em very rough}
comparison of \start/'s message passing performance compared to other
machines.  Aside from \start/'s numbers, the numbers in
Figure~\ref{tab: mp-machines-cp} are reported by other researchers,
and were measured either with Active Message (AM)\cite{vonEicken92} or
Illinois Fast Messages (FM)\cite{Pakin95}, both of which are very fast
message passing libraries, and are taken from many
articles\cite{Liu94,Martin94,Liu95,Culler96,Chang96b,Hoe96,Karamcheti,Pakin95}.
It is impossible to conduct a completely fair comparison because the
machines are from different time periods, not all the measurements
reported are for the same message size (varies from zero to several
words of payload), and some implementations include sliding window
protocols to deal with lossy network hardware which also provides
flow-control as a side benefit.  Nevertheless, the table does provide
some insight into how \start/'s performance compares with these other
machines.

\begin{figure}
\begin{tabular}{|l|c|c|c|c|c|c|}
%
\hline
			        &	    &           & one-way        &	    &	 	&	\\
 				& processor & Interface & nearest        &  Send    &  Receive 	&  Peak	\\
\multicolumn{1}{|c|}{Machine}   &   speed   &  Location & neighbor       & Overhead & Overhead 	&  Bandwidth \\
			        &  (MHz)    &           & latency 	 & ($\mu$s) & ($\mu$s)	& (MByte/sec)\\
			        &	    &           & ($\mu$s)       &	    &	 	&	\\
\hline
%
\hline
{\it \start/ (AM)}		
&{\it 150} & {\it memory bus} & {\it 1.25} & {\it 0.13} & {\it 0.51} & {\it 140}\\
\hline
{CM-5} (CMAM)\cite{Liu94}     
& 33 & memory bus &  5.7  &   1.5    &   1.25   &    10  \\
\hline
Paragon (AM)\cite{Liu95} 	
& 50 & memory bus & 8.4   &   2.2    &   1.0    &   145  \\
\hline
Meiko CS-2 (AM)\cite{Culler96}
& 66 & memory bus & 10.8  &   1.7    &   1.6    &    39  \\
\hline
T3D (FM)\cite{Karamcheti}        
& 200 & memory bus &  10   & \multicolumn{2}{|c|}{4} & \NA \\
\hline
%----------
\hline
HP+Medusa (AM)\cite{Martin94}
& 99 & graphics bus & 10.15 & \NA     &   \NA     &    12  \\
\hline
%----------
\hline
StarT-Jr (AM)\cite{Hoe96}   
&120 & I/O bus    &  27   &   1.5    &   1.1    &    7 \\ 
\hline
Sparc20+ATM (AM)\cite{Chang96b}
& 50 & I/O bus    &  33   & \multicolumn{2}{|c|}{3} & 14  \\
\hline
SP-2 (AM)\cite{Chang96b}            
& 66 & I/O bus    & 25.5  & \multicolumn{2}{|c|}{4} & 34 \\
\hline
Sparc20+Myrinet(AM)\cite{Culler96} 
& 50 & I/O bus & 15.7 &   2.0    &   2.6    &    20 \\
\hline
Sparc20+Myrinet(FM)\cite{Pakin95} 
& 50 & I/O bus & 25   &    \NA    &   \NA     &    20 \\
\hline
%(?)Myrinet2 (FM)13.1 us(n)      <-- 4.4us -->                            17.5MB/sec
%\hline
%
\end{tabular}
\caption{ Message passing performance of several representative
systems.  \start/'s numbers are estimates obtained in the fashion
described in Section~\protect{\ref{sec:performance}}. }
\label{tab: mp-machines-cp}
\end{figure}

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