Distributions

View distributions.chpl on GitHub

This primer demonstrates uses of some of Chapel’s standard distributions. To use these distributions in a Chapel program, the respective module must be used:

use BlockDist, CyclicDist, BlockCycDist;
use DimensionalDist2D, ReplicatedDim, BlockCycDim;

ReplicatedDist is covered in the Replicated Distribution primer.

For each distribution, we’ll create a distributed domain and array and then initialize it just to give a brief flavor of how the distribution maps across locales. Running this example on 6 locales does a nice job of illustrating the distribution characteristics.

All of these distributions support options to map to a different virtual locale grid than the one used by default (a multidimensional factoring of the built-in Locales array), as well as to control the amount of parallelism used in data parallel loops. For more details, see the documentation on Standard Distributions.

Make the program size configurable from the command line.

config const n = 8;

Declare a 2-dimensional domain Space that we will later use to initialize the distributed domains.

const Space = {1..n, 1..n};

Block (and distribution basics)

The Block distribution distributes a bounding box from n-dimensional space across the target locale array viewed as an n-dimensional virtual locale grid. The bounding box is blocked into roughly equal portions across the locales. Note that domains declared over a Block distribution can also store indices outside of the bounding box; the bounding box is merely used to compute the blocking of space.

In this example, we declare a 2-dimensional Block-distributed domain BlockSpace and a Block-distributed array BA declared over the domain.

const BlockSpace = Space dmapped Block(boundingBox=Space);
var BA: [BlockSpace] int;

To illustrate how the index set is distributed across locales, we’ll use a forall loop to initialize each array element to the locale ID that stores that index/element/iteration.

forall ba in BA do
  ba = here.id;

The hasSingleLocalSubdomain method on arrays will return true if the index set for a locale can be represented by a single domain.

if !BA.hasSingleLocalSubdomain() then
  halt("For a Block distribution, the index set per locale should be \
      represented by a single domain");

If the distribution’s subdomains can be represented as single subdomain, we can use localSubdomain() to get the index set for the current locale.

Below, we’ll use the index set to confirm that the array elements have the correct locale ID.

for L in Locales {
  on L {
    const indices = BA.localSubdomain();
    for i in indices {
      if BA[i] != L.id then
        halt("Error: incorrect locale id");
    }
  }
}

Output the Block-distributed array to visually see how the elements are partitioned across the locales.

writeln("Block Array Index Map");
writeln(BA);
writeln();

Most of Chapel’s standard distributions support an optional targetLocales argument that permits you to pass in your own array of locales to be targeted. In general, the targetLocales argument should match the rank of the distribution. So for example, to Block-distribute a domain over a 2D numLocales * 1 view of the locale set, one could do something like the following.

We start by creating our own MyLocales array of the locale values. Here we use the standard array reshape function for convenience. Generally, this array could be accessed/assigned like any other.

var MyLocaleView = {0..#numLocales, 1..1};
var MyLocales: [MyLocaleView] locale = reshape(Locales, MyLocaleView);

Then we declare a distributed domain/array that targets this view of the locales:

const BlockSpace2 = Space dmapped Block(boundingBox=Space,
                                        targetLocales=MyLocales);
var BA2: [BlockSpace2] int;

Now we can do a similar computation as before to verify where each array element ended up:

forall ba in BA2 do
  ba = here.id;

writeln("Block Array Index Map");
writeln(BA2);
writeln();

We can use the targetLocales method available on an array to get the locales array used as targets:

for (L, ML) in zip(BA2.targetLocales(), MyLocales) do
  if L != ML then
    halt("Error: BA2.targetLocales() should equal MyLocales");

Cyclic

Next, we’ll perform a similar computation for the Cyclic distribution. Cyclic distributions start at a designated n-dimensional index and distribute the n-dimensional space across an n-dimensional array of locales in a round-robin fashion (in each dimension). As with the Block distribution, domains declared using the Cyclic distribution may have lower indices than the distribution’s starting index. The starting index should just be considered a parameterization of how the distribution is defined.

const CyclicSpace = Space dmapped Cyclic(startIdx=Space.low);
var CA: [CyclicSpace] int;

forall ca in CA do
  ca = here.id;

writeln("Cyclic Array Index Map");
writeln(CA);
writeln();

The domain returned by localSubdomain need not be a dense block, as is the case for the Cyclic distribution.

on Locales[0] {
  const indices = CA.localSubdomain();
  for i in indices {
    if CA[i] != 0 then
      halt("Error: Cyclic array values on Locale 0 should be zero");
  }
}

Block-Cyclic

Next, we’ll use a BlockCyclic distribution. Block-Cyclic distributions also deal out indices in a round-robin fashion, but rather than dealing out singleton indices, they deal out blocks of indices. Thus, the BlockCyclic distribution is parameterized by a starting index (as with Cyclic) and a block size (per dimension) specifying how large the chunks to be dealt out are.

const BlkCycSpace = Space dmapped BlockCyclic(startIdx=Space.low,
                                              blocksize=(2, 3));
var BCA: [BlkCycSpace] int;

forall bca in BCA do
  bca = here.id;

writeln("Block-Cyclic Array Index Map");
writeln(BCA);
writeln();

A locale’s index set for a Block-Cyclic distribution cannot be represented by a single subdomain.

if BCA.hasSingleLocalSubdomain() then
  halt("A Block-Cyclic index set cannot be represented by a single subdomain");

If the local index set cannot be represented by a single subdomain, we can use the localSubdomains iterator to yield a number of domains that represent the whole index set.

Let’s write a function that uses localSubdomains to verify the correctness of the array values.

proc verifyID(Data: []) {
  for L in Locales {
    on L {
      for indices in Data.localSubdomains() {
        for i in indices {
          if Data[i] != L.id then
            halt("Error: incorrect locale id");
        }
      }
    }
  }
}
verifyID(BCA);

The localSubdomains iterator is also available on distributions that can represent a locale’s index set with a single domain. This allows us to write more general code that will work for all distributions.

This means that we can call the ‘verifyID’ function on any array, like the ‘BA’ array from earlier.

verifyID(BA);

2D Dimensional

The DimensionalDist2D distribution lets us build a 2D distribution as a composition of specifiers for individual dimensions. Under such a “dimensional” distribution each dimension is handled independently of the other.

The dimension specifiers are similar to the corresponding multi-dimensional distributions in constructor arguments and index-to-locale mapping rules. However, instead of an array of locales, a specifier constructor accepts just the number of locales that the indices in the corresponding dimension will be distributed across.

The DimensionalDist2D constructor requires: an [0..nl1-1, 0..nl2-1] array of locales, where nl1 and nl2 are the number of locales in each dimension, and two dimension specifiers, created for nl1 and nl2 locale counts, resp.

Presently, the following dimension specifiers are available (shown here with their constructor arguments):

  • ReplicatedDim(numLocales)

  • BlockDim(numLocales, boundingBoxLow, boundingBoxHigh)

  • BlockCyclicDim(lowIdx, blockSize, numLocales)

The following example creates a dimensional distribution that replicates over 2 locales (when available) in the first dimension and distributes using block-cyclic distribution in the second dimension. The example computes nl1 and nl2 and reshapes MyLocales correspondingly.

var (nl1, nl2) = if numLocales == 1 then (1, 1) else (2, numLocales/2);
MyLocaleView = {0..#nl1, 0..#nl2};
MyLocales = reshape(Locales[0..#nl1*nl2], MyLocaleView);

const DimReplicatedBlockcyclicSpace = Space
  dmapped DimensionalDist2D(MyLocales,
                            new ReplicatedDim(numLocales = nl1),
                            new BlockCyclicDim(numLocales = nl2,
                                               lowIdx = 1, blockSize = 2));

var DRBA: [DimReplicatedBlockcyclicSpace] int;

The ReplicatedDim specifier always accesses the local replicand. (This differs from how the Replicated distribution works.)

This example visits each replicand. The behavior is the same regardless of the second index into MyLocales below.

for locId1 in 0..#nl1 do on MyLocales[locId1, 0] {

  forall drba in DRBA do
    drba = here.id;

  writeln("Dimensional2D(Replicated,BlockCyclic) Array Index Map",
          " from ", here);

  // Technicality: 'writeln(DRBA)' would read DRBA always on Locale 0.
  // Since we want to see what DRBA contains on the current locale,
  // we use 'Helper' that is mapped using the default distribution.
  // 'Helper = DRBA' captures the view of DRBA on the current locale,
  // which we then print out.

  const Helper: [Space] int = DRBA;
  writeln(Helper);
  writeln();

}