削減演算子

コンピュータサイエンスにおいて、縮約演算子^[1]は、並列プログラミングで配列の要素を単一の結果に縮約するために一般的に使用される演算子の一種です。縮約演算子は結合性があり、多くの場合（必ずしもそうとは限りませんが）可換性があります。^{[2] [3] [4]}要素セットの縮約は、縮約演算子が縮約される前にすべての要素に適用（マップ）されるMap Reduceなどのプログラミングモデルの不可欠な部分です。他の並列アルゴリズムでは、より複雑な問題を解決するための主要な操作として縮約演算子を使用します。多くの縮約演算子は、データをすべてのプロセッサに配布するためのブロードキャストに使用できます。

リダクション演算子は、最終結果を得るために使用できる部分的な結果を計算することで、タスクをさまざまな部分タスクに分割するのに役立ちます。これにより、特定のシリアル操作を並列に実行し、それらの操作に必要なステップ数を削減できます。リダクション演算子は、部分タスクの結果を変数のプライベート コピーに格納します。これらのプライベート コピーは、最後に共有コピーにマージされます。

次の場合、演算子は縮約演算子です。

• 配列を単一のスカラー値に減らすことができます。^[2]
• 最終的な結果は、作成された部分的なタスクの結果から得られるはずです。^[2]

これら 2 つの要件は、すべての配列要素に適用される可換演算子と結合演算子に対して満たされます。

これらの要件を満たす演算子には、加算、乗算、および一部の論理演算子 (and、or など) があります。

削減演算子は、それぞれが要素を持つベクトルの入力セットに定数時間で適用できます。演算の結果は要素の組み合わせであり、実行の最後に指定されたルート プロセッサに格納される必要があります。計算の終了後に結果をすべてのプロセッサで使用できるようにする必要がある場合、多くの場合、Allreduce と呼ばれます。削減のための最適な順次線形時間アルゴリズムは、演算子を前から後ろへ連続して適用し、常に 2 つのベクトルをそのすべての要素に適用された演算の結果で置き換えて、ベクトルが 1 つ少ないインスタンスを作成します。だけが残るまでステップが必要です。順次アルゴリズムは線形時間よりも優れたパフォーマンスを発揮することはできませんが、並列アルゴリズムは最適化のための余地を残します。 ${\displaystyle \oplus}$$${\displaystyle V=\left\{v_{0}={\begin{pmatrix}e_{0}^{0}\\\vdots \\e_{0}^{m-1}\end{pmatrix}},v_{1}={\begin{pmatrix}e_{1}^{0}\\\vdots \\e_{1}^{m-1}\end{pmatrix}},\dots ,v_{p-1}={\begin{pmatrix}e_{p-1}^{0}\\\vdots \\e_{p-1}^{m-1}\end{pmatrix}}\right\}}$$${\displaystyle p}$${\displaystyle m}$${\displaystyle r}$$${\displaystyle r={\begin{pmatrix}e_{0}^{0}\oplus e_{1}^{0}\oplus \dots \oplus e_{p-1}^{0}\\\vdots \\e_{0}^{m-1}\oplus e_{1}^{m-1}\oplus \dots \oplus e_{p-1}^{m-1}\end{pmatrix}}={\begin{pmatrix}\bigoplus _{i=0}^{p-1}e_{i}^{0}\\\vdots \\\bigoplus _{i=0}^{p-1}e_{i}^{m-1}\end{pmatrix}}}$$${\displaystyle r}$${\displaystyle (p-1)\cdot m}$${\displaystyle r}$

配列があるとします。この配列の合計は、'+' 演算子を使用して配列を 1 つの合計に順次減らすことによって、連続的に計算できます。配列の先頭から合計を開始すると、次のようになります。 ${\displaystyle [2,3,5,1,7,6,8,4]}$$${\displaystyle {\Bigg (}{\bigg (}{\Big (}{\big (}\,(\,(2+3)+5)+1{\big )}+7{\Big )}+6{\bigg )}+8{\Bigg )}+4=36}$$

'+' は可換かつ結合的であるため、リダクション演算子です。したがって、このリダクションは複数のコアを使用して並列に実行できます。各コアは配列のサブセットの合計を計算し、リダクション演算子が結果をマージします。バイナリツリーリダクションを使用すると、4 つのコアで、、、 を計算できます。次に 2 つのコアでと を計算し、最後に 1 つのコアで を計算します。したがって、合計 4 つのコアを使用して、シリアルバージョンに必要な手順ではなく、段階的に合計を計算できます。この並列バイナリツリー手法では を計算します。もちろん結果は同じですが、リダクション演算子の結合性によるものです。マスターコアが作業を複数のプロセッサに分散している場合、リダクション演算子の可換性は重要になります。これは、結果がマスタープロセッサに任意の順序で戻ってくる可能性があるためです。可換性という特性により、結果が同じになることが保証されます。 ${\displaystyle (2+3)}$${\displaystyle (5+1)}$${\displaystyle (7+6)}$${\displaystyle (8+4)}$${\displaystyle (5+6)}$${\displaystyle (13+12)}$${\displaystyle (11+25)=36}$${\displaystyle \log_{2}8=3}$${\displaystyle 7}$${\displaystyle {\big (}\,(2+3)+(5+1)\,{\big )}+{\big (}\,(7+6)+(8+4)\,{\big )}}$

行列乗算は、演算が可換ではないため、縮約演算子ではありません。プロセスが行列乗算の結果を任意の順序でマスター プロセスに返すことが許可されている場合、結果が順序どおりに到着しなかった場合は、マスターが計算する最終結果が不正確になる可能性があります。ただし、行列乗算は結合的であるため、バイナリ ツリー縮約手法のように、適切な順序が強制されている限り、結果は正しいことに注意してください。

並列アルゴリズムに関しては、並列計算には主に 2 つのモデルがあります。処理ユニット間の共有メモリを備えた RAM の拡張としての並列ランダム アクセス マシンと、通信と同期を考慮したバルク同期並列コンピュータです。両方のモデルは時間計算量に対して異なる意味合いを持つため、2 つのアルゴリズムを示します。

このアルゴリズムは、2の累乗である入力を処理するための広く普及した方法を表しています。逆の手順は、要素をブロードキャストするためによく使用されます。^{[5] [6] [7]}${\displaystyle p}$

するために${\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}$

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

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

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

メイン ループは 回実行され、並列処理される部分に必要な時間は、処理ユニットが 2 つのベクトルを結合するか非アクティブになるため、 です。したがって、PRAM の並列時間は です。読み取りと書き込みの競合を処理する戦略は、排他的読み取りと排他的書き込み (EREW) のように制限的に選択できます。アルゴリズムの高速化は であり、したがって効率は です。各ステップの後にアクティブな処理ユニットの半分が非アクティブになるため、効率が低下します。そのため、ユニットはステップ でアクティブになります。 ${\displaystyle \lceil \log _{2}p\rceil }$${\displaystyle {\mathcal {O}}(m)}$${\displaystyle T(p,m)}$${\displaystyle T(p,m)={\mathcal {O}}(\log(p)\cdot m)}$${\displaystyle S(p,m)}$${\displaystyle S(p,m)\in {\mathcal {O}}\left({\frac {T_{\text{seq}}}{T(p,m)}}\right)={\mathcal {O}}\left({\frac {p}{\log(p)}}\right)}$${\displaystyle E(p,m)\in {\mathcal {O}}\left({\frac {S(p,m)}{p}}\right)={\mathcal {O}}\left({\frac {1}{\log(p)}}\right)}$${\displaystyle {\frac {p}{2^{i}}}}$${\displaystyle i}$

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}$

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

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

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

ユニット間の通信は、ある程度のオーバーヘッドをもたらします。アルゴリズムの簡単な分析では、BSP モデルを使用し、通信の開始に必要な時間とバイトの送信に必要な時間を組み込みます。その結果、ベクトルの要素が各反復で送信され、合計サイズが に なるため、実行時間は になります。${\displaystyle T_{\text{start}}}$${\displaystyle T_{\text{byte}}}$${\displaystyle \Theta ((T_{\text{start}}+n\cdot T_{\text{byte}})\cdot log(p))}$${\displaystyle m}$${\displaystyle n}$

分散メモリモデルでは、パイプライン通信を使用するのが合理的です。これは、が と比較して小さい場合に特に当てはまります。通常、線形パイプラインはデータまたはタスクを小さな部分に分割し、段階的に処理します。二項木アルゴリズムとは対照的に、パイプラインアルゴリズムは、ベクトルが分離不可能ではないという事実を利用しますが、演算子は単一の要素に対して評価できます。^[9]${\displaystyle T_{\text{start}}}$${\displaystyle T_{\text{byte}}}$

するために${\displaystyle k\gets 0}$ ${\displaystyle p+m-3}$

並行して行う${\displaystyle i\gets 0}$ ${\displaystyle p-1}$

もし ${\displaystyle i\leq k<i+m\land i\neq p-1}$

送信 先${\displaystyle x_{i}^{k-i}}$ ${\displaystyle p_{i+1}}$

もし ${\displaystyle i-1\leq k<i-1+m\land i\neq 0}$

受け取る ​${\displaystyle x_{i-1}^{k+i-1}}$ ${\displaystyle p_{i-1}}$

${\displaystyle x_{i}^{k+i-1}\gets x_{i}^{k+i-1}\oplus x_{i-1}^{k+i-1}}$

アルゴリズムが機能するには、送信操作と受信操作を同時に実行する必要があることに注意してください。結果ベクトルは最後に保存されます。関連するアニメーションは、5 つの処理ユニットを使用してサイズ 4 のベクトルでアルゴリズムを実行する様子を示しています。アニメーションの 2 つのステップは、1 つの並列実行ステップを視覚化します。 ${\displaystyle p_{p-1}}$

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

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

リダクションは、メッセージ パッシング インターフェースで実装されている主要な集合操作の 1 つであり、使用されるアルゴリズムのパフォーマンスが重要であり、さまざまなユース ケースで継続的に評価されます。^[10] 演算子は、およびのパラメーターとして使用できますが、結果は 1 つの (ルート) 処理ユニットで使用できるか、すべての処理ユニットで使用できるかが異なります。MapReduce は、大規模なクラスターであっても、大規模なデータ セットを処理するために効率的なリダクション アルゴリズムに大きく依存しています。^{[11] [12]}MPI_ReduceMPI_Allreduce

いくつかの並列ソートアルゴリズムでは、非常に大きなデータセットを処理できるようにリダクションを使用します。^[13]

• Fold（高階関数）