Main Content

MATLAB^{®} supports an important exception, called reduction, 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 sides of an assignment statement, such as any of
the following, where `expr`

is a MATLAB expression.

`X = X + expr` | `X = expr + X` |

`X = X - expr`
| See Associativity in Reduction Assignments in Requirements for Reduction Assignments |

`X = X .* expr` | `X = expr .* X` |

`X = X * expr` | `X = expr * X` |

`X = X & expr` | `X = expr & X` |

`X = X | expr` | `X = expr | X` |

`X = [X, expr]` | `X = [expr, X]` |

`X = [X; expr]` | `X = [expr; X]` |

`X = min(X, expr)` | `X = min(expr, X)` |

`X = max(X, expr)` | `X = max(expr, X)` |

`X = union(X, expr)` | `X = union(expr, X)` |

`X = intersect(X, expr)` | `X = intersect(expr, X)` |

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

The general form of a reduction assignment is

`X = f(X, expr)` | `X = f(expr, X)` |

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

.

X = 0; % Do some initialization of X parfor i = 1:n X = X + d(i); end

This loop is equivalent to the following, where you calculate each
`d(i)`

by a different iteration.

X = X + d(1) + ... + d(n)

In a regular `for`

-loop, the variable `X`

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 partial sums of the workers into
`X`

. Thus, workers do some of the additions, and the client does
the rest.

If your `parfor`

code does not adhere to the guidelines and
restrictions labeled as **Required**, you get an error.
MATLAB catches some of these errors at the time it reads the code, and others
when it executes the code. These errors are labeled as **Required (static)** or **Required
(dynamic)** respectively. Guidelines that do not cause errors are
labeled as **Recommended**. You can use MATLAB Code Analyzer to help `parfor`

-loops comply with the
guidelines.

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

Required (static): For any
reduction variable, the same reduction function or operation must be
used in all reduction assignments for that 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.

Invalid | 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 |

Required (static): If the
reduction assignment uses `*` ,
`[,]` , or `[;]` , then
`X` must be consistently specified as the first
or second argument in every reduction assignment. |

The `parfor`

-loop on the left 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.

Invalid | 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 |

Required (static): You cannot
index or subscript a reduction variable. |

The code on the left is not valid because it tries to index `a`

,
and so MATLAB cannot classify it as a reduction variable. To fix it, the code on the
right uses a non-indexed variable.

Invalid | Valid |
---|---|

a.x = 0 parfor i = 1:10 a.x = a.x + 1; end |
tmpx = 0 parfor i = 1:10 tmpx = tmpx + 1; end a.x = tmpx; |

*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

`X = f(X, expr)` | `X = f(expr, X)` |

Required (static):
`f` can be a function or a variable. If
`f` is a variable, then you cannot change
`f` in the `parfor` body (in
other words, it is a broadcast variable). |

If `f`

is a variable, then for all practical purposes its value
at run time is a function handle. However, as long as the right side can be
evaluated, the resulting value is stored in `X`

.

The `parfor`

-loop on the left does not execute correctly
because the statement `f = @times`

causes `f`

to
be classified as a temporary variable. Therefore `f`

is cleared at
the beginning of each iteration. The `parfor`

-loop on the right
is correct, because it does not assign `f`

inside the loop.

Invalid | Valid |
---|---|

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 |

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`

. However, `f(u,v)`

*always* evaluates `v`

before calling
`f`

. Therefore `&&`

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.* The following practice is recommended for the function
`f`

, as used in the definition of a reduction variable.
However, this rule does not generate an error if not adhered to. Therefore, it is up
to you to ensure that your code meets this recommendation.

Recommended: To get
deterministic behavior of `parfor` -loops, the
reduction function `f` must be associative. |

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 rule,
each execution of the loop might result in different answers.

**Note**

The addition of mathematical real numbers is associative. However, the
addition of floating-point numbers is only approximately associative. Different
executions of this `parfor`

statement might produce values of
`X`

with different round-off errors. You cannot avoid this
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)

Except for the minus operator (`-`

), all special cases listed in
the table in Reduction Variables have a corresponding
(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)

Noncommutative functions include `*`

(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.

Recommended: Except in the cases
of `*` , `[,]` , and
`[;]` , the function `f` of a
reduction assignment must be commutative. If `f` is
not commutative, different executions of the loop might result in
different answers. |

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 function, it is
assumed to be commutative. There is currently no way to specify a user-defined,
noncommutative function in `parfor`

.

Recommended: An overload of
`+` , `*` ,
`.*` , `[,]` , or
`[;]` must be associative if it is used in a
reduction assignment in a `parfor` -loop. |

Recommended: An overload of
`+` , `.*` ,
`union` , or `intersect` must
be commutative. |

Similarly, because of the special treatment of `X = X - expr`

,
the following is recommended.

Recommended: An overload of the
minus operator (`-` ) must obey the mathematical law
that `X - (` is equivalent to
`(X - ` . |

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

First consider the reduction function itself. To compare one iteration result against another, the function requires as input the current result and the known maximum from other iterations so far. Each of the two inputs is a vector containing iteration results 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 end

Inside the loop, each iteration calls the reduction function
(`comparemax`

), passing in a pair of two-element
vectors:

The accumulated maximum and its iteration index, which is the reduction variable

`cummax`

The iteration 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.

Each iteration calls the reduction function `comparemax`

to
compare its own data `[dat i]`

to data already accumulated in
`cummax`

. Try the following code for this loop.

% 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);

MATLAB classifies assignments of the form `X = expr op X`

or
`X = X op expr`

as reduction statements when they are
equivalent to the parenthesized assignments `X = (expr) op X`

or
`X = X op (expr)`

respectively. `X`

is a
variable, `op`

is a reduction operator, and `expr`

is an expression with one or more binary reduction operators. Consequently, due to
the MATLAB operator precedence rules, MATLAB might not classify some assignments of the form ```
X = expr op1
X op2 expr2 ...
```

, that chain operators, as reduction statements in
`parfor`

-loops.

In this example, MATLAB classifies `X`

as a reduction variable because the
assignment is equivalent to `X = X + (1 * 2)`

.

X = 0; parfor i=1:10 X = X + 1 * 2; end

In this example, MATLAB classifies `X`

as a temporary variable because the
assignment, equivalent to `X = (X * 1) + 2`

, is not of the form
`X = (expr) op X`

or ```
X = X op
(expr)
```

.

X = 0; parfor i=1:10 X = X * 1 + 2; end

As a best practice, use parentheses to explicitly specify operator precedence for chained reduction assignments.