ブロードキャスト（並列パターン）

集合的コミュニケーションのプログラミング

ブロードキャストは、並列プログラミングにおける集合的な通信プリミティブであり、プログラミング命令やデータをクラスター内のノードに配布する。これはリダクションの逆操作である。^{[1]ブロードキャスト操作は、行列ベクトル乗算、}^[1]ガウス消去法、最短経路法などの並列アルゴリズムで広く使用されている。^[2]

メッセージパッシングインターフェースはブロードキャストを実装しますMPI_Bcast。^[3]

意味

長さのメッセージは、1 つのノードから他のすべてのノードに配布される必要があります。 $M[1..m]$ $m$ $p-1$

$T_{\text{byte}}$ 1 バイトを送信するのにかかる時間です。

$T_{\text{start}}$ メッセージが長さに関係なく、別のノードに移動するのにかかる時間です。

したがって、あるノードから別のノードにパッケージを送信するのにかかる時間は^[1]です。 $t=\mathrm {size} \times T_{\text{byte}}+T_{\text{start}}$

$p$ ノード数とプロセッサ数です。

二項木放送

二項木ブロードキャストでは、メッセージ全体が一度に送信されます。メッセージを受信した各ノードは、さらにメッセージを送信します。送信ノードの数は時間ステップごとに倍増するため、このアルゴリズムは指数関数的に増加します。このアルゴリズムは短いメッセージには最適ですが、長いメッセージには不十分です。最初の転送が行われている間は、1つのノードだけがビジー状態だからです。

すべてのノードにメッセージを送信するには時間がかかり、実行時間は $\log_{2}(p)t$ $\log _{2}(p)(mT_{\text{byte}}+T_{\text{start}})$

メッセージ M

id  : = ノード 番号
p  := ノード数  

 id  >  0 の  
    場合、Mをブロック受信します。for  ( i := ceil ( log_2 ( p )) - 1 ; i >= 0 ; i -- ) 、if ( id % 2 ^ ( i + 1 ) == 0 && id + 2 ^ i <= p )の場合、 M をノードid + 2 ^ iに送信します。

^[4]

リニアパイプラインブロードキャスト

メッセージはパッケージに分割され、ノードからノードへと分割されて送信されます。最初のメッセージ部分を配布するのに必要な時間は、あるプロセッサから別のプロセッサにパッケージを送信するのに必要な時間です。 $k$ $n$ $n+1$ ${\textstyle pt={\frac {m}{k}}T_{\text{byte}}+T_{\text{start}}}$ $t$

メッセージ全体の送信には時間がかかります。 $(p+k)\left({\frac {mT_{\text{byte}}}{k}}+T_{\text{start}}\right)=(p+k)t=pt+kt$

最適なのは、実行時間が約 $k={\sqrt {\frac {m(p-2)T_{\text{byte}}}{T_{\text{start}}}}}$ $mT_{\text{byte}}+pT_{\text{start}}+{\sqrt {mpT_{\text{start}}T_{\text{byte}}}}$

実行時間はメッセージの長さだけでなく、役割を果たすプロセッサの数にも依存します。このアプローチは、メッセージの長さがプロセッサの数よりもはるかに大きい場合に効果を発揮します。

メッセージ M  :=  [ m_1 ,  m_2 ,  ... ,  m_n ] 
id  = ノード 番号

for  ( i  :=  1 ;  i  <=  n ;  i ++ )を 並列に if ( id != 0 )をblocking_receive m_iで実行する
       
         
        
    if  ( id  !=  n ) 
        m_i をノードid + 1に送信する

^[4]

パイプライン化されたバイナリツリーブロードキャスト

このアルゴリズムは、二項木ブロードキャストと線形パイプラインブロードキャストを組み合わせたもので、短いメッセージと長いメッセージの両方で適切に機能します。このアルゴリズムの目的は、短いメッセージを迅速に送信する能力を維持しながら、できるだけ多くのノードが動作するようにすることです。木を分割する際にフィボナッチ木を使用するのが良いアプローチです。これは、メッセージを両方の子ノードに同時に送信できないため、良い選択肢です。これにより、二分木構造が形成されます。

以下では、通信は全二重であると仮定します。フィボナッチ木構造の深さは約で、黄金比となります。 $d\approx \log _{\Phi }(p)$ $\Phi ={\frac {1+{\sqrt {5}}}{2}}$

結果として得られる実行時間はです。最適な実行時間はです。 ${\textstyle ({\frac {m}{k}}T_{\text{byte}}+T_{\text{start}})(d+2k-2)}$ $k={\sqrt {\frac {n(d-2)T_{\text{byte}}}{3T_{\text{start}}}}}$

これにより、実行時間はになります。 $2mT_{\text{byte}}+T_{\text{start}}\log _{\Phi }(p)+{\sqrt {2m\log _{\Phi }(p)T_{\text{start}}T_{\text{byte}}}}$

メッセージ M  :=  [ m_1 ,  m_2 ,  ... ,  m_k ]

 i  =  1 から k 
    の場合、if  ( hasParent ())は
        m_iをブロックして受信します。 
        
    if  ( hasChild ( left_child ))は
        m_i をleft_childに送信します。   
        
    if  ( hasChild ( right_child ))は
        m_i をright_childに送信します。

^[2]^[4]

ツーツリー放送（23放送）

^[5]^[6]^[7]

意味

このアルゴリズムは、パイプラインを用いたツリー構造モデルのいくつかの欠点を改善することを目的としています。通常、パイプラインを用いたツリー構造モデル（上記の方法を参照）では、リーフは自身のデータのみを受信し、データの送信や拡散には寄与しません。

このアルゴリズムは、2つの二分木を同時に使用して通信を行います。これらの木を木Aと木Bと呼びます。二分木は構造上、内部ノードよりも葉ノードの数が多い傾向があります。このアルゴリズムの基本的な考え方は、木Aの葉ノードを木Bの内部ノードにすることです。これは、木Bから木Aへの反対側にも同様の技術的機能を持ちます。つまり、内部ノードと葉ノードは、異なるステップで2つのパケットを送受信します。

木の構築

2 つの並列動作するバイナリツリーを構築するために必要なステップ数は、プロセッサの数に依存します。他の構造と同様に、1 つのプロセッサが 2 つのツリーにメッセージを送信するルートノードになることができます。バイナリツリーでメッセージを送信する方向は通常上から下であることは容易に認識できるため、ルートノードを設定する必要はありません。2 つのバイナリツリーを構築するためのプロセッサ数に制限はありません。結合されたツリーの高さを $h = ⌈log(p + 2)⌉$ とします。ツリー A と B の高さはにすることができます。特に、プロセッサ数がに対応する場合は、両側のツリーとルートノードを作成できます。 $h-1$ $p=2^{h}-1$

このモデルを、完全に構築されたツリーを用いて効率的かつ容易に構築するために、「シフト」と「ミラーリング」と呼ばれる2つの手法を用いて2つ目のツリーを作成します。ツリーAが既にモデル化されており、ツリーBはツリーAに基づいて構築されると仮定します。プロセッサは0から順に並べられているものとします。 $p$ $p-1$

シフト

「シフト」方式では、まずツリー A をコピーし、すべてのノードを 1 つ左に移動してツリー B を取得します。-1 に配置されるノードはプロセッサの子になります。 $p-2$

ミラーリング

「ミラーリング」はプロセッサ数が偶数の場合に最適です。この方法では、新しいツリーを作成するために構造的な変換を行う必要がないため、ツリーAからツリーBをより簡単に構築できます。さらに、対称的なプロセスにより、このアプローチはシンプルになります。この方法はプロセッサ数が奇数の場合にも適用でき、その場合、両方のツリーのルートノードとしてプロセッサを設定できます。残りのプロセッサについては、「ミラーリング」を使用できます。 $p-1$

着色

1ステップで2つの木から2つのメッセージを送受信するプロセッサが存在しないようにするためのスケジュールを見つける必要があります。エッジは2つのノードを接続する通信接続であり、0または1のラベルを付けることで、すべてのプロセッサが0と1のラベルが付いたエッジを交互に使用できるようにすることができます。AとBのエッジは、2つの色（0と1）で色分けできます。

AとBの親ノードに同じ色のエッジで接続されたプロセッサはありません。
AまたはBの子ノードに同じ色のエッジで接続されたプロセッサはありません。^[7]

すべての偶数ステップでは 0 のエッジがアクティブになり、すべての奇数ステップでは 1 のエッジがアクティブになります。

時間計算量

この場合、パケット数kは各ツリーごとに半分に分割されます。両方のツリーが連携して動作し、パケットの総数（上側のツリーと下側のツリー）は $k=k/2+k/2$

各二分木において、他のノードへのメッセージの送信には、プロセッサがステップで少なくとも1つのパケットを取得するまで、ステップかかります。したがって、すべてのステップはと計算できます。 $2i$ $i$ $d:=\log _{2}(p+1)\Rightarrow \log _{2}(p+1)\approx \log _{2}(p)$

結果として得られる実行時間はです。(最適 ) ${\textstyle T(m,p,k)\approx ({\frac {m}{k}}T_{\text{byte}}+T_{\text{start}})(2d+k-1)}$ ${\textstyle k={\sqrt {{m(2d-1)T_{\text{byte}}}/{T_{\text{start}}}}}}$

これにより、実行時間はになります。 $T(m,p)\approx mT_{\text{byte}}+T_{\text{start}}\cdot 2\log _{2}(p)+{\sqrt {m\cdot 2\log _{2}(p)T_{\text{start}}T_{\text{byte}}}}$

ESBT ブロードキャスト（辺素全域二項木）

このセクションでは、電話通信モデルを基礎とする別のブロードキャストアルゴリズムを紹介します。ハイパーキューブは、を持つネットワークシステムを作成します。各ノードは、次元の数に応じてバイナリで表されます。基本的に ESBT (Edge-disjoint Spanning Binomial Trees) は、ハイパーキューブグラフ、パイプライン (メッセージがパケットに分割される)、および二項木に基づいています。プロセッサは、パケットを ESBT のルートに循環的に拡散します。ESBT のルートは、二項木を使用してデータをブロードキャストします。からのすべてのパケットを離れるには、すべてのパケットがによって配布されるため、ステップが必要です。最後のリーフノードがパケットを受信するまで、さらに d ステップかかります。ESBT を介してメッセージをブロードキャストするには、合計ステップが必要です。 $p=2^{d}(d=0,1,2,3,...)$ ${0,1}$ $m$ $k$ $0^{d}$ $k$ $p_{0}$ $k$ $p_{0}$ $d+k$ $m$

結果の実行時間は. . ${\textstyle T(m,p,k)=({\frac {m}{k}}T_{\text{byte}}+T_{\text{start}})(k+d)}$ ${\textstyle (k={\sqrt {{mdT_{\text{byte}}}/{T_{\text{start}}}}})}$

これにより、実行時間はになります。 $T(m,p):=mT_{\text{byte}}+dT_{\text{start}}+{\sqrt {mdT_{\text{start}}T_{\text{byte}}}}$

^[8]^[9]

参照

縮約演算子

参考文献

^ abc Kumar, Vipin (2002). 並列コンピューティング入門（第2版）. ボストン, マサチューセッツ州, 米国: Addison-Wesley Longman Publishing Co., Inc. pp. 185, 151, 66. ISBN 9780201648652。
^ ab Bruck, J.; Cypher, R.; Ho, CT. (1992). 「一般化フィボナッチ木を用いた複数メッセージブロードキャスト」. [1992] 第4回IEEE並列分散処理シンポジウム議事録. pp. 424– 431. doi :10.1109/SPDP.1992.242714. ISBN 0-8186-3200-3. S2CID 2846661。
^ MPI: メッセージパッシングインターフェース標準バージョン3.0、メッセージパッシングインターフェースフォーラム、pp. 148、2012
^ abc Michael Ikkert、T. Kieritz、P. Sanders Parallele Algorithmen - Script（ドイツ語）、カールスルーエ工科大学、pp. 29-32、2009
^ Michael Ikkert、T. Kieritz、P. Sanders Parralele Algorithme - Script（ドイツ語）、カールスルーエ工科大学、pp.33-37、2009
^ P.サンダース [1] （ドイツ語）、カールスルーエ工科大学、pp. 82-96、2018
^ ab サンダース, ピーター; スペック, ヨッヘン; トレフ, イェスパー・ラーソン (2009). 「フル帯域幅ブロードキャスト、リダクション、スキャンのための2ツリーアルゴリズム」.並列コンピューティング. 35 (12): 581– 594. doi :10.1016/j.parco.2009.09.001. ISSN 0167-8191.
^ Michael Ikkert、T. Kieritz、P. Sanders Parallele Algorithmen - Script (ドイツ語)、カールスルーエ工科大学、pp.40-42、2009
^ P.サンダース [2] （ドイツ語）、カールスルーエ工科大学、pp. 101-104、2018

[:1-1] Kumar, Vipin (2002). 並列コンピューティング入門（第2版）. ボストン, マサチューセッツ州, 米国: Addison-Wesley Longman Publishing Co., Inc. pp. 185, 151, 66. ISBN 9780201648652。

[:0-2] Bruck, J.; Cypher, R.; Ho, CT. (1992). 「一般化フィボナッチ木を用いた複数メッセージブロードキャスト」. [1992] 第4回IEEE並列分散処理シンポジウム議事録. pp. 424– 431. doi :10.1109/SPDP.1992.242714. ISBN 0-8186-3200-3. S2CID 2846661。

[3] MPI: メッセージパッシングインターフェース標準バージョン3.0、メッセージパッシングインターフェースフォーラム、pp. 148、2012

[:2-4] Michael Ikkert、T. Kieritz、P. Sanders Parallele Algorithmen - Script（ドイツ語）、カールスルーエ工科大学、pp. 29-32、2009

[:5-5] Michael Ikkert、T. Kieritz、P. Sanders Parralele Algorithme - Script（ドイツ語）、カールスルーエ工科大学、pp.33-37、2009

[:6-6] P.サンダース [1] （ドイツ語）、カールスルーエ工科大学、pp. 82-96、2018

[:7-7] サンダース, ピーター; スペック, ヨッヘン; トレフ, イェスパー・ラーソン (2009). 「フル帯域幅ブロードキャスト、リダクション、スキャンのための2ツリーアルゴリズム」.並列コンピューティング. 35 (12): 581– 594. doi :10.1016/j.parco.2009.09.001. ISSN 0167-8191.

[:8-8] Michael Ikkert、T. Kieritz、P. Sanders Parallele Algorithmen - Script (ドイツ語)、カールスルーエ工科大学、pp.40-42、2009

[:9-9] P.サンダース [2] （ドイツ語）、カールスルーエ工科大学、pp. 101-104、2018