OpenMP嵌套循环并行化C程序优化及考试解题咨询

问题背景 #

需并行化以下C程序：从数组values[]中查找位置i到N-1的最大元素，结果存入数组maxs[]。要求实现两种方案：

1. 基于外循环的并行化
2. 基于内循环的并行化
   需优化代码效率，并说明两种方案的并行方式及T个线程（T<<N）的协作机制。

修正后的原始代码 #

（注：原始代码存在笔误：sums[N]应为maxs[N]，value[j]应为values[j]）

int values[N], maxs[N];
int i , j, s;

for (i = 0; i < N ; i ++) {
    s = values[i];

    for (j = i+1; j < N ; j ++)
        if (s < values[j])
            s = values[j];
 
    maxs[i] = s;
} 

初步解答的问题分析 #

1. 外循环并行方案：全局变量s会引发数据竞争——多个线程同时读写s导致结果错误；dynamic(1)调度的小粒度任务会频繁触发线程调度，开销极大。
2. 内循环并行方案：同样存在s的竞争问题，且每次外循环迭代都创建/销毁线程组，额外开销过高；dynamic(1)在内循环的小粒度任务下调度成本远超并行收益。

优化后的方案 #

方案一：基于外循环的高效并行化 #

优化代码

#include <omp.h>

int values[N], maxs[N];

// 外循环并行，线程私有变量避免竞争，选择低开销调度策略
#pragma omp parallel private(i, j, s) schedule(static)
for (int i = 0; i < N ; i ++) {
    s = values[i];
    // 内循环串行，每个线程独立处理一个i对应的后缀最大值计算
    for (int j = i+1; j < N ; j ++) {
        if (s < values[j]) {
            s = values[j];
        }
    }
    maxs[i] = s;
}

并行化方式与线程协作机制

• 并行化方式：仅对i的外循环进行拆分，每个线程分配一段连续的i迭代区间。
• 线程协作（T<<N时）：
  • 程序启动时创建T个线程的固定线程组；
  • static调度将N个外循环迭代平均划分为T块，每个线程处理N/T左右的连续i值；
  • 每个线程独立计算分配到的i对应的后缀最大值：s为线程私有，maxs[i]的写入无竞争（每个i仅被一个线程处理）；
  • 所有线程完成任务后，线程组销毁。

优化点说明

• 用private(i,j,s)将变量声明为线程私有，彻底消除数据竞争；
• 选择static调度：相比dynamic(1)大幅降低调度开销，且因i越大内循环次数越少，可通过调整块大小（如schedule(static, 64)）进一步优化负载均衡；
• 内循环保持串行：内循环计算量随i递减，并行内循环的调度开销远大于收益。

方案二：基于内循环的高效并行化 #

优化代码

#include <omp.h>

int values[N], maxs[N];

for (int i = 0; i < N ; i ++) {
    int local_max = values[i];
    // 内循环并行，用reduction自动聚合最大值，避免手动同步
    #pragma omp parallel for reduction(max: local_max) schedule(static)
    for (int j = i+1; j < N ; j ++) {
        if (local_max < values[j]) {
            local_max = values[j];
        }
    }
    maxs[i] = local_max;
}

并行化方式与线程协作机制

• 并行化方式：外循环串行，对每个i对应的内循环j进行拆分，通过reduction(max: local_max)自动完成线程间的最大值聚合。
• 线程协作（T<<N时）：
  • 每次外循环迭代时，复用线程池（或创建T个线程的临时线程组，取决于OpenMP实现）；
  • static调度将j的迭代区间[i+1, N-1]拆分为T个连续块，每个线程处理一块；
  • 每个线程维护自己的局部最大值副本，独立遍历分配的j区间并更新局部值；
  • 内循环结束时，OpenMP自动将所有线程的局部最大值聚合为最终的local_max；
  • 线程回到线程池（或销毁），外循环继续下一个i的迭代。

优化点说明

• 使用reduction(max: local_max)替代手动变量，自动处理线程间最大值聚合，彻底消除数据竞争；
• 用局部变量local_max替代全局变量，避免全局内存访问开销；
• static调度减少内循环的调度开销，比dynamic(1)更适合大区间的内循环拆分；
• 避免显式同步（如临界区），reduction操作的性能远优于手动同步。

额外加分优化建议（算法层面） #

若允许调整原始算法，可先预处理从后往前的后缀最大值数组，时间复杂度从O(N²)降至O(N)，再并行化反向循环进一步提升效率：

#include <omp.h>

int values[N], maxs[N];
maxs[N-1] = values[N-1];

#pragma omp parallel for schedule(static)
for (int i = N-2; i >= 0; i--) {
    maxs[i] = (values[i] > maxs[i+1]) ? values[i] : maxs[i+1];
}

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