Subject: re: static contexts writeup

From: Tony Skjellum <[email-masked]>
Date: Wed, 10 Mar 93 05:10:50 CST

[My comments prepended with **** - Tony]

**** In mail immemorial, Rik agreed to merge his (enclosed) write-up with
**** the first-generation PRECIS, to generate a more useful one,
**** Please correct me if I am wrong, but I cannot find this!
**** (Again, I apologize for calling this a PRECIS, not a SKETCH.)
**** I want to generate the next version of this SKETCH/PRECIS,
**** with specifics garnered from our lengthy bantering and 
**** discussions.  Particularly, I will discuss the sparse matrix
**** of proposals X closure options.  Lyndon, you indicated that
**** one of my comments challenged you to make a new added entry
**** to one of the proposal categories.  May I have that now/soon?
****
**** In interest of refocusing discussion, I will work on such a
**** new PRECIS/SKETCH, reviewing all the mail flurry from last days,
**** and then suggest writing assignments.  Lyndon will be off-line, but
**** Lyndon will still get some brain work to do off-line. :-) Lyndon
**** will you phone me periodically, to stay abreast of things?
**** Perhaps we will need the manpower of Rusty/Bill to help us, given
**** the amount of work on filling the sparse matrix of issues.  Willing?
****
**** Our PRECIS/SKETCH and work from it will not address the following things
**** (related to discussion in our group, but not central to it):
****	-	the fully portable MPI program
****	-	I/O
****	-	the semantics and syntax of process management
****	-	the time-table for MPI-1,MPI-2,MPI-3,...
**** In a truly global sense, these could be construed to be closure as
**** well, but I want to exclude them for sanity reasons.  I do believe
**** that parts of these issues could be addressed within MPI-1, but
**** it is not now this subcommittee's role to do that for MPI at-large.
**** Strong objections?  If so, we are in deep trouble:-)
****
**** We will assume that discussion in this 4-proposal X closure effort is
**** all essential to MPI-1.  Anything you really don't think is essential
**** for MPI-1... once we agree to same .... should probably get deferred.
**** Is that controversial?
****
**** I thank everyone for their sincere efforts.
**** - Tony
****
**** PS Per constructive advice from Rik, all of my mail is getting copied to
****    mpi-context now.  All should do so.  I did not hear any dissent
****    about this suggestion, and it adds potential help to
****    discussion.  As we need the help, and few people are writing
****    anyway, this will not likely cause problems.
****    Continue to include the five names jim, lyndon, tony, sanjay &
****    Rik, incase any of us are not on the mpi-context mailing list!!!
****
**** PPS Lyndon, where are you.  I got up at 4am to read the next round
****     of mail from you, but none to be found :-)
****

**** Rik writes...

>Before it gets TOO stale, here's a copy of my writeup on static
>contexts et.al. as it last went to Lyndon and Tony.  (You two can
>stop reading at the line of dashes.)  
>
>I have opted not to hack on static contexts any more because I
>would rather kill them.  
**** Is this a proposal to include static contexts as in within
**** the 4-proposal model, and that we stop working on same?
**** If so, I can make it so...
>I now suspect that I would trade static contexts for something
>like the MPI_set_group_attribute cacheing facility that I have
>outlined in recent email.  I will think more about this and get
>back to you.
>
>In the meantime, I would very much like more feedback on the
>cacheing facility, especially how it breaks.
>
>Thanks,
>--Rik
>
>----------------------------------------------------------------------
>

>This note discusses message context ID's -- what they're good for,
>how to generate them, how to use them.
>
>Credits.. At the last Dallas meeting, Mark Snir asked me to write
>up some thoughts on this topic and to send them around to the
>whole committee.  Paul Pierce, Tony Skjellum, several other
>people (whose names I can't remember) and I discussed some of the
>ideas over lunch on the last day.  Then Lyndon Clarke of the
>contexts subcommittee emailed me asking for some clarification of
>static context generation, which I guess I'm the main proponent
>of.  He reviewed an earlier (and even longer) draft of this note,
>and it is now much improved.  (Thanks, Lyndon!)  However, I have
>substantially rewritten it since talking with any of those folks,
>so I have to take full blame for the fallacies of this version.
>
>1. Notation and assumptions
>
>  In this note, I assume that
>
>    . "context ID" means a message selection field 
>      that cannot be wildcarded,
>
>    . "tag" means a message selection field
>      that *can* be wildcarded, and 
>
>    . context ID, tag, and process ID are the *only* fields 
>      that can be used for pt-pt message selection.
>
>  In particular, I assume that "group ID" cannot be used for
>  selection unless it is somehow propagated into the tag or
>  context ID fields.
>
>  I will speak of "modules" that operate within "groups".  By
>  "module", I mean a procedure (subroutine) or collection of
>  procedures that can exploit knowledge of each other's internal
>  workings in order to coordinate their message passing.  By
>  "group", I mean a collection of processors identified by a
>  globally unique "group ID".  By "operating within a group", I
>  mean that the module is called simultaneously by all processes
>  belonging to the group and exchanges messages primarily with
>  those copies of itself.  (I assume that arbitrary communication
>  is always possible.  The focus of this discussion is how to
>  make restricted communication easy.)  I assume that the group
>  ID is passed into the module.
>
>  I will also speak of an "instance of a module".  By this, I
>  mean a module, plus the group that it is operating in, plus the
>  data it is working on.  (The latter becomes important if the
>  module supports nonblocking operation.  In that case, I assume
>  that some data ID is passed into the module.  An example is the
>  'tag' argument of the nonblocking collective routines.)
>
>  My notation requires that independently written modules can be
>  called sequentially within the same group.  Specifically, if a
>  a group must be "duplicated" in order to guarantee that two
>  modules do not conflict, then I will say that those modules are
>  operating in different groups.
>
>  By definition, independent modules do not coordinate their use
>  of tags.  (A module can of course coordinate with itself.
>  That's what tags are for.)
>
>2. Why do we want context ID's?
>
>  The most important purpose of context ID's is to avoid message
>  collisions between independent modules.  (This is the only way
>  to avoid such collisions, since coordination of tag values is
>  excluded by definition.)
>
>  Context ID's are sometimes also be the best way to avoid
>  collisions between instances of the same module.  (This depends
>  on the definition of "best", as discussed below.)  The tag
>  field can also be used for such avoidance, since the module has
>  full control over how the tags are used.
>
>3. Desirable features of contexts and groups:
>
>  I think there will be little debate about these:
>
>    A. It should easy to write modules that don't conflict with the
>       same or other modules, even when the modules are called
>       within overlapping groups.  (Or, save us all, with multiple
>       outstanding non-blocking operations.)
>  
>    B. It should be easy to call these modules.
>
>  There may be more debate about these, but I like them as sanity
>  checks:
>
>    C. The MPI routines that manage groups and contexts should 
>       be definable in terms of MPI point-to-point communication
>       and process-local operations.  
>
>       (For example, I get nervous about group and context
>       management semantics that require asynchronous servers or
>       their equivalent, like an asynchronous atomic
>       fetch-and-increment.  We already decided to eliminate
>       interrupt receive at the user level, on the argument that
>       it was too hard to implement correctly.  Asynchronous
>       servers are a bit easier, since they can run on
>       resources other than the processes calling MPI, but
>       personally I would rather avoid servers if possible.)
>
>    D. The "closed-system constraint": standard global operations
>       (e.g., broadcasting within a group) should be definable in
>       terms of MPI point-to-point and group/context operations.
>
>       (For example, we must be careful to avoid bootstrap
>       problems like needing a context specific to a group, in
>       order to create the group.)
>
>3. How do modules get and use context ID's ?
>
>  Assume that we have already created a group and distributed its
>  group ID, and that we have a mechanism for broadcasting within
>  the group.  (More on this later.)
>
>  Then we have at least the following options for managing
>  context ID's:
>
>  Option 1. "Context ID = group ID" (and no group-dup'ing).
>
>    By my definition of "same group", i.e. dup'ing gets you
>    a different group, this option means that two modules can
>    get called back-to-back with the same context.
>
>    I think this is OK, courtesy sequencing constraints, if and
>    only if both modules use exact match on tag and source.
>    Since the group ID is already available (passed in), this
>    provides a simple and efficient mechanism for many useful
>    algorithms, such as blocking global ops.
>
>    This option fails, however, with modules that use wildcard
>    tag or source.  (I won't bother to provide an example -- 
>    having the same context is the same as having no context,
>    and we know what havoc that creates.)
>
>  Option 2. One process obtains from MPI a unique context ID
>            for each instance of a module, and distributes it
>            for that instance's use.
>
>    I believe that this is the strategy proposed by Tony Skjellum
>    in his 3-page handout at Dallas.  The distribution might be
>    done either within a module or by its caller.  Presumably
>    there are more callers than modules, so doing it within the
>    module is preferred.  As noted above, distribution of the new
>    context can be done with a broadcast using exact match on
>    tag and source, with context=group, presuming of course that
>    the module follows the rule of doing wildcard matches only
>    in a different context.
>
>    In the Dallas discussions, it seemed to be assumed that this
>    option requires an asynchronous server, since the context
>    generation calls have to be coordinated to ensure uniqueness
>    but can occur at any time.  This bothered me.
>
>    However, I realized while writing this note that this option
>    can also be done without a server by having a process-local
>    pool of preassigned context ID's.  For example, let the
>    bottom bits of a context ID be the ordinal (in some global
>    numbering scheme) of the process that assigned it, and manage
>    the upper bits however you would in a server.  For P
>    processes, this would require at most log(P) extra bits in
>    the context field, compared to having a server.
>
>    So now my main concerns about this approach are the extra
>    communication to distribute the context ID's, plus a nagging
>    feeling that there's still a bootstrap problem if this is
>    the only option.
>
>  Option 3. "Static context ID's"
>
>    This is the option that I pushed at the Dallas meeting.
>
>    The idea is that each module gets a context ID that is based
>    solely on a source code key, then manages its tag values to
>    keep the groups and instances separate.
>
>    To be definite, assume that a module can obtain a context ID
>    via a call like
>
>      error = MPI_get_context_for_name (name, &contextID)
>
>    where <name> is the character string unique to the module, and
>    the generated context ID depends only on the supplied name.
>    This call is made independently on all processes wishing to
>    share the context.
>
>    The simplest convention would be to require that <name> be
>    the name of a procedure within the module.  That way the
>    linker guarantees uniqueness.  There are other ways to get
>    unique strings, such as the "dollar bill algorithm" and
>    whatever strategies people use to reserve names for expansion
>    of libraries, but these do not affect the basic idea.
>    However, you cannot use the address of a routine in place of
>    its name, since this would not work in heterogeneous systems.
>
>    The most efficient strategy is to require that all names be
>    "registered offline".  By this, I mean that MPI be given a
>    list, prior to execution, of all the names that might be
>    passed to MPI_get_context_for_name by this particular
>    program.  There are several ways that this could be
>    accomplished.  For example, if we require that the names
>    always be those of modules, then a (conservative) list can be
>    generated at link time using Unix 'nm' or equivalent.
>
>    With offline registration, MPI_get_context_for_name can
>    be implemented so as to require no communication at all.
>
>    We can go farther and require that <name> be a constant
>    string, in which case the call to MPI_get_context_for_name
>    could be implemented as a compile-time macro substitution.
>    (I hate citing it, but as precedent I note that this strategy
>    is used by the optimizer for some versions of 'Linda'.)
>
>    Without offline registration, it seems that MPI_get_context_for_name
>    would require an asynchronous server.  I will not discuss this
>    further because in my view static contexts are intended to
>    make for simple implementations and fast execution.
>
>    OK, now we can quickly and efficiently (zero execution
>    cost) get a context ID that is unique to the module, but all
>    instances of that module have to share the context.  (Please,
>    no kneejerk reactions -- hear me out before labeling this as
>    a stupid idea in complete violation of the spirit of contexts.)
>
>    How does the module keep multiple instances straight?
>    It uses the message tag field.
>
>    The idea is to generate an MPI tag value by smushing together
>    the group ID, data ID (if needed), and the nominal tag value
>    that the module would have used if it didn't have to worry
>    about multiple instances.  No other module cares how the
>    smushing is done -- the context is unique and we have agreed
>    that modules can use the tag bits however they want.  This is
>    just an example of a module coordinating with itself
>    regarding how to handle the tag bits.
>
>    Yes, this scheme does seem like jumping through a hoop, but
>    it does have some advantages.  If the group and data ID's are
>    short enough to be smushed into a message tag without losing
>    any bits, then the MPI tag can be generated with absolutely
>    no communication.  This means that:
>
>      1. It provides a method to implement other group
>         and context management functions that is bulletproof
>         and free of bootstrap problems.  
> 
>      2. It executes fast.
>
>    To understand the first advantage, consider the problem of
>    how to implement MPI_close_group(gid) using only MPI pt-pt
>    operations.  Remember that the module executing within that
>    group on other nodes can legitimately still have a wildcard
>    receive posted.  If MPI_close_group tries to use the group
>    context, its messages can get eaten.  Sync the group first?
>    That just means you have the same problem implementing sync.
>    Having static contexts for MPI_close_group and/or sync solves
>    this problem.  Are there other solutions for which MPI pt-pt
>    operations would be sufficient?
>
>    The second advantage is perhaps weaker, but I for one keep
>    finding myself writing modules that are sensitive to
>    communication performance, particularly latency.  In many
>    cases, I would prefer to write a few extra lines of code than
>    to use functionality that would cost extra messages.  I
>    have lots of experience with tag-smushing due to working
>    with low-functionality communication systems (like select
>    on message tag only, and no useful wildcarding).  I find
>    that extra coding effort is very small.  Typically it's
>    embedded in a macro call or cover routine, so that I still
>    have to write only one line of code to handle a message.
>
>    Note that I do NOT propose static contexts as a solution for
>    everyone.  However, they are useful for speed, and may be
>    required under the closed-system constraint.
>
>4. Summary
>
>  It looks to me like all three options presented here are
>  complementary.  They might all might be provided, in the
>  expectation that they will be used by different audiences.
>
>Questions, comments?
>
>--Rik Littlefield
>
>

---

From: [email-masked]
Date: Wed, 10 Mar 93 11:46:20 PST

Tony,

You write

> **** Please correct me if I am wrong, but I cannot find this!

I think I'm clean.

The exchange was

> > > (Tony writes)
> > > So, my first action item is to get a merger of what you wrote and our
> > > precis, and redistribute that to group.  OK?
> > 
> > (Rik replies)
> > I'm not sure that I've seen your precis yet.  The stuff you've sent me
> > so far seems to be quite a ways from precise (pardon the pun), so I'm
> > reluctant to guess what's what.  Can you send me a labeled copy?
> > 
> > It would be faster and perhaps less confusing if I incorporated the
> > last round of your and Lyndon's comments into my words and distributed
> > that to the subcommittee as a separate document.  Then we would have
> > a collective opinion (well, five separate ones anyway) of how the
> > two documents fit together, instead of just the one opinion of whoever
> > did the merger.
> 
> (Tony replies)
> Yes, I concur.  Go ahead.

Several copies of my document were subsequently distributed, including
ones by me and by you!  As I noted when I sent it out, I did not
incorporate your and Lyndon's comments because I decided my time
might better go into exploring cacheing mechanisms.

By the way, I'm sorry, but I'm still not sure that I have correctly
identified your precis or sketch or whatever.  You sent me some stuff
at a level of detail like

> Proposal II. GROUP ID != CONTEXT
> 
> GROUP corresponds to "data/instance" in this model
> CONTEXT is statically defined at link time, corresponding to
> 	code or class
> 
> In this model, group ID's appear explicitly, and separately
> from CONTEXTS in global operations.  It was noted by Littlefield
> that he would write global operations, and product bits of the
> GROUP ID and static CONTEXT to guarantee that his code produced
> unique, deterministic, non-interfering results.
> 
> Proposal III. GROUP ID null, GROUP scope == CONTEXT scope
> 
> CONTEXT is a dynamic concept, and global (or as global as necessary)
> Whenever a group is created, a context is assigned to it.  CONTEXTS
> are used to disambiguate global operations.
> 
> GROUP ID is the CONTEXT for the group.  
> 
> GROUP is an enumeration of PROCESS ID's OR ONE OF SEVERAL
> 	possible hashing formulas, with exceptions (more scalable)

with a bunch of comments interspersed with it.  

Is this what you are talking about?  In other mail, you have mentioned
a "sparse matrix of proposals X closure options", but I haven't the
foggiest idea what that refers to.

Help?

--Rik Littlefield