OpenMP 通用 qsort 加速不足

Question

因此，我的实现似乎在大约 10 亿个元素时与基本串行 qsort 收支平衡。大多数在线并行 qsort 算法用于对整数数组和东西进行排序，但我希望能够使用自定义比较器（如内置 qsort）对任何内容进行排序，因为我想对我拥有的一些结构进行排序。我正在使用 12 个线程，并且可以验证它们是否正确生成并查看顶部。也许我产生了太多并且应该停止基于递归深度产生新线程？我知道我对 qsort 的实现是相当基础的，显然内置的 qsort 已经进行了大量的工作和优化，但我不明白为什么我没有得到很好的并行化加速。任何输入都将不胜感激，因为如果我能保持它的通用性，我可以在很多领域使用它。谢谢！

void test ( void* data, uint64_t startIdx, uint64_t endIdx, size_t dataSize, int (*cmp)(const void *, const void *) )
{
    #pragma omp parallel
    {
        #pragma omp single nowait
        {
            p_qsort( data, 0, MAX_INTS - 1, sizeof (testint), cmp );
        }
    }
}

void p_qsort ( void* data, uint64_t startIdx, uint64_t endIdx, size_t dataSize, int (*cmp)(const void *, const void *) )
{
    uint64_t idx = p_qsort_partition( data, startIdx, endIdx, dataSize, cmp );

    //Left array
    if ( startIdx < idx - 1 )
    {
        #pragma omp task
        p_qsort( data, startIdx, idx - 1, dataSize, cmp );
    }
    //Right array
    if ( endIdx > idx )
    {
        #pragma omp task
        p_qsort( data, idx, endIdx, dataSize, cmp );
    }
}

void swapVoidElements ( void* el1, void* el2, size_t size )
{
    if ( el1 == el2 )
        return;

    void* temp = malloc( size );

    //temp = el1
    memcpy( temp, el1, size );
    //el1 = el2
    memcpy( el1, el2, size );
    //el2 = temp
    memcpy( el2, temp, size );

    free( temp );
}

uint64_t p_qsort_partition ( void* data, uint64_t left, uint64_t right, size_t dataSize, int (*cmp)(const void *, const void *) )
{
    void* pivotP = getVoidPtr( data, left, dataSize );
    void* pivotCmp = malloc( dataSize );
    memcpy( pivotCmp, pivotP, dataSize );

    while ( left <= right )
    {
        while ( cmp( getVoidPtr( data, left, dataSize ), pivotCmp ) < 0 )
            left++;
        //while ( array[right] > pivot )
        while ( cmp( getVoidPtr( data, right, dataSize ), pivotCmp ) > 0 )
            right--;
        //Swap
        if ( left <= right )
        {
            void* leftP = getVoidPtr( data, left, dataSize );
            void* rightP = getVoidPtr( data, right, dataSize );

            swapVoidElements( leftP, rightP, dataSize );

            left++;
            right--;
        }
    }
    free( pivotCmp );

    return left;
}

void* getVoidPtr ( void* data, uint64_t idx, size_t dataSize )
{
    uint64_t idxNum = idx * dataSize;
    char* test = ((char*) data) + idxNum;

    return (void *) test;
}

Answer 1

您创建的每个 OMP 任务都会产生一些开销，并且您的特定任务会变得越来越小。随着每个任务的工作量变小，开销也会成比例地增加。串行快速排序的一些常见优化技术可能不仅对基本算法有帮助，而且对您的开销问题也有帮助。

通过切换小子数组的策略，您可以大大减少所涉及的任务总数，从而减少相关的开销。这与针对小子数组切换到插入排序的常见快速排序优化非常吻合。 "small" 的定义是一个可调参数，其最佳值在某种程度上取决于您要排序的内容，但 5 - 30 范围内的值可能对您来说是一个很好的截止值。当你进行这样的切换时，在一个任务中执行整个子数组插入排序。

您也可能受益于仅对每对子数组中较小的子数组进行递归，而不是循环处理较大的子数组。这将最大递归深度限制为 O(log n)，否则在最坏情况下为 O(n)。由于每个递归涉及其自己的任务，这也将减少至少两倍所需的任务总数。

选择好的枢轴是快速排序性能的核心问题之一，但枢轴选择算法的相对效果高度依赖于数据。我建议至少 little 比总是选择最左边的元素更复杂——在一般情况下，三中位数或随机枢轴选择可能会产生更好的性能.由于枢轴的选择会影响子数组大小，这与创建的任务数量和它们的大小有关，这可能是您的并行版本的额外胜利。

OpenMP 通用 qsort 加速不足

OpenMP generic qsort lackluster speedup

c

generics

parallel-processing

openmp

qsort