Subject: Cancel

From: [email-masked] (James Cownie)
Date: Fri, 5 Mar 93 14:43:16 GMT

People,

I believe that any of the non-blocking operations which MPI mandates
should be cancellable.

Why have cancel ?
=================
There are various reasons for this (in random order)

1) Resource liberation
   Some (? ALL ?) of these operations commit system resources. If the
   user knows that the operation can never complete, then she should
   be able to release those resources.

2) Access revocation 
   Some of these operations give the MPI system authority to modify
   areas of the user's store. (non blocking receive in particular).
   The user should be able to revoke this permission.  [See examples
   with receive buffers on the stack for the true potential horror
   here !]

3) Cleanliness
   In some of Marc's early documents (and maybe still) there is an
   implication that all messages MUST have been received at program
   exit, otherwise the program is erroneous. 
   It seems reasonable also to require all non-blocking operations to
   have completed (even MPI -1.1's non blocking exit call completes at
   this point !), if this is so then we need to be able to force the
   completion of these operations.  (This is particularly the case for
   server type objects which may wish to queue many non-blocking
   receives [so as to avoid system buffering and additional data
   copying], but then wish to exit, possibly returning to the rest of
   the code...).

What does cancel mean ?
=======================
Cancelling an operation forces its completion with an error status of
CANCELLED. One can reasonably require that the cancelled operation
then be tested for completion in the normal way that any such
non-blocking operation would be.

Cancelling an operation can FAIL. This occurs if the operation to be
cancelled has already successfully completed (Entered the state in
which it could be successfully found as complete) or the system can
guarantee its completion in a bounded time (in which case the cancel
call should block until the operation completes).

After an operation has been cancelled, I know that either
1) The operation completed normally
or
2) The operation will never now proceed (it has been cancelled)

The two cases can be separated by testing the completion return from
the normal WAIT or STATUS call. (This is preferable to returning this
result as the status of the cancel call as it makes the case of one
thread cancelling a call on which another thread is already waiting
resolve correctly).

Consider for example cancelling a non-blocking send operation, there
are three possible cases :-

1) data transfer has not actually started 
   => it never starts, the operation is really cancelled, returning a
      CANCELLED kind of result.

2) data transfer has already completed
   => cancel failed and returns a COMPLETED kind of result

3) data transfer has started, so it is allowed to complete
   then reduces to case 2)

Note that cancellation is an operation which happens to a REQUEST, it
is not an operation which is applied to a MESSAGE. Therefore once a
particular receive has been (successfully) cancelled the system state
is as if that receive had never existed. There is NO implication that
the cancel has an effect on any future incoming message which would
have matched the, now cancelled, receive. Such a message can still be
received in the normal way by any suitable matching receive call.

Cancelling Group operations
===========================
If we have non-blocking group operations we should be able to cancel
them. It seems entirely reasonable to require that all the
participants who have started the operation have also to cancel it.

Issues
======
People are nervous about cancel because there is a race condition
involved. This race is between the cancel operation itself, and the
external event which signals completion of the operation being
cancelled. (e.g. the cancel and the incoming message on a non-blocking
receive).

However this race is no worse than the existing one between a receive
and an incoming message. (Does the data go straight into the user
buffer, or require system buffering ??)

Implementing a full cancel as described above is non-trivial, since
it may be necessary to send out a cancel message after a non-blocking
send. (This is the case if one uses receiver buffering).

If this is viewed as too complex, (however note that various people
already have implementations of cancel which implement semantics
similar to those described above), then at the very least we should
still seriously consider including the ability to cancel operations
which gave the system permission to write into our address space.

(Thanks to Lyndon for some of the examples and other discussion).

-- 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]