リダクション変数

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 ループはリダクション代入の 1 つのインスタンスに + を使用し、別のインスタンスに [,] を使用しているため、無効です。右側の 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 を最初か 2 番目の引数として指定しなければなりません。

左側の 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 が変数の場合、parfor 本体で f を変更することはできません (つまり、ブロードキャスト変数であるということです)。

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)

非可換の関数には、* (両方の次元のサイズが 1 より大きい行列では乗算が可換ではないため)、[,] および [;] が含まれます。非可換のため、これらの関数では引数の順序に一貫性が必要です。実践的な問題として、関数が可換的かつ結合的で、parfor が可換性を生かすよう最適化されている場合は、より効率的なアルゴリズムが可能となります。

推奨: *、[,] および [;] の場合を除いて、リダクション代入の関数 f は可換でなければなりません。f が可換的ではない場合、異なるループの実行により異なる回答が返される可能性があります。

リダクションに使用される関数内で可換性の制限に違反すると、たとえエラーが発生しなくても、予期しない動作につながる可能性があります。

f は、それが既知の非可換な組み込み関数でない限りは可換であると仮定されます。現時点では、parfor にユーザー定義の非可換的関数を指定する方法はありません。

推奨: parfor ループのリダクション代入で +、*、.*、[,] または [;] を使用する場合、そのオーバーロードは結合的でなければなりません。

推奨: +、.*、union または intersect のオーバーロードは可換でなければなりません。

同様に、X = X - expr の特殊な扱いのため、以下を推奨します。

推奨: マイナス演算子 (-) のオーバーロードでは、X - (y + z) が (X - y) - z と等価であるという数学の法則に従わなければなりません。

カスタムリダクション関数の使用

この例では、ループでの計算を実行し、最大値とそれに対応するループインデックスを格納します。独自のリダクション関数と parfor ループを使用して、コードを高速化することができます。反復ごとに、計算の値とループインデックスを 2 要素の行ベクトルに格納します。カスタムリダクション関数を使用して、このベクトルを格納されたベクトルと比較します。計算からの値が格納された値より大きい場合は、古いベクトルを新しいベクトルに置き換えます。

リダクション関数 compareValue を作成します。この関数は、入力として valueAndIndexA と valueAndIndexB の 2 つのベクトルを取ります。各ベクトルには値とインデックスが含まれています。リダクション関数 compareValue は、値 (最初の要素) が最も大きいベクトルを返します。

function v = compareValue(valueAndIndexA, valueAndIndexB)
    valueA = valueAndIndexA(1);
    valueB = valueAndIndexB(1);
    if valueA > valueB
        v = valueAndIndexA;
    else
        v = valueAndIndexB;
    end
end

すべて 0 からなる 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 ループで計算された最大の乱数値で、2 番目の要素はそれに対応するループインデックスです。

maxValueAndIndex

maxValueAndIndex =

    0.9706   89.0000

リダクション演算子の連結

X = expr op X または X = X op expr の形式の代入が、かっこで囲んだ代入 X = (expr) op X または X = X op (expr) とそれぞれ等価であるとき、MATLAB ではそれらがリダクションステートメントとして分類されます。X は変数、op はリダクション演算子、そして expr は二項リダクション演算子を 1 つ以上含む式です。その結果、MATLAB の演算子の優先順位のルールにより、MATLAB では演算子が連結する X = expr op1 X op2 expr2 ... の形式の代入の一部が、parfor ループ内のリダクションステートメントとして分類されない可能性があります。

次の例では、代入が X = X + (1 * 2) と等価であるため、MATLAB は X をリダクション変数として分類します。

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

次の例では、X = (X * 1) + 2 と等価である代入が X = (expr) op X または X = X op (expr) の形式ではないため、MATLAB は X を一時変数として分類します。

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

ベストプラクティスとして、連結するリダクション代入では、かっこを使用して明示的に演算子の優先順位を指定します。