マルチコアCPUによるパラレル・ソート

2年ほど前に作成したマージ・ソートの分割処理及び併合処理を並列化したソート・プログラムをご紹介します。
キモは、CPUコアをフル稼働させるため連の組を分割し並列併合処理している点とその連の組の分割を効率よく行うためにバイナリサーチ・アルゴリズムを応用している点ですが、自作PC(Xeon 14コアx2=28コア56スレッド)でのランダムな1000万~5000万個の整数ソート性能はCPUコア数倍にまで達し理想的な結果であり、最初から最後まで完全に並列処理することによりCPUコアをフル稼働できていることによる結果と言えます。
基本ソートとして安定だけど遅い挿入ソートを利用していますが、後日、JavaのArrays.parallelSort()と比較してみたところほぼ同性能でした。が、JavaのArrays.sort()はシングルスレッドでもかなり早い...こんだけCPU使ってと考えるとなんとなく萎えます。(笑)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください