再考—並列ソートと検索 in C/C++

前回 sort_r-20100723.tar.bz2 とともに示したように、並列マージソートと並列イントロソートは極めてパフォーマンスが良好である事がわかった。但し、要素数が少ないとスレッド処理のオーバーヘッドが無視できないことから、詳細な調査を行った。

並列マージソート、並列イントロソート

• pmergesort_r が C による並列マージソート（自作）
• parallel_stable_sort が C++ による並列マージソート（自作）
• pintrosort_r が C による並列イントロソート（自作）
• parallel_sort が C++ による並列イントロソート（自作）
• psort* が C および GCD による並列イントロソート
• mergesort* が C による逐次マージソート（mergesort_rは自作）
• stable_sort が C++ STL による逐次マージソート
• introsort_r, qsort* が C による逐次イントロソートもしくは逐次クイックソート（introsort_r, qsort_rは自作）
• sort が C++ STL による逐次イントロソート

以上を踏まえて、調査結果の一部を見てみよう。ちなみにこれは、並列度 4 の計算機環境での結果である。

これは「要素doubleのソート」の結果である。並列ソートは psort* を除き、数万以下の要素数でパフォーマンスが頭打ち傾向になるのがわかる。それに比べて psort* は少ない要素数でも極めて安定している。また、C++ による並列マージソートが思いのほか高速である。

これは「要素doubleが比較対象のインデックスのソート」の結果である。先の結果と同様だが、C++ による並列マージソートが非常に高速である。

これは「要素が構造体でそのメンバ in6_addr が比較対象のソート」の結果である。先の結果と近い傾向だが、この場合は順当に、C++ による並列イントロソートが高速となっている。ちなみに、自作の introsort_r, qsort_r はシステム標準の qsort_b より若干性能がよくなっている。これは配布物のソースコードを見て貰えればわかるように、バイナリサイズを犠牲にして型によってコードを最適化されるように工夫したからである。

並列奇偶転置ソート、並列シェルソート

さて、書籍「並行コンピューティング技法」には、並列奇偶転置ソート、並列シェルソート、および、並列クイックソートについて紹介されている。並列クイックソートは、技術的には並列イントロソートとほぼ同様なので、並列奇偶転置ソートと並列シェルソートについて詳細な調査を行った。

まず、並列奇偶転置ソートでは、書籍で紹介されている OpenMP による技法でも、独自にスレッドの粒度を調整しても、逐次奇偶転置ソートと比べて性能が上がらなかった事から、以下の調査結果には載せていない。元来低速なソートアルゴリズムなので、現時点ではこれ以上の調査は行わないことにした。

一方、並列シェルソートについては、使い勝手がよいかは別として、一定の性能向上が得られた。

• pshellsort_r が C による並列シェルソート（自作）
• parallel_shell_sort が C++ による並列シェルソート（自作）
• shellsort_r が C による逐次シェルソート（自作）
• shell_sort が C++ による逐次シェルソート
• partialsort_r, heapsort* が C による逐次ヒープソート（partialsort_r, heapsort_rは自作）
• partial_sort が C++ STL による逐次ヒープソート

以上を踏まえて、調査結果の一部を見てみよう。ちなみにこれは、並列度 4 の計算機環境での結果である。

これは「要素doubleのソート」の結果である。並列シェルソートの性能向上が見られるのは、要素数が数万を超えてからであり、それ以下の場合はスレッド処理のオーバーヘッドが大きすぎて使い勝手が悪いだろう。

これは「要素doubleが比較対象のインデックスのソート」の結果である。先の結果と同様である。

これは「要素が構造体でそのメンバ in6_addr が比較対象のソート」の結果である。先の結果と近い傾向だが、性能向上の割合がより大きくなっている。

まとめ

並列奇偶転置ソート、並列シェルソートを選択する動機までは得られなかったが、配布物のソースコードを見て貰えればわかるように、並列コンピューティングにはいろいろな技術があり、実際に与えられた計算機環境で試してみないと、性能向上が得られるかどうか分からない場合が多い。

一方、並列マージソート、並列イントロソートを選択する動機が大いに得られた。特に、並列マージソートは場面によっては並列イントロソートよりも高速なので極めて利用価値が高いと言える。