Subject: safe, unsafe and erroneous MPI programs

From: L J Clarke <[email-masked]>
Date: Wed, 3 Mar 93 20:25:31 GMT

MPI, more specifically  the  point-to-point component, describes three
classes of  programs: safe,  unsafe and erroneous. I'm  thinking about
buffer resource exhaustion here. It is possible to write safe programs
in  MPI. It  is  not possible to  identify a  subset  of  MPI which is
guaranteed to  provide  either safe or erroneous programs,  and cannot
produce unsafe programs. We  think that MPI  should  contain  such  an
identifiable subset.

This subset was provided by the SYNCHRONOUS completion mode proposed by
Marc Snir, which was rejected at the last meeting.  I could not support
the proposal because I do not believe that the completion mode proposed
is actually what users want, and did not reflect common practice. 

Primary proposal
----------------

I propose that a further  completion mode  should be added to  MPI, in
addition to the  surviving  REGULAR  completion  mode, which  reflects
common practice and creates the identifiable subset of MPI which.

I propose that a SECURE (for want of a better name) completion mode be
added, which has the following semantics:

(a)  The COMPLETE operation will wait until the user buffer for send is
clear for  use.  In send the data has been copied from the user buffer
(without specification of where it has been copied to), and in receive
the data has been copied to the user buffer.

AND

(b) The  COMPLETE operation  will wait until the sender (receiver)  has
performed the START operation which matches the receiver (sender).

Note that (a) is just the REGULAR completion mode, and (b) has no
additional meaning for a receiver. It really just applies to senders.

With this addition, the identifiable subset of MPI which produces
either safe or erroneous programs is that which contains the SECURE
complete mode and does not contain the READY start mode. 

The program

Process 1                       Process 2
---------                       ---------
secure send to 2                secure send to 1

blah                            blah blah

secure recv from 2              secure recv from 1

is erroneous (by definition?).  It will deadlock with every correct
implementation of MPI. 

The program

Process 1                         Process 2
---------                         ---------
nonblocking secure send to 2      nonblocking secure send to 1
nonblocking secure recv from 2    nonblocking secure revc from 1

blah                              blah blah

wait for send to 2                wait for send to 1
wait for recv from 2              wait for recv from 1

is safe (by definition?).  It will not deadlock with any correct
implementation of MPI. 

Secondary proposal
------------------

MPI should not contain a combination of SECURE complete mode and READY
start mode.  I can see no sense in such a combination, and leaving it
out decreases the overlap between the safe subset of MPI and the
potentially unsafe subset of MPI. 

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

---

From: [email-masked]
Date: Wed, 03 Mar 93 13:52:31 -0800

I agree that there should be a way to produce programs which are known to be
safe. However, I also think that once a program is proven safe, it should be
easy to allow it to take advantage of buffering when available. To make it
easy, I recommend a global safeness mode, rather that one that must be
selected on each send and receive.

I would suggest that the environmental management section contain a call in
which the user can specify that all operations are to have SECURE semantics if
coded as normal semantics, and those coded with READY semantics would either
be proved correct (might be hard) or flagged as erroneous.

This way, a program can be proved safe and then released from SECURE semantics
with a single line change, instead of going through all the sends and receives
and changing them from SECURE to normal. This is particularly important if we
decide to distinguish modes by syntax rather than by a mode parameter.
(I think we should use syntax because it can be more efficient.)

So, I would propose a call like this:

	MPI_safe()

which, if present, will cause the implementation to flag an unsafe program as
erroneous. Alternatively, it could be a link option (that is, the MPI standard
would require that the implementor provide a means of specifying that a
program is to be created or executed in such a way as to report an error if any
unsafe operation is attempted.)

This would be analogous to lint for C programs. You use it when you need it,
and the rest of the time it is not in the way.

Paul