Subject: safe buffering proposal

From: [email-masked]
Date: Thu, 2 Sep 93 11:10:48 PDT

PROPOSAL TO SUPPORT SAFE MPI MESSAGE BUFFERING IN USER-PROVIDED SPACE

This is to formally submit the buffering proposal 
that I outlined at the last MPI meeting.  I have copied
it to all attendees of the last MPI meeting to make sure
that all those who requested individual copies get them.

People with long memories may note that an earlier version of
this proposal appeared in mpi-pt2pt and mpi-envir on April 8.
Relevant discussion occurred on Feb 8 and Apr 8-11 in mpi-pt2pt.

The current proposal extends the April 8 version by associating
buffer space with a communicator.

This extension allows to

 . cancel MPI access to the user-provided buffer
   (by freeing the communicator), and 

 . specify multiple buffers
   (by associating them with separate communicators).

The complete proposal follows.

1. INTERFACE

   An application program can optionally provide space for 
   MPI's use in buffering message data via the following call:

    MPI_USER_PROVIDES_BUFFER (comm,len,buffer)
   
    where  IN  comm      is a communicator with which the
                         buffer is to be associated;

           IN  len       is the length of 'buffer', in bytes;

           OUT buffer    is a scratch array of len bytes for MPI's
                         use in buffering messages.  

2. FUNCTIONALITY

   By default, application programs are "unsafe" if they assume
   buffering.  However, an application can make it safe to assume
   a specified amount of data buffering, by providing buffer space
   via the MPI_USER_PROVIDES_BUFFER call.

   If MPI_USER_PROVIDES_BUFFER is called, then for subsequent
   regular sends using the specified communicator, MPI must
   provide as much safety *as if* outgoing message data were
   buffered by the sending process, in the provided buffer space,
   using a circular contiguous-space allocation policy.

   That is, user-provided buffer space may be consumed by outgoing
   messages, but not by incoming ones, and MPI is not required
   to split any message if it must be copied to the buffer.

   Following the call to MPI_USER_PROVIDES_BUFFER, the
   application is not permitted to access the buffer until the
   corresponding communicator has been freed.

   Access to the provided buffer space is not inherited by
   communicators derived from the initially specified one.
        
3. POSSIBLE IMPLEMENTATION

   One approach is for MPI to simply transform all blocking sends
   on the specified communicator into 

         . copy data to (application-provided) buffer space
         . issue non-blocking send from the buffer copy
         . return to application
   and 
         . check completion on subsequent MPI call(s)

   No doubt many optimizations within MPI are possible -- the
   proposal just requires that MPI provide at least this much
   safety.

4. DISCUSSION

   This proposal does not provide guarantees on the *number* of
   outstanding sends, only their aggregate message length.  Not
   guaranteeing number is consistent with MPI's general stance of
   treating limits as a quality-of-implementation issue.
   Guaranteeing the length is nominally at odds with MPI's
   general stance, but is felt to be an important compromise in
   order to support programs that assume current "common practice".
   It is unreasonable to simply declare existing programs to be 
   "unsafe", when a simple method exists to make them safe.

----------------------------------------------------------------------
[email-masked] (alias 'd39135')   Rik Littlefield
Tel: 509-375-3927                         Pacific Northwest Lab, MS K1-87
Fax: 509-375-6631                         P.O.Box 999, Richland, WA  99352

---

From: [email-masked]
Date: Thu, 2 Sep 93 17:28:02 PDT

In non-reflected email, Tom Henderson wrote:

> In general, I like your proposal.  One thing is confusing me:  
> 
> Why is buffer an OUT argument?  (I assume that the routine malloc()'s buffer 
> in user space.)  Why would a user want a pointer to a scratch array s/he is 
> not allowed to use?  
> ...
> Feel free to pass this on to pt2pt if you like.  

The 'buffer' array is allocated by the caller of MPI_USER_PROVIDES_BUFFER,
in whatever way the caller finds convenient -- static, automatic, or
malloc'd.  The caller then passes a pointer to this array, to
MPI_USER_PROVIDES_BUFFER.

Trying to describe 'buffer' as IN or OUT may be more confusing 
than helpful in this case.  MPI_USER_PROVIDES_DATA does not care
about the contents on entry, and the application cannot use the
contents later.  It would be better to call the buffer SCRATCH.

> If we have MPI_USER_PROVIDES_BUFFER(), do we still need the "synchronous" 
> communication mode?  

(As I recall the definition, synchronous mode is where the send is
guaranteed not to return, until the matching receive is sure to
complete also.  Assuming that definition is right, then...)

MPI_USER_PROVIDES_BUFFER complements synchronous mode,
but does not replace it.

Synchronous mode guarantees that an unsafe program will fail.

MPI_USER_PROVIDES_BUFFER allows an unsafe program to be made safe, 
assuming that you know how much buffering is required.

My proposal did not do so, but I suppose the interaction between
synchronous mode and MPI_USER_PROVIDES_BUFFER should be specified.

Possible specifications include:

1. Synchronous mode cannot be used with communicators for which
   MPI_USER_PROVIDES_BUFFER has been called.

2. The behavior of mixing synchronous mode and MPI_USER_PROVIDES_BUFFER
   is explicitly undefined.

3. On a communicator for which MPI_USER_PROVIDES_BUFFER has been
   called, a synchronous send will block waiting for a matching
   receive if and only if the user-provided buffer space has been
   exhausted, assuming a circular contiguous-space allocation
   policy for that buffer.

Specification 3 is intended to guarantee failure of a program
that is still unsafe, even though MPI_USER_PROVIDES_BUFFER has 
been called.  (I.e., for which not enough buffer space has been
provided to guarantee safety.)

HOWEVER, I suspect that specification 3 is inadequate, and I
would not be surprised even to find that its intent is
impossible to accomplish for all possible programs.
The reason is that any sort of buffering at least partially
uncouples the dependencies between processes, and I imagine
that it could be very difficult or impossible to guarantee
safety of all possible execution sequences by observing only
one.

Personally, I would propose for now to use specification 2: 
explicitly undefined behavior.  That way it can be fixed later
if anyone cares and also figures out what it should be.

--Rik

---

From: Ian Glendinning <[email-masked]>
Date: Fri, 3 Sep 93 12:50:04 BST

> From: [email-masked]

>    to split any message if it must be copied to the buffer.

Could you explain what the bit about MPI not being required to split messages
means please?
   Ian

---

From: Ian Glendinning <[email-masked]>
Date: Fri, 3 Sep 93 13:06:33 BST

> From: [email-masked]

>    exhausted, assuming a circular contiguous-space allocation

How about:

4. The behaviour of synchronous mode communications is unaffected by calls
   to MPI_USER_PROVIDES_BUFFER.

> if anyone cares and also figures out what it should be.

Why complicate things?  The whole point of the synchronous mode is that it has
a clean semantics that is unaffected by the vagaries of system buffering (or
system administered buffering).  I actually WANT my synchronous sends to
block until a matching receive commits.  This is not, as option 3 implies, an
unwanted side-effect of the mode.
   Ian
--
[email-masked]        Ian Glendinning
Tel: +44 703 593368                  Dept of Electronics and Computer Science
Fax: +44 703 593045                  University of Southampton SO9 5NH England

---

From: [email-masked]
Date: Fri, 3 Sep 93 08:57:27 PDT

Ian Glendinning writes:

> Why complicate things?  The whole point of the synchronous mode is
> that it has a clean semantics that is unaffected by the vagaries of
> system buffering (or system administered buffering).  I actually WANT
> my synchronous sends to block until a matching receive commits.  This
> is not, as option 3 implies, an unwanted side-effect of the mode.

Offline, Robert Harrison commented:

>     I must disagree with what I think your intent is on synchronous
> mode combined with user-provides buffer.  The semantics of synchronous
> mode (send blocks until receive issued) require no buffering and
> under some circumstances (e.g., a necessary synchronization) is
> a very useful mode.  Why should the availability of buffering when
> none is needed change this?

Rik replies:

I will happily yield on this point.

My personal interpretation of synchronous mode is that its main
purpose is to facilitate writing safe programs.  Since the definition
of safety is changed by MPI_USER_PROVIDES_BUFFER, it seems to me
conceptually cleaner for the two to interact as I had previously
outlined.  However, as I commented in my earlier posting, it is
not obvious that my preferred definition (option 3) can actually
be implemented.

Ian and Robert apparently have a different interpretation, with more
emphasis on forced synchronization than safety.  The resulting
option 4 is easy to explain and implement, and I'm surely in
favor of that!

Anybody else care?

--Rik

---

From: [email-masked]
Date: Fri, 3 Sep 93 10:57:26 PDT

Ian Glendinning writes:

> > From: [email-masked]:
> 

The intent was to simplify handling of buffer fragmentation.
(Fragmentation can result from receives being issued in a
different order from sends.)  

My gut feeling is that if MPI has to be able to utilize arbitrary
noncontiguous buffer fragments, then the guarantee will become
difficult to explain and/or implement.

The key point of my proposal is that an implementation be allowed
to allocate buffer space circularly, strictly in terms of send order.

Thus, the required amount of buffer space is equal to the combined
data length of all messages sent after (and including) the first
one that has not yet been received.  I do not see any simpler
guarantee.

However, the words "not required to split any message" may be too
strong, because the simple guarantee requires that a message be
able to wrap from the end to the beginning of the buffer.  

If MPI is not required to wrap, then the guarantee would have to
become something like "the required amount of buffer space is
equal to the combined data length of all messages ... plus an
extra copy of the current message".  I find this distasteful, and
would rather require wrapping.  (Wrapping imposes essentially no
extra burden on the rest of MPI, which already has to be prepared
to handle noncontiguous data.)

If someone can argue convincingly that fragmentation is NOT,
in fact, difficult to handle, then I would be happy to delete
the restriction altogether.

--Rik

---

From: L J Clarke <[email-masked]>
Date: Mon, 6 Sep 93 11:09:19 BST

Just a wee one to say that I basically agree with Ian.  If there is
buffering then synchronous mode can just ignore such buffering. 

Cheers
Lyndon

> unwanted side-effect of the mode.

         /--------------------------------------------------------\
    e||) | Lyndon J Clarke    Edinburgh Parallel Computing Centre | e||) 
    c||c | Tel: 031 650 5021  Email: [email-masked]  | c||c 
         \--------------------------------------------------------/

---

From: Ian Glendinning <[email-masked]>
Date: Mon, 6 Sep 93 14:40:05 BST

Rik,
    I asked what you meant in your buffering proposal when you said "MPI is
not required to split any message if it must be copied into the buffer.", and
you replied, clarifying your intent.  I now understand roughly what you are
trying to achieve, but unfortunately I'm no clearer about the meaning of the
original sentence.  Perhaps I should have been more specific;  What do you
mean by splitting a message?  It's rather hard to make sense of the rest
without knowing that.
   Ian

---

From: [email-masked]
Date: Mon, 6 Sep 93 14:37:53 PDT

> mean by splitting a message?  It's rather hard to make sense of the rest

"Splitting a message" merely meant copying it to a noncontiguous 
set of memory addresses within the buffer.

--Rik

---

From: Ian Glendinning <[email-masked]>
Date: Tue, 7 Sep 93 16:16:22 BST

> set of memory addresses within the buffer.

Thanks for that clarification.  Now I'm really sure I don't understand the
original sentence:

"MPI is not required to split any message if it must be copied into the
buffer."

Why "not required to split"?  Don't you mean "required not to split"?  As
written it doesn't seem to impose any constraint.  It might split, or it might
not.  Still confused,
   Ian
--
[email-masked]        Ian Glendinning
Tel: +44 703 593368                  Dept of Electronics and Computer Science
Fax: +44 703 593045                  University of Southampton SO9 5NH England

---

From: [email-masked]
Date: Tue, 7 Sep 93 11:00:57 PDT

Ian Glendinning writes:

> written it doesn't seem to impose any constraint.  It might split, or 
> it might not.  Still confused,
>    Ian
> --

Ian is fine; the clause is confused.  Actually, it's pretty much
nonsense, not even worthy of trying to explain.

Instead, let me try again to say what I should have meant in the
first place.  

Here is the complete "functionality" part of the proposal, as
modified in light of the several emails that Ian and I have
exchanged.  Major changes are marked with bars.

---- partial spec follows --------------------

    2. FUNCTIONALITY

 |     That is, a "send" on a communicator is guaranteed not to
 |     block indefinitely IF the program has provided buffer space
 |     that is equal to or longer than the combined data lengths of:
 |      . the message currently being sent,
 |      . the earliest outstanding (unreceived) message
 |        that was sent on the same communicator, and
 |      . all intervening messages sent on the same communicator.

       Buffer space is not consumed by incoming messages.

---- end partial spec --------------------        

Is this better?

--Rik

---

From: Ian Glendinning <[email-masked]>
Date: Tue, 7 Sep 93 19:23:21 BST

> Instead, let me try again to say what I should have meant in the

[Explanation deleted]

> Is this better?

Yes, much better.  Thanks,
   Ian
--
[email-masked]        Ian Glendinning
Tel: +44 703 593368                  Dept of Electronics and Computer Science
Fax: +44 703 593045                  University of Southampton SO9 5NH England