Domain Map Standard Interface¶

Status of this document¶

This document, as well as the DSI interface itself, are work in progress. We solicit feedback on both.

The following aspects are not documented yet:

• a summary of the six descriptor classes
• the requirements for a domain map to support associative, opaque, or sparse domains;
• the significance of dsiClone();
• the "local descriptor" classes;
• some required methods.

Additional Resources¶

Implementations of the standard domain maps may be consulted as examples. They are available in:

$CHPL_HOME/modules/dists
$CHPL_HOME/modules/layouts

In addition, the following publication provide more background information on domain maps in general.

• "User-Defined Distributions and Layouts in Chapel: Philosophy and Framework." Bradford L. Chamberlain, Steven J. Deitz, David Iten, Sung-Eun Choi. 2nd USENIX Workshop on Hot Topics in Parallelism, June 2010.

  The high level motivation and overview of DSI.

  https://chapel-lang.org/publications/hotpar10-final.pdf

• "Authoring User-Defined Domain Maps in Chapel." Bradford L. Chamberlain, Sung-Eun Choi, Steven J. Deitz, David Iten, Vassily Litvinov. CUG 2011, May 2011.

  A follow-on paper that outlines how to write a domain map.

  https://chapel-lang.org/publications/cug11-final.pdf

class GlobalDistribution¶

This class is visible to the users of the domain map: the dmap wrapper in Chapel's dmapped clauses wraps instances of this class. This class must be a subclass of BaseDist.

proc GlobalDistribution.GlobalDistribution() // or with arguments

Constructor(s) These are not regulated by DSI - their specifics are at the domain map implementor's discretion.

We suggest providing constructor(s) that accept, as an argument, an array of locales over which to distribute, with Locales as the default value.

proc GlobalDistribution.dsiClone(): GlobalDistribution

Returns a duplicate of this.

proc GlobalDistribution.dsiDisplayRepresentation(): void

A debugging method. It implements displayRepresentation() on the dmap wrapper.

proc GlobalDistribution.dsiEqualDMaps(that: /*some other GlobalDistribution*/): bool

Return whether or not the two domain maps are "equal" (specify the same distribution). This is invoked when == is applied to two domain maps.

class GlobalDomain¶

An instance of this class is created whenever a GlobalDistribution-mapped Chapel domain is created (e.g. when a domain variable is declared). There is a one-to-one correspondence at run time between a (conceptual) Chapel domain value and an instance of GlobalDomain. For presentation simplicity, GlobalDomain's properties refer to the properties of the corresponding Chapel domain value, when clear from the context.

Depending on the domain kind, this class is returned by the following method on GlobalDistribution and must be a subclass of the following class:

domain kind	creating method	required superclass
rectangular	dsiNewRectangularDom	BaseRectangularDom
associative	dsiNewAssociativeDom	BaseAssociativeDom
opaque	dsiNewOpaqueDom	BaseOpaqueDom
sparse	dsiNewSparseDom	BaseSparseDom

It is legal for these methods to return instances of different classes in different circumstances. (For example, due to the absence of multiple inheritance, different domain kinds require different classes.)

The DSI requirements apply to each of those classes. GlobalDomain is used in this document to refer to each such class.

The DSI requirements depend on the domain kind that is supported. The following requirements apply when supporting rectangular domains.

class GlobalDomain¶

class GlobalDomain ... {
  param rank: int;
  type idxType;
  param stridable: bool;
  var dist;
  ...
}

The fields rank, idxType, stridable are the attributes of the corresponding Chapel domain. (They could be replaced with parenthesesless functions of the same names and param/type intents.)

The field dist must contain a reference to the GlobalDistribution object that created this GlobalDomain. It is used when creating the (runtime) type for this domain, which contains the domain's domain map.

proc GlobalDomain.dsiMyDist() return dist;

Returns this domain's domain map. This procedure should be provided as shown. (Exception: see dsiLinksDistribution().)

proc GlobalDistribution.dsiNewRectangularDom(param rank: int, type idxType, param stridable: bool) : GlobalDomain(rank, idxType, stridable)

This method is invoked when the Chapel program is creating an uninitialized domain value of the type domain(rank, idxType, stridable) mapped using the domain map this.

This method returns a new GlobalDomain instance that will correspond to that Chapel domain value, i.e., be that value's runtime representation. The field dist of the returned GlobalDomain must point to this.

proc GlobalDomain.dsiGetIndices(): rank * range(idxType, BoundedRangeType.bounded, stridable)

Returns a tuple of ranges describing the dimensions of this domain.

dsiDims() and dsiGetIndices() have the same specification and so may be implemented in terms of one another.

proc GlobalDomain.dsiSetIndices(dom: domain(rank, idxType, stridable)): void

Updates the internal representation of this to match the index set of dom.

dsiSetIndices and dsiGetIndices are used to assign a domain value to a domain variable (or any domain l-value). Note: the arrays associated with this domain will be updated outside these method.

proc GlobalDomain.dsiSetIndices(ranges: rank * range(idxType)): void

The same as the other dsiSetIndices. Could be implemented like this:

{ dsiSetIndices([(...rangesArg)]); }

It is used to initialize the index set of the object returned by dsiNewRectangularDom() to the index set of the corresponding Chapel domain value.

iter GlobalDomain.these()

The serial iterator over the indices of this domain. Yields values of the type idxType if rank==1, otherwise rank*idxType.

iter GlobalDomain.these(param tag) where tag == iterKind.leader

iter GlobalDomain.these(param tag, followThis) where tag == iterKind.follower

The "leader" and "follower" iterators (defined below). They are invoked implicitly to implement parallel ("forall") loops over this domain. Currently the serial iterator must also be defined for "forall" loops to work.

The presentation below is tailored to the use of leader/follower iterators in domain maps. For a more general discussion, see:

$CHPL_HOME/examples/primers/leaderfollower.chpl

The job of the leader iterator is to:

• subdivide the given domain into subdomains,
• introduce parallelism between these subdomains, and
• place computations for each subdomain on the desired locale, as appropriate for this domain map.

The leader iterator must yield, for each subdomain it chooses, a description of that subdomain, created as defined below. Parallelism and placement are achieved, for example, by placing the yield statements within parallel loops and on statements. The leader is invoked (implicitly) once per parallel loop or expression over the corresponding domain.

The job of the follower iterator is simply to iterate sequentially over a subdomain whose description is yielded by the leader iterator, yielding all indices in that subdomain. Each time the leader yields a description, the follower is invoked (implicitly) with that description passed to its followThis argument. (The argument name must be exactly "followThis".)

For a zippered loop, only the leader for the first of the zippered items is invoked. Each time that leader yields a description, all followers are invoked in a zippered manner, with that description passed to their followThis arguments.

In general, it is up to the implementer of the leaders/followers whether and how to support their interoperability in this situation. That is, whether and how the description from the leader of one zippered item is handled by the follower of another item. For example, one could support zippering of similar items and generate a compile-time or run-time error when the items are not "similar".

DSI requires interoperability between domain maps only for rectangular domains, by prescribing:

1. how the leader builds the description of a subdomain, and
2. in what order the follower yields the indices of that subdomain.

class GlobalArray¶

An instance of this class is created whenever a Chapel array is created over a domain represented by a GlobalDomain. There is a one-to-one correspondence at run time between a (conceptual) Chapel array value and an instance of GlobalArray.

This class is returned by GlobalDomain.dsiBuildArray. It must be a subclass of BaseArr.

It is legal for GlobalDomain.dsiBuildArray to return instances of different classes in different circumstances. The DSI requirements apply to each of those classes. Here GlobalArray refers to each such class.

class GlobalArray ... {
  type eltType;
  var dom;
  ...
}

The field eltType gives the type of the array elements.

The field dom must contain a reference to the GlobalDomain object that created this GlobalArray. This is used when creating the (runtime) type for this array, which contains the array's domain.

proc GlobalArray.GlobalArray() // or with arguments

Constructor(s). These are not regulated by DSI -- their specifics are at the domain map implementor's discretion.

proc GlobalDomain.dsiBuildArray(type eltType) : GlobalArray(eltType, this.type)

This method is invoked when the Chapel program is creating an array value over the domain this with the element type eltType. This method returns a new GlobalArray instance that will correspond to that Chapel array value, i.e., be that value's runtime representation. The field dom of the returned GlobalDomain must point to this.

proc GlobalArray.dsiGetBaseDom() return dom;

Returns this array's GlobalDomain. This procedure should be provided as shown.

proc GlobalArray.dsiAccess(indexx) var: eltType

Given an index, returns the corresponding array element (as an l-value).

The domain map implementer is allowed to restrict the type of indexx that this method accepts.

proc GlobalArray.dsiSerialWrite(f: Writer): void

Writes out the array to the given Writer (e.g. a file or stdout) serially. Is used to implement write() on the corresponding array.

The restrictions on this method are the same as on GlobalDomain.dsiSerialWrite().

iter GlobalArray.these() var: eltType

The serial iterator over the elements of this array.

iter GlobalArray.these(param tag) where tag == iterKind.leader

iter GlobalArray.these(param tag, followThis) var where tag == iterKind.follower

iter GlobalArray.these(param tag) where tag == iterKind.standalone

The leader, follower, and standalone iterators.

These are defined in the same way as the leader and follower for GlobalDomain, except the follower must yield array locations.

Given a subdomain description passed to the followThis argument, the GlobalArray follower iterator must yield array locations corresponding to the indices yielded by the GlobalDomain follower, in the same order.

proc GlobalArray.dsiReallocate(d: domain): void

When this array's domain is assigned a new value, say newDom, first dsiReallocate(newDom) is invoked on this array. Then, dsiSetIndices(newDom) is invoked on this array's dom.

Correspondingly, dsiReallocate needs to adjust everything that won't be taken care of in dsiSetIndices.

NOTE: the formal's name must be exactly d at present (due to compiler specifics).

NOTE: this method can/should be a no-op if:

• GlobalArray stores its array elements in Chapel array(s), and
• the domain(s) of those array(s) are updated by dsiSetIndices,

as in the following simplified example:

class GlobalDomain : BaseRectangularDom {
  // required
  param rank: int;
  type idxType;
  param stridable: bool;
  const dist;
  // for example, store indices as a single Chapel domain
  var myIndices: domain(rank, idxType, stridable);
}

proc GlobalDomain.dsiSetIndices(dom: domain(rank,idxType,stridable)): void
{ myIndices = dom; }

class GlobalArray : BaseArr {
  // required
  type eltType;
  const dom;
  // for example, store elements as a single Chapel array
  var myElements: [dom.myIndices] eltType;
}

Given one instance of each class, say gd and ga, where ga.dom == gd the domain of ga.myElements is gd.myIndices. A call gd.dsiSetIndices(newDom) updates gd.myIndices, which, in turn, resizes ga.myElements, according to Chapel's array semantics. Nothing remains to do in dsiReallocate().

(Behind the scene, resizing of ga.myElements is implemented by dsiReallocate of the default domain map. That's the domain map that myIndices is distributed with, since myIndices's type provides no explicit domain map.)

proc GlobalArray.dsiDisplayRepresentation(): void

A debugging method. It implements displayRepresentation() on the corresponding Chapel array value.

Naming¶

Once you have chosen the name for your domain map, say, MyMap, we suggest naming the descriptor classes as follows:

in this document	in your code
GlobalDistribution	MyMapDist
GlobalDomain	MyMapDom
GlobalArray	MyMapArr
LocalDistribution	LocMyMapDist
LocalDomain	LocMyMapDom
LocalArray	LocMyMapArr

Some domain maps in this Chapel distribution use just the domain map name for their GlobalDistribution classes, e.g. Block and Cyclic.

What is privatization?¶

Privatization of an object X means providing a local copy of X on each locale. Such a copy is called the "privatized copy". On X.locale, X itself serves as the privatized copy. We refer to X as the "original object".

Privatization aims at reducing communication between locales. When X needs to be accessed (by reading its fields or invoking its methods) from another locale, its privatized copy on the current locale is used instead. Therefore, communication to X.locale is eliminated.

How does privatization work with DSI?¶

Privatization is optional in DSI. Each of the global descriptor classes can support privatization independently of the others. A class indicates to the Chapel implementation whether it supports privatization via its method dsiSupportsPrivatization() (see below).

Layouts (i.e. the domain maps that do not distribute domains across locales) can potentially benefit from privatization. However, the standard layouts do not support it.

The remainder of DSI privatization requirements must be implemented by each global descriptor class that chooses to support privatization.

The domain map implementation must provide methods to:

• create a privatized copy given the original object, and
• update a privatized copy when some other privatized copy changes (see "reprivatization" below).

The Chapel implementation:

• invokes DSI privatization methods to create or update privatized copies, and
• redirects original object accesses to its privatized copies.

The Chapel implementation creates privatized copies (over all locales) greedily as follows (if that class supports privatization):

• of a GlobalDistribution - when it is wrapped in new dmap() and when that wrapper is copied;
• of a GlobalDomain or GlobalArray - when the corresponding Chapel domain or array is created.

What is reprivatization?¶

Should any privatized copy be modified, the changes need to be propagated to all the other privatized copies. This propagation is called reprivatization.

The domain map implementation provides methods to update a privatized copy. The Chapel implementation invokes these methods when necessary.

DSI privatization requirements¶

The following requirements apply individually to each global descriptor class that chooses to support privatization. Global denotes such a class.

proc Global.dsiSupportsPrivatization() param return true;

Returns true to indicate that privatization is supported. NOTE: do not specify the return type (due to a bug in the compiler).

class Global ... {
  ...
  var pid = -1;
  ...
}

The field pid should be provided as shown. It should not be accessed by the DSI implementation except in conjunction with chpl_getPrivatizedCopy() as discussed later.

proc Global.dsiGetPrivatizeData()

Returns the data to be used as the argument to dsiPrivatize(). It can be a tuple of values or any other type, at the implementor's discretion. See dsiPrivatize() for explanation.

proc Global.dsiPrivatize(privatizeData): Global

Returns a privatized copy of this. The Chapel implementation invokes this method as follows:

• on the locale where the privatized copy is to be located,
• this is either the original object or its privatized copy created by dsiPrivatize on some other locale,
• privatizeData is the result of invoking dsiGetPrivatizeData() on the original object.

Typically dsiPrivatize() will need to copy and/or privatize some information from the original object into the privatized copy being created. This information could be obtained by querying this directly. Alternatively, it could be passed from the original object via privatizeData. This approach could allow the needed information to be bundled into the original active message, rather than requiring additional communications when accessing this.

proc Global.dsiGetReprivatizeData()

Similar do dsiGetPrivatizeData(), except the result is used as the argument to dsiReprivatize().

proc Global.dsiReprivatize(other: Global, reprivatizeData): void

Updates a privatized copy.

this is the object to be updated as part of reprivatization.

other is either the object whose modification originally necessitated reprivatization or one of the privatized copies that have already been updated for that modification by dsiReprivatize().

reprivatizeData is the result of invoking dsiGetReprivatizeData() on the originally-modified object.

Q: What modifications must dsiReprivatize() reflect?

A: Any changes that the domain map implementation may perform on an instance of Global (or its privatized copy) after that instance has been created and privatized.

For example, GlobalDomain.dsiReprivatize() must reflect any changes that GlobalDomain.dsiSetIndices() may perform.

Tip: testing privatization¶

In addition to the usual correctness testing, it may be useful to check whether array access is purely local, i.e., results in no communication. This can be done using local statements.

(A local statement performs runtime checks that report an error whenever any communication occurs within the its body.)

Here is a simple example:

// declare an array that uses the domain map to be tested
var A: ...;

// initialize it
A = value1;

forall loc in (locales that A is distributed over) do
  // run the check on each locale
  on loc {
    // value2 to be different from value1
    var valTemp = value2;
    const idxTemp = (an index (tuple) that is mapped to the locale 'loc');
    local {
      // Access the array.
      // This statement succeeds if there is no communication.
      valTemp = A[idxTemp];
    }
    // reference the read value
    assert(valTemp == value1);
  }

Tip: privatized copies should reference privatized copies¶

The global descriptor classes are required to reference each other (e.g. GlobalArray.dom references GlobalDomain; GlobalDomain.dist references GlobalDistribution). Therefore, if it is desired to eliminate communication completely upon array references, all the three global descriptor classes may have to be privatized. When one descriptor object references another, a privatized copy of the former needs to reference a privatized copy of the latter.

To obtain a privatized copy of an object, e.g. for use within dsiPrivatize(), use the following procedure:

proc chpl_getPrivatizedCopy(type objectType, objectPid:int): objectType

Notes:

• The first argument is type of the object being privatized.
• The second argument is the original object's pid field.
• The procedure returns a privatized copy of the original object.
• The procedure can be applied only to objects that have already been privatized.
  • A GlobalArray is privatized after its GlobalDomain, which is privatized after its GlobalDistribution.
  • The pid field is set to a different value than -1 when an object is privatized.

Here is an example of using it for privatizing GlobalDomain, assuming that GlobalDistribution also supports privatization:

proc GlobalDomain.dsiGetPrivatizeData() {
  // include the desired 'pid'
  return (this.dist.pid, ... other data as needed ...);
}

proc GlobalDomain.dsiPrivatize(privatizeData) {
  // extract the 'pid' provided above
  const distPid = privatizeData(1);
  // obtain the privatized copy of the GlobalDistribution object
  const privatizedDMap = chpl_getPrivatizedCopy(this.dist.type, distPid);

  return new GlobalDomain(dist = privatizedDMap,
                          ... other fields as needed ...)
}

Tip: "privatize" the domains and arrays used in the implementation¶

If a global descriptor class to be privatized uses domains and arrays, those need to be "privatized", too, to reduce communication. In the case of domains and arrays mapped using the default layout, their "privatization" is achieved by copying.

Careful consideration is needed to eliminate all communication. For example:

• Copying an array preserves the source's domain - unless the destination's domain is declared explicitly.
• Copying a domain preserves the source's domain map - unless the destination's type is declared explicitly.
• If an array's domain or a domain's domain map is declared explicitly, ensure that privatized copies of those are used.
• There is no need to privatize the default layout. Specifically, copying a domain declared without an explicit domain map is sufficient to privatize that domain.
• The same considerations are valid for reprivatization.

Here is an example of "privatizing" domains/arrays within GlobalDomain. The key insight here is that auxArrayG's domain needs to be "privatized". Cf. the domains of auxArrayED1 and auxArrayED2 are created implicitly for each GlobalDomain object and so will be local in any case.

class GlobalDomain ... {
  ...

  // this field is generic
  var auxArrayG;

  // domain is specified explicitly
  var auxArrayED1: [1..10] int;

  // similar
  var auxDomain: domain(1);
  var auxArrayED2: [auxDomain] int;
}

proc GlobalDomain.dsiGetPrivatizeData() {
  return (this.dist.pid, auxArrayG,
          auxArrayED1, auxDomain, auxArrayED2, ...);
}

proc GlobalDomain.dsiPrivatize(privatizeData) {

  // To privatize auxArrayG, we must "privatize" its domain first.
  // No need to declare privDom's type if auxArrayG uses the default layout.
  var privDom = privatizeData(2).domain;
  var privArr: [privDom] privatizeData(2).eltType = privatizeData(2);

  // If the following were used, privArr.domain would be the same
  // as privatizeData(2).domain, i.e., it would not be privatized.
  //var privArr = privatizeData(2);

  return new GlobalDomain(..., auxArrayG = privArr,
    // the other fields can be simply copied
    auxArrayED1 = privatizeData(3),
    auxDomain   = privatizeData(4),
    auxArrayED2 = privatizeData(5));

}