Reduce Intents¶

Overview¶

Reduce intents are a kind of forall intent - see Section 25.3 "Forall Intents" of the Chapel Language Specification.

As with any forall intent, a reduce intent can be specified on any outer variable - that is, a variable used within the body of a forall loop and declared outside that loop. References to such a variable within the loop implicitly refer to the corresponding formal argument of the task function or the leader iterator.

Reduce intents are distinct:

• Each task formal that corresponds to an outer variable with a reduce intent is initialized, at the beginning of its task, to the identity value for the corresponding reduction.
• The value of the outer variable immediately after the forall loop is a reduction of the values of the corresponding formals at the end of their tasks.

Note that the value of the outer variable immediately before the forall loop is discarded.

Reduce intents are also available with coforall statements.

Syntax¶

The syntax of task-intent-list is extended to allow reduce-intent:

task-intent-list:
  // no change with these
  formal-intent identifier
  formal-intent identifier, task-intent-list
  // added for reduce intents:
  reduce-intent
  reduce-intent, task-intent-list

reduce-intent:
  reduce-operator 'reduce' identifier
  reduce-class    'reduce' identifier

reduce-operator: one of
   // these have the same meaning as in a reduction expression
   +  *  &&  ||  &  |  ^  min  max

reduce-class:
   // the name of the class that implements a user-defined reduction
   identifier

Examples¶

Increment x in the loop -- counts the number of iterations:

var x = 5;
forall myIterator() with (+ reduce x) {
  x += 1;
}
writeln("The number of loop iterations is: ", x);

Set x in the loop -- counts the number of tasks:

var x = 5;
forall myIterator() with (+ reduce x) {
  x = 1;
}
writeln("The number of tasks is: ", x);

For a user-defined reduction, there is a task-private instance of the reduction class for each task created for the forall or coforall loop. Here is an example of such a class:

/* Implements + reduction over numeric data. */
class PlusReduceOp: ReduceScanOp {

  /* the type of the elements to be reduced */
  type eltType;

  /* task-private accumulator state */
  var value: eltType;

  /* identity w.r.t. the reduction operation */
  proc identity         return 0: eltType;

  /* accumulate a single element onto the accumulator */
  proc accumulate(elm)  { value = value + elm; }

  /* accumulate a single element onto the state */
  proc accumulateOntoState(ref state, elm)  { state = state + elm; }

  // Note: 'this' can be accessed by multiple calls to combine()
  // concurrently. The Chapel implementation serializes such calls
  // with a lock on 'this'.
  // 'other' will not be accessed concurrently.
  /* combine the accumulations in 'this' and 'other' */
  proc combine(other)   { value = value + other.value; }

  /* Convert the accumulation into the value of the reduction
     that is reported to the user. This is trivial in our case. */
  proc generate()       return value;

  /* produce a new instance of this class */
  proc clone()          return new PlusReduceOp(eltType=eltType);
}

// Use the above class.
var A = [1000, 200, 30, 4];
var sum: int;
forall elm in A with (PlusReduceOp reduce sum) {
  sum += elm;  // equivalently:  sum reduce= elm;
}
writeln(sum);

// To have different input/accumulator/result types of the reduction,
// specify the input type explicitly, e.g. PlusReduceOp(int) below:
var A = [false, false, true, false, true];
var sum: real;
forall elm in A with (PlusReduceOp(int) reduce sum) {
  sum reduce= elm;   // bools are implicitly coerced to 'int' input type
  writeln(sum);      // accumulation state: int
}
writeln(sum);        // result: real

Open Issues¶

• Should reduce-intent variables within the loop body be task-private or iteration-private? I.e. should the variable's value that is reduced into the final result be taken at the end of each task or at the end of each loop iteration?

  The current implementation and the above examples provide the former. Both above examples would report the number of iterations if the latter.

• How to support reductions where the type of the result is different from the type of the values being reduced, e.g. for a min-k reduction?

• Should the initial value of the reduction variable participate in the reduction as well?

• How would we support reductions over nested forall loops, e.g.:

  var global = 0;
  
  forall i in iterX() with (+ reduce global) do
    forall j in iterY() with (+ reduce global) do
       global += kernel(i,j);
  
  writeln("result = ", global);
  

  The current implementation would exclude, from the final result, the values of kernel(i,j) for most i. Indeed, assume that each task of the outer forall executes several inner forall loops. The reduction result of the inner loop will be stored into the outer task's global formal. Since the value of that formal is discarded when entering the inner loop, only the result from the last inner loop within the outer task will be retained and reduced into the outer global.

Future Work¶

• Provide reduce intents as task intents for cobegin statements.

• Provide the other predefined reduction operators as reduce intents:

  minloc maxloc