還元演算子

このアルゴリズムは、入力を処理する広く普及した方法を表しています。${\displaystyle p}$は 2 のべき乗です。逆の手順は、要素の放送によく使用されます。^{[ 6 ] [ 7 ] [ 8 ]}

のために${\displaystyle k\gets 0}$に${\displaystyle \lceil \log _{2}p\rceil -1}$する

のために${\displaystyle i\gets 0}$に${\displaystyle p-1}$並行して実行する

もし${\displaystyle p_{i}}$アクティブである場合

ビットの場合${\displaystyle k}$の${\displaystyle i}$設定すると

セット${\displaystyle p_{i}}$非アクティブにする

そうでなければ、${\displaystyle i+2^{k}<p}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

ベクトルの二項演算子は、要素ごとに次のように定義されます。$${\displaystyle {\begin{pmatrix}e_{i}^{0}\\\vdots \\e_{i}^{m-1}\end{pmatrix}}\oplus ^{\star }{\begin{pmatrix}e_{j}^{0}\\\vdots \\e_{j}^{m-1}\end{pmatrix}}={\begin{pmatrix}e_{i}^{0}\oplus e_{j}^{0}\\\vdots \\e_{i}^{m-1}\oplus e_{j}^{m-1}\end{pmatrix}}.}$$

このアルゴリズムはさらに、最初は${\displaystyle x_{i}=v_{i}}$すべての人々のために${\displaystyle i}$そして${\displaystyle p}$2のべき乗であり、処理ユニットを使用する${\displaystyle p_{0},p_{1},\dots p_{n-1}}$各反復において、処理ユニットの半分が非アクティブになり、それ以上の計算には寄与しなくなります。図は、加算を演算子として使用したアルゴリズムの視覚化を示しています。垂直線は、その線上の要素の計算が行われる処理ユニットを表しています。8つの入力要素は下部に配置されており、各アニメーションステップはアルゴリズムの実行における1つの並列ステップに対応しています。アクティブなプロセッサ${\displaystyle p_{i}}$要素に対して指定された演算子を評価する${\displaystyle x_{i}}$現在保有しており、${\displaystyle x_{j}}$どこ${\displaystyle j}$最小インデックスは${\displaystyle j>i}$、 となることによって${\displaystyle p_{j}}$現在のステップでは、非アクティブなプロセッサになります。${\displaystyle x_{i}}$そして${\displaystyle x_{j}}$入力セットの要素とは限らない${\displaystyle X}$フィールドは上書きされ、以前に評価された式に再利用されるためです。各ステップで処理ユニットの役割を調整し、それらの間の追加の通信を引き起こさないようにするため、処理ユニットは番号でインデックス付けされています。${\displaystyle 0}$に${\displaystyle p-1}$が使用されています。各プロセッサは、${\displaystyle k}$下位ビットは、非アクティブになるか、自身の要素とインデックスを持つ要素に対して演算子を計算するかを決定します。${\displaystyle k}$番目のビットは設定されていません。このアルゴリズムの基本的な通信パターンは二項ツリーであるため、この名前が付けられています。

のみ ${\displaystyle p_{0}}$は最終的に結果を保持するため、ルートプロセッサです。Allreduce操作の場合、結果を分散する必要があります。これは、からブロードキャストを追加することで実現できます。${\displaystyle p_{0}}$さらに、その数は${\displaystyle p}$プロセッサ数は2のべき乗に制限されています。これは、プロセッサ数を次の2のべき乗にパディングすることで解除できます。また、このユースケースに特化したアルゴリズムもあります。^{[ 9 ]}

PRAMアルゴリズムとは対照的に、分散メモリモデルでは、メモリは処理ユニット間で共有されず、データは処理ユニット間で明示的に交換する必要があります。したがって、以下のアルゴリズムに示すように、ユニット間でデータを明示的に交換する必要があります。

のために${\displaystyle k\gets 0}$に${\displaystyle \lceil \log _{2}p\rceil -1}$する

のために${\displaystyle i\gets 0}$に${\displaystyle p-1}$並行して実行する

もし${\displaystyle p_{i}}$アクティブである場合

ビットの場合${\displaystyle k}$の${\displaystyle i}$設定すると

送信${\displaystyle x_{i}}$に${\displaystyle p_{i-2^{k}}}$

セット${\displaystyle p_{k}}$非アクティブにする

そうでなければ、${\displaystyle i+2^{k}<p}$

受け取る${\displaystyle x_{i+2^{k}}}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

分散アルゴリズムとPRAMバージョンの唯一の違いは、明示的な通信プリミティブが含まれているかどうかであり、動作原理は同じです。

並列実行におけるステップ数は${\displaystyle p+m-2}$、 かかる${\displaystyle p-1}$最後の処理ユニットが最初の要素と追加の要素を受け取るまでのステップ${\displaystyle m-1}$すべての要素が受信されるまで。したがって、BSP モデルの実行時間は${\textstyle T(n,p,m)=\left(T_{\text{start}}+{\frac {n}{m}}\cdot T_{\text{byte}}\right)(p+m-2)}$仮定すると${\displaystyle n}$これはベクトルの合計バイトサイズです。

それでも${\displaystyle m}$固定値を持つ場合、ベクトルの要素を論理的にグループ化して削減することが可能です。${\displaystyle m}$例えば、サイズが4のベクトルを持つ問題インスタンスは、ベクトルを最初の2つと最後の2つの要素に分割し、それらを常に一緒に送信および計算することで処理できます。この場合、各ステップで送信されるボリュームは2倍になりますが、ステップ数はほぼ半分になります。これは、パラメータが${\displaystyle m}$合計バイトサイズは半分になり、${\displaystyle n}$同じままです。ランタイム${\displaystyle T(p)}$このアプローチは、${\displaystyle m}$これは、${\displaystyle T_{\text{start}}}$そして${\textstyle T_{\text{byte}}}$は既知です。${\textstyle m={\sqrt {\frac {n\cdot (p-2)\cdot T_{\text{byte}}}{T_{\text{start}}}}}}$結果としてより小さくなると仮定すると${\displaystyle m}$それは元のものを分割する。