Parallel Quick Sort

個人的メモ

クイックソートはピボットの値以上の要素、 未満の要素と分割したときにそれぞれの部分問題は独立しているためそれらを並列に計算するという効率的なアルゴリズムをまず考えることができる. $1$ つ目の実装としてこちらを載せている. ある程度の THRESHOLD でそれ以下になった場合は分割せず通常の std::sort を用いてソートをすることにしている.
これでもある程度高速になるのだが、 std::partition を愚直に行っている部分が配列が大きくなったときにボトルネックになってしまう. 加えて, (ピボット以上の要素) と (ピボット未満の要素) の要素数に差が生じた場合に一方のスレッドの実行をもう一方が待つ時間が長くなってしまうというようなことも起こりうる.
partition アルゴリズムを parallel に行うのは考えてみると結構難しいことが分かり、 実際に研究されていることも調べてわかった(参考スライド, その論文).
詳しくは論文を見てもらえるとわかりやすいが, 論文で言うところの F & A algorithm を実装しており, 論文の主手法は実装していないことに注意(後に述べる). 配列を多数のブロックに分割し、 各スレッドは分割されたブロックを左端と右端から順に外から内に向かって (左, 右) のペアで取っていく(各スレッドには static ではなく dynamic にプロックを割り当てる). そして各スレッドで取ったブロック内の要素を外から内に見ていき, 左のブロックで pivot 以上のもの, 右のプロックで pivot 未満のものに到達したらそれらを swap するという操作を繰り返す. そして右もしくは左のブロックの終点に達したら新たに次の右および左のブロックをそのスレッドに割り当てる. 以上を繰り返すと最終的に高々 m(スレッドの数) 個のブロックが正しく配置されていない状況となるので, それを std::partition を用いて並び替える(Cleanup 操作).
論文ではこの Cleanup 操作における比較回数をより小さくするような手法を提案している. ただ比較回数は少なくなるものの少なくとも数列のソートでは単純な F & A アルゴリズムでも十分な速度が出ていることが論文内の実験から分かる(比較の演算の計算コストが重い場合などは論文の手法の方が良いように見える). 実際に論文のアルゴリズムが C++17 の parallel_quick_sort の実装に使われているようだ. 著者のホームページにその実装が上がっている(参考). また F & A algorithm についてはこちらのブログも参考になった.
実装では(ピボット以上の要素) と (ピボット未満の要素) の要素数に差が生じるような場合が気になったので std::future で待つのではなく task を queue に突っ込む実装にしている.