Subject: Context proposals overview

From: [email-masked] (James Cownie)
Date: Tue, 23 Mar 93 15:39:41 GMT

Jim's initial summary/comments on the Contexts proposals

Gentlemen, here is my summary and initial comclusions on the three
extant Contexts proposals received via Lyndon. Since I have probably
misunderstood or misrepresented some of the proposals, please correct
me as appropriate.

Proposal I (Marc Snir)
----------------------
Key points :
A group and a context are identical.
All communication (including point to point) is addressed by group and
rank. 
The receiver MUST be a member of the same group as the sender, and
explicitly give the group as an argument to the receive function.

Group descriptors are not passable to other processors.

Creation of a new context involves creation of a new group which is a
group synchronising operation. 

For:
Simplicity, it's easy to explain and understand (and probably
implement).

Insisting on a group for all addressing gives the 0..n-1 rank model
for subgroups which aids in importing libraries. 

Against:
The receiver of a message has to both know the group of the sender,
and be a part of it. This feels like it makes servers hard, but may be
ok. If you keep having to go into the ALL group, then the security
which was the whole point of a context is lost.

The argument that contexts can be checked at the sender is incorrect
because a single process can be in many different groups/contexts, and
therefore the group/context must be transferred to ensure correct
matching. (Maybe this wasn't the intent of the comments anyway...)

I don't understand how to build a group/context using only point to
point messages. I still seem to have the bootstrap problem that I need
the new context to safely receive the message which will tell me what
the new context is.

Proposal V (Rik Littlefield)
----------------------------
Key points :
A desire to have caching of arbitrary library (or even user) defined
entities on the groups. 

Point to point communication is expected to be addressed by TID and
Context. TIDs have global scope, they can be passed around
arbitrarily.

There is explicit translation from (group,rank) to TID.

Group descriptors are local objects, but can be passed around through
special mechanisms. 

Contexts are globally unique, (and expected to be allocated locally
through one of the normal bit space partitioned schemes. i.e.
processor number // identifier. There appears to be an expectation
that the identifiers are managed closely), and can be passed
transparently in messages (? is this true ?).

Contexts are created inside groups, creating a context is a barrier
synchronisation (? is this true ?).

For:
The caching is good idea, but orthogonal to all the other issues, it
could be added just as easily to any of the other proposals

The use of TIDs in the point to point removes any issues of group
membership from these functions. There is thus a way to achieve any 
inter group communication which is required (even if it is unpleasant).

Against:
The complexity of the "paired exact match criterion" is non trivial to
explain. 

Proposal VI (Lyndon Clarke)
---------------------------

Key points:
ALL descriptors (process, group, context) are process local, but may
be sent elsewhere through special mechanisms.

Contexts are created inside groups, and are bound to them. The context
can be used to refer (indirectly) to the owning group. 

Creating a context is a barrier synchronisation of the group.

Three different forms of process address are discussed for point to
point messaging. (Ouch !)

For:
Can be made to address complex inter group communications

Against:
The complexity of the whole proposal.

The passing of opaque entities with translation is rather unpleasant
for people with homogeneous machines. Before this we could ignore all
of the type info, now we have to check some of it and take special
actions.

Jim's initial conclusions...
----------------------------

1) Marc's approach of insisting that all communications occur inside a
group has some simplifying effects. In particular it easily gives the
base shift for sub-groups, so that they "think" their processors are
numbered 0..n-1. It has the disadvantage that there is an extra
translation required on ALL communications. This will add to the
latency at the most fundamental level (though not much if we expect to
consume space linear in the group size).

2) Creating a new group for each context may be expensive, though Marc
suggests an implementation which makes this relatively cheap.
Adding Rik's caching ideas here could also defer the cost until it was
required. (e.g. there is no need to build a broadcast tree in a group
until the first broadcast is performed. [Fundamental optimisation 0:
"Don't do it until you need to, you might never have to do it at
all"])

At the moment I favour Marc's with added caching. Can anyone explain
where the big gain is from the added complexity of the others ?

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

---

From: L J Clarke <[email-masked]>
Date: Tue, 23 Mar 93 17:21:18 GMT

> group synchronising operation. 

More accurately it involves duplication of an existing group.

One problem which I have with this is that if we anticipate future
extension to groups which are dynamic in membership (they expand and
contract) then the duplication concept breaks because the identical
nature of the grouping is lost. 

This is why I much prefer to have contexts as references to groups and
groups as frames of contexts - the contexts shrink and stretch according
to the expansion and contraction of the underlying group. 

> Simplicity, it's easy to explain and understand (and probably

Indeed but please see further comments attatched to Proposal VI below.

> for subgroups which aids in importing libraries. 

Indeed and Proposal VI gives all (and more) of this aid.  

> which was the whole point of a context is lost.

The restriction in Proposal I really does make programming of
communicative functionally distinct groups hard.  I am thinking well
beyond singleton service processes and I have explained some of the
things I am thinking previous messages. 

> matching. (Maybe this wasn't the intent of the comments anyway...)

Our interpretations concur.

> Proposal V (Rik Littlefield)

... which the poor user *must* do.

> Group descriptors are local objects, but can be passed around through

Check.  If the feature of Proposal VI is a disdavantage of that proposal
then it is also a disadvantage of Proposal V! Just being consist :-)

> transparently in messages (? is this true ?).

Our interpretations concur.

> synchronisation (? is this true ?).

Our interpretations concur.

> could be added just as easily to any of the other proposals

Precisely and this is recognised in the revision of Proposal VI which
will be circluated within the hour. 

> inter group communication which is required (even if it is unpleasant).

It is unpleasant indeed.  I appreciate that I am stating a value
jugement here which may be interpreted as "my personal opinion".  In
fact at Edinburgh we have done plenty of intergroup communication
programming and the opinion is shared. 

> The complexity of the "paired exact match criterion" is non trivial to

I concur.

> Proposal VI (Lyndon Clarke)

The revision, particularly in the improved discussion notes, explores
the possibility that processes are expressed as identifiers but groups
and contexts are process local opaque references to objects of undefined
size and structure (implemenation dependent). 

> can be used to refer (indirectly) to the owning group. 

Exactly.  Please recall the point I made above about group (context)
duplication in Proposal I. 

> Creating a context is a barrier synchronisation of the group.

The proposal says this, the discusion explains that it may not be
necessary to actually synchronise.  My mind is still working on this
one. 

> point messaging. (Ouch !)

From the point of view of the MPI provider this is a just small
amount of additional work.  The three forms link to a generic send/recv
so there is not at all three times as much implementation.  The size of
a test suite increases of course.

Form the point of view of the MPI user there could be an issue here,
however the facilities can be described in a stepwise manner such that
users do not need to be explored to more complexity then they need to
use.  

The revision tries to clean up the business of presenting these forms in
a uniform syntactic framework which is one way to address the
"point-to-point contains too many procedures" concern. 

> Can be made to address complex inter group communications

Does address such communications directly and with expressive power. 

I'd like to add "For: VI is functional superset of Proposal I;
group/context user cache of V is easy to add to VI."

> The complexity of the whole proposal.

Proposal VI is larger than Proposal I which is at a similarly mature
stage of development, because it is more powerful, as I say it is
functionally a superset of Proposal I (and this is drawn out better in
the discussion in the revision).  

The facilities can be presented to users in a friendly fashion which
does not require substantially different entry level user sophistication
than Proposal I.  The more "advanced" facilities can be introduced in a
user manual after the more "basic" facilities.  I conjecture that there
is no real problem here. 

> of the type info, now we have to check some of it and take special

I mentioned above that if this is a disadvantage of VI then it must also
be a disadvantage of V. 

This was one suggestion as to how we might give the user an interface to
transmission of these opaque objects.  I'm sure we can think of other
approaches which avoid the implementor having to check the data type
description in homogeneous kit.  For example we could provide a set of
procedures which do the send and receive, although this does again add
more procedures to point-to-point which I am trying to avoid, honest
guv' :-) 

I do not believe that this is any big deal for the user, since the kind
of users who are currently doing this kind of programming (and they are
certainly not high priests) are understand and think about data
translation issues anyway. 

If these are the only real objections you have to passing around
descriptors then I am confident we can do something about that.  Would
you like to make a suggestion as to how you would prefer to see
transmission done?

> Jim's initial conclusions...

Proposal VI has all of the facilities, which has been implemented and
used in systems for a couple years now, and a whole lot more.  For speed
demons Proposal VI lets them use process descriptots (or identifiers)
directly. 

> where the big gain is from the added complexity of the others ?

I hope I did. If you need more explanation then please do ask.

Best Wishes
Lyndon

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