Subject: Requested action: add opaque object comparisons to Context chapter

From: Tony Skjellum <[email-masked]>
Date: Mon, 28 Feb 94 13:55:10 CST

Dear Context sub-committee,

The draft of the chapter passed with minor changes, to be posted.  For
now, I need to draw your attention to additional important, but minor
fixes not discussed.  These are very important for library developers,
and the standard is inadequate without them.  I encourage others to
look at their opaque objects to see if similar tests are needed elsewhere;
if so, this discussion might also be appropriate in Section 2.

Because we need to review text and fixes before the MPI editor's
meeting in mid to late March, I propose discussion on the enclosed
proposal, till March 7, to be followed by vote of subcommittee, but
only if there are objections to their inclusion, to be followed by
consideration by the whole MPI committee with e-mail vote, but only if
there are any objections to their inclusion.

Regards,
Tony Skjellum
	-	-	-	-	-	-	-	-

Some significant discussion transpired on "empty" and "invalid" objects
last week.  We did not get to a crucial, related issue, however.

The following type of operations need to be relatively cheap for libraries.
1) Comparison of two MPI_Comm opaque objects for 
       i) identity (reference copied)
       ii) congruency (closely related, but different contexts, etc)

This operation needs to be "fast" in good implementations so that
libraries can determine if distributed objects with communicators are
"compatible" to varying degrees, on the fly.  Use of attributes is
insufficient because many types of compatible communicators do not
share attributes.

2) Comparison of two MPI_Group objects for
	i) identity (including identical ranks)
	ii congruency

This group operation also needs to be specifiable as "fast" in good
implementations so that libraries can determine that distributed
group operations may be optimized or otherwise simplified if the
groups are the same or differ only by rank order.

Note: 2.ii is doable with group difference, but is recommended here for
	convenience, and is possibly more optimizable in this form.

      However, 2.i is not possible with group difference, but
      can be achieved by using MPI_GROUP_TRANSLATE_RANKS, and then
      studying the translation for the identity mapping (lots of work,
      not particularly scalable, ==> we need a specific solution). 

Note: In pointer implementations, where MPI_Comm and MPI_Group are
      really pointers, equality can be determined in C; in Fortran, it is
      always a reference or index and therefore allegedly comparable
      as integers. This is not enough, in general.  Implementations of 
      MPI_Comm as a structure would render == comparison illegal, and
      therefore a portable mechanism is needed.

      This discussion is extremely closely related to the agreement to
      have
		MPI_COMM_EMPTY, MPI_GROUP_EMPTY
      which are special "empty" communicators and groups, resp.

      We also will have

		MPI_COMM_INVALID, MPI_GROUP_INVALID

      which are equivalent to NULL pointers in a pointer implementation.
      These were added at the Knoxville meeting, but without any comparison
      mechanisms.
 
Proposal:
---------

1a. The following non-communicating, local operation is proposed:
	MPI_COMM_TEST_EQUAL(comm1, comm2, flag)
	IN comm1
	IN comm2
	OUT flag[2] (int)

flag[0] is MPI_IDENT if the communicator objects are identical in all respects
		(that is they would pass == equality for a pointer
			 implementation), flag[1] is undefined
        MPI_CONGRUENT if the communicator objects are dup's of each other,
			flag[1] is undefined
        MPI_SIMILAR  if the communicator objects are related as noted in (*)
		for this case, flag[1] is also defined, and is as follows:
			MPI_CONGRUENT if groups are congruent
			MPI_SIMILAR   if groups are similar
	MPI_FALSE  otherwise.

Both comm1 and comm2 are intra-communicators.

(*) The issue of MPI_COMM_MAKE, MPI_COMM_SPLIT, MPI_MAKE_CART,
MPI_MAKE_GRAPH must be addressed.  These calls do not pass attributes.
They also permit subgrouping to occur in this collective step.
However, if the "new group" specified is the same (for MPI_COMM_SPLIT:
one color, original or permuted ranks used) as the original group,
then the implementation can recognize this, and subsequently return
MPI_SIMILAR, because these communicator constructors have effectively
replicated a communicator, and this information is of value to a
library.  [I have specifically asked for Rolf for clarification on
intended the behavior of the MPI_MAKE_CART/_GRAPH this morning, yet I
am already convinced that they have the same semantics as
MPI_COMM_MAKE.]  It is useful to distinguish between congruent and
similar communicators, because of attributes, and topologies.

1b. The following non-communicating, local operation is proposed:
	MPI_INTERCOMM_TEST_EQUAL(comm1, comm2, flag)
	IN comm1
	IN comm2
	OUT flag[3] (int)

flag[0] is MPI_IDENT if the communicator objects are identical in all respects
		(that is they would pass == equality for a pointer
			 implementation)
		For this case, flag[1] and flag[2] are undefined.
       MPI_CONGRUENT if the communicators are related through a dup,
		For this case, flag[1] and flag[2] are undefined.
       MPI_SIMILAR:
		For this case, flag[1] is
			MPI_CONGRUENT if local groups are congruent
			MPI_SIMILAR   if local groups are similar
		and flag[2] is
			MPI_CONGRUENT if remote groups are congruent
			MPI_SIMILAR   if remote groups are similar
		(Related, but not created through a dup)

	MPI_FALSE  otherwise.

Both comm1 and comm2 are inter-communicators.  
 
2. The following non-communicating, local operation is proposed
	MPI_GROUP_TEST_EQUAL(group1, group2, flag)
	IN group1
	IN group2
	OUT flag (int)

flag is MPI_IDENT if the group objects are identical in all respects
		(that is they would pass == equality for a pointer
			implementation)
        MPI_CONGRUENT if the group objects are dup's of each other
		(see ***) [ie, same members, same ranks]
	MPI_SIMILAR if the group objects are identical except for
		permutation of ranks (see ***)
	MPI_FALSE otherwise

(***) Although there is no MPI_GROUP_DUP capability in MPI,
MPI_COMM_GROUP creates a copy of a group object, so groups can
effectively be duplicated.  Other calls also can effectively
duplicate groups, perhaps identically, perhaps with rearrangement
of ranks.

(PS Given the final semantics of MPI_COMM_GROUP, the re-inclusion
of MPI_GROUP_DUP seems reasonable, but can be achieved other ways.)
	-	-	-	-	-	-	-

Relationships between parts 1 & 2.  

a. MPI_IDENT for groups and communicators mean that the user or a library
copied a reference (created by MPI) (e.g., when making a data structure).

==> Identical communicators have identical groups.

b. MPI_CONGRUENT for groups and communicators mean that the system made
a duplicate reference to the object.  

==> Congruent communicators have congruent groups.

c. MPI_SIMILAR

Similar groups are well defined above, using MPI_GROUP_TEST_EQUAL. 

Similar intra-communicators have either similar or congruent groups,
as noted above under MPI_COMM_EQUAL.

Similar inter-communicators have their local and remote groups
defined as noted above under MPI_INTERCOMM_EQUAL.

	-	-	-	-	-	-	-

!!! Consequences of potentially omitting this functionality. !!!

It is now possible, but expensive to tell if two groups are identical,
in a portable way.  It is not possible to say anything about
communicators.  This will limit runtime optimization of libraries that
use persistent distributed objects (like vectors and matrices) and
want to compare communicators, when two such objects appear as
arguments.  This kind of testing will be wanted by library developers.
Library writers will tend to encapsulate communicators in different,
incompatible ways, to get this functionality, if it is not inherent in
communicators.  This will limit interoperability of libraries.

Note: Because relationships cross boundaries where user-defined
attributes do not follow, no adequate mechanism for using user-defined
attributes has been found as an alternative to the above
functionality.

Impact on implementations/performance:

The impact on performance should be strictly positive or zero.  Groups
and communicators that are identical will be identifiable easily by
implementations (O(1) time).  Groups that are similar will be
identifiable in time no worse than what an MPI_GROUP_DIFFERENCE could
do, without asking the user to deal with the empty group, etc, and
possibly much better if internal tagging of related groups is
incorporated into an implementation.
 
This functionality does not impact any communication functions of MPI;
it is strictly bookkeeping on processes.
 
Who will use this?

Library writers who are trying to reduce overheads or discover shortcuts
while operating on distributed data structures, defined in unpredictable
ways by users and libraries, and therefore mainly amenable to runtime
optimization.  A good example would be redistribution of a vector
from one topology to another.  If the shape is different, but the 
underlying processes are the same, the amount of communication could
be significant reduced.

Average users will not use this capability, so that the exposition of MPI
is not particularly complicated.