Subject: mpi

From: Charles Simmons <[email-masked]>
Date: Sat, 16 Jan 93 02:21:14 PST

Dear Sirs,

Over the past 4 years, some of us at Oracle have been addressing many
of the same problems that you are addressing in your MPI effort.  We
have approached the problem from a C/Unix/Systems Software point of view
instead of a Fortran/Scientific Software point of view.  We learned of
your effort from Sandia, whom we are hoping to work with in developing
systems software for MP machines, and the communications interface will
be a substantial part of this effort.

I sent the following comments about MPI to Jack Dongarra.  He suggested
dropping the note on the 'pt2pt' mailing list.  My primary hope is that
my radically different background and point of view will stimulate new
ideas.  My expectations, however, are that you will find me obnoxious
and ask me to go away. :-)

Cheers, Chuck Simmons
[email-masked]

General Comments
----------------

The proposed interface specification is at best disappointing.  From
our point of view, it essentially standardizes and extends the
existing nCUBE model of a message passing interface.  We explicitly
rejected this model two years ago.  In this document, I'll describe
why I think this interface model is inadequate.

The most important aspect of the proposed standard is its lack of
reference to prior related work.  Communications interfaces have been
standardized before.  Thus, the most important question that the
proposed standard must address is: Why does no existing interface meet
the requirements of our applications?  Associated with this are the
questions: What concepts can we steal from existing interfaces?  What
can we learn from past mistakes?  The current work on the MPI
interface appears to be occuring in a vaccuum, ignoring prior work.

The introduction to the draft standard states: "The main advantages of
establishing a message passing standard are portability and
ease-of-use."  If that is the case, then the MPI effort is seriously
misguided.  For example, the existing TCP/IP standard is far more
portable and easier to use than MPI will ever be.

However, I would agree that TCP/IP is not adequate as a communications
interface for an MP machine.  The reason for this is that MP machines
provide relatively high-bandwidth low-latency communications.  To take
advantage of this, a very lightweight communications protocol is
required.  We first need a highly efficient communications interface;
we then need a portable and easy-to-use interface.

An efficient communications interface needs to provide the following
properties: (1) We require the ability to copy messages from a user
address space directly onto a wire without an intervening memcpy() of
the message into a system buffer.  Similarily, we require that
received messages be able to move from a wire into a user address
space without an intervening memcpy().  (2) We require that messages be
packetized.  That is, in TCP/IP, individual message packets are
concatenated together at the sender and sent out as a stream of data.
This requires the receiver to parse the incoming data stream to
recover the individual packets.  In an efficient interface, we want
the packet boundaries to be preserved.

Once we have outlined our requirements from the communications
interface, the next question to ask is whether we are ready to
standardize on an approach.  Standards bodies work best when they
standardize existing work, and work worst when they attempt to design.
Standardizing too early on an inferior interface will impede research
efforts to improve the interface, and additional work will be needed
when it becomes time to standardize the desired interface.

If it is decided that a standard is desired, then the scope of the
standard needs to be carefully delineated.  A reasonable scope is that
of defining a communications interface at about the ISO network or
transport layer.  Unfortunately, some of the text in the draft
standard suggest that some of the researchers want to address all of
the issues associated with building an MP operating system.  For
example, section 5 refers to creating and destroying processes and to
addressing distributed computing in a heterogeneous environment.
Appendix A contains routines that are completely unrelated to
communications, and which may well conflict with other existing
standards, or which are already well defined in other existing
standards.  (Consider, for example, the date and time routines.
Compare and constrast these to functionality provided by ANSI C and/or
Posix.)  In general, most of the draft standard stays within a reasonable
scope.  Attempts to extend the standard beyond that reasonable scope
should be brutally (:-) suppressed.

The core issues of the standard are:

1) Point-to-point communications.  This is the heart and soul of the
standard.

2) Communications amongst multiple instantiations of a single program
(a group or collection), and communications between these collections.
This is a reasonable topic to explore since these collections will be
common entities on MP machines.  However, this is far less important
than point-to-point communications.  Given a good portable interface
for point-to-point communications, an application can fairly easily
implement completely portable and reasonably efficient inter- and
intra- collection communications.

3) Reliable messaging and sequencing of messages.  This is, for the
most part, explicitly ignored by the draft standard.  However, this is
far more important than (2).  As mentioned before, applications don't
need (2) to be standardized in order to be portable.  However, it is
extremely difficult to write the code needed to provide robust,
efficient reliable messaging.

4) Threads (aka "Communications Contexts").  For the most part, this is
orthogonal to communications.  Threads need to be addressed to the extent
that the communications interface model must be capable of coexisting
with a reasonable threads implementation.

In summary, the draft standard should contain a section describing the
scope of the standard.  Issues such as heterogeneity, performance tracing,
parallel I/O, process creation, load balancing, and environmental queries
should be placed explicitly outside the scope of the standard, except to
the extent that the standard needs to coexist with these features.

[Note:  On page 3, a reference is made to dynamic load balancing.  The
interesting problem of dynamic load balancing from the communications
interface point of view is that some addresses known to some processes
may become invalid at arbitrary points in time.  The operating system
may need to be able to forward messages that were sent to an obsolete
address.]

Specific Comments
-----------------

My specific objections to details of the MPI standard fall into
the following areas:

1) Reliability and sequencing.  I feel that the standard should pay far
more attention to these subjects.  Reliability and sequencing of messages
are extremely important in industrial strength applications.  Because of the
importance of this area and its difficulty of implementation, the standard
should pressure hardware vendors and operating system vendors to provide
this functionality.

On page 6 of the draft standard, for example, it is explicitly allowed
that an operating system may discard a message if that message would overflow
system buffers, and the operating system need not inform the sender that
the message has been discarded.  This immediately requires most applications
to make use of inefficient algorithms to detect when a message may have been
discarded and retry the send of the message as well as to detect when a
message has been successfully received but also retried.  This is so onerous,
that we have asked nCUBE to implement hardware for their next generation
system so that when an OS receives a message, it can immediately return
one of the following stati to the sending OS:  message accepted; message
tossed due to parity error; message tossed due to lack of space.

Allowing unreliable messages to be implemented encourages the implementation
of unreliable applications.

2) The mechanisms used to receive a message are inefficient.  In
particular, many applications make use of variable length messages.
The current proposal only works well for fixed length messages.  In
the face of variable length messages, the current proposal requires
that an application either over allocate storage; or it requires that the
application allow the OS to buffer the message, and then the application
will probe for the message to determine the length, allocate a correctly
sized buffer, and copy the message into the new buffer.

Essentially, we want the OS to be able to copy messages off of a wire
directly into user address space, so that it is then easy for the
application to access variable length packets.  We are willing to
accept interfaces that require the hardware to implement paging for
efficient implementation.

3) The 'mode' argument on the send and receive functions is inefficient.
We strongly suspect that this argument will virtually always be a constant.
If that is the case, it is more appropriate to make this constant part
of the function name instead of an argument.  For example, the obvious
implementation of the mpi_csend() routine would look like:

	int
	mpi_csend (mode, buf, dest, type, len)
	...
	{
		switch (mode) {
		case NON_BLOCKING:
			return mpi_csend_blocking (buf, dest, type, len);
		case BLOCKING:
			return mpi_csend_nonblocking (buf, dest, type, len);
		case SYNCHRONOUS:
			return mpi_csend_synchronous (buf, dest, type, len);
		default:
			return (save_errno, -1);
		}
	}

	static int
	mpi_csend_nonblocking (buf, dest, type, len)
	...
	{
		trap to os;
		save any error;
		return value;
	}

	static int
	mpi_csend_blocking (buf, dest, type, len)
	...
	{
		int msgid;

		msgid = mpi_csend_nonblocking (buf, dest, type, len);
		mpi_wait (msgid);
		return status/length sent;
	}

	...

The costs of this approach are:  (A) An extraneous error condition
when the value of 'mode' is out of bounds.  Making the mode part of
the function name allows this error to be detected at compile time.
(B) Additional cpu cycles wasted passing an additional argument to
various routines.  (C) Cpu cycles as we decide which piece of code
to execute in response to the 'mode'.

Further, we take the point of view that the non-blocking operations
are of fundamental importance, and that the other modes of operation
are relatively minor, uninteresting envelopes around this fundamental
operation.

4) The send and receive routines for scatter-gather messages ignore
prior work.  Consider, for example, the closely related Unix readv()
and writev() operations.  These are specified as:

	int readv (int fd, struct iovec *iov, int iovcnt);

Since an 'iovec' structure is already defined, this structure should
be used instead of inventing a new paradigm that separates this into
two distinct arrays.  In particular, the draft standard pretty much
requires system software to perform an expensive translation to convert
iovec's into separate arrays.

[Note also that we consider the sending of a contiguous message as
a relatively uninteresting envelope around the more fundamental transmission
of a scatter-gather message.]

5) The send and receive routines specify the use of a <pid,type>
pair of arguments.  At a conceptual level, these arguments are a single
concept:  the address to which a message should be sent (or from which
the message should be received).  This approach has numerous problems:

	A) Passing two arguments to specify an address is slower than
	passing a single argument.

	B) This implies an implementation whereby each process has one
	message receive queue.  To pull messages off this queue in an
	order other than that in which the message was received requires
	a potentially time-consuming queue scan to search for a desired
	message.  A much better approach would allow the OS to take a
	received message and quickly hash it to one of a few receive
	queues for a process.  Since the code that sends a message is
	generally closely related to the code that receives a message,
	the sender can make sure that it puts the message on a queue
	in such a fashion that the receiver will never be interested
	in anything other than the head of one of its queues.

	C) Allocation of message type constants by library code in
	a robust fashion is exceedingly difficult.  If message types
	are to be required, the standard must address the mechanisms
	that are to be used to allocate message types so that separately
	developed libraries are guaranteed to have no conflicts.

We prefer the concept of a "port".  Essentially, this allows a process
to ask the OS to create another receive queue for the process.  Sending
processes then send messages to a specific queue.  A receiving process
can retrieve a message from the head of a specific queue, or it can use
a routine similar to the Unix select() system call to provide a bitmap
of interesting queues and retrieve a message from the head of one of these
queues.

Taking the above into account, we would then specify the interface
as:

	/* non-blocking scatter/gather recv */
	int mpi_recv (port_t local_port, struct iovec *iovecp, int iovec_len);

	/* blocking version of the above */
	int mpi_recvb (port_t local_port, struct iovec *iovecp, int iovec_len);

	/* synchronous version of the above */
	int mpi_recvs (port_t local_port, struct iovec *iovecp, int iovec_len);

	/* vector versions of the above */
	int mpi_recvv (port_t local_port, void *bufp, int blklen, int stride,
			int nblks);
	int mpi_recvvb (port_t local_port, void *bufp, int blklen, int stride,
			int nblks);
	int mpi_recvvs (port_t local_port, void *bufp, int blklen, int stride,
			int nblks);

	/* contiguous versions of the above */
	int mpi_recvc  (port_t local_port, void *bufp, int buflen);
	int mpi_recvcb (port_t local_port, void *bufp, int buflen);
	int mpi_recvcs (port_t local_port, void *bufp, int buflen);

Also, in the above, the vector versions of the above routines may need
additional work.  We envision an rpc protocol whereby an rpc header is
prepended to a vector that is to be scattered.  The application would
like to receive the rpc header into one buffer and then scatter the
vector into numerous locations.  The most general approach would be
for the primitive operation to specify a list of arrays into which the
received buffer is to be vector scattered.

For mpi_infos() and mpi_infot()...  Here you are addressing the problem
of how to handle an OS header that is prepended to every message.  We agree
that the general problem is somewhat tricky.  Which is probably why the
proposed implementation has some constraints on it that are less than
trivially easy to use.  Note that in a C program running on Unix, the
application may need to disable signals before it calls a recv routine,
and re-enable the signals after calling a routine to retrieve header
information.

One question that needs to be answered is the purpose of this header
information.  If the purpose is application specific, then perhaps
the application should have embedded this information in its RPC header.
(Our most generally used RPC protocol does this.  This approach also
allows a thread context pointer to be easily embedded in the message
and appropriately retrieved.)  If the purpose of this header is for
security and verification that a sender has permission to perform an
operation, then the simple source/type information available here is
probably inadequate.  (The existing Unix paradigm is to provide a
cred_t structure in this header that specifies the credentials of the
sender.  This header information is sufficiently burdensome that
an application may want to tell the operating system whether or not
to attach credentials information to each message.)

For mpi_probe(), we strongly desired both blocking and non-blocking
versions of this.  The non-blocking version simply tests for the presence
of a message and returns.  The blocking version blocks until a desirable
message is present.  Consider again the select() system call which
provides for both of these functionalities as well as the ability to
specify a timeout on the blocking version of the operation.

I'm not qualified to comment on groups since we don't use those
much, and when we do, we completely ignore little things like topology
and locality.  However, lack of qualification never stopped me before...

We've been toying with the idea of an "array port".  The concept is
not well defined.  For certain types of applications, we may be able
to create a port in a number of processes such that the ports have
the property that the bit pattern of one port is easily computable from
the bit pattern of another port.  The primary goal here is to use
a very small amount of storage in each process to specify the addresses
of all processes.

I would appreciate a lot more information about the intended use
of groups.  Certainly the proposal is far more complicated than anything
I would ever use.  Also, it wouldn't work for things that I would use.

In particular, when I use a group, the first thing that I am doing
is creating a list of addresses for all processes in the group.  I cannot
implement this using MPI_DEFRG.  In particular, the processes in the group
don't know the addresses of the processes in the group until after all
processes have become part of the group.  Typically, what we do is have
one process in the group store its address in a well known location (a
nameserver).  Other processes in the group wait for the first process
to appear, and then they send their addresses to the first process.  The
first process generates the list of addresses and broadcasts it back
to all of the processes (now that all the processes are known).

Thus, the list of addresses is our canonical data structure.  Our canonical
operations are the routines that help create this data structure, the
routines that help us broadcast the data structure, and the routines that
allow us to communicate pt-to-pt to an indexed address in the data structure.
This approach is easily extended to allow processes outside the group
to communicate with processes inside the group.

The mpi_*unpack routines specify that the 'msg' argument is an output
argument.  It should really be an input argument.

For the general pack/unpack routines; again, using a 'struct iovec *'
instead of <int *nlist, int *ilist> would prevent conflicts with existing
paradigms.

For section A.4, this section is completely outside the scope of
the document.  The communications contexts essentially implement threads.
The communications routines should not specify how you get information
about threads, nor how you go about creating a new thread.  Also, the
PUSH and POP approach to communications and group contexts looks like
a design flaw waiting to bite.

In section A.5, the cpu,date,machine,infmn,time, and wall routines
are outside the scope of the document.  The date and time functions
are particularly suspect.  Compare then to the ANSI C and Posix routines
for manipulating the date and time.

The mpi_etext and mpi_error routines are reasonable.  Note that in our
heavily layered applications, we will constantly need to convert
mpi_error codes into Unix error codes, and it might be nice if the MPI
error handling paradigm was better integrated into Posix error
handling.  (All we care is that in addition to implementing mpi_error
and mpi_etext, the implementation set 'errno' to a reasonable value.)

Note that it is not at all clear that communications contexts will
work except for in highly restricted circumstances.  They are less
general than either threads or ports.  In fact, I suspect that ports
can provide all the needed functionality of communications contexts,
and message types, and pids with less hassle.

---

From: [email-masked] (James Cownie)
Date: Tue, 19 Jan 93 16:36:37 GMT

Gentlepeople,

Chuck Simmons has raised some interesting issues, with which I have a
great deal of sympathy.

The original messaging model which we implemented on our machines (and
which we still support, and expect to continue to support) is in
exactly the vein which Chuck is asking for (and has been used for an
Oracle port !).

In particular CSN supports
	1) multiple end points for communication in a single process
	   (know as "transports")
	2) No tagging of messages
	3) No system buffering, but the ability for users to queue
	   multiple non-blocking receives on a transport, thus
	   providing the buffering they require.
	4) Send and receive by struct iovec. (As Chuck observes, the
	   implementation ends up building an iovec (on the stack) for
 	   the simpler forms)
	5) Both blocking and non-blocking tests for I/O completion.
	   (our test actually has a timeout value).
	6) The ability to pass transport addresses around the machine
	   without the system being involved.
	7) A standard name server service to associate textual names
	   with transport addresses. 

If people are really interested then I can probably send the man pages.
(Though this is not the main point of this note).

HOWEVER (and this is one of the points) although this system had
clean, specified semantics and a fast implementation (on our
hardware), it hasn't helped to sell machines, and we have now produced
an NX style interface as an alternative.

I think that the problem with popularising such an interface among
users is that it appears to do less for them than a model with
implicit buffering, and is therefore harder to start to use. The fact
that it allows them greater control and can ultimately produce higher
performance is not their immediate concern and does not therefore
count for much. Many FORTRAN programmers in particular to do not wish
to be concerned with "system programming issues" like buffer management.

I would certainly like MPI to be able to support such an interface (so
that we can achieve the higher performance it offers, and also make
MPI applicable in non-scientific application areas). (Though those who
were present in Dallas will have noted that I wasn't trying to push
such an approach there, mainly because I think it's a lost cause. NX
style is what we have to live with...) 

(Second point coming up...)
However it crosses my mind that there may be some potential for
embedding such an interface within the MPI model. (This is a vague
thought, but I'm throwing it out so others can think about it as
well).

Observe that
1) Marc's persistent communication descriptors seem to remove the tag
   matching requirement (though they're still rather vague !)
2) One way of viewing contexts would be to implement a context as a particular
   queue of messages (or in other words an entirely separate
   communication end point) within a process.
   (The implications of this for contexts would be
	a) contexts must be declared before use
	b) their number may be limited 
	c) they should be freed after use
   )
The combination of the two things could then come somewhere near to what Chuck is
asking for...

-- Jim
James Cownie 
Meiko Limited			Meiko Inc.
650 Aztec West			Reservoir Place
Bristol BS12 4SD		1601 Trapelo Road
England				Waltham
				MA 02154

Phone : +44 454 616171
FAX   : +44 454 618188
E-Mail: [email-masked] or [email-masked]