(何时)是实用的并行分类,你如何写一个有效的？

Question

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

我的第一个问题是,在现实世界中有用的排序算法的并行版本,还是主要是学术性的？如果它们有用,它们在哪里有用？我个人很少在我的工作中使用它们,仅仅是因为我通常使用比单一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)Quicksort似乎会给出线性加速,但事实并非如此.分区步骤是一个连续的瓶颈,如果你进行分析,你会看到这个,并且在四核上它会倾向于2-3倍.

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

如果你想在更大的系统上获得更好的加速,你需要查看基于扫描的并行排序,有关于此的论文.比特排序也很容易并行化.并行基数排序也很有用,PPL中有一个(如果你不反对Visual Studio 11).