Subject: Re: Intercommunication Issues as yet Unresolved

From: Tony Skjellum <[email-masked]>
Date: Mon, 27 Sep 93 12:59:32 CDT

I prefer if we bounce this off the reflector, just for completeness.  However,
I expect that the smaller number of us will arrive at the solution.  Given
recent input from the reflector, I don't see it likely we will hear much
from others ;-(

- Tony

----- Begin Included Message -----

---

From: [email-masked] (Tom Henderson)
Date: Mon, 27 Sep 93 10:30:51 MDT

Hi all,

Here's a few more thoughts on unresolved intercommunication issues.  Should 
we be bouncing this discussion off the reflector?  

>    The following points were raised by Marc...
> 	. Does the "symmetric" protocol lead to more problems than our previous
> 	  asymmetric protocol?  If so, should we switch back to something
> 	  like what we had before (publish/subscribe)?  
> 
> 	. For either the current, or an altered set of intercommunication calls,
> 	  can the sufficient conditions for non-deadlocking be described?
> 	  Can the necessary/sufficient conditions for non-deadlocking be
> 	  described?

      . For publish/subscribe, can we satisfy the same list of "objectives" 
        that the current draft was designed to satisfy?  These objectives came 
        from objections to the original publish/subscribe scheme.  As a 
        reminder, here are those objectives:  

>> INTER-COMMUNICATION OBJECTIVES
>> 
>> 
>> 1  The inter-communicator object is used for inter-group communication with
>>    the same point-to-point syntax as intra-communication.
>> 
>> 2  An instance of communicator will provide either intra-group or 
>>    inter-group and never both.
>> 
>> 3  The same inter-communicator can be used for send and receive.
>> 
>> 4  The inter-communicator object is invalid for MPI collective operations
>>    and there must be a simple (quick) way for an implementation to determine
>>    this.  The (quick) way should be made available to the user via an
>>    enquiry routine.
>> 
>> 5  Communications using an inter-communicator are resolved from 
>>    communications using any other communicator.
>> 
>> 6  Processes in group G address processes in group H by the ranks of 
>>    processes in group H (and therefore vice versa) in both send and receive.
>> 
>> 7  There is no "out-of-band" communication, i.e. if group H is bound to 
>>    inter-communicator C then communicator C can only be used to send 
>>    (receive) messages to (from) processes in group H.
>> 
>> 8  The mechanisms for constructing inter-communicator objects must not 
>>    introduce insecurity into the basic usage of MPI.  (The mechanisms must 
>>    not allow contexts to be bound in multiple usable inter-communicators.)
>> 
>> 9  There is a mechanism for establishing communicator objects for 
>>    inter-communication which does not synchronize the two groups.
>> 
>> 10 There is support for user level servers.
>> 
>> 11 There should be a name service however it should no be central to the 
>>    provision of inter-group.  It should be possible to implement the name 
>>    service using the other provisions. 
>> 
>> 12 It should be possible to isolate the more advanced features of the 
>>    context proposal from the more basic features.  Users who only need basic 
>>    features should not have to understand advanced features (or pay a 
>>    performance penalty for existence of advanced features).  
>> 
>> 13 The provision for inter-communication should not adversely affect the 
>>   (potential) performance of intra-communication.

I think the objectives most likely to be affected by a change to 
publish/subscribe are 7, 8, 9, and 12.  

>    Tom raised the following point:
>      . Is the intercommunication functionality of MPI different in its
>        deadlocking properties than any of the other aspects of MPI related
>        to communication order, cycles, etc, in process communication?
>        [I believe that Marc also raised a similar flag.]
> 
> As I see this, we have at least to be able to state the sufficient conditions
> for non-deadlocking in the current calls, or change to suitable "publish"
> and "subscribe" type calls, and also state the sufficient conditions there.
> I invite earnest, and specific discussion over the next week.  I will also
> think on this, of course, and contribute.
...
> -Tony

To elaborate on my (limited) understanding of deadlocking properties...  

The "possible implementation" of MPI_INTERCOMM_START() and 
MPI_INTERCOMM_FINISH() went like this:  

MPI_INTERCOMM_START(local_comm, local_leader, bridge_comm, remote_leader, 
                    tag, handle)

Begin
  Duplicate local_comm using MPI_COMM_DUP().            (COLLECTIVE OPERATION)
  If (I am local_leader) 
    Begin
      "Flatten" duplicated communicator
      Non-blocking send flat communicator to remote_leader using 
        bridge_comm and tag.
      Non-blocking receive "remote" flat communicator from remote_leader using 
        bridge_comm and tag.
      (Store communication handles in handle).
    End
End

MPI_INTERCOMM_FINISH(handle, new_comm)

Begin
  If (local leader) 
    Begin
      Complete the non blocking send and receive from the START.
      (Use MPI_WAITALL() with communication handles previously stored in 
        handle).
    End
  Broadcast the remote flat communicator in local_comm. (COLLECTIVE OPERATION)
  Merge the local and remote flat communicators.  
  Free memory used to store flat communicators (if necessary).
End

This looks like:  

  1)  COLLECTIVE OPERATION (in local_comm)

  2)  NON-BLOCKING POINT-TO-POINT OPERATION ("leaders" only)

  3)  COLLECTIVE OPERATION (in local_comm)

I'm going to try and make the case that these operations are separable:  if we  can describe sufficient conditions for non-deadlocking for collective 
operations and for non-blocking point-to-point operations then we can describe 
sufficient conditions for non-deadlocking for MPI_INTERCOMM_START() and 
MPI_INTERCOMM_FINISH().  I'll go slow because I don't understand most of this 
stuff as well as the rest of you.  Let's see how far I get...  :-)

The first collective operation has the annoying property that I don't know 
how to describe sufficient conditions for non-deadlocking...  If the local and 
remote groups do not overlap, I don't think we have a problem.  If they do 
overlap, then it's more complicated...  Suppose we have three partially 
overlapping groups, A, B, and C with the following properties:

  Some processes are members of group A only.  
  Some processes are members of group B only.  
  Some processes are members of group C only.  
  Some processes are members of both groups A and B.  
  Some processes are members of both groups A and C.  
  Some processes are members of both groups B and C.  

What happens with the following codes?  

/* Process in the overlap of groups A and B. */
  MPI_COLLECTIVE_OP(A, ...);
  MPI_COLLECTIVE_OP(B, ...);

/* Process in the overlap of groups A and C. */
  MPI_COLLECTIVE_OP(A, ...);
  MPI_COLLECTIVE_OP(C, ...);

/* Process in the overlap of groups B and C. */
  MPI_COLLECTIVE_OP(B, ...);
  MPI_COLLECTIVE_OP(C, ...);

I think the operations complete in order A, B, C.  

How about this (cyclic dependency)?  

/* Process in the overlap of groups A and B. */
  MPI_COLLECTIVE_OP(A, ...);
  MPI_COLLECTIVE_OP(B, ...);

/* Process in the overlap of groups A and C. */
  MPI_COLLECTIVE_OP(C, ...);
  MPI_COLLECTIVE_OP(A, ...);

/* Process in the overlap of groups B and C. */
  MPI_COLLECTIVE_OP(B, ...);
  MPI_COLLECTIVE_OP(C, ...);

This looks like deadlock.  None of the collective operations will complete.  
(Unfortunately, this could easily happen since the processes in the overlap of 
groups A and C may have no knowledge of the existence of group B!)  I don't 
think we have defined sufficient conditions for non-deadlocking for collective 
operations with overlapping groups.  Once we have defined these, I think we 
will be able to describe sufficient conditions for non-deadlocking for the 
collective operation in MPI_INTERCOMM_START() (operation 1 above).  

Operation 2 is two point-to-point operations (send and receive) between the 
"leaders" of the two groups.  Given that operation 1 has completed without 
deadlock (because we figure out how to describe sufficient conditions for 
non-deadlocking for collective operations :-) the sufficient conditions for 
operation 2 are just the conditions for non-blocking point-to-point.  I think 
non-blocking point-to-point will work as long as all interdependent "start" 
operations are called without any intervening blocking operations.  Applying 
this to INTERCOMM_MAKE:  

  MPI_INTERCOMM_START(a) 
  MPI_INTERCOMM_START(b) 
  MPI_INTERCOMM_START(c) 
  MPI_INTERCOMM_FINISH(a)
  MPI_INTERCOMM_FINISH(b)
  MPI_INTERCOMM_FINISH(c)

should be non-erroneous (but not SAFE) while

  MPI_INTERCOMM_START(a) 
  MPI_INTERCOMM_FINISH(a)
  MPI_INTERCOMM_START(b) 
  MPI_INTERCOMM_FINISH(b)
  MPI_INTERCOMM_START(c) 
  MPI_INTERCOMM_FINISH(c)

or

  MPI_INTERCOMM_START(a) 
  MPI_INTERCOMM_START(b) 
  some other collective/blocking operation
  MPI_INTERCOMM_START(c) 
  MPI_INTERCOMM_FINISH(a)
  MPI_INTERCOMM_FINISH(b)
  MPI_INTERCOMM_FINISH(c)

might be erroneous.  It may not be possible to detect erroneousness until run
time.  

If we believe this, then operation 3 looks just like operation 1.  

So, did I miss anything?  Are there interactions between the three operations
I haven't thought about?  Any other comments?  

On publish/subscribe:  should we be looking at the publish/subscribe mechanism 
from the June 23-25 meeting?  Can anyone point to a mail message that contains 
the version of publish/subscribe we want to look at?  

Bye for now...  

Tom

----- End Included Message -----