OpenMP实现Summed Area Table（积分图像）性能不及串行版本问题咨询

我来帮你拆解一下问题所在，你的并行代码性能不佳主要是几个关键的设计和实现问题导致的，咱们一个个说：

1. 转置操作的缓存灾难（最大瓶颈） #

你的transpose函数实现是导致性能暴跌的核心原因：

void transpose(unsigned long *src, unsigned long *dst, const int N, const int M) {
    #pragma omp parallel for
    for(int n = 0; n<N*M; n++) {
        int i = n/N;
        int j = n%N;
        dst[n] = src[M*j + i];
    }
}

当遍历全局索引n时，src[M*j + i]的访问是按列跳跃式的——每次访问的元素间隔M个位置，完全不利用CPU缓存的空间局部性。缓存行是连续存储的，按列读取意味着每个元素都在不同的缓存行，缓存命中率几乎为0，导致大量的内存访问延迟，这比串行代码的连续内存访问慢几个数量级。

2. 多次并行区域的同步开销 #

你的代码里用了3次独立的#pragma omp parallel for，每次并行区域都会触发线程的调度、同步（barrier）开销。尤其是当图像尺寸不大时，这些开销的占比会远超过并行带来的收益，直接抵消了并行加速的效果。

3. 冗余的内存操作 #

并行代码额外分配了rows数组，加上两次转置的数据拷贝，内存带宽的消耗是串行代码的两倍以上。而内存带宽本身就是很多计算密集型任务的瓶颈，这进一步拖慢了并行版本的速度。

4. 行求和的内存访问冗余 #

原并行代码的行求和部分每次都要读取前一个元素的内存值：

rows[i*m + j] = x[i*m + j] + rows[i*m + j - 1];

其实可以用累加变量减少一次内存读取，提升缓存效率：

unsigned long sum = x[i*m];
rows[i*m] = sum;
for (int j = 1; j < m; ++j) {
    sum += x[i*m + j];
    rows[i*m + j] = sum;
}

改进后的并行实现方案 #

针对以上问题，我给你调整了代码，核心优化点是分块转置提升缓存命中率、合并并行区域减少同步开销、优化内存访问模式：

优化后的转置函数（分块实现） #

分块转置让每个块内的内存访问是连续的，充分利用CPU缓存：

void transpose(unsigned long *src, unsigned long *dst, const int rows, const int cols) {
    const int block_size = 32; // 适配缓存行大小，可根据CPU调整
    #pragma omp parallel for collapse(2)
    for (int i = 0; i < rows; i += block_size) {
        for (int j = 0; j < cols; j += block_size) {
            // 转置当前块内的元素
            for (int ii = i; ii < std::min(i + block_size, rows); ++ii) {
                for (int jj = j; jj < std::min(j + block_size, cols); ++jj) {
                    dst[jj * rows + ii] = src[ii * cols + jj];
                }
            }
        }
    }
}

优化后的积分图像并行函数 #

合并所有并行操作到一个#pragma omp parallel区域，减少线程初始化开销，同时优化行求和的累加方式：

#include <algorithm> // 用于std::min

unsigned long * integralImageMP(uint8_t*x, int n, int m){
    unsigned long * out = new unsigned long[n*m];
    unsigned long * rows = new unsigned long[n*m];

    #pragma omp parallel
    {
        // 并行计算行前缀和
        #pragma omp for
        for (int i = 0; i < n; ++i) {
            unsigned long sum = x[i*m];
            rows[i*m] = sum;
            for (int j = 1; j < m; ++j) {
                sum += x[i*m + j];
                rows[i*m + j] = sum;
            }
        }

        // 第一次转置：行求和结果转置为列优先
        transpose(rows, out, n, m);

        // 并行计算转置后的行前缀和（等价于原矩阵的列前缀和）
        #pragma omp for
        for (int i = 0; i < m; ++i) {
            unsigned long sum = out[i*n];
            rows[i*n] = sum;
            for (int j = 1; j < n; ++j) {
                sum += out[i*n + j];
                rows[i*n + j] = sum;
            }
        }

        // 第二次转置：恢复原矩阵的行列顺序
        transpose(rows, out, m, n);
    }

    delete [] rows;
    return out;
}

额外的性能优化建议 #

1. 开启编译器优化：你的编译命令没有加优化选项，一定要加上-O3，比如：

   g++ -fopenmp -Wall -O3 main.cpp
   

   编译器的优化对串行和并行代码的性能影响极大，尤其是串行代码在-O3下会被优化到接近硬件极限。

2. 合理设置线程数：不要设置超过机器物理核心数的线程数（比如双核i5设为2，12核Xeon设为12），超线程的收益有限，过多线程会导致上下文切换开销增加。

3. 尝试直接并行列求和：如果不想用转置，也可以直接并行处理列前缀和，利用按列并行（每列内部顺序计算）的方式，避免转置的开销，比如：

   // 行前缀和之后，并行列求和
   #pragma omp parallel for
   for (int j = 0; j < m; ++j) {
       unsigned long sum = 0;
       for (int i = 0; i < n; ++i) {
           sum += out[i*m + j];
           out[i*m + j] = sum;
       }
   }
   

   这种方式不需要转置，但列访问的缓存命中率较低，适合大尺寸图像（此时计算量占主导，内存延迟的影响相对较小）。

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