multithreading - (何时)并行排序实用，您如何编写有效的排序？

Question

我正在为 D 编程语言开发一个并行化库。现在我对基本原语(并行 foreach、map、reduce 和任务/ future )非常满意，我开始考虑一些更高级别的并行算法。并行化最明显的候选者之一是排序。

我的第一个问题是，排序算法的并行版本在现实世界中有用吗，还是它们主要是学术性的？如果它们有用，它们在哪里有用？我个人很少在我的工作中使用它们，仅仅是因为我通常使用比单个 sort() 调用更粗粒度的并行度将我的所有内核固定在 100%。

其次，对于大型数组来说，快速排序似乎几乎令人尴尬地并行，但我无法获得我认为应该获得的近线性加速。对于快速排序，唯一固有的串行部分是第一个分区。我尝试通过在每个分区之后并行排序两个子数组来并行化快速排序。在简化的伪代码中:

// 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()从池中窃取其他作业并执行它们，直到它等待的作业完成。如果任务未启动，则在当前线程中完成。这意味着等待并不是低效的。只要有工作要做，所有线程都会保持忙碌。

Answer 1

请记住，我不是并行排序方面的专家，人们在并行排序之外从事研究工作，但是......

1) 它们在现实世界中是否有用。

当然，如果您需要对一些昂贵的东西(例如字符串或更糟)进行排序并且您没有固定所有核心，那么它们是。

想想您需要根据上下文对大型动态字符串列表进行排序的 UI 代码

想想像 barnes-hut n-bodies sim 一样的东西，你需要在其中对粒子进行排序

2) 快速排序似乎可以提供线性加速，但事实并非如此。分区步骤是一个顺序瓶颈，如果您进行分析，您会看到这一点，并且它往往会在四核上以 2-3 倍的速度达到上限。

如果您想在较小的系统上获得良好的加速，您需要确保每个任务的开销非常小，理想情况下，您需要确保没有太多线程在运行，即在双线程上不超过 2 个核。线程池可能不是正确的抽象。

如果你想在更大的系统上获得良好的加速，你需要查看基于扫描的并行排序，有关于这方面的论文。双调排序也很容易并行化，就像归并排序一样。并行基数排序也很有用，PPL 中有一个(如果您不反对 Visual Studio 11)。