.. default-domain:: chpl .. _primers-parIters: 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 :ref:`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=`` option. .. code-block:: chapel 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. .. code-block:: chapel 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=`` option). .. code-block:: chapel 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. .. code-block:: chapel 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``: .. code-block:: chapel 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``: .. code-block:: chapel 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: .. code-block:: chapel for (i, a) in zip(count(probSize), A) do a = i/10.0; writeln("After re-assigning A using zippering:"); writeln(A); writeln(); .. primers-parIters-standalone-parallel 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``. .. code-block:: chapel 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. .. primers-parIters-standalone-usage 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. .. code-block:: chapel 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: .. code-block:: chapel 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(); .. _primers-parIters-leader-follower: 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: .. code-block:: chapel 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: .. code-block:: chapel 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. .. primers-parIters-roles: Leader-follower Roles --------------------- At a high level, the role of a leader iterator is to: a) create the parallel tasks used to implement the forall loop, b) associate the tasks with specific locales, if desired, c) 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: .. primers-parIters-leader 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`` .. code-block:: chapel 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 :mod:`DynamicIters` for some more interesting examples of leader iterators, including those that use dynamic partitioning. .. primers-parIters-follower 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``. .. code-block:: chapel 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). .. code-block:: chapel 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. .. code-block:: chapel 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: .. code-block:: chapel A = count(probSize, low=100); writeln("After re-assigning A using whole-array assignment:"); writeln(A); writeln(); .. primers-parIters-closing-notes 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. .. code-block:: chapel proc computeChunk(r: range, myChunk, numChunks) { 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; } } .. _User-Defined Parallel Zippered Iterators in Chapel: http://pgas11.rice.edu/papers/ChamberlainEtAl-Chapel-Iterators-PGAS11.pdf