Subject: mpi-context: context and group (medium)

From: L J Clarke <[email-masked]>
Date: Thu, 8 Apr 93 15:56:22 BST

Dear MPI Colleagues

This letter is about groups, contexts, independence and coupling
thereof, the kinds of point-to-point communication which we have talked
about, and to brief extent libraries. 

Before embarking on the guts of the letter, I should like to express
very strong support for the suggestion that MPI users can cleanly
program in the host-node model.  In my opinion, this model of
programming is of considerable commercial significance, and I observer
that their are a number of important programs around which use this
model. 

			o--------------------o

I understand three different kinds of point-to-point communication which
have been discussed by various people in MPIF.  I write these out with
separate group and context concepts, as per a previous message to
mpi-context [Subject: mpi-context: comment and suggestion].  I will then
discuss coupling of group and context.  I refer the reader to my prevous
message to mpi-comm which described classes of MPI user libraries
[Subject: mpi-comm: various (long)], as their is some follow on
discussion below. 

Groupless (process addressed)
-----------------------------
(process, context, tag)
Wildcard on process, tag.
No wildcard on context

Intragroup (closed group)
-------------------------
(group, rank, context, tag)
Wildcard on rank, tag. 
No wildcard on group, context.

Intergroup (open group)
-----------------------
(lgroup, rgroup, rank, context, tag)
Wildcard on rgroup, rank, tag. 
No wildcard on lgroup, context.

Observe that "group" in intragroup and "lgroup" in intergroup  are the
same thing, they are the group of the callling process.

Since neither "group" nor "context" in intragroup can be wildcard then
there  may  appear to be appeal in some coupling of them  in order  to
provide  shorter  syntax and  easier  context/group  management.  This
implies that we couple context to group of calling process.  Now  this
coulping  is not compatible  with intergroup  since  the  two  calling
processes have  different  groups, thus different  contexts, thus  the
send and receive can never match. We can resolve this  difficulty by a
more careful statement of where the context of the message is coupled.
In particular  we can state that the context of the message is coupled
to the  group of the message receiver.   In  this way we would express
intragroup  as a coupling  of (group,context),  and  we would  express
intergroup as a pair of such couplings.

The claim  we have  heard that  context  and  group  must  be strongly
coupled, resulting in a proposal which asserts that context and  group
are identical,  is  possibly nothing  more  than a  consequence of  an
assumption  that messages may only be  distinguished  on the basis  of
(process, context, tag)  (here process is a process label which can be
a rank  within  a group).   Given  that  assumption, we  can only  use
context to  distinguish messages within different groups  and  the two
entities become  strongly coupled.   Examining records  of  the  early
meetings  of  MPI,  I  find  that  this "decision"  was  made  by  the
point-to-point subcommittee  in a straw  poll which rejected selection
by group by  a narrow  majority of 10 to 11. Please note also that the
same  meeting  rejected context  modifying process  identifier  ---  a
"decision" which we are already  often  ignoring.   These  "decisions"
predate the existence of  the contexts  subcommittee  and the vigorous
discussion of contexts and groups which has been and continues to take
place.  We should uniformly be  open minded enough  to allow ourselves
to question all such "decisions", and to change them if we see fit.

The description of  MPI  user libraries which has been  given by  Mark
Sears and  myself strongly  suggests  that  context and group  must be
independent entities. 

Provision  of the process addressed communication immediately suggests
that a context can appear without coupling to a group in which case it
seems (to me) that they are independent entities.

There  is an  argument  against process  addressed communication which
says that process addressed communication gains nothing in performance
over intragroup  communication  in the group of all processes.  If the
process  description in process addressed communication will, for sake
of generality and thus portability, have to be an some kind of pointer
to a process description object which contains whatever information is
needed to route a message to the intended recipient.  It could be just
that (in C, at  least), a pointer.  Sometimes,  on  some  machines, it
will actually  be implementable with some other kind of magic which is
more scalable, but it must always appear the same way.  It could be an
index, representable as  an integer in the host language, into a table
of process description objects  (better for F77, for sure).   It could
be  a  rank in  a group  of (all)  processes, used as an  index into a
process  description object table,  which is  just fine  for  a static
process model (and reflects existing practice).  It could be some kind
of global  unique process  identifier which is again  user as  a table
index  somewhere.  If  tables  grow too large in either of the  latter
cases, then there may be some hashing and/or caching involved.

There are counter arguments. I give one,  and invite you to give more.
On some machines,  the global unique process identifier is  sufficient
to route the message, and is representable  as an integer in  the host
language. For example, the global process id can be a composite of two
bit fields (nodeid,  procid) where nodeid is a physical processor node
number and procid is a process number  on the node, and the nodeid bit
field is sufficient to route.  In  these cases, there is no need for a
process description object table, and no need to do a table lookup. We
probably all have used machines just like this.

For  me the arguments  have  piled up  in favour  of context and group
being separate and  independent entities.  This letter therefore makes
the recommendation that context and group are separate and independent
entities. In that light  I propose further discussion on management of
contexts within and between processes, and within  and between groups,
and on the  subject of the use objects which bind one or more contexts
and  one or more  groups in  order  to keep  the  communcation  syntax
compact by overloading. I shall post another letter to you tomorrow.

			o--------------------o

Comments, questions, (flames :-) please?!

Best Wishes
Lyndon

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

---

From: [email-masked]
Date: Thu, 08 Apr 93 11:29:42 -0700

> From: L J Clarke <[email-masked]>
> Subject: mpi-context: context and group (medium)
>
> ...
> 
> being separate and  independent entities.
>
> Lyndon

I agree, although I also see merit in associating a context with a group.

I would like to share my thoughts about context which lead me to think we need
two differently managed forms of context. Some of you have already heard this.

Most of the discussion about context has revolved around protecting two
different entities: libraries and groups. I think this is
required, but I think they need very differently managed contexts. One form
is not adequate to cover both needs without sacrificing performance.

Consider a SPMD program with these calls. Assume the calls are loosely
synchronous.

		call to LibA (Group1)
		call to LibB (Group1)
		call to LibB (Group2)

In a loosely synchronous environment, messages for the next call can come in
before the previous one has completed. Here we see two forms of overlap.

Within the call to LibA, we might get messages from processes which have already
entered LibB. If LibA and LibB are independently written, they might use some
of the same tags. To avoid messages from LibB matching receives in LibA, we
must use different contexts. If we have static contexts, allocated when the
libraries are initialized, each call in the library can quickly provide the
context to its point-to-point calls. If we only have dynamic contexts,
especially if contexts are carried inside groups, then a library must be
prepared to dynamically allocate a new context on any call when it sees a new
group. I know we discussed ways to do this locally, so the context could be
created and cached locally on the fly without communication, but I find the
idea of incorporating such code into every library call horrifying.

Within the first call to LibB, we might get messages from processes which have
entered the second call to LibB. Since these calls are in different groups, it
might be difficult to code LibB in such a way that messages could not
intermix, since a process' position in Group2 might be quite different from
its position in Group1. (I would hope that libraries would be coded so that
multiple sequential calls to the same library with the same group would be
safe. That seems to be current practice.) To keep the two calls from
interfering, it would be convenient to have a different context for each
group. If each group contains a dynamically allocated context, thats easy. But
if contexts are statically allocated, especially if they require a name
server, getting a new context for each new group might be a global operation
that wouldn't scale well.

So I propose that we need two forms of context, one that is quite static for
protecting code, and one that is more dynamic for protecting groups.

The only mechanism I know of that is adequate for protecting code is context
alloctated via a nameserver. In MIMD programs, one cannot say much about the
order in which libraries are initialized. Thus, if context is statically
allocated at initialization time, there must be a way to obtain the global
context value for a piece of code independently of other processes. A more
static method, such as a MPI registry or a "dollar bill server" has the
disadvantage of requiring a much larger value range for context. That uses
precious bits in the envelope of every message. Once a context is allocated to
a piece of code, it can be safely stored in a global variable without
endangering thread safety or shared memory implementations, because no matter
how many instantiations of the library store into the variable, they will
always store the same value.

There are nice dynamic mechanisms for allocating context for groups, which
require only communication within the group. This can piggyback on the
communication which is probably required to set up and synchronize the group
when it is created. For instance, one might set aside a small number of
context values for use by groups. When a group is created, every process in
the group could provide its current set of free context values, possibly as a
bit vector. After a groupwide reduction, each process chooses the smallest
value from the intersection, resulting in every process choosing the same
value.

Other forms of context protection might be required in the future. I don't
predict any, and expect that with both a static and a dynamic form, it is
likely that future needs would be covered.

The point-to-point calls might be configured to accept (group, rank, context).
In this configuration, the static context protecting the code is passed in
explicitly, and the context protecting the group is inside the group object.

I'm not sure how this interacts with cross-group message passing. Perhaps the
simplest solution is to use a well-known group context in such cases, which
effectively disables group protection.

Those are my thoughts on context. Although I think the methods outlined here
are simple enough, I would be happy to see simpler mechanisms that solve the
same problems. I am not comfortable with any solution that requires active
participation by every library call, no matter how local.

Paul