Subject: Re: Context and safety

From: L J Clarke <[email-masked]>
Date: Tue, 27 Jul 93 17:24:39 BST

Hi Jim

> 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). 

I understand that Tony intends to make "context" opaque, rather than
just an integer.

> 
> 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."

I think that I understand what you mean but surely the rule, if so
important, should be more accurately stated. Perhaps something like

"All collective operations within a group must occur in the same order
in all processes within the group."

> (This is already necessarily true for the collective operation we have
> previously defined in MPI collective, 

Yes.

> since they are permitted to
> contain barriers, and therefore the whole code will deadlock if this
> rule is not obeyed.)

I dont think this is a correct statement at all.  Its got nothing to do
with the barriers.  Imagine that barrier were the only collective
operations.  It would be impossible to speak of collective operations
within a group occuring in different orders in different processes of
the group.

The reason why the rule is nevertheless true for the collective
operations defined in mpi-collcomm, is that the behaviour would be
undefined and reasonably unpredictable if the collective operations were
not done in the same order.

Sometimes there would indeed be a deadlock, unless each routine contains
an intial barrier-synchronising operation that determines that the call
made by each process are compatible. 

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

Couple of points:

1) If you guarantee no barrier then you are not permitting the
implementation to do any kind of error checking on the ordering of
context allocation - if any were possible anyway.

2) I dont see how the GUARANTEE can be made considering that the pool of
contexts allocated to the group is not inexhaustible - i.e.  sometimes
the implementation has to synchronise to get some more contexts.  So we
have a collective operation which may or may not synchronise, depending. 
Just like mpi-collcomm, really. 

> 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 !). 

I just dont get it with this function pointer stuff.  If you had a
heterogeneous machine then the memory map on the different architectures
is arbitrarily different and the relationship between addresses such as
those of pointers is also arbitrarily differet.  If you had a non SPMD
program - i.e.  different executables - then again the memory map is
totally different. 

Do I miss something? Or are you thinking only of SPMD and heterogeneous?

Best Wishes
Lyndon

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

---

From: James Cownie <[email-masked]>
Date: Wed, 28 Jul 1993 09:49:05 +0100

Lyndon,

> I understand that Tony intends to make "context" opaque, rather than

Unfortunately although a step in the right direction this does not
entirely remove the problem, since it is still possible to bind
different (intersecting) groups to the same context in different
processes. This leads to all of the "Who sent me this" problems. This
is not a locally checkable process, to ensure that it does not happen
context allocation and binding have to be collective. 

It's my relaxation of the second of these rules which leads to the
insecurities in my proposal. I am (of course) happier with those
mainly because the rule which must be obeyed for correctness is easy
to explain to the user.

> in all processes within the group."
I'm happy with your restatement, I see no major increase or decrease
in the clarity. Trying to reconstruct my thought processes I think I
used "node" rather than "process" to attempt to avoid any lightweight
process (== thread) confusions. As to the choice of "within" or "on" I
really see no difference at all. If it makes you happier though I'll
certainly take your formulation.

> made by each process are compatible. 
You're right, I was implicitly assuming a "barrier with key", and
matching of the keys which would immediately lead to deadlock.

Whatever the reason the statement is true, which is all I ask.

> > What this rule does allow us to do, is to locally      <==========
*** SORRY *** As Tom points outs this should say COLLECTIVELY
> context allocation - if any were possible anyway.

True, however at least the rule one has to obey is easy to understand.
In the cases where the barrier would be acceptable a check can be made
in a checking version of the library at least.

> Just like mpi-collcomm, really. 

The guarantee can be made because the failure happens when the
contexts are pre-allocated. Either there are enough or not AT THAT
POINT. If you don't pre-allocate, then the behaviour is as you
describe. (See mpi_groupsReserve, and the difference between
MPI_LOOKUPCREATE and MPI_LOOKUPCREATENB).

> Do I miss something? Or are you thinking only of SPMD and heterogeneous?

Yes you do. The function pointer and key  are not the context, they
are the key to allow you to get at the context. They are ONLY
meaningful entirely locally to the process. Really I'm just using a
trick to allow me to get the linker to produce guaranteed unique local
keys at low cost. Since these keys are entirely local to the process
it makes no difference whether we are on a heterogenous machine running
a non SPMD code or not. (Though as Tom points out [and I'll answer his
mail next !] the inability to compare these keys globally does remove
some security...)

Hope this helps.

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