MPIクイックソートプログラム

Question

私は初心者で、プログラムを編集しようとしています。私は、配列をサブセットに分割するMPIプログラムを持っています。マスターはサブセットをスレーブに送り、クイックソートを行い、ソートされた数値をマスターに返して、ファイルに書き込むことができます。 私がしようとしているのは、クイックソートをさらに早く行うことです。私の考えは、マスターがアレイを分割し、サブセットを奴隷に送りますが、自分自身のためにそれを保持することです。次に、それらを再び新しいサブセットに分割します（たとえば、配列内に1〜100の番号がある場合、新しいサブセットは1〜25,26〜50,51〜75および76〜100でなければなりません）。 1から25まで）、第2のスレーブ（26から50）を第1のスレーブに、第3のスレーブ（51から76）を第2のスレーブなどに送る。スレーブは同じことをするべきである。次にクイックソートを実行し、スレーブはソートされた数値をマスターに返す必要があります。私はこのようにソートがより速くなることを望んでいます。問題は、私が言ったように私は初心者であり、アイデア、アドバイス、そしてコードで助けが必要なので、私は自分の目標を達成することができるということです。

Answer 1

この回答では、これをQuicksortで実行し、データを1つのプロセスで読み込むことを前提にしています。 many sophisticated parallel sorting techniquesがあることに留意してください。

サブセットで数値を区切って考えると、データの形状を前提にしているので問題があります。非一様分布のデータセットの場合、最小値と最大値を知ることさえ役立ちません。各プロセスに等しい数の数値を送信し、それらのデータをソートして後でマージすることができます。

ntasksのソートされたサブリストから始まり、1つのサブリストにしたいと考えています。素朴なマージは、各サブリスト内の最小要素を繰り返し探し、それを削除して最終リストに追加します。これには、ntasks * Nの比較、Nのスワップ、N * 2のメモリが必要です。実際のマージソートを行うことによって、log2(ntasks) * Nへの比較を最適化できますが、これにはのスワップも必要です。サブリスト（または最初の要素へのポインタ）をpriority queueに保存すると、log2(ntasks) * Nの比較とNのスワップが得られるはずです。 MPIの使用方法について

：

1. は右互いの後MPI_Isend & MPI_Waitを使用しないでください。この場合は代わりにMPI_Sendを使用してください。 MPI_IsendとMPI_Waitの間で有用な何かを実際に行うことができる場合にのみ、即時型を使用してください。
2. 可能な限り集団操作を使用してください。ルートからすべてのスレーブにデータを配布するには、MPI_ScatterまたはMPI_Scattervを使用します。最初は、すべてのランクに同じ数の要素を受け取る必要があります。これは、パディングによっても達成できます。マスタのスレーブからデータを収集するには、MPI_GatherまたはMPI_Gathervを使用します。集団は、高いレベルの操作を記述しているため、右に進む方が簡単です。それらの実装は通常、高度に最適化されています。
3. 不明なサイズのメッセージを受信するには、メッセージを直接送信し、受信側でMPI_Probeを使用してサイズを判断することもできます。上限を知っていれば、MPI_Recvには、より大きいバッファーを持つバッファーを使用することもできます。

また削減などのマージステップを検討し、そのために必要な計算を並列化することができます。

Answer 2

原則として、あなたのソリューションは非常によく見えます。大きなファイルについては、それらをまとめるか全体として処理しようとしているかどうかは完全に分かりません。私の経験から、可能な限り大きなブロックをスレーブに割り当てることをお勧めします。このようにして、かなり高価なメッセージパッシング操作は非常にまれにしか実行されません。

私があなたの質問で理解できないことは、あなたのプログラムの全体的な目標は何かです。完全な入力ファイルを並行して並べ替えることはあなたの意図ですか？このような場合は、個々のプロセスから受け取った結果にマージソートを適用する必要があります。