ハイパーキューブ（通信パターン）

${\displaystyle d}$次元ハイパーキューブは、処理要素を備えた並列コンピュータのネットワークトポロジです。このトポロジにより、ブロードキャスト、全削減、プレフィックス合計などの基本的な通信プリミティブを効率的に実装できます。^[1]処理要素にはから番号が付けられています。各処理要素は、番号が1ビットだけ異なる処理要素に隣接しています。このページで説明するアルゴリズムは、この構造を効率的に利用しています。 ${\displaystyle 2^{d}}$${\displaystyle 0}$${\displaystyle 2^{d}-1}$

この記事で紹介した通信プリミティブのほとんどは、共通のテンプレートを共有しています。^[2]最初に、各処理要素は、アルゴリズムの過程で他のすべての処理要素に到達しなければならない 1 つのメッセージを持っています。次の疑似コードは、必要な通信手順を示しています。ここで、初期化、操作、および出力は、特定の通信プリミティブに依存するプレースホルダーです (次のセクションを参照)。

入力:メッセージ。
出力:初期化、操作、出力に依存します。
初期化は、操作から受信までの送信を行い、出力を終了します。${\displaystyle m}$
${\displaystyle s:=m}$
 ${\displaystyle 0\leq k<d}$ 
    ${\displaystyle y:=i{\text{XOR}}2^{k}}$
     ${\displaystyle s}$  ${\displaystyle y}$
     ${\displaystyle m}$  ${\displaystyle y}$
    ${\displaystyle (s,m)}$

各処理要素は、隣接する要素を反復処理します (式は、のバイナリ表現の - 番目のビットを否定し、隣接する要素の番号を取得します)。各反復処理では、各処理要素は隣接する要素とメッセージを交換し、その後受信したメッセージを処理します。処理操作は、通信プリミティブによって異なります。 ${\displaystyle i{\text{XOR}}2^{k}}$${\displaystyle k}$${\displaystyle i}$

プレフィックス合計演算の開始時に、各処理要素はメッセージ を所有します。目標は を計算することです。ここで は結合演算です。次の疑似コードはアルゴリズムを説明しています。 ${\displaystyle i}$${\displaystyle m_{i}}$${\displaystyle \bigoplus_{0\leq j\leq i}m_{j}}$${\displaystyle \oplus}$

入力:プロセッサのメッセージ。
出力:プロセッサのプレフィックス合計。for
 do Send to Receive from if bit in is set then endfor${\displaystyle m_{i}}$${\displaystyle i}$${\displaystyle \bigoplus_{0\leq j\leq i}m_{j}}$${\displaystyle i}$${\displaystyle x:=m_{i}}$ 
${\displaystyle \sigma :=m_{i}}$
 ${\displaystyle 0\leq k\leq d-1}$ 
    ${\displaystyle y:=i{\text{XOR}}2^{k}}$
     ${\displaystyle \sigma}$  ${\displaystyle y}$
     ${\displaystyle m}$  ${\displaystyle y}$
    ${\displaystyle \sigma :=\sigma \oplus m}$
    ${\displaystyle k}$${\displaystyle i}$ ${\displaystyle x:=x\oplus m}$

アルゴリズムは次のように機能します。次元 のハイパーキューブは、次元 の 2 つのハイパーキューブに分割できることに注目してください。先頭に 0 があるノードを含むサブキューブを 0 サブキューブ、先頭に 1 があるノードを含むサブキューブを 1 サブキューブと呼びます。両方のサブキューブでプレフィックスの合計を計算したら、0 サブキューブのすべての要素の合計を 1 サブキューブのすべての要素に追加する必要があります。これは、0 サブキューブのすべての処理要素のランクが 1 サブキューブの処理要素よりも低いためです。疑似コードでは、プレフィックスの合計を変数 に格納し、サブキューブのすべてのノードの合計を変数 に格納します。これにより、1 サブキューブのすべてのノードが、すべてのステップで 0 サブキューブの合計を受け取ることができます。 ${\displaystyle d}$${\displaystyle d-1}$${\displaystyle x}$${\displaystyle \sigma}$

この結果、 の因数と の因数が得られます。${\displaystyle \log p}$${\displaystyle T_{\text{start}}}$${\displaystyle n\log p}$${\displaystyle T_{\text{byte}}}$${\displaystyle T(n,p)=(T_{\text{start}}+nT_{\text{byte}})\log p}$

全収集操作は、各処理要素がメッセージを持つことから始まります。操作の目的は、各処理要素が他のすべての処理要素のメッセージを知ることです。つまり、は連結です。操作は、アルゴリズム テンプレートに従って実装できます。 ${\displaystyle m_{i}}$${\displaystyle x:=m_{0}\cdot m_{1}\dots m_{p}}$${\displaystyle \cdot}$

入力:処理ユニットのメッセージ。出力
:すべてのメッセージ。for
 do Send to Receive from endfor${\displaystyle x:=m_{i}}$${\displaystyle i}$${\displaystyle m_{1}\cdot m_{2}\dots m_{p}}$${\displaystyle x:=m_{i}}$
 ${\displaystyle 0\leq k<d}$ 
    ${\displaystyle y:=i{\text{XOR}}2^{k}}$
     ${\displaystyle x}$  ${\displaystyle y}$
     ${\displaystyle x'}$  ${\displaystyle y}$
    ${\displaystyle x:=x\cdot x'}$

反復ごとに、転送されるメッセージの長さは 2 倍になります。これにより、実行時間は になります。 ${\displaystyle T(n,p)\approx \sum _{j=0}^{d-1}(T_{\text{start}}+n\cdot 2^{j}T_{\text{byte}})=\log(p)T_{\text{start}}+(p-1)nT_{\text{byte}}}$

同じ原理はAll-Reduce操作にも適用できますが、メッセージを連結するのではなく、2 つのメッセージに対して削減操作を実行します。つまり、すべての処理ユニットが結果を知っているReduce操作です。通常の削減操作の後にブロードキャストを実行する場合と比較して、ハイパーキューブの All-Reduce では通信ステップの数が減少します。

ここでは、すべての処理要素が他のすべての処理要素に対して一意のメッセージを持ちます。

入力:処理要素のメッセージを処理要素に。
処理要素から受信します:${\displaystyle m_{ij}}$${\displaystyle i}$${\displaystyle j}$ ${\displaystyle d>k\geq 0}$ 
    ${\displaystyle i{\text{XOR}}2^{k}}$私の-次元サブキューブ
    
        のすべてのメッセージを処理要素に送信します:${\displaystyle k}$${\displaystyle i{\text{XOR}}2^{k}}$その次元サブキューブ
endfor
        のすべてのメッセージ${\displaystyle k}$

各反復で、メッセージがまだ到着していない場合は、1 次元ずつ宛先に近づきます。したがって、すべてのメッセージは最大でステップ後に宛先に到達します。各ステップでメッセージが送信されます。最初の反復では、メッセージの半分は自身のサブキューブ向けではありません。後続の各ステップでは、サブキューブのサイズは以前の半分になりますが、前のステップでは別の処理要素からまったく同じ数のメッセージが到着しました。 ${\displaystyle d=\log {p}}$${\displaystyle p/2}$

これにより、実行時間は になります。 ${\displaystyle T(n,p)\approx \log {p}(T_{\text{start}}+{\frac {p}{2}}nT_{\text{byte}})}$

ESBT ブロードキャスト (エッジ分離スパニング二項木) アルゴリズム^[3]は、ハイパーキューブ ネットワーク トポロジを持つクラスターに最適な実行時間を持つパイプライン ブロードキャスト アルゴリズムです。このアルゴリズムは、ハイパーキューブにエッジ分離二項木を埋め込むため、処理要素の各隣接ノードは、ノード上のスパニング二項木のルートになります。メッセージをブロードキャストするには、ソース ノードがメッセージを同じサイズのチャンクに分割し、それらを二項木のルートに周期的に送信します。チャンクを受信すると、二項木はそれをブロードキャストします。 ${\displaystyle d}$${\displaystyle 0}$${\displaystyle 2^{d}-1}$${\displaystyle k}$

各ステップで、ソース ノードはチャンクの 1 つを二項木に送信します。二項木内でチャンクをブロードキャストするには、ステップが必要です。したがって、すべてのチャンクを配布するにはステップが必要で、さらに最後の二項木のブロードキャストが完了するまでステップが必要なので、全体でステップになります。したがって、長さのメッセージの実行時間は です。最適なチャンク サイズ の場合、アルゴリズムの最適な実行時間は です。 ${\displaystyle k}$${\displaystyle d}$${\displaystyle k}$${\displaystyle d}$${\displaystyle k+d}$${\displaystyle n}$${\displaystyle T(n,p,k)=\left({\frac {n}{k}}T_{\text{byte}}+T_{\text{start}}\right)(k+d)}$${\displaystyle k^{*}={\sqrt {\frac {nd\cdot T_{\text{byte}}}{T_{\text{start}}}}}}$${\displaystyle T^{*}(n,p)=n\cdot T_{\text{byte}}+\log(p)\cdot T_{\text{start}}+{\sqrt {n\log(p)\cdot T_{\text{start}}\cdot T_{\text{byte}}}}}$

このセクションでは、二項木を体系的に構築する方法について説明します。まず、次のようにノードから単一の二項全域木を構築します。ノードにから番号を付け、それらのバイナリ表現を考慮します。次に、各ノードの子は、先頭の単一のゼロを否定することによって取得されます。これにより、単一の二項全域木が得られます。ツリーのエッジ分離コピーを取得するには、ノードを変換して回転させます。ツリーの 番目のコピーに対して、各ノードに対してとの XOR 演算を適用します。次に、すべてのノードを数字で右に回転させます。結果として得られる二項木はエッジ分離であるため、ESBT ブロードキャスト アルゴリズムの要件を満たします。 ${\displaystyle 2^{d}}$${\displaystyle 0}$${\displaystyle 2^{d}-1}$${\displaystyle d}$${\displaystyle k}$${\displaystyle 2^{k}}$${\displaystyle k}$