Subject: 5184; one small point

From: [email-masked] (Steve Otto)
Date: Thu, 4 Feb 93 14:01 PST

I got into my office late today, and I must say,
how exciting to see all the mail concerning 5184!

Jim Cownie writes:

>The data is necessarily serialised to some degree over the
>communications medium, so where's the problem ? I believe it is
>actually HARDER to insist that the buffer sepcifications match at each
>end than not to do this. (Certainly I have to pass additional
>information with the message if I'm to check this.)

	I did not mean to imply that the standard should RULE OUT
	mix+match or that it should check for it at run time, 
	merely that the standard should not make the
	guarantee that one IS allowed to do this.  There is an
	important difference.  I really don't believe we can foresee
	everything, so we should be conservative on what the standard
	guarantees.

	Jim agrees that in the case of heterogeneity, it does seem
	that we want matching:

>The only place where I can see a need for matching of send and receive
>formats is in the heterogeneous case. Here I would be happy to insist
>that a heterogeneous send be matched to a heterogeneous receive. 

	So maybe we don't want to allow all 5184 combinations.  OK,
	at least we are admitting that there is an issue here.

--Steve Otto

---

From: [email-masked]
Date: Thu, 04 Feb 93 14:50:38 -0800

> 	everything, so we should be conservative on what the standard

One of the important differences is that if the standard does not guarantee
that you can mix, you can't write a portable program that mixes. Since we have
seen one or two good examples of useful mixing, I think its important to
guarantee the ability to mix at least for some combinations. My preference
would be to guarantee mixing in all but specific cases, as few as possible.
In fact, I would recommend against including features that cannot be mixed.

I am optimistic that we can take care of the heterogeneous case in a
sufficiently uniform way that mixing heterogeneous levels with
non-heterogeneous becomes a non-issue. There was a good argument for not
having a non-heterogeneous level, that would take care of it.

The one case where mixing probably can't be justified is synchronous
operation, where the send does not complete until the receive does. I've never
liked this option, and worry that some support comes from  misunderstanding
about the difference between blocking and synchronous, as evidenced by Chuck's
comment "You can't reuse the buffer being sent until you know that it has been
received at the other side". This is of course not true. If the blocking send
semantics are that 1) the send completes when the send buffer can be written
safely and 2) message delivery is guaranteed, then you may happily overwrite
the send buffer when the send completes with the assurance that the undamaged
message will eventually appear at the receiver if its not already there.

The only interesting difference between blocking send and synchronous send is
in the amount of system buffering that may be required by applications. A
correct application using blocking send might require some amount of system
buffering, while a correct application that exclusively uses synchronous send
requires no system buffering. In my opinion, we should focus on the problem of
implied system buffering in the system environment area and eliminate
synchronous send from the point-to-point portion of the standard.

With reasonable care, we can make a clear and simple guarantee that appropriate
different sends and receives can be mixed freely. This will allow people to
write portable applications which use mixed structures.

Paul

---

From: [email-masked]
Date: Fri, 05 Feb 93 15:02:57 -0800

Folks, here is an offline exchange Jon and I had that you might enjoy.

To: [email-masked]
Subject: Re: 5184; one small point

Paul, I saw your message about blocking and synchronous messages. Without
wanting to speak for Chuck I think there is a pretty important difference
between the two, particularly for applications such as Oracle. Using the
blocking send it is true that the send buffer can be reused as soon as
it is "clear" AS LONG AS IT IS GUARANTEED that it will be delivered.
Unfortuntely this can't be guaranteed in the case where system buffers
are required because the system may simply be out of memory at
the receiver. In this case MPI and other systems will simply drop
the offending message on the ground. For a database I assume this
would be fatal. On the other hand the synchronous scheme has
the advantage that you know it's worked when it returns, on both
send and receive sides.

	Jon Flower

This is an area where we must be clear about the semantics.

We have agreed to some extent that message passing in MPI will be reliable. If
I remember correctly, this passed on a straw vote early in the first
point-to-point discussion.

When I say "agreed to some extent" I mean that not everyone has the
same understanding of what the standard is about on this issue.

To me it means that if I have a send, and a receive that matches the message
sent, that the message will absolutely be delivered. This is how NX works. If
there isn't enough buffer space, the send must block so that the message waits
in the send buffer until it can be delivered. Flow control is required in the
underlying protocol.

There seem to be a lot of people that expect no underlying protocol. When you
say "send", the system sends - whether the message can be delivered or not.
Apparently some systems work this way, and therefore it is expected behavior
for people who have been users of these systems.
To me, it is not at all compatible with the notion of reliable message passing.

If you have reliable message passing as I understand it, clearly the important
difference you mention goes away, leaving the lesser difference I wrote about.

Without reliable message passing, I see no point whatsoever in blocking send.
In fact, I see little point in having a typed send/receive standard, because
such an interface is loaded up with friendly help for the user and it seems
ridiculous to turn around and expect that same user to worry about reliable
delivery.

Does any of this make sense?

Paul

Hi Paul. I think what you're saying makes some sense. I have two more 
questions though....

a) Having the sender block until memory is available potentially
   invalidates some algorithms, particularly as the number of nodes
   grows. It's quite easy to come up with a sort of "ring" 
   algorithm in which everyone ends up hung. I would agree that
   the trivial case (a single one-dimensional ring) in which this
   happens is a "user error" but there are more complex 
   multi-dimensional cases in which it is quite hard for users
   to guarantee that it won't come up, even with quite reasonable
   programs.

b) What are the implications of the flow control that you are
   using on performance? Is your routing hardware doing the claiming
   of memory blocks on the receiver or is there an initial software
   handshake to get started. The latter probably costs a fair
   amount that the "high priests" don't like???

I agree that the definition of "reliable devliery" in the MPI
picture is not solid. I thought I remembered a piece that actually
said that it was OK to drop a message if there wasn't enough
memory on the receiver but I could be hallucinating. I wonder
if it's worth trying to straighten this out? I have a nasty
feeling that we'll get down to implementation details. If we
can't get IBM and TMC to agree that

    Node 0:
	send to 1
	read from 1

    Node 1:
	send to 0
	read from 0

is a reasonable thing to do I don't see much hope for anything
else at this level.......

	Jon

> a) Having the sender block until memory is available...

This is inherently a hard problem that is all about system buffering. You
can't solve this problem by careful or clever definition of the semantics of
a message passing interface (whether and when sends block, and whether message
passing is reliable.) If you push it down here, it pops up over there -
depending on the semantics defined for the interface, the problem must be
solved by the system or by the user. My preference (for a typed send/receive
interface) is to push the problem to the system side, as much as possible.
That way most users won't have to deal with it. But you can't completely solve
the problem on the system side, because the user can always write a program
that will confound any system buffering that has finite buffer space.

With a reasonably good system implementation, it is actually rather difficult
to come up with an algorithm that breaks it. Also, it is possible to define
straightforward rules that will guarantee correct execution. That way,
although the user must be careful being careful is easy.

> b) What are the implications of the flow control...

There is a performance penalty. People have claimed that NX overheads are too
high, and it is true that they are noticeably higher than raw hardware. But
there is quite a bit of overhead from message matching too, so for those who
want ultimate performance there should be an alternative to the typed
send/receive interface. Active messages is a good candidate. Such an interface
is outside the scope of MPI.

> I agree that the definition of "reliable devliery" in the MPI
> picture is not solid. I thought I remembered a piece that actually
> said that it was OK to drop a message if there wasn't enough
> memory on the receiver but I could be hallucinating. I wonder

It was in the first draft.

> if it's worth trying to straighten this out? I have a nasty
> feeling that we'll get down to implementation details. If we
> can't get IBM and TMC to agree that
> 
>     Node 0:
> 	send to 1
> 	read from 1
> 
>     Node 1:
> 	send to 0
> 	read from 0
> 
> is a reasonable thing to do I don't see much hope for anything
> else at this level.......

We have to develop and agree on a way to manage system buffering. To get
Intel, IBM, and TMC together it must allow for the case where the above works
and the case where it doesn't.

> 	Jon

Paul

Do you have any plan for how to reconcile the difference between
the three camps on the simple program I sent you? My impression
is that:

	NX (& Express, in fact) want that program to work
	as well as it possibly can. I believe that >95% of
	Express users code that way and are successful. I
	think you mentioned a similar fact in Dallas.

	TMC is prepared to say that the program is incorrect and 
	won't work at all.

	IBM is not convinced either way.

I don't see how to reconcile these camps in any good way. If we allow
for the possibility that the code doesn't work AT ALL then the 95% of
Express codes I mentioned above ALL have to be re-written in order to
become portable. Furthermore, if the only way to guarantee portability,
even within MPI, is to assume "half-duplex" communication then why not
toss the other kind completely -- it would certainly reduce the 
complexity of the draft?

	Jon

I think the answer (if there is one) is to provide a mechanism where the user
declares a need for system buffering. This is a job for the system environment
group to work out properly. With a declaration, you get:

 - Portability: The code is written for a specific buffering model but will
port between environments because it tells the system what it needs.

 - Efficiency: If the user declares no buffering, the system can eliminate
the associated overhead. (How to do this is a trick.)

 - Bloat: Every vendor must provide system buffering in case the user declares
a need for it.

Paul

I agree....... do you think TMC will?
Should we attempt to make a formal suggestion along these lines
to the entire group. "Prepare to be flamed!!!!"

	Jon

[I'm ready]

Paul

---

From: [email-masked] (James Cownie)
Date: Mon, 8 Feb 93 11:52:48 GMT

While I am no fan of arbitrary system buffering of messages, I
believe that if it is to succeed MPI must allow the easy importation
of existing Express and NX style codes. This necessarily implies that
system buffering is required, so that code like this

	Blocking send to myself
	Blocking receive from myself

works. (This is an even simpler version of the test case given by
Jon/Paul). 

I agree with the approach that the user should declare her buffering
requirement up front. This seems to be the only way to ensure
portability. (Even if all it achieves is ensuring that she gets an
"MPI-INSFMEM insufficient buffer space available" message on some
systems, this is still preferable to a crash or hang).

This is exactly the set of issues Marc was addressing in his
discussion on SAFE and UNSAFE programs, and the amounts of buffering
such codes could assume (he also addressed issues such as "How many
outstanding messages can a code assume it is allowed ?").

I've a feeling that a lot of users (most ?) don't actually know what
their buffer requirement is, however I still think that requiring a
user specification of required buffer space is the correct way
forward. 

(It might also be nice to have a system enquiry function which could
return the buffer space currently used and the high water mark. This
would at least let users find out about the behaviour of their codes.
Unfortunately this information is rather implementation specific, and
would not be accessible through the currently proposed profiling
interface. Is this an issue for the profiling committee, or the
environmental enquiry one ??? [As chair of the Profiling committe I'd
vote for Environmental Enquiry !])

-- 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		+1 617 890 7676
FAX   : +44 454 618188		+1 617 890 5042
E-Mail: [email-masked]   or    [email-masked]

---

From: [email-masked] (James Cownie)
Date: Mon, 8 Feb 93 12:09:13 GMT

One more point I ommitted before...

Paul says :-
> to work out properly. With a declaration, you get:
> 

The last point is not actually true. It's entirely reasonable to have
a standard which contains a buffering request and allow it to  be
refused. (There's not actually any point in having the request unless
it can be refused !)

I don't see a huge logical distinction between an implementation which
permits system buffering of 1 byte and one which permits no system
buffering. If the user needed 1Mb, then neither system is any use !

So it's merely an implementation quality issue. If someone has been
able to sell their current system and keep their users happy without
system buffering, then they should still be able to keep them happy
with an MPI implementation in which the amount of system buffering is
zero, and any request for more fails.

Such an implementation would be standard conforming too. (Though such
a vendor might expect some moaning from people trying to import code
onto the machine, and maybe market pressure would push them into an 
implementation which did support system buffering !)

(As an analogy, I believe that it is possible to have a standard
conforming ADA implementation whose sole action when presented with
any program is to raise the "Implementation limit exceeded" exception.
Not useful, not saleable, but standard !)

-- Jim
James Cownie 
Meiko Limited			Meiko Inc.

---

From: Rusty Lusk <[email-masked]>
Date: Tue, 09 Feb 93 01:22:40 CST

| 
| Folks, here is an offline exchange Jon and I had that you might enjoy.
  ....
| Should we attempt to make a formal suggestion along these lines
| to the entire group. "Prepare to be flamed!!!!"

(not a flame)
I did enjoy this exchange, because it is a tutorial on the buffering problem.
Paul says it perfectly: You can't solve the system buffering problem by
careful or clever definition of the semantics of a message passing interface.

I agree that most users would rather not worry about it (and don't) and we
should allow systems that try to handle the problem for the user to do so (the
example programs in the discussion should run).  I agree with Jim Cownie on
this point.  For portability, an enquiry function can be provided to alert the
user who checks to find out how much (or how little) buffering is provided.
I think the environmental enquiry subcommittee should propose something along
these lines.

As Paul says, handling this robustly has a cost, and some users certainly want
to avoid it.  After all, the user can know some things about his program that
the system cannot, and should be able to take over responsibility for the
buffering problem if he wants to.  This is just what is done in the case of
the "ready-receiver" communication.  I admit that this is not a particularly
euphonious name, but some way is needed for the user to relieve the system of
buffer management if he wants to do so in the interest of greater efficiency.

Rusty