归约变量
MATLAB® 支持一个重要的例外,称为简化,即循环迭代必须独立的规则。归约变量会累积一个取决于所有迭代的值,但与迭代顺序无关。MATLAB 允许在 parfor 循环中使用归约变量。
归约变量出现在赋值语句的两侧,例如以下任何一个,其中 expr 是 MATLAB 表达式。
X = X + expr | X = expr + X |
X = X - expr | 请参阅 减量分配的要求 中的归约赋值中的结合律 |
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) |
该表中列出的每个允许的语句都称为缩减分配。根据定义,归约变量只能出现在这种类型的赋值中。
归约分配的一般形式是
X = f(X, expr) | X = f(expr, X) |
下面的示例显示了归约变量 X 的典型用法。
X = 0; % Do some initialization of X parfor i = 1:n X = X + d(i); end
此循环等效于以下内容,其中您通过不同的迭代计算每个 d(i)。
X = X + d(1) + ... + d(n)
在常规的 for 循环中,变量 X 会在进入循环之前或从循环的上一次迭代中获取其值。但是,这个概念不适用于 parfor 循环。
在 parfor 循环中,X 的值永远不会从客户端传输到工作单元或从工作单元传输到工作单元。而是在每个工作单元中增加 d(i),而 i 则覆盖在该工作单元上执行的 1:n 子集。然后将结果传回客户端,客户端将工作单元的部分总和添加到 X 中。因此,工作单元负责一些添加工作,客户端负责其余工作。
关于必需和推荐准则的说明
如果您的 parfor 代码不遵守标记为必需的准则和限制,您将收到错误。MATLAB 会在读取代码时捕获其中一些错误,并在执行代码时捕获其他错误。这些错误分别被标记为必需(静态)或必需(动态)。不会导致错误的指南被标记为推荐。您可以使用 MATLAB 代码分析器来帮助 parfor 循环遵守指南。
归约变量的基本规则
以下要求进一步定义与给定变量相关的归约赋值。
| 必需(静态):对于任何归约变量,在该变量的所有归约分配中必须使用相同的归约函数或运算。 |
左边的 parfor 循环无效,因为缩减分配在一个实例中使用 +,在另一个实例中使用 [,]。右边的 parfor 循环是有效的。
| 无效 | 有效 |
|---|---|
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 |
必需(静态):如果归约分配使用 *、[,] 或 [;],则必须在每个归约分配中一致地将 X 指定为第一个或第二个参量。 |
左边的 parfor 循环无效,因为连接中的项目顺序在整个循环中并不一致。右边的 parfor 循环是有效的。
| 无效 | 有效 |
|---|---|
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 |
| 必需(静态):您不能对归约变量进行索引或下标索引。 |
左边的代码无效,因为它尝试索引 a,因此 MATLAB 无法将其归类为归约变量。为了解决这个问题,右边的代码使用了一个非索引变量。
| 无效 | 有效 |
|---|---|
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; |
减量分配的要求
减少任务。除了 归约变量 表中列出的特定形式的归约赋值外,归约赋值的唯一其他(更一般的)形式是
X = f(X, expr) | X = f(expr, X) |
必需(静态):f 可以是函数或变量。如果 f 是一个变量,那么您就无法在 f 主体中更改 parfor(换句话说,它是一个广播变量)。 |
如果 f 是一个变量,那么从实际目的来看,它在运行时的值是一个函数句柄。然而,只要右边能够求值,结果值就会存储在 X 中。
左边的 parfor 循环无法正确执行,因为语句 f = @times 导致 f 被归类为临时变量。因此,在每次迭代开始时,f 都会被清除。右边的 parfor 循环是正确的,因为它没有在循环内分配 f。
| 无效 | 有效 |
|---|---|
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 |
操作符 && 和 || 未在 归约变量 中的表中列出。除了 && 和 || 之外,MATLAB 的所有矩阵运算都有对应的函数 f,例如 u op v 等价于 f(u,v)。对于 && 和 ||,无法编写这样的函数,因为 u&&v 和 u||v 可能会或可能不会评估 v。然而,f(u,v) 总是在调用 v 之前评估 f。因此,&& 和 || 被排除在 parfor 循环允许的减少分配表之外。
每个归约赋值都有一个相关函数 f。以下章节讨论了确保 parfor 语句确定性行为的 f 的属性。
归约作业中的结合性。对于函数 f,建议采用以下做法,如用于定义归约变量。然而,即使不遵守此规则也不会产生错误。因此,您必须确保您的代码符合此建议。
推荐:为了获得 parfor 循环的确定性行为,归约函数 f 必须具有结合性。 |
为了具有结合性,函数 f 必须对所有 a、b 和 c 满足以下条件。
f(a,f(b,c)) = f(f(a,b),c)
变量(包括归约变量)的分类规则纯粹是句法的。它们无法确定您提供的 f 是否真正具有联想性。假设具有结合性,但是如果违反此规则,则每次执行循环都可能会产生不同的答案。
注意
数学实数的加法是结合的。然而浮点数的加法仅是近似结合的。此 parfor 语句的不同执行可能会产生具有不同舍入误差的 X 值。您无法避免这种并行性的成本。
例如,左边的语句得出 1,而右边的语句返回 1 + eps:
(1 + eps/2) + eps/2 1 + (eps/2 + eps/2)
除了减运算符 (-) 之外,归约变量 中的表中列出的所有特殊情况都有相应的(近似的)结合函数。MATLAB 使用 X = X - expr 计算赋值 X = X + (-expr)。(因此,从技术上讲,计算此归约分配的函数是 plus,而不是 minus。)然而,赋值 X = expr - X 不能使用结合函数来编写,这解释了它从表中被排除的原因。
归约分配中的交换性。一些结合函数,包括 +、.*、min、max、intersect 和 union,也是可交换的。也就是说,对于所有 a 和 b,它们都满足以下条件。
f(a,b) = f(b,a)
非交换函数包括 *(因为对于两个维度都大于一的矩阵,矩阵乘法不交换)、[,] 和 [;]。非交换性是这些函数的参量顺序需要一致的原因。实际上,当函数既可交换又可结合时,可以实现更有效的算法,并且 parfor 经过优化以利用交换性。
推荐:除了 *、[,] 和 [;] 的情况外,归约赋值的函数 f 必须是可交换的。如果 f 不满足交换律,则循环的不同执行可能会产生不同的答案。 |
违反用于归约的函数中的交换性限制可能会导致意外行为,即使它不会产生错误。
除非 f 是已知的非交换内置函数,否则假定它是交换的。目前无法在 parfor 中指定用户定义的非交换函数。
推荐:如果在 + 循环中的归约赋值中使用 *、.*、[,]、[;] 或 parfor 的重载,则它们必须是结合性的。 |
推荐:+、.*、union 或 intersect 的过载必须是可交换的。 |
同样,由于对 X = X - expr 的特殊处理,建议如下。
推荐:减运算符 (-) 的重载必须遵循 X - ( 等同于 (X - 的数学定律。 |
使用自定义归约函数
在此示例中,您在循环中运行计算并存储最大值和相应的循环索引。您可以使用自己的归约函数和 parfor 循环来加快您的代码速度。在每次迭代中,将计算的值和循环索引存储在 2 元素行向量中。使用自定义归约函数将此向量与存储的向量进行比较。如果计算得出的值大于存储的值,则用新向量替换旧向量。
创建一个归约函数 compareValue。该函数接受两个向量作为输入:valueAndIndexA 和 valueAndIndexB。每个向量包含一个值和一个索引。归约函数 compareValue 返回具有最大值的向量(第一个元素)。
function v = compareValue(valueAndIndexA, valueAndIndexB) valueA = valueAndIndexA(1); valueB = valueAndIndexB(1); if valueA > valueB v = valueAndIndexA; else v = valueAndIndexB; end end
创建一个全零的 1×2 向量 maxValueAndIndex。
maxValueAndIndex = [0 0];
parfor 循环。在每次迭代中,使用 rand 创建一个随机值。然后,使用归约函数 compareValue 将 maxValueAndIndex 与随机值和循环索引进行比较。当将结果存储为 maxValueAndIndex 时,您使用 maxValueAndIndex 作为归约变量。parfor ii = 1:100 % Simulate some actual computation thisValueAndIndex = [rand() ii]; % Compare value maxValueAndIndex = compareValue(maxValueAndIndex, thisValueAndIndex); end
在 parfor 循环运行完成后,归约变量 maxValueAndIndex 在客户端可用。第一个元素是在 parfor 循环中计算的最大随机值,第二个元素是相应的循环索引。
maxValueAndIndex
maxValueAndIndex =
0.9706 89.0000链式归约运算符
当 MATLAB 形式为 X = expr op X 或 X = X op expr 的赋值分别等同于带括号的赋值 X = (expr) op X 或 X = X op (expr) 时,它们将归类为归约语句。X 是一个变量,op 是一个归约运算符,而 expr 是一个具有一个或多个二元归约运算符的表达式。因此,由于 MATLAB 运算符优先规则,MATLAB 可能不会将某些形式为 X = expr op1 X op2 expr2 ... 的赋值(即链运算符)归类为 parfor 循环中的归约语句。
在这个示例中,MATLAB 将 X 归类为归约变量,因为赋值等同于 X = X + (1 * 2)。
X = 0; parfor i=1:10 X = X + 1 * 2; end
在此示例中,MATLAB 将 X 归类为临时变量,因为与 X = (X * 1) + 2 等效的赋值不是 X = (expr) op X 或 X = X op (expr) 的形式。
X = 0; parfor i=1:10 X = X * 1 + 2; end
作为最佳做法,使用括号明确指定链式归约分配的运算符优先级。