Formally define "collective call"

The collectives (allreduce, barrier, broadcast), and constructors for team and dist_object all state a precondition that the function must be called "collectively". Most users have an intuitive notion of what "collective call" means, but it should be formally defined to avoid ambiguity. In particular, the intuitive notions can get ambiguous and fuzzy when it comes to issuing multiple non-blocking collective calls on disjoint subteams.

Here is the UPC definition of "collective" (although note UPC does not have teams):

collective
constraint placed on some language operations which requires evaluation of
such operations to be matched across all threads.(4) The behavior of collective
operations is undefined unless all threads execute the same sequence of
collective operations.

(4)A collective operation need not provide any actual synchronization between threads,
unless otherwise noted. The collective requirement simply states a relative ordering property
of calls to collective operations that must be maintained in the parallel execution trace
for all executions of any legal program. Some implementations may include unspecified
synchronization between threads within collective operations, but programs must not rely
upon the presence or absence of such unspecified synchronization for correctness.

Here's some GASNet (currently non-normative) text about this topic, dealing with team issues:

To avoid deadlock when using team collectives, a client must follow
certain ordering constraints.  Informally, we require that for any
pair of collectives all images which participate in both must agree on
their ordering.  Formally this may be expressed as follows.

  For any collective X let Participants(X) denote the set of images which
  are members of the corresponding team.  For non-team collectives,
  Participants() is the set of all images across all the GASNet nodes.

  For image I, and collectives X and Y, let Precedes_I(X,Y) be a
  predicate true when X != Y and collective X is initiated before
  collective Y on the node hosting image I.

  For all collectives X and Y:
    For all images I and J in Intersection(Participants(X), Participants(Y)):
      Precedes_I(X,Y) = Precedes_J(X,Y).

Note there is no ambiguity when X==Y or I==J

MPI deals with this issue in a less-than-formal, operational manner, eg 5.13:

A correct, portable program must invoke collective communications so that deadlock will not
occur, whether collective communications are synchronizing or not. The following examples
illustrate dangerous use of collective routines on intracommunicators.
(followed by 8 pages of examples)

Basically saying that portable programs must remain deadlock-free under the assumption every collective initiation executes a full barrier across the given team. This is essentially the same condition outlined formally by GASNet.

Lots of additional relevant info in issue ~~#13~~.

Comments (5)