はじめに
MPI_Bcastは、MPI集団通信の中でも比較的よく使われる命令ではないでしょうか。
MPI_Bcastに限らずですが、集団通信は、全てのノードが通信に参加するため通信コストがかかりやすく、故にスーパーコンピュータ上で計算を実行する際には集団通信にかかる時間がボトルネックになりがちです。
したがって、集団通信をただなんとなく使うのではなく、きちんと性能などに関して知識を得た上で使う事が望ましい事では無いでしょうか。
(本当はそうなっていないのがいいのだとは思いますが…)
そこで、本稿では、MPI_Bcastに関してその性能を予測する方法などに関して、備忘録的に残しておきたいと思います。
これを見て「あれ…？私の集団通信遅すぎ…？」となる方が一人でも減るといいですね。
MPI_Bcastのコスト予測
まず、ここで今更書く事でも無いような気もしますが、Bcastとはbroadcast(放送)の略で、あるプロセスが持っている変数の値(メッセージとか言います)を、その他のプロセス全てに教える事です。
この送信元のプロセスをルートプロセスと言い、以下このルートプロセスの番号は$0$としておきます。
さて、プロセスは基本的に他のプロセスとは同時に1つとしか通信できません。
したがって、ルートプロセスが他の全てのプロセスに同時にデータを投げる、という事はできません。
この制約の下でどの様にBcastするかという話ですが、パッと思いつくのは
「プロセス$0$が$1$にデータを送信し、$1$はそれを受信。次に、$1$が$2$にデータを送信し、$2$はそれを受信。次に、$2$が$3$に…」
というパターンでしょうか、バケツリレー方式です。
これは、chainと呼ばれています(ここには絵を描こうと思ったのですが面倒なので後回しにしています)。
一方で、ルートプロセスが全ての責任を負って、
「プロセス$0$が$1$にデータを送信し、$1$はそれを受信。$0$は次に$2$にデータを送信し、$2$はそれを受信。次に、$0$は$3$に…」
というパターンもありなのではないでしょうか(ここには絵を描こうと思ったのですが面倒なので後回しにしています)。
これはbasic linearと呼ばれています。
さて、いずれのパターンにしてもですが、基本的には総プロセス数を$P$とした時、$P-1$回の送受信が発生しています。
そこで、これらの手法でMPI_Bcastした際のコストに関して、その通信時間を簡単に見積もってみましょう。
見積もりの方法はいくつかありますが、今回は恐らく一番簡単な、Hockneyモデル(https://doi.org/10.1016/S0167-8191(06)80021-9) を用いたいと思います。
(通信時間モデルには他にもLogGPモデルや、PlogPモデルと呼ばれる物もあるので、気になる方は調べてみてください。)
さて、Hockneyモデルでは、まず、通信時間を、通信を行う際の準備に必要な時間(レイテンシとか言います)と実際の転送にかかった時間に分割します。
前者を$L$と書き、後者を$M / B$と書きますと、通信1つにかかる時間$t$は、以下の用に書けます。
t = L + \frac{M}{B}
ただし、ここで$M$はメッセージのサイズ(byte)、$B$はプロセス間の通信の速度(バンド幅 byte/sec)です。
この通信が$P - 1$回発生するので、結局このBcast一回にかかる通信時間$T$は、
T = (P - 1)\left(L + \frac{M}{B}\right)
となります。
さて、実際にはこれら以外にも木構造ベースの通信アルゴリズムが存在しています。
例えば、二分木構造を用いて、
「プロセス$0$が$1$にデータを送信し、次に$2$に送信。プロセス$1$はプロセス$3$に、その次に$4$に送信、同時にプロセス$2$はプロセス$5$に、その次に$6$に送信…」
とするものです(ここには絵を描こうと思ったのですが面倒なので後回しにしています)。
データを受信したプロセスが同時に通信する事で、通信回数は同じでも通信ラウンドの数をへらす事が可能になります。
結果、通信時間は、
T = 2 \left(\left\lfloor \log_2 P \right\rfloor - 1\right) \left(L + \frac{M}{B} \right)
に削減する事が可能になります(導出は略)。
これはbinary treeと呼ばれています。
また、split binary treeという物も存在していますが、一旦省略します。
また、二項木構造を用いて、
「プロセス$0$が$1$にデータを送信する。次に、$0$が$2$に、$1$は$3$に。次に、$0$は$4$に、$1$は$5$に、$2$は$6$に、$3$は$に$。…」
とする物もありでしょう(ここには絵を描こうと思ったのですが面倒なので後回しにしています)。
通信時間は、
T = \left\lceil \log_2 P \right\rceil \left(L + \frac{M}{B} \right)
となります。
これはbinomial treeと呼ばれています。
ここまでの結論
さて、これらの事から、実際にグラフを書いてみるまでもなくbinomial treeが最速なので、MPI_Bcastを行う時は深いことを考えずとりあえずbinomial treeを使えばいい、という様に見えます。
しかしながら、実際には$L$や$B$は、ネットワークスイッチの状況やプロセスとノードのマップのされ方など、ハードウェア的な部分から決まり、故にアルゴリズムに依存します。
したがって、性能予測をしようと言いつつも、結局のところやってみないとわからない、という面も多々あります。
また、ではここまでで紹介した事だけで終わりかというとそうでもなく、実際にはパイプライン転送と呼ばれるアルゴリズムが適用され、更に効率的な転送を行える様になっています。
これは(2)で書く事にしましょう(いつになるか全くわからないけど…)。