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

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

アルゴリズムの概要

この記事で紹介する通信プリミティブのほとんどは、共通のテンプレートを共有しています。^[2]初期状態では、各処理要素は1つのメッセージを保持しており、このメッセージはアルゴリズムの実行中に他のすべての処理要素に届く必要があります。以下の擬似コードは、必要な通信手順を示しています。ここで、Initialization、Operation、Outputは、特定の通信プリミティブに依存するプレースホルダーです（次のセクションを参照）。

入力: message 。出力: Initialization、Operation、Outputに依存します。Initialization for do Send to Receive from Operation endfor Output ${\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}$

次元ハイパーキューブに適用されるアルゴリズムの概要。最初のステップ（通信前）では、各処理要素は1つのメッセージ（青）を保持します。通信は赤で示されています。各ステップの後、処理要素は受信したメッセージを保存しますが、他の操作も可能です。 ${\displaystyle 3}$

通信プリミティブ

プレフィックス合計

プレフィックス和演算の開始時、各処理要素はメッセージ を所有します。目標は を計算することです。ここでは結合演算です。次の擬似コードは、このアルゴリズムを説明しています。 ${\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 x}$ ${\displaystyle \sigma }$

オールギャザー/オールリデュース

全収集操作は、各処理要素がメッセージ を持つことから始まります。この操作の目的は、各処理要素が他のすべての処理要素のメッセージを知ることです。つまり、は連結です。この操作は、アルゴリズムテンプレートに従って実装できます。 ${\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放送

ESBTブロードキャスト（Edge-disjoint Spanning Binomial Tree）アルゴリズム^[3]は、ハイパーキューブネットワークトポロジを持つクラスターに最適な実行時間を持つパイプラインブロードキャストアルゴリズムです。このアルゴリズムは、ハイパーキューブ内にEdge-disjoint Binomial Treeを埋め込み、各処理要素の隣接ノードが全域二項木のルートとなるようにします。メッセージをブロードキャストするために、送信元ノードはメッセージを均等なサイズのチャンクに分割し、それらを二項木のルートノードに周期的に送信します。チャンクを受信すると、二項木はそれをブロードキャストします。 ${\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}}}}}$

二項木の構築

3 つの ESBT が埋め込まれた 次元ハイパーキューブ。 ${\displaystyle 3}$

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

参照

• ハイパーキューブインターネットワークトポロジ

参考文献

1. Grama, A.(2003). 並列コンピューティング入門. Addison Wesley; Auflage: 2 ed. ISBN 978-0201648652。
2. Foster, I.(1995). 並列プログラムの設計と構築：並列ソフトウェアエンジニアリングの概念とツール. Addison Wesley; ISBN 0201575949。
3. Johnsson, SL; Ho, C.-T. (1989). 「ハイパーキューブにおける最適ブロードキャストとパーソナライズ通信」. IEEE Transactions on Computers . 38 (9): 1249– 1268. doi :10.1109/12.29465. ISSN  0018-9340.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hypercube_(communication_pattern)&oldid=1276155565"