Subject: ready receive

From: [email-masked] (Steve Huss-Lederman)
Date: Tue, 6 Apr 93 10:07:19 EDT

We have now met three times in Dallas and each time we have had a vote
on ready receive.  The votes have been:

Jan: 13 Y   10 N
Feb: 20 Y   12 N
Apr: 10 Y   10 N

Given these votes, I assume that ready receive remains in the draft by
default.  However, since the discussion was limited at the last
meeting, I thought it would be useful to outline the arguments on this
topic.  That way, if we need to vote again, we can hopefully do it
quickly and with the pros/cons at hand.

Ready receive is a special type of send that tells the processor that
an appropriate receive has already been posted for this message.  On
some systems this allows the sender to transmit the message without
having to send system request/acknowledge packets (or significantly
reduces the number).  This effectively raises the bandwidth that the
user achieves on the system.  For example, on the Intel Delta ready
receive (forced type) can increase the bandwidth by over 20%.

An example of the use of ready receive is for a fan in/fan out
collection/distribution of information.  A standard algorithm would
use a tree structure to recursively collect the information at the
root node.  Then the inverse tree is used to distribute the
information back out to the other nodes in the tree.  The modification
with ready receive is to post an asynchronous receive for the fan out
step at each node before the node sends the data to the next node
during the fan in steps.  Thus, when the fan out occurs, the sender
knows that a receive is already posted and can use ready receive to
decrease the overhead associated with this step.

Some arguments for ready receive:

- it reduces system overhead for message passing on some systems

- variants of it are used on current generation systems (Intel NX)

Some arguments against ready receive:

- when improperly used a message can be lost.  worse yet, this may
only happen on a larger problem where synchronization is worse.  this
leads to users filling bug reports with the vendor.

- it is yet another variant of send and adds more calls to MPI

Now, IMHO:

Lots of things in MPI will fail if used improperly by the user.  Ready
receive is not unique in this fashion.  We left in asynchronous calls
for several reasons but if the user does not properly issue a wait
then he/she can get the wrong answer.  I don't think we should
penalize a knowledgeable user because some people may do the wrong
thing.

As for it being yet another call, I do have sympathize here.  However,
ready receive can simply do a standard send and that would comply with
the MPI standard.  Thus, on systems that don't care, the extra work is
minimal.  This is the same as the extra call for every regular call to
get profiling.  On the other hand, it can be a big win on some
systems and there the implementor can spend the time to do it right.
For these reasons I support ready receive (with a new name :-).

I hope this summarizes the arguments but fear I have left something
out.  I welcome additions and comments.

Steve

---

From: [email-masked] (Peter Rigsbee)
Date: Tue, 6 Apr 93 10:29:16 CDT

> receive (forced type) can increase the bandwidth by over 20%.

I think this is a good description of ready receive.  It matches the
description given in each meeting.

One thing that bothers me, and that is behind the reason I vote *against*
the feature, is that while the proponents say:
	"some systems [can benefit]"
they always mention the same example -- Intel systems.  No other vendor's
MPP or cluster system ever gets mentioned, nor any of the workstation 
packages.

Will ready receive be of benefit to other current or soon-to-be systems or 
packages?

I'll start.  I do not anticipate that ready receive will be of benefit to 
the CRAY T3D (MPP system).

As we all know, defining a standard requires balancing several opposing 
pressures.  I can live with MPI including a familiar, commonly-used 
performance feature even if our architecture may not be able to use it 
optimally.  But I dislike the idea of standardizing an uncommon feature 
that is only beneficial to one kind of system.  (Especially a competitor! ;-)

Thanks.

	- Peter Rigsbee
	  Cray Research, Inc.
	  [email-masked]

---

From: William Gropp <[email-masked]>
Date: Tue, 6 Apr 93 11:06:55 CDT

...

Why?  I've heard arguments that other systems operate in what I'll call 
receiver-probably-ready which may (or may not) reduce the need for
receiver-ready, but I have not heard anyone offer EVIDENCE that receiver-ready
will not help.  The only evidence that we have is that the one vendor that has
implemented it does see a significant performance improvement.  Because of the
strong assertion that receiver-ready makes about the communication, there is a
some reason to believe that any system could take advantage of the additional
semantic information, though it need not do so.  

Does anyone care to provide some evidence that ready-receive can not provide
additional performance on other systems?  
Bill

---

From: [email-masked]
Date: Tue, 06 Apr 93 18:23:57 -0700

First a little history of "force types", which is our form of ready receive.
It was first implemented on the iPSC/2 system to solve a flow control problem
which has not been discussed here and might have been specific to the NX
protocols. It had the side effect of being faster, and was used for that reason
in applications. Because it was useful, it was propogated to the iPSC/860 and
Delta systems where the performance effects were more pronounced. Since the
Delta system is effectively a prototype of the Paragon system, we expect to
continue to see a performance win.

We would certainly implement ready receive in MPI if it is part of the
standard. So, it will not be ignored in all implementations.

Certainly vendor input is valuable in assessing the (near-term) benefit of
including ready receive in the first version of MPI, but I think that users should
make the decision to keep it in or not. After all, it is a very small burden
for vendors; once implemented or ignored, it is done. The bigger question is,
will it be used and provide benefit enough to make it worth having.
Application writers should make the call.

Thats the meat of my comments, as a postscript I will try to motivate the
notion that ready receive is inherently advantageous in at least the simplest
implementations.

A compliant implementation of MPI should run this program. Otherwise, what
is the point in having tags (I oversimplify, that is a separate argument):

	1				2

	async send to 2, tag=1
	async send to 2, tag=2
	async send to 2, tag=3
					blocking receive from 1, tag=3

A simple implementation with no buffering must use a protocol where the
receiver somehow lets the sender know which message can be sent. Otherwise, if
the sender simply sent the first message (tag=1) and waited for a matching
receive, the program would deadlock because the receiver is blocked waiting
for the (tag=3) message and won't post any other receive until it comes in.

For simple implementations with buffering assume the message sizes are very
large (too large to buffer more than part of 1 message) and the same arguments
hold. Only complex protocols which can partly buffer messages can get around
the problem, and then one can simply increase the number of messages sent to
defeat the buffering, although this might not fall within the spirit of the
standard.

So, the argument is that, in general, a compliant implementation must use a
protocol where information travels from a receiving process back to the
sender. This is more true for simple implementations than complex ones.
Such a protocol incurs a minimum 2-trip penalty for at least some messages.

Ready receive semantics eliminate the need for this step. With ready receive,
the implementation does not have to use two or three trips, or does not have
to figure out how many trips to use. It just sends the message, and the
receiver gives an error or drops the message if there is no matching receive.

Paul Pierce

---

From: [email-masked] (Peter Rigsbee)
Date: Wed, 7 Apr 93 11:41:42 CDT

[email-masked] writes:
> including ready receive in the first version of MPI, but I think that 
> users should make the decision to keep it in or not. After all, it is a 
> very small burden for vendors; once implemented or ignored, it is done. 
> The bigger question is, will it be used and provide benefit enough to 
> make it worth having.  Application writers should make the call.

I agree that it is trivial to write a ready-receive send that just looks like
or invokes the regular send.  But that may not be the only cost involved.

To properly use ready receive, an application must ensure that the receive
is ready before the message is sent.  If the application would normally
be written in such a way that this just "falls out" (that is, you can simply
change a "send" to a "ready-receive send"), then I agree there is minimal
impact involved to the application.

But what if the application required special synchronization or was written
in such a way that some additional overhead was required in order to properly
use ready receive?  If the cost of this extra overhead is less than the
benefit from the ready receive, this would make sense.  

But now you have an application whose optimal performance *depends* on 
ready-receive send working faster than the regular send.  If they port this
to a system in which ready-receive send is nothing more than the regular 
send, then they are paying the cost of the extra overhead, but getting no 
benefit from it.  And unfortunately, the people doing the port may not 
realize or remember this.

So, one might argue, the vendor supplying that system ought to implement the 
ready-receive send!  But if the underlying architecture doesn't lend itself
to any benefit, what should the vendor do?  Use a different mechanism so that
the ready-receive send is faster than the (now slower) regular send?  

(This isn't hypothetical -- I've thought hard the last couple days about how 
I would implement a faster ready-receive on the CRAY T3D, and the only way I
can think of how to do it is to use a protocol similar to what Paul describes.
But I have a different protocol for the T3D that I believe is faster and just
as reliable; one that is made possible by features of the T3D architecture
that aren't in most other systems.)

If ready-receive isn't in MPI, Intel still has the option of extending MPI to 
support a ready-receive send on their systems.  It would be clear to a user 
choosing to use that extension that they are making a choice that will 
reduce portability.  But by using ready-receive in any case, they are 
making this choice; this would make the decision explicit.

In a sense, this is a general issue.  People have argued for several MPI
functions because they offer the enticing prospect of both portability and
optimization.  But this analysis is based on the design of the current
architectures that people are familiar with, and in the long run may 
prove specious.

	- Peter Rigsbee

---

From: Adam Greenberg <[email-masked]>
Date: Wed, 14 Apr 93 18:34:29 EDT

From: William Gropp <[email-masked]>
   Date: Tue, 6 Apr 93 11:06:55 CDT

      ...

Within the confines of the higher levels of the CMMD message passing system (ie
*not* the active message layer), a ready-receive, used correctly, could improve
the performance for sending small messages.  It would not appreciably effect
the performance sending suitably large messages.  The important factor for us
is that a misused ready-receive would create unrecoverable havoc within the
messaging protocol.  Should this beast be accepted by the forum, we will
implement it as an ordinary blocking send.

moose