Subject: Context and safety

From: James Cownie <[email-masked]>
Date: Tue, 27 Jul 1993 16:47:47 +0100

As you know I am in favour of removing the ability of users to bind
arbitrary integers into communicators, since this removes any security
from the communications. (and in my mind that was the sole purpose of
contexts). 

Or phrased another way :
Groups   provide spatial  insulation of communication.
Contexts provide temporal insulation of communication.

How did we get here ?
=====================

Why did we introduce contexts and communicators as separate objects
from groups ?

I think the logic runs like this :-
1) We know that it is necessary to make the SAFE creation of
   context(s) within a group a collective (and possibly synchronising)
   operation.
2) But we want to allow the creation of communicators without
   synchronisation of the group.

[A third possible reason has to do with establishing between-group
 communication, however I would like to leave that for now, since I see
 it as a large area of additional complexity, and I'd like to solve the
 "simple case" first. (I'll discuss how I'd handle this later).
]

We overcome this problem in two separate ways :-
1) We allow totally unsafe creation of contexts (by hard coding, using
   the phase of the moon, or whatever).
2) We amortise the cost of the synchronisation (and move it elsewhere)
   by using an allocation function which allocates multiple contexts
   simultaneously.

Communicators then arise as a result of exposing the separation of the
communication context and the group. They are a syntactical
convenience to bind these two entities back into a single object,
since they can only ever be used in a communication together.

However I don't think that we need solution one (unsafe creation), and
I think that if we accept only solution two (context pre-allocation)
we can do it WITHOUT having to expose contexts explicitly to the user.

How to do without explicit contexts.
====================================

As in Marc Snir's proposal, we do everything inside a group. A group
now replaces a communicator in all communication operations. 

(If you prefer you could keep a group as a topological entity, or
process list, and have a synchronising mpi_group_activate command
which produces a communicator from a group, you can then use
mpi_duplicate_communicator to get a copy of the communicator with a
different context, and still separate the concept of group and
communicator. For now I'll explain in terms of groups, the explanation
in terms of communicators should follow trivially.)

So how do we create duplicate groups safely and locally ?
(You could read this as "How do we allocate contexts safely and
locally ?", since that is what the implementation will actually be doing.)

We introduce a VERY IMPORTANT rule which is :-
"All collective operations on a group must occur in the same order on
 each node."

(This is already necessarily true for the collective operation we have
previously defined in MPI collective, since they are permitted to
contain barriers, and therefore the whole code will deadlock if this
rule is not obeyed.)

What this rule does allow us to do, is to locally
pre-allocate a set of contexts for a given group, and then manage them
entirely locally, just as the user could explicitly by using
mpi_contexts_alloc, BUT we don't have to expose the context numbers to
the user, so safety is preserved.

[This follows by induction, each node with the group in starts with
the same set of contexts allocated (by definition, as the group was
established or initialised collectively), and each allocation occurs
in the same order, so they can allocate the same result at each node
and remain in identical states]

I think that this rule is unobjectionable, (as noted it is a restating
of the rule we already have for collective routines) since a group
exists for collective operations, and context allocation is
(conceptually) a collective operation, even though we're going to
GUARANTEE that in certain circumstances it is not a barrier.

Cacheing
========

To simplify the user interface I would introduce cacheing of duplicate
groups on the "primary" group. (If you prefer this is cacheing of
communicators on the primary communicators.) In implementation terms
this involves holding multiple contexts on the same group, and
choosing the correct one to use based on the symbol table lookup.

To allow the semantics we require, the keys to the cache lookup should
be 
	a function address
and	an integer

By definition, the function address is sufficient on any machine to
apply the function, and is therefore guaranteed unique. (Of course its
interpretation is potentially different on different machines, but the
library is machine specific, so can be expected to understand how to
convert a function pointer into a useful value for hashing on, on most
machines it is safe simply to cast to int !). 

The additional integer allows a library function safely to distinguish
between different instances of itself operating on the same group.
(Say if one wanted to implement non-blocking collective operations.)

So suppose we have a function like this ...

enum LOOKUPOP {
   OP_LOOKUP,	      /* Lookup ONLY */
   OP_LOOKUPCREATE,   /* Lookup, create if not present */
   OP_DELETE,         /* Remove the entry */
   OP_LOOKUPCREATENB, /* Lookup, create if not present, BUT only if
                       * there is a pre-allocated context */
};

MPI_GROUP mpi_lookupGroup( MPI_GROUP g, void (*key1)(), const int key2,
        	           enum LOOKUPOP op);

and a way of pre-allocating contexts, say

int mpi_groupsReserve( MPI_GROUP g, void (*key1)(), const int number);

Which is a group synchronisation in "g", and allocates "number"
duplicate groups which can only be used by quoting the key "key1".

We can use these to solve various of our classic problems

Tony's library example #1
Multiple instances of the same library function operating in the same
group at the same time, with guaranteed non-blocking properties.

The main program

int main(int argc, char ** argv)
{
    int done = 0;
    userLibHandle h1;
    userLibHandle h2;

    ...
    mpi_init();
    ...
   
    /*            Group,        Concurrent ops in this group */
    init_user_lib(MPI_COMM_ALL, 2);
    h1 = user_start_op(dataset1);
    h2 = user_start_op(dataset2);

    while (!done)
    {	
        /* Work including reductions on COMM_ALL, comms in COMM_ALL
           etc */   
        done = /* Whatever */ ;
    }

    user_end_op(MPI_COMM_ALL, h1);
    user_end_op(MPI_COMM_ALL, h2);
}

/* The library. Doesn't handle local multi threading, could do with
 * mutexes around access to instanceNo.
 */

typedef int userLibHandle;   /* Type of the data the user must give us
                              * back, could pack a group in as well if
                              * we preferred
                              */
static int instanceNo = 0;

/* Library initialisation code */
void init_user_lib(MPI_GROUP g, const int concurrentOps)
{
    if (mpi_groupsReserve(g,
                          (void(*)(void))init_user_lib,
                          concurrentOps) != MPI_SUCCESS )
    {
       /* Error handling */
    }
    instanceNo = 0;
}

/*
 * If this call is allowed to synchronise in g, then we can use
 * LOOKUPCREATE, and should never get an error.
 */
userLibHandle user_start_op(MPI_GROUP g, void * data)
{
    MPI_GROUP myGroup = mpi_lookupGroup(g, 
	                                (void(*)(void))init_user_lib,
	                                ++ instanceNo,
		                        OP_LOOKUPCREATENB);
    if (!myGroup)
    { /* Error handling, insufficient pre-allocated groups */
    }       

    mpi_irecv(myGroup, ...);
    mpi_isend(myGroup, ...);
    /* Etc */

   return instanceNo;
}

void user_end_op(MPI_GROUP g, userLibHandle key)
{
    MPI_GROUP myGroup = mpi_lookupGroup(g, 
	                                (void(*)(void))init_user_lib,
	                                key,
		                        OP_LOOKUP);
    
    if (!barrierGroup)
    {
        /* 
         * Fatal error, attempt to end user op without starting it
         */
    } else
    {
	/* 
         * Wait for all communications in myGroup to complete
         * The proposed waitAll( GROUP ) would be useful here,
	 * otherwise we need the return tag from startBarrier
         * to contain the comms handles of all the non-blocking ops we
         * started so that we can wait for them to complete.
         */
    }

    /* Free the group we used. */  
    mpi_lookupGroup (void(*)(void))init_user_lib,
	                                key,
		                        OP_DELETE);
}

Summary
=======

I believe that this proposal achieves the objectives of maintaining
security allowing a simple user interface, and allowing guaranteed
non-blocking operations.

In this proposal the structure of a group (or communicator) is
completely hidden from the user, and can be guaranteed secure.

There are none of the  problems of receiving messages in a group which
is different from that in which it was sent, since the system controls
the binding of contexts to groups.

All of the magic is contained in the single routine mpi_groupsReserve,
which can use a hidden context which is always created on the group to
ensure its own safety.

It is clearly possible to implement all of the collective operations
using this interface, though an implementation would probably reserve
some contexts in the group explicitly for these functions, rather than
using the lookup mechanism.

I'm out of time now, so I'll try to cover some of the missing issues
tomorrow. (Between group communication, more detailed implementation
thoughts). 

FEEDBACK PLEASE !!!!!

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] (Tom Henderson)
Date: Tue, 27 Jul 93 17:43:45 MDT

Jim, 

One other question I forgot to include...  You mention waitAll(),  

>          * The proposed waitAll( GROUP ) would be useful here

How would waitAll() work with nested groups (as in my "dumb question")?  

      mpi_groupsReserve(MPI_COMM_ALL, myFuncA(), 10);
      G = mpi_lookupGroup(MPI_COMM_ALL, myFuncA(), 5, OP_LOOKUP);
      mpi_groupsReserve(G, myFuncB(), 4);
      H = mpi_lookupGroup(G, myFuncB(), 2, OP_LOOKUP);
      waitAll(G);

Would waitAll() wait for all communication in H?  Or just communication in 
the first context of H (which I assume is context "2" in G)?  

No more dumb questions for the moment...  

Tom

---

From: [email-masked] (Tom Henderson)
Date: Wed, 28 Jul 93 10:43:24 MDT

Jim,

> I don't think that waitAll(GROUP) exists, so this is a moot point. I'd
> certainly expect it only to wait on the actual group it is passed, so
> in this case (which I now find confusing, should the waitAll be on H ?) 
> [attempt to get back to parity on the beers !], as written it would
> wait for completion of all communications on the G group.
> Communications in H or MPI_COMM_ALL would be irrelevant.
> 
> James Cownie 

You're right, the waitAll() should be on H.  I guess I owe you a moot 
beer...  :-)  

Tom

---

From: Tony Skjellum <[email-masked]>
Date: Wed, 28 Jul 93 12:56:31 CDT

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

---

From: James Cownie <[email-masked]>
Date: Wed, 28 Jul 1993 17:46:38 +0100

Tony, 

> I have to read Jim's comments in greater detail before I respond.
> I guess it is somewhat late for a totally new proposal, don't you
> think... as we are refining the intra-comm quite well at this point.

I agree it's late. I apologise. As I warned you before I left I had
other unavoidable committments which ate up a week of my time away
from the net.

I believe that I could construct something very close to the current
proposal in its treatment of groups, but containing the cacheing scheme
I proposed as the way of manipulating contexts, and thus avoiding
their exposure to the user. 

This would retain communicators as separate objects from groups, but
initial communicator creation from a group would be a collective
operation. 

I will happily do this if you care to send me the latest source for
the chapter.

Alternatively we can try to have a straw poll to find out which style
the (full ?) committee prefers. In some sense this is unfair unless I
produce a full document to the same level of detail as the extant
draft, since sketchy outlines can easily look more attractive than a
full proposal.

Tell me what to do ! (other than go jump in a lake !)

-- Jim
James Cownie 
Meiko Limited			Meiko Inc.

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

No, please do not jump into a lake.  We want your feedback.  Please
let me finish the chapter by August 4 or 5, and I will have had time
to digest your significant comments.  After that, let us discuss and
refine your comments with the sub-committee, and see where that gets
us.  If it means that there are a number of friendly and unfriendly
amendments that you will make during the reading, then this a reasonable
approach that still gets us reading the chapter as scheduled.  

I think I just sent you another message that complained about the lateness
issue.  Probably duplicate in my thinking, but I did not send to mpi-context
by accident... the main issue there of interest is my view that
contexts (as opaque objects) are safer than you asserted.  IE,

---------

Having opaque contexts strongly increases the safety of the system, in my
opinion.  It reduces the closeness to implementation that Jim discussed
before.  I am concentrating on intra-communication now.  A context can
have an attribute that says it is invalid for inter-communication.   When
one tries to use it in a communicator for inter communication, one fails.
The problem cannot happen, if one is prohibited from binding the communicator
(whether locally or globally) if it is a closed-mode context.  Since one
has to transmit (by flattening/unflattening) an opaque context, one 
presumably DOES NOT FLATTEN a closed-mode context, making it unreasonable
that a non-group process would have it in the first place.

---------

- Tony

---

From: Tony Skjellum <[email-masked]>
Date: Wed, 28 Jul 93 13:09:38 CDT

Jim,

I am happy to do straw polls only after we have a complete chapter, next
week, if you have a complete chapter too.

As Marc Snir might say, it only makes sense to view "complete" chapters
(well, he used to say "complete proposals" but we are at the chapter
stage now).  

- Tony