Documentation

MATLAB^® supports an important exception, called reductions, to the rule that loop iterations must be independent. A reduction variable accumulates a value that depends on all the iterations together, but is independent of the iteration order. MATLAB allows reduction variables in parfor-loops.

Reduction variables appear on both side of an assignment statement, such as any of the following, where expr is a MATLAB expression.

Each of the allowed statements listed in this table is referred to as a reduction assignment, and, by definition, a reduction variable can appear only in assignments of this type.

The following example shows a typical usage of a reduction variable X:

This loop is equivalent to the following, where each d(i) is calculated by a different iteration:

If the loop were a regular for-loop, the variable X in each iteration would get its value either before entering the loop or from the previous iteration of the loop. However, this concept does not apply to parfor-loops:

In a parfor-loop, the value of X is never transmitted from client to workers or from worker to worker. Rather, additions of d(i) are done in each worker, with i ranging over the subset of 1:n being performed on that worker. The results are then transmitted back to the client, which adds the workers' partial sums into X. Thus, workers do some of the additions, and the client does the rest.

Basic Rules for Reduction Variables

The following requirements further define the reduction assignments associated with a given variable.

The parfor-loop on the left is not valid because the reduction assignment uses + in one instance, and [,] in another. The parfor-loop on the right is valid:

parfor i = 1:n
   if testLevel(k)
      A = A + i;
   else
      A = [A, 4+i];
   end
   % loop body continued
end

parfor i = 1:n
   if testLevel(k)
      A = A + i;
   else
      A = A + i + 5*k;
   end
   % loop body continued
end

The parfor-loop on the left below is not valid because the order of items in the concatenation is not consistent throughout the loop. The parfor-loop on the right is valid:

parfor i = 1:n
   if testLevel(k)
      A = [A, 4+i];
   else
      A = [r(i), A];
   end
   % loop body continued
end

parfor i = 1:n
   if testLevel(k)
      A = [A, 4+i];
   else
      A = [A, r(i)];
   end
   % loop body continued
end

Further Considerations with Reduction Variables

This section provides more detail about reduction assignments, associativity, commutativity, and overloading of reduction functions.

Reduction Assignments. In addition to the specific forms of reduction assignment listed in the table in Reduction Variables, the only other (and more general) form of a reduction assignment is

If f is a variable, then for all practical purposes its value at run time is a function handle. However, this is not strictly required; as long as the right-hand side can be evaluated, the resulting value is stored in X.

The parfor-loop below on the left will not execute correctly because the statement f = @times causes f to be classified as a temporary variable and therefore is cleared at the beginning of each iteration. The parfor on the right is correct, because it does not assign f inside the loop:

f = @(x,k)x * k;
parfor i = 1:n
   a = f(a,i);
   % loop body continued
   f = @times;  % Affects f
end

f = @(x,k)x * k;
parfor i = 1:n
   a = f(a,i);
   % loop body continued
end

Note that the operators && and || are not listed in the table in Reduction Variables. Except for && and ||, all the matrix operations of MATLAB have a corresponding function f, such that u op v is equivalent to f(u,v). For && and ||, such a function cannot be written because u&&v and u||v might or might not evaluate v, but f(u,v) always evaluates v before calling f. This is why && and || are excluded from the table of allowed reduction assignments for a parfor-loop.

Every reduction assignment has an associated function f. The properties of f that ensure deterministic behavior of a parfor statement are discussed in the following sections.

Associativity in Reduction Assignments. Concerning the function f as used in the definition of a reduction variable, the following practice is recommended, but does not generate an error if not adhered to. Therefore, it is up to you to ensure that your code meets this recommendation.

To be associative, the function f must satisfy the following for all a, b, and c:

f(a,f(b,c)) = f(f(a,b),c)

The classification rules for variables, including reduction variables, are purely syntactic. They cannot determine whether the f you have supplied is truly associative or not. Associativity is assumed, but if you violate this, different executions of the loop might result in different answers.

Note:   While the addition of mathematical real numbers is associative, addition of floating-point numbers is only approximately associative, and different executions of this parfor statement might produce values of X with different round-off errors. This is an unavoidable cost of parallelism.

For example, the statement on the left yields 1, while the statement on the right returns 1 + eps:

(1 + eps/2) + eps/2           1 + (eps/2 + eps/2)

With the exception of the minus operator (-), all the special cases listed in the table in Reduction Variables have a corresponding (perhaps approximately) associative function. MATLAB calculates the assignment X = X - expr by using X = X + (-expr). (So, technically, the function for calculating this reduction assignment is plus, not minus.) However, the assignment X = expr - X cannot be written using an associative function, which explains its exclusion from the table.

Commutativity in Reduction Assignments. Some associative functions, including +, .*, min, and max, intersect, and union, are also commutative. That is, they satisfy the following for all a and b:

f(a,b) = f(b,a)

Examples of noncommutative functions are * (because matrix multiplication is not commutative for matrices in which both dimensions have size greater than one), [,], and [;]. Noncommutativity is the reason that consistency in the order of arguments to these functions is required. As a practical matter, a more efficient algorithm is possible when a function is commutative as well as associative, and parfor is optimized to exploit commutativity.

Violating the restriction on commutativity in a function used for reduction, could result in unexpected behavior, even if it does not generate an error.

Unless f is a known noncommutative built-in, it is assumed to be commutative. There is currently no way to specify a user-defined, noncommutative function in parfor.

Overloading in Reduction Assignments. Most associative functions f have an identity element e, so that for any a, the following holds true:

f(e,a) = a = f(a,e)

Examples of identity elements for some functions are listed in this table.

MATLAB uses the identity elements of reduction functions when it knows them. So, in addition to associativity and commutativity, you should also keep identity elements in mind when overloading these functions.

There is no way to specify the identity element for a function. In these cases, the behavior of parfor is a little less efficient than it is for functions with a known identity element, but the results are correct.

Similarly, because of the special treatment of X = X - expr, the following is recommended.

Example: Using a Custom Reduction Function

Suppose each iteration of a loop performs some calculation, and you are interested in finding which iteration of a loop produces the maximum value. This is a reduction exercise that makes an accumulation across multiple iterations of a loop. Your reduction function must compare iteration results, until finally the maximum value can be determined after all iterations are compared.

First consider the reduction function itself. To compare an iteration's result against another's, the function requires as input the current iteration's result and the known maximum result from other iterations so far. Each of the two inputs is a vector containing an iteration's result data and iteration number.

function mc = comparemax(A, B)
% Custom reduction function for 2-element vector input

if A(1) >= B(1) % Compare the two input data values
    mc = A;     % Return the vector with the larger result
else
    mc = B;
end

Inside the loop, each iteration calls the reduction function (comparemax), passing in a pair of 2-element vectors:

• The accumulated maximum and its iteration index (this is the reduction variable, cummax)

• The iteration's own calculation value and index

If the data value of the current iteration is greater than the maximum in cummmax, the function returns a vector of the new value and its iteration number. Otherwise, the function returns the existing maximum and its iteration number.

The code for the loop looks like the following, with each iteration calling the reduction function comparemax to compare its own data [dat i] to that already accumulated in cummax.

% First element of cummax is maximum data value
% Second element of cummax is where (iteration) maximum occurs
cummax = [0 0];  % Initialize reduction variable
parfor ii = 1:100
    dat = rand(); % Simulate some actual computation
    cummax = comparemax(cummax, [dat ii]);
end
disp(cummax);