Promotion: implicit data parallelism

In Chapel, function promotion (or simply promotion) refers to an implicit form of data parallelism that is triggered by passing a collection of values to an argument that expects a single value. More precisely, when passing:

  • an array of type t,

  • a range or domain whose index type is t, or

  • a forall expression yielding type t,

to a function argument expecting type t, that function will be called in a data-parallel manner for all values in the expression.

As a simple example, consider the following function, negate() which takes a real value by reference and negates it:

examples/users-guide/datapar/promotion.chpl
proc negate(ref x: real) {
  x = -x;
}

In addition to calling the function with a single real variable, we can also call the function in a promoted manner using an array of reals, as follows:

var A = [1.2, 3.4, 5.6];
negate(A);

If we print out the array after making this call, we can see that each element has been negated, as expected:

-1.2 -3.4 -5.6

Moreover, the execution will be equivalent to the following data-parallel forall-loop:

forall a in A do
  negate(a);

Nothing about the above requires using a 1D array. We could also promote negate() by passing it a multidimensional array of reals:

var A2: [1..3, 1..3] real
      = forall (i,j) in {1..3, 1..3} do i + j/10.0;

negate(A2);

which would again be equivalent to the loop:

forall a2 in A2 do
  negate(a2);

Multi-Argument Promotion

When multiple function arguments are promoted in a single call, the result is equivalent to a zippered forall-loop. As an example, consider the following function which takes two real arguments by ref and sorts them relative to one another using a swap assignment:

proc sortTwo(ref x: real, ref y: real) {
  if x > y then
    x <=> y;
}

This function can be promoted using two arrays of reals as follows:

var B = [2.3, 3.4, 5.6],
    C = [0.2, 4.6, 1.3];

sortTwo(B, C);

This promotion is equivalent to the following zippered forall-loop:

forall (b, c) in zip(B, C) do
  sortTwo(b, c);

Either form will leave the arrays as follows:

0.2 3.4 1.3
2.3 4.6 5.6

Promoting multiple arguments simultaneously requires that the arguments can legally be zippered together, as in an explicit forall-loop.

All of a function’s arguments need not be promoted simultaneously. Any arguments that are promoted define the implicit, potentially zippered forall-loop. All others are simply passed through to their formal argument normally. For example, consider the following function which assigns its y argument into its x argument only if the third argument, b, is true:

proc maybeCopy(ref x: real, y: real, b: bool) {
  if b then
    x = y;
}

The following calls demonstrate that various combinations of arguments may be promoted, where A and B are as above, and Mask is an array of bool values:

A = 0.0;
B = [1.2, 3.4, 5.6];
var Mask = [true, false, true];

maybeCopy(A, 1.2, Mask);
maybeCopy(A, B, true);

These calls are equivalent to the following forall-loops:

forall (a, m) in zip(A, Mask) do
  maybeCopy(a, 1.2, m);
forall (a, b) in zip(A, B) do
  maybeCopy(a, b, true);

So, after the respective calls above, A will store the following values:

1.2 0.0 1.2
1.2 3.4 5.6

Any non-promoted arguments to a promoted call are only promoted once. Consider a promoted call to maybeCopy() where the first two arguments are promoted and the third argument is not.

proc computeMask() {
  writeln("computing mask...");
  return true;
}
maybeCopy(A, B, computeMask());

The third argument, the result of a call to computeMask(), will be resolved before the promotion and the message will only be printed once. The equivalent forall-loop is:

var tmp = computeMask();
forall (a, b) in zip(A, B) do
  maybeCopy(a, b, tmp);

Promoting Using Ranges, Domains, Forall Expressions

As mentioned at the outset, not only can arrays be used to promote functions, but ranges, domains, and forall expressions can as well. For example, the following calls promote maybeCopy() using a range, a domain, and a forall expression respectively:

maybeCopy(A, 1..6 by 2, true);
maybeCopy(A, A.domain, true);
maybeCopy(A, forall i in 1..3 do 2*i + 0.5, true);

The contents of A after these calls is as follows:

1.0 3.0 5.0
0.0 1.0 2.0
2.5 4.5 6.5

At the time of this writing, Chapel does not support an official way for users to create their own collection types that support promotion. We expect to support this capability in the future by having the collection type support certain well-defined iterator methods.

Promotion vs. Whole-Array Operations

Chapel’s promoted operators result in different behavior than you might expect from a typical array language. To understand the difference, let’s look at an example:

C = A + 2*B;

As expected, this statement doubles each element of B, adds the result to its corresponding value in A, and then assigns that result to the corresponding value in C. However, most array languages would define the semantics of this statement by evaluating an operator at a time, as follows:

const T = 2*B;
C = A + T;

In contrast, Chapel defines it using zippered iteration:

forall (c, a, b) in zip(C, A, B) do
  c = a + 2*b;

In this case, the two approaches compute the same values, but the Chapel approach has the benefit of avoiding the need for any temporary arrays to store intermediate array results. This makes memory requirements of Chapel programs more explicit to users while also tending to make better use of memory caches in modern architectures.

For other computations, Chapel’s promotion semantics generate a different result than most array languages would. For example, consider the following computation which attempts to replace each interior element of V with the average of its neighbors:

var V: [1..10] real;
V[2..9] = (V[1..8] + V[3..10]) / 2.0;

Again, in an array language, this computation would typically be evaluated by applying each operator in turn:

const T2 = V[1..8] + V[3..10];
V[2..9] = T2 / 2.0;

However, Chapel’s zippered promotion semantics result in the following interpretation:

forall (v1, v2, v3) in zip(V[2..9], V[1..8], V[3..10]) do
  v1 = (v2 + v3)/2.0;

which is equivalent to:

forall i in 2..9 with (ref V) do
  V[i] = (V[i-1] + V[i+1]) / 2.0;

Both of these loops have a race condition, and therefore so does the original whole-array computation in Chapel. Specifically, the tasks used to execute the forall-loop may try to read and write overlapping values of V simultaneously. Thus, where the author likely intended for all the original values of V to be averaged, in reality one or more tasks are likely to end up reading the new values that were computed by their sibling tasks.

For this reason, it is important that users of promotion keep the underlying zippered interpretation in mind and ensure that they are not introducing race conditions between the iterations. For example, to write the previous computation safely in Chapel using promotion, users could introduce a temporary array:

const V2 = (V[1..8] + V[3..10]) / 2.0;
V[2..9] = V2;

Alternatively, they could create an explicit array-oriented implementation of + to avoid the promotion. Note that this still requires a temporary array in which to store and return the result:

proc arrayAdd(X: [] real, Y: [] real) {
  var Z = X + Y;
  return Z;
}

V[2..9] = arrayAdd(V[1..8], V[3..10]) / 2.0;