D プログラミング言語の並列化ライブラリに取り組んでいます。基本的なプリミティブ (並列 foreach、map、reduce、タスク/フューチャー) にかなり満足しているので、より高レベルの並列アルゴリズムについて考え始めています。並列化のより明白な候補の中にソートがあります。
私の最初の質問は、並べ替えアルゴリズムの並列化されたバージョンは現実の世界で役立つのか、それともほとんど学術的なものなのかということです。それらが役立つ場合、どこで役立ちますか? 私が個人的に仕事でそれらを使用することはめったにありません。単純に、単一の sort() 呼び出しよりもはるかに粒度の粗いレベルの並列処理を使用して、すべてのコアを 100% に固定するためです。
第二に、大規模な配列の場合、クイックソートはほとんど恥ずかしいほど並列であるように見えますが、得られるはずであると信じているほぼ線形のスピードアップを得ることができません。クイック ソートの場合、本質的にシリアルな部分は最初のパーティションだけです。各パーティションの後で、2 つのサブアレイを並列にソートすることで、クイック ソートを並列化してみました。簡略化された疑似コードでは:
// I tweaked this number a bunch. Anything smaller than this and the
// overhead is smaller than the parallelization gains.
const smallestToParallelize = 500;
void quickSort(T)(T[] array) {
if(array.length < someConstant) {
insertionSort(array);
return;
}
size_t pivotPosition = partition(array);
if(array.length >= smallestToParallelize) {
// Sort left subarray in a task pool thread.
auto myTask = taskPool.execute(quickSort(array[0..pivotPosition]));
quickSort(array[pivotPosition + 1..$]);
myTask.workWait();
} else {
// Regular serial quick sort.
quickSort(array[0..pivotPosition]);
quickSort(array[pivotPosition + 1..$]);
}
}
最初のパーティションにかかる時間が無視できる非常に大きな配列の場合でも、アルゴリズムの純粋なシリアル バージョンと比較して、デュアル コアでは約 30% の高速化しか得られません。ボトルネックは共有メモリアクセスだと思います。このボトルネックを解消する方法、またはボトルネックが他に何であるかについての洞察はありますか?
編集：私のタスクプールには、システム内のコア数から1を引いた数に等しい固定数のスレッドがあります（メインスレッドも機能するため）。また、私が使用している待機のタイプは作業待機です。つまり、タスクが開始されたが終了していない場合、スレッド呼び出しworkWait()はプールから他のジョブを盗み、待機中のジョブが完了するまでそれらを実行します。タスクが開始されていない場合は、現在のスレッドで完了します。これは、待機が非効率的ではないことを意味します。実行する作業がある限り、すべてのスレッドはビジー状態になります。