并行奇偶归并排序优化疑问：循环并行化后性能下降且单线程执行

问题根源分析 #

1. 嵌套并行默认禁用：代码外层已存在#pragma omp parallel并行区域，oddEvenMerge中的parallel for属于嵌套并行场景。OpenMP默认关闭嵌套并行，因此内层并行区域不会真正创建新线程，只会复用当前执行task的单一线程运行循环。
2. 线程开销抵消收益：即便开启嵌套并行，小循环的线程创建、销毁及调度开销可能远超过并行计算带来的性能提升，直接导致整体性能下降。
3. 循环迭代数不足：当n较小时，n/2 -1的循环迭代次数过少，并行化的额外成本完全覆盖了加速效果。

具体优化方案 #

1. 复用外层线程池，避免嵌套并行 #

外层已存在并行线程池，无需在循环处重新创建新的并行区域，直接用#pragma omp for将任务分配给空闲线程：

void oddEvenMerge(int *arr, int n) {
    // ... 原有代码 ...

    // 去掉parallel，直接用omp for复用外层线程
    #pragma omp for schedule(static)
    for (int i = 1; i < n / 2; i++) {
        printf("Thread %d\n", omp_get_thread_num());
        compare(arr, 2 * i - 1, 2 * i);
    }

    // ... 原有代码 ...
}

注意：编译时需开启OpenMP支持（如GCC添加-fopenmp参数），且外层并行区域需始终存在（你的代码已满足该条件）。

2. 按循环规模动态选择并行策略 #

仅当数组规模n足够大时才并行循环，小规模循环保持串行，避免不必要的开销：

void oddEvenMerge(int *arr, int n) {
    // ... 原有代码 ...

    const int PARALLEL_THRESHOLD = 1024; // 可根据实际测试调整阈值
    if (n > PARALLEL_THRESHOLD) {
        #pragma omp for schedule(static)
        for (int i = 1; i < n / 2; i++) {
            compare(arr, 2 * i - 1, 2 * i);
        }
    } else {
        // 小规模循环串行执行
        for (int i = 1; i < n / 2; i++) {
            compare(arr, 2 * i - 1, 2 * i);
        }
    }

    // ... 原有代码 ...
}

3. 用统一任务调度替代并行循环 #

将循环中的每个比较操作包装为OpenMP task，让全局任务调度器统一分配给空闲线程，与排序task共享线程池：

void oddEvenMerge(int *arr, int n) {
    // ... 原有代码 ...

    #pragma omp single
    {
        for (int i = 1; i < n / 2; i++) {
            #pragma omp task firstprivate(i) shared(arr)
            compare(arr, 2 * i - 1, 2 * i);
        }
    }
    #pragma omp taskwait // 等待所有比较task完成

    // ... 原有代码 ...
}

这种方式能更灵活地利用线程资源，避免线程池重复创建的开销。

额外性能优化建议 #

• 减少动态内存开销：oddEvenMerge中频繁的malloc/free会严重拖慢性能，可改用栈上数组（当n在栈容量范围内时）或预先分配内存池复用。
• 调整task粒度阈值：代码中的level和limit参数可根据硬件情况测试调整，避免创建过多微小task导致调度过载。

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