基于OpenMP的奇偶归并排序并行优化问题：并行性能劣于串行

问题现象 #

• 在oddEvenMergeSort函数中使用#pragma omp task拆分递归任务后，性能与串行版本完全一致；
• 在oddEvenMerge函数中添加#pragma omp task并行处理子任务时，性能反而比串行版本更差；
• 给oddEvenSplit和oddEvenJoin中的简单循环添加#pragma omp parallel for后，性能同样劣于串行，推测是循环逻辑过于简单，并行调度开销远大于计算收益。

相关代码 #

oddEvenMergeSort 函数 #

void oddEvenMergeSort(int *arr, int n) {
    if (n > 1) {
        int m = n / 2;

        #pragma omp task shared(arr) // 为前半部分创建任务
        oddEvenMergeSort(arr, m);

        #pragma omp task shared(arr) // 为后半部分创建任务
        oddEvenMergeSort(arr + m, n - m);

        // #pragma omp taskwait // 等待前两个任务完成
        oddEvenMerge(arr, n);
    }
}

oddEvenMerge 函数 #

void oddEvenMerge(int *arr, int n) {
    if (n == 1) return;
    if (n == 2) {
        compare(arr, 0, 1);
        return;
    }
    else {
        int *odd = (int *)malloc(sizeof(int) * (n / 2));
        int *even = (int *)malloc(sizeof(int) * (n / 2));
        oddEvenSplit(arr, odd, even, n);
        
        // #pragma omp task shared(odd, even)
        oddEvenMerge(odd, n / 2);

        // #pragma omp task shared(odd, even)
        oddEvenMerge(even, n / 2);

        oddEvenJoin(arr, odd, even, n);

        for (int i = 1; i < n / 2; i++) {
            compare(arr, 2 * i - 1, 2 * i);
        }

        free(odd);
        free(even);
    }
}

oddEvenSplit 与 oddEvenJoin 函数 #

void oddEvenSplit(int *arr, int *odd, int *even, int n) {
    // #pragma omp parallel for
    for (int i = 0; i < n/2; i++) {
        odd[i] = arr[2 * i + 1];
        even[i] = arr[2 * i];
    }
}

void oddEvenJoin(int *arr, int *odd, int *even, int n) {
    // #pragma omp parallel for
    for (int i = 0; i < n/2; i++) {
        arr[2 * i + 1] = odd[i];
        arr[2 * i] = even[i];
    }
}

优化建议 #

1. 控制任务粒度：递归到足够大的子数组再开启并行。比如设置阈值（如n < 1024），当子数组大小小于阈值时直接用串行排序，避免过小任务带来的调度开销。
2. 修复同步问题：oddEvenMergeSort中必须恢复#pragma omp taskwait，否则oddEvenMerge会在子任务未完成时提前执行，不仅导致排序错误，还会破坏并行逻辑的性能。
3. 消除动态内存开销：oddEvenMerge中每次递归都调用malloc和free会带来大量内存操作开销，并行场景下还会加剧内存竞争。建议预先分配全局临时数组，或者改用原地排序的奇偶归并实现。
4. 移除简单循环的并行指令：oddEvenSplit和oddEvenJoin的循环单迭代操作极少，并行调度的开销远大于计算收益，保持串行即可。
5. 优化任务共享属性：在#pragma omp task中，尽量使用private或firstprivate减少线程间的内存竞争。例如oddEvenMergeSort的子任务中，arr + m可以作为私有指针传递，避免shared带来的潜在竞争。

内容的提问来源于stack exchange，提问作者Marcos Alonso