Module: AdvancedIters

This module contains several iterators that can be used to drive a forall loop by performing dynamic and adaptive splitting of a range’s iterations.

For more information, see User-Defined Parallel Zippered Iterators in Chapel. Bradford L. Chamberlain, Sung-Eun Choi, Steven J. Deitz, Angeles Navarro. PGAS 2011: Fifth Conference on Partitioned Global Address Space Programming Models, October 2011.

config param debugAdvancedIters: bool = false

Toggle debugging output.

iter dynamic(c: range(?), chunkSize: int, numTasks: int = 0)

The serial version of the dynamic iterator.

Equivalent to serial iteration over the range c.

iter dynamic(param tag: iterKind, c: range(?), chunkSize: int, numTasks: int = 0)
Arguments:
  • c : range(?) – The range to iterate over. The length of the range must be greater than zero.
  • chunkSize : int – The size of chunks to be yielded to each thread. Must be greater than zero.
  • numTasks : int – The number of tasks to use. Must be >= zero. If this argument has the value 0, it will use the value indicated by dataParTasksPerLocale.
Yields:

Indices in the range c.

This iterator is equivalent to the dynamic scheduling approach of OpenMP.

Given an input range c, each task is assigned chunks of size chunkSize from c (or the remaining iterations if there are fewer than chunkSize). This continues until there are no remaining iterations in c.

iter guided(c: range(?), numTasks: int = 0)

The serial version of the guided iterator.

Equivalent to serial iteration over the range c.

iter guided(param tag: iterKind, c: range(?), numTasks: int = 0)
Arguments:
  • c : range(?) – The range to iterate over. Must have a length greater than zero.
  • numTasks : int – The number of tasks to use. Must be >= zero. If this argument has the value 0, it will use the value indicated by dataParTasksPerLocale.
Yields:

Indices in the range c.

This iterator is equivalent to the guided policy of OpenMP: Given an input range c, each task is assigned chunks of variable size, until there are no remaining iterations in c. The size of each chunk is the number of unassigned iterations divided by the number of tasks, numTasks. The size decreases approximately exponentially to 1. The splitting strategy is therefore adaptive.

iter adaptive(c: range(?), numTasks: int = 0)

The serial version of the adaptive iterator.

Equivalent to serial iteration over the range c.

enum Method { Whole, RoundRobin, WholeTail }

The enum used to represent adaptive methods.

  • Whole Each task without work tries to steal from its neighbor range until it exhausts that range. Then the task continues with the next neighbor range, and so on until there is no more work. This is the default policy.
  • RoundRobin Each task without work tries to steal once from its neighbor range, next from the following neighbor range and so on in a round-robin way until there is no more work.
  • WholeTail Similar to the Whole method, but now the splitting in the victim range is performed from its tail.
config param methodStealing = .(Method, "Whole")

Used to select the adaptive stealing method. Defaults to Whole. See Method for more information.

iter adaptive(param tag: iterKind, c: range(?), numTasks: int = 0)
Arguments:
  • c : range(?) – The range to iterate over. Must have a length greater than zero.
  • numTasks : int – The number of tasks to use. Must be >= zero. If this argument has the value 0, it will use the value indicated by dataParTasksPerLocale.
Yields:

Indices in the range c.

This iterator implements a naive adaptive binary splitting work-stealing strategy: Initially the leader iterator distributes the range to split, c, evenly among the numTasks tasks.

Then, each task performs adaptive splitting on its local sub-range’s iterations. When a task exhausts its local iterations, it steals and splits from the range of another task (the victim). The splitting method on the local range and on the victim range is binary: i.e. the size of each chunk is computed as the number of unassigned iterations divided by 2. There are three stealing strategies that can be selected at compile time using the config param methodStealing.