parallel-processing - MPI 通信の複雑さ

Question

MPI での Quicksort の並列実装の通信の複雑さを研究していて、本で次のようなものを見つけました。

「単一のプロセスは、他の p-1 プロセスのそれぞれから p 個の通常のサンプルを収集します。比較的少数の値が渡されるため、メッセージの待ち時間がこのステップの支配的な用語になる可能性があります。したがって、収集の通信の複雑さは O(log p)" (O は実際にはシータであり、p はプロセッサの数です)。

ブロードキャスト メッセージについても同じ肯定が行われます。

これらのグループ通信の複雑さは、なぜ O(log p) なのですか? ある種のツリーベースの階層を使用して通信が行われているためでしょうか?

レイテンシが支配的な用語ではなく、大量のデータが送信されている場合はどうなるでしょうか? 複雑さは O(n log (p)) で、n は送信されるデータのサイズを利用可能な帯域幅で割ったものになりますか?

また、MPI_Send() と MPI_Recv() の通信の複雑さはどうですか?

前もって感謝します！

Answer 1

はい、収集と分散は、たとえば二項ツリー、ハイパーキューブ、線形配列、または2D正方形メッシュを使用して（特定のMPIリリースに応じて）実装されます。オールギャザー操作は、ハイパーキューブなどを使用して実装できます。

ギャザーまたはスキャッターの場合、ラムダをレイテンシー、ベータを帯域幅とします。次に、logpステップが必要です。それぞれ4バイトを使用して表されるn個の整数を送信するとします。それらを送信する時間は

これは、n = O（1）の場合はO（log p）であり、それ以外の場合はO（log p + n）です。放送の場合、所要時間は

これは、n = O（1）の場合はO（log p）であり、それ以外の場合はO（n log p）です。

最後に、MPI_Send（）のようなポイントツーポイント通信の場合、n個の整数を送信する場合、通信の複雑さはO（n）です。n = O（1）の場合、複雑さは明らかにO（1）です。