\documentstyle{article}

\oddsidemargin 0in
\textwidth 6.5in
\textheight 9in


\title{Designing A Deposit Model Interface For Diverse Needs}
\author{Peter A. Dinda}

\begin{document}

\maketitle

\section{Essential Properties}



In the message passing paradigm, the combination of the application 
generator, the application, and the message passing system performs a 
series of steps to accomplish a communication.  For a single source node, 
these steps, ignoring synchronization, include:
\begin{enumerate}
  \item{For each target node
        \begin{enumerate}
             \item{Creating a mapping from local to 
                   remote addresses in some form}
             \item{Casting that mapping into an efficient form}
        \end{enumerate}}
  \item{Combining these efficient mappings}
  \item{Scheduling the communication represented by the combination}
  \item{Casting the communication into a hardware-dependent form}
  \item{Performing the communication}
\end{enumerate}
The division of these steps between generate-time and run-time depends on 
the amount of information available at generate-time and the capabilities 
of the application generator.  Unfortunately, many conventional message 
passing systems implicitly perform most of these steps at run-time below a 
single level interface with ``mailbox''-style semantics.  While this 
greatly simplifies the task of the parallel programmer, it often forces 
sophisticated application generators to defer steps to run-time that could 
be performed at generate-time.  To empower application generators, we have 
found that a low level hardware data transfer mechanism, such as {\em put}, 
combined with separate, minimal synchronization is ideal because the 
combination permits us to perform many of the steps at generate-time and to 
avoid extraneos synchronizations.  We call this the {\em deposit model} of 
communication.However, this is not a complete solution because when little 
information is available at generate-time, decisions must be defered to 
run-time, where a higher level interface is desirable.

This paper defines a single message passing interface for deposit model 
message passing that satisfies the needs of diverse application generators 
and applications.  The key to this {\em unified} interface is that it is 
layered, multi-customer and multi-entry.  The interface is {\em layered} 
because the steps enumerated above are exposed and must be explicitly done.  
It is {\em multi-customer} because it can be used to perform steps at 
generate-time as well as run-time.  Finally, it is {\em multi-entry} in 
that any step up to mapping the communication into a hardware-dependent 
form may be done without using the interface.

systems hide many of these steps below a simple single level 
interface, which often forces additional data copying in order to arrange 
application data into a form suitable for the interface.  Many interfaces 
make it impossible to describe, even in a hardware-independent way, a 
scatter or gather map, which makes it difficult for the message passing 
system to make full use of hardware that supports scatter/gather.  Even 
when such a facility is provided (such as for sends in PVM), the interface 
may not make it possible for the system to know precisely when an internal 
representation of the communication can be mapped into a hardware-dependent 
form, short of doing it as part of the actual performance of the 
communication.  Further, the interface may make it impossible to let the
system know that a communication will be performed again, making it 
difficult to amortize the work the system has already performed.

..
force the steps to be performed at 
run-time.



\section{Additional Properties for Deposit Model}

In deposit model message passing, essentially no semantic sugar is
applied to the steps enumerated above.  Synchronization must be
explicitly done and correctness depends on the ability of the
programmer or application generator.  The interface for deposit model
should have several additional properties beyond those described in
the first section:
\begin{itemize}
  \item{The interface should have great descriptive power, but
        at no loss to internal representation efficiency.} 
  \item{The interface should make it clear when the system can map
        communications unto the communications hardware.}
  \item{Amortizing communication steps should be easy.}
\end{itemize}

The interface should allow the caller to describe the local to remote
mapping of a point-to-point communication in a manner that is most
natural for the caller, while making it possible for the system to
internally represent the mapping in an efficient manner.  In other
words, the interface should make it possible for the system to find
and exploit contiguity in the mapping, no matter how the caller
describes it.  Most current communication interfaces make explicit
that only a ``buffer'' - a contigious chunk of data - can be
communicated.  This necessitates a copy stage for many common kinds of
communications and is especially insideous in that it provides no
mechanism for using hardware gather/scatter facilities.

Indeed, Second, the interface should require a caller to indicate when he has
finished specifying a communication.  This is necessary to give the
system a natural point at which to map the communication into a form
that makes the best use of the available communications hardware.

Finally, the interface should make it possible to amortize the cost of
composing a communication






...

\end{document}