Subject: Mea culpa on previous letter to Ho/Pierce; Question about proposal VIII (Sears)

From: Tony Skjellum <[email-masked]>
Date: Sun, 9 May 93 21:31:10 CDT

Dear friends/colleagues:

1) I think I misunderstood who was saying what in my last message, re Ho/Pierce.
   But, I hope my point was clear.  I disagree with Howard on the concept that
   the context is convenient, but not important/essential.  I thank Paul for his
   examples.  If I was sounding inflamed, ignore that, I had low blood sugar.
 
   I think that the context should be a separate, logical extension to the tag
   field, the latter should be 32 bits long, for sufficient flexibility in layering,
   and the tag matching should permit layering by selective bit inclusion/exclusion.
   Please see that my tag matching and context/tag (as a logical partitioning) are
   correlated.  The MPI layer partitions the context field from the "logical tag,"
   and controls it.  The user has control over the format of the rest of the tag,
   and may build layers (or use other layers), that subsequently partition the rest
   of the tag to continue to build safe service layers.  That is why I keep pounding 
   the receipt selectivity mechanism based on the dont_care bits, and the care_bits.    
   
   I do not view the context as a large quantity in some implementations.  In certain
   cases, there might be as few as 16, but the implementer (like a compiler writer
   using registers), allows the code to work if the hard limit is exceeded, by
   reserving a context that supports a higher-cost propocal (eg, requeueing of
   messages).  

-------------------------------------------

2) Lyndon suggested some time ago that I revive my two-dimensional grid example, 
vis a vis Rik Littlefield's collections of examples, and ask how that applies to
Mark Sear's proposal VIII...

Basically, in this case, there is a two-dimensional logical array of processes
(a virtual topology), of shape PxQ.  In a given position (p,q), there are three
possible contexts for a given global operation G (eg, combine):

	1) G over the whole collective, PxQ topology
	2) G over the row that includes process (p,q) [the pth row]
	3) G over a column that includes process (p,q) [the pth column]

How many contexts are needed to provide for safe intermixing of operation G
over the three possible combinations.  Assume that the operations of 1, 2, 3
may operate in sequence correctly, for now (ie, two G's over the
whole collection work correctly).   This is true of multiple combines, deterministic
broadcasts, etc.  It is not true if there are non-deterministic G operations
included.

If there are three contexts of communication, then everything is fine, because
row G, col G, and whole G cannot interfere.  By extension, a total of three
unique contexts are needed for the whole PxQ topology, reusing the same context
on parallel (row, column) entities, and an additional one for the "whole."
I pointed up this example at an earlier MPI meeting.

In the Proposal VIII model, contexts and groups are disjoint, so no property of
group will provide the safety needed.  Hence, I assert that either three contexts
should be needed here, or tag values would be needed to disambiguate the G operations.

Now, in an earlier mail message, Ho/Pierce bantered about "how many contexts are
needed for a given group."  I argued, one per unique library, with the discussion
of non-deterministic broadcast, because I wanted my non-deterministic broadcast
to work safely when other communication was going on.  At least, there must be
a point-to-point context for a group, and a global operations context for a
group [which is what Zipcode 1.0 has].  Further non-deterministic operations
would need more contexts.  In the light of this issue, I would suggest that my
PxQ topology above reasonably needs 6 contexts of communication to be implemented
safely [and assuming that all global operations are deterministic, as asserted].

In short, six contexts are needed for this group.  In the PxQxR three-dimensional
case, the number is larger:

	1) G over the whole collective, PxQxR topology
	2) G over PxQ plane
	3) G over PxR plane
	4) G over QxR plane

By simple study, this requires 1 + 3 * 6 = 19 contexts to be implemented safely,
and sets a limit on the number of contexts that one would want to have, to support
a single 3D topology safely.

Remember, I am assuming that we are talking about Proposal VIII, which does not
offer group-based safety for messaging.  Proposal I, by Snir, does offer this
safety inherently [which masks the need for explicit contexts when dealing with
SPMD-type calculations].  I am arguing that the assumption of small numbers of
contexts (where small is about 8 or 16, and where the code breaks if the number
is exceeded) is not reasonable.  The code must continue to work, if slower, if
many contexts are needed, beyond that which is available as fast, hardware
contexts.  Proposal VIII must accomodate that to be reasonable.

In an application at Livermore, one of my colleagues uses multiple two-dimensional
topologies to implement stages of a calculation.  They overlap.  So, he wants
at least two unique topologies, completely supported, or at least 12 contexts.
If he goes to three dimensions, he want 38 minimum, for his code to work.

Summary: Proposal VIII cannot cope with practical situations illustrated above,
because it breaks when there are "too many contexts," and contexts are assumed
rare (eg, 8 or 16).  To be reasonable, it would have to have a fall-back to 
support many contexts in some way.  Lyndon and others have made this request,
in the past weeks.

Comments?  
- Tony