Parallel Iterators

View parIters.chpl on GitHub

This primer explains how to write parallel iterators in Chapel, which can be used to drive parallel forall loops. It assumes that the reader already knows how to define serial iterators in Chapel, as summarized in the iterators primer (iterators.chpl) for example.

Chapel has two main flavors of parallel iterators: Standalone parallel iterators are the simpler form and can be used to define parallelism for a simple forall loop like forall i in myIter(...). Leader-follower iterators are a more involved form that support zippered forall loops, like forall (...,i,...) in zip(..., myIter(...), ...). Note that only defining leader-follower iterators is sufficient for use in a non-zippered forall loop, though often with additional overhead.

For a more thorough introduction to leader-follower iterators, refer to our PGAS 2011 paper, User-Defined Parallel Zippered Iterators in Chapel. Note that there are known lacks and issues with Chapel’s current definition of parallel iterators, and that we anticipate addressing these and improving them over time. To that end, this primer should be considered a snapshot of their status in the current implementation.

Motivating Example: a count iterator

In this primer, we’re going to create a simple iterator named count that will be able to be invoked in either for or forall loops. count will be defined to take an argument n as input and an optional argument low (set to 1 by default), and it will yield n integers starting with low.

We’ll use the following config const numTasks to indicate the degree of parallelism that count() should use in its forall loops. By default, we’ve set it to the maximum amount of parallelism expected on the current locale, but this can be overridden on the executable command-line using the --numTasks=<n> option.

config const numTasks = here.maxTaskPar;
if numTasks < 1 then
  halt("numTasks must be a positive integer");

If compiled with verbose set to true, the parallel iterators in this primer will print indications of what they’re doing under the surface.

config param verbose = false;

Next, we declare a problem size for this test. By default we use a small problem size to make the output readable. Of course, to use the parallelism effectively you’d want to use a much larger problem size (override on the execution command-line using the --probSize=<n> option).

config const probSize = 15;
var A: [1..probSize] real;

To get started, we’ll define a traditional serial iterator for count. In part, this is for purposes of illustration in this primer. However, it is also a necessity in that Chapel’s current implementation of parallel iterators requires there to be a serial overload of the iterator as well, to model the expected signature and yielded type.

iter count(n: int, low: int=1) {
  for i in low..#n do
    yield i;
}

Here are some simple loops using the serial iterator to demonstrate it. First we iterate over all indices in our problem size to initialize array A:

for i in count(probSize) do
  A[i] = i:real;

writeln("After serial initialization, A is:");
writeln(A);
writeln();

Then we override the default value of low in order to negate the “middle” elements of A:

for i in count(n=probSize/2, low=probSize/4) do
  A[i] = -A[i];

writeln("After negating the middle of A:");
writeln(A);
writeln();

For serial zippered iteration, nothing is required other than this single iterator:

for (i, a) in zip(count(probSize), A) do
  a = i/10.0;

writeln("After re-assigning A using zippering:");
writeln(A);
writeln();

A standalone parallel count iterator

To create a parallel version of count, we will declare a second overload of the iterator with the same signature, but an additional param argument named tag of built-in enumerated type iterKind, to distinguish it from the serial version. The author of a standalone parallel iterator should use a where clause to distinguish this overload from others. Specifically, when the Chapel compiler attempts to implement a forall loop like forall i in count(...), it will attempt to resolve the iterator by passing in iterKind.standalone as its value, to distinguish it from the serial iterator above. This argument is what marks this version of the iterator as a parallel iterator. After the tag argument, the rest of the argument list should exactly match that of the serial iterator. For the count() example, this means providing the same n and low arguments as before.

Unlike serial iterators, parallel iterators are allowed to contain yield statements within parallel constructs like coforall, cobegin, and forall. In our implementation of the standalone parallel version of count here, we use a coforall loop to define numTasks tasks and then divide the iteration space up amongst them. Specifically, each task calls into a helper routine defined at the bottom of this file, computeChunk() that computes its sub-range of the values to be counted as a function of its task ID (tid) and the total number of tasks (numTasks). The iterator also contains debugging output which can be enabled by compiling with -sverbose=true.

iter count(param tag: iterKind, n: int, low: int = 1)
       where tag == iterKind.standalone {
  if verbose then
    writeln("Standalone parallel count() is creating ", numTasks, " tasks");

  coforall tid in 0..#numTasks {
    const myIters = computeChunk(low..#n, tid, numTasks);

    if verbose then
      writeln("task ", tid, " owns ", myIters);

    for i in myIters do
      yield i;
  }
}

Though not shown in this example, standalone parallel iterators may also target multiple locales using features like on statements or distributed arrays.

Using the standalone parallel ‘count’ iterator

Having defined a standalone parallel iterator, we can execute the same loops as before, but using forall loops to make the execution parallel. Since these forall loops are not using zippered iteration, the standalone version of the count() iterator is used.

forall i in count(probSize) do
  A[i] = i:real;

writeln("After parallel initialization, A is:");
writeln(A);
writeln();

Invoking it again with a different low value:

forall i in count(n=probSize/2, low=probSize/4) do
  A[i] = -A[i];

writeln("After negating the middle of A in parallel:");
writeln(A);
writeln();

Leader-follower iterators

The parallel iterators for zippered forall loops are necessarily more involved since each iterand expression may have its own preferred way of doing parallel iteration, yet its yielded values must be combined with the other iterands in a way that generates a coherent result tuple. To deal with this challenge, given a forall loop of the form:

forall (a, b, c) in zip(A, B, C) do
   // ...loop body...

Chapel’s definition designates the first iterand – in this case, A – as the ‘leader’. In addition, all iterands in the zippering are considered ‘followers’ (so for this loop, A, B, and C would be).

Given such a loop, the compiler will roughly translate it into the following loop structure:

for work in A.lead() do   // implemented by inlining the leader
  for (a, b, c) in zip(A.follow(work), B.follow(work), C.follow(work)) do
    // ...loop body...

where .lead() and .follow() represent the leader-follower iterators using a simplified naming scheme.

Note that since Chapel’s implicitly parallel features are defined in terms of zippered iteration, they are also implemented using leader-follower iterators. For example, A = B + C; will be converted to an equivalent zippered parallel loop and then to the leader-follower idiom shown above. foo(A, B, C) goes through a similar transformation, where foo() is defined to take scalar arguments and is promoted in this call. In both cases, A serves as the leader and A, B, and C are all followers.

Leader-follower Roles

At a high level, the role of a leader iterator is to:

  1. create the parallel tasks used to implement the forall loop,

  2. associate the tasks with specific locales, if desired,

  3. assign work (e.g., iterations) to each parallel task

The leader typically creates the parallelism using task parallel features like coforall loops; and it associates tasks with locales using locality features like on-clauses. The leader specifies work for tasks by having each task it creates yield some representation of the work it owns.

The role of the follower iterator is to take as an input argument a chunk of work (as yielded by a leader) and to serially iterate over and yield the elements/values corresponding to those iterations in order.

Let’s consider how these roles might play out for our count() iterator:

count: leader

As with the standalone parallel iterator, leader and follower iterators are defined as overloads of the serial version of the iterator, once again distinguished by an initial param argument of type iterKind. To invoke the leader iterator and differentiate it from the other overloads, the compiler will pass in the value iterKind.leader to this argument. The author of the leader iterator should use a where clause to distinguish this overload from the others. As with the standalone iterator, the rest of the argument list should match that of the serial iterator exactly.

The implementation of our count() leader iterator is relatively similar to the standalone case. It again uses a coforall loop to create a number of tasks equal to the number specified by our numTasks configuration constant. However, rather than iterating over and yielding the values owned by each task, it will instead yield a version of the range itself as a means of telling the follower iterators what to do.

To be a legal leader iterator, we could simply have each task yield its range as the representation of the work we want the follower to perform. However, to support zippering our leader with follower iterators written by others, we typically take the convention of having iterators over 1D or dense rectangular index spaces yield tuples of ranges shifted to a 0-based coordinate system. In this way, the leader-follower iterators have a common representation for the work even though each may use its own indexing system. This permits, for example, arrays of the same size/shape to be zippered together even if they have different indices.

For this reason, rather than yielding subranges of low..#n, we’ll yield subranges of 0..n-1 and rely on the follower to shift the values back to their preferred coordinate system. As a result, we translate each task’s range by -low to shift it from low-based coordinates to 0-based coordinates; and then we make a 1-tuple out of it.

Note the debugging output inserted into this iterator. While learning about leader-follower iterators, it’s useful to turn this debugging output on by compiling with -sverbose=true

iter count(param tag: iterKind, n: int, low: int=1)
  where tag == iterKind.leader {

  if verbose then
    writeln("In count() leader, creating ", numTasks, " tasks");

  coforall tid in 0..#numTasks {
    const myIters = computeChunk(low..#n, tid, numTasks);
    const zeroBasedIters = myIters.translate(-low);

    if verbose then
      writeln("task ", tid, " owns ", myIters, " yielded as: ", zeroBasedIters);

    yield (zeroBasedIters,); // yield a 1-tuple of our sub-range
  }
}

As mentioned at the outset, this leader is fairly static and simple. More generally, a leader can introduce tasks more dynamically, partition work between the tasks more dynamically, etc. See DynamicIters for some more interesting examples of leader iterators, including those that use dynamic partitioning.

count: follower

The follower is another overload of the same iterator name, this time taking the iterKind.follower param enumeration as its first argument. The subsequent arguments should match the leader and serial iterators exactly again (so, n and low for our example). The final argument must be called followThis which represents the data yielded by the leader (in our case, the 1-tuple of 0-based ranges).

The goal of the follower is to do the iteration specified by the followThis argument, serially yielding the elements corresponding to those iterations. In our case, this involves plucking the range back out of the 1-tuple of ranges, and shifting it back to our low-based coordinate system. We then use a standard for-loop to iterate over that range and yield the corresponding indices. Followers, as the name suggests, tend not to be very sophisticated, and simply do what the leader tells them to.

As with the leader, this follower has been authored to support debugging output when compiled with -sverbose=true.

iter count(param tag: iterKind, n: int, low: int=1, followThis)
       where tag == iterKind.follower && followThis.size == 1 {
  const (followInds,) = followThis;
  const lowBasedIters = followInds.translate(low);

  if (verbose) then
    writeln("Follower received ", followThis, " as work chunk; shifting to ",
            lowBasedIters);

  for i in lowBasedIters do
    yield i;
}

Now let’s use our leader/follower iterators. In the following loop, count() serves as the leader and follower while the A array is just a follower. This works because A is a rectangular array whose follower iterator also accepts tuples of 0-based ranges like the ones count()’s leader is yielding. If we were to have count() yield something else (like a raw subrange of low..#n), then the two things could not be zippered correctly because they wouldn’t be speaking the same language – either in terms of the type of work being yielded (range vs. 1-tuple of range), nor the description of the work (low-based indices vs. 0-based indices).

forall (i, a) in zip(count(probSize), A) do
  a = i/10.0;

writeln("After re-assigning A using parallel zippering:");
writeln(A);
writeln();

We can also zipper in the opposite order, making A the leader, in which case count() no longer controls the degree of parallelism and work assignment since it is no longer the leader. Instead, A’s leader iterator (defined as part of its domain map) is invoked. For standard Chapel arrays and domain maps, these leader-follower iterators are controlled by the dataPar* configuration constants described in doc/rst/usingchapel/executing.rst.

forall (a, i) in zip(A, count(probSize)) do
  a = i/100.0;

writeln("After re-assigning A using parallel zippering and A as the leader:");
writeln(A);
writeln();

Finally, as mentioned at the outset, operations that are equivalent to zippering also use leader-follower iterators, so for example the following whole-array assignment will use A’s leader and count()’s follower:

A = count(probSize, low=100);

writeln("After re-assigning A using whole-array assignment:");
writeln(A);
writeln();

Closing notes

Chapel data types like records and classes can support iteration by defining iterator methods (invoked by name) or these() iterators which support iterating over variables of that type directly. Such iterator methods can be overloaded to support standalone and/or leader-follower versions to support parallel iteration over the variable.

As mentioned at the outset, our leader-follower scheme has a number of changes planned for it such as interface improvements and better error checking. We’ll update this primer over time as we improve these features.

Definition of helper function used above:

The following utility function partitions a range into numChunks sub-ranges and returns a range representing the indices for sub-range myChunk (counting from 0). The absolute difference between the size of the ranges returned is at most 1 (either 0 or 1). If the value of remainder rem is equal to 0, then each sub-range contains elemsPerChunk indices, equal to floor(numElements/numChunks) work items. But if rem is not equal to 0, then the first rem sub-ranges get (elemsPerChunk+ 1) indices and the rest (chunks rem to numChunks-1) get elemsPerChunk indices. For simplicity, this routine works only for unstrided ranges with the default index type of int. These constraints could be relaxed with more effort.

proc computeChunk(r: range, myChunk, numChunks) where r.stridable == false {
  const numElems = r.size;
  const elemsperChunk = numElems/numChunks;
  const rem = numElems%numChunks;
  var mylow = r.low;
  if myChunk < rem {
    mylow += (elemsperChunk+1)*myChunk;
    return mylow..#(elemsperChunk + 1);
  } else {
    mylow += ((elemsperChunk+1)*rem + (elemsperChunk)*(myChunk-rem));
    return mylow..#elemsperChunk;
  }
}