并行算法比串行算法慢是否正常？矩阵乘法代码性能疑问

问题描述 #

我需要对比矩阵乘法的串行与并行版本性能，以下是测试代码及遇到的问题：

串行代码 #

// sequential
for (int k = 0; k < ROWS; k++) {
    for (int i = 0; i < COLUMNS; i++) {
        for (int j = 0; j < COLUMNS; j++) {
            c[i][j] += a[i][k] * b[k][j];
        }
    }
}

初始并行代码（分块版本） #

// parallel
omp_set_num_threads(8);
int r = 128;
#pragma omp parallel for
for (int i = 0; i < ROWS; i += r) {
    for (int j = 0; j < COLUMNS; j += r) {
        for (int k = 0; k < COLUMNS; k += r) {
            for (int ii = i; ii < i + r; ii++) { 
                for (int jj = j; jj < j + r; jj++) {
                    for (int kk = k; kk < k + r; kk++) {
                        c[ii][jj] += a[ii][kk] * b[kk][jj];
                    }
                }
            }
        }
    }
}

补充的并行代码（Reduction版本） #

#pragma omp parallel for reduction(+:sum)
for (int k = 0; k < ROWS; k++) {
    for (int i = 0; i < COLUMNS; i++) {
        sum = 0.0;
        for (int j = 0; j < COLUMNS; j++) {
            sum = a[i][k] * b[k][j];
            c[i][j] += sum;
        }
    }
}

注：必须使用上述循环嵌套结构！

实际测试发现并行版本比串行版本更慢：当矩阵规模为1024时，串行耗时0.61秒，并行耗时1.16秒。请问是代码存在错误，还是循环嵌套结构导致的这种情况？

原因分析与优化建议 #

1. 初始分块并行代码的问题 #

（1）缓存局部性被破坏

串行代码的循环顺序是k-i-j，虽然b[k][j]是按列访问（缓存命中率低），但分块并行后直接改成了i-j-k的分块嵌套，完全打乱了原本的内存访问模式。加上分块大小r=128，内层循环的内存访问变成跳跃式，缓存命中率进一步下降，内存读写开销远超并行带来的收益。

（2）循环层级开销过高

分块后额外增加了3层嵌套循环，每个小循环的迭代次数减少，循环控制的固定开销占比大幅上升，直接抵消了多线程的计算优势。

2. 补充的Reduction并行代码的问题 #

（1）Reduction完全误用

你给sum加了reduction(+:sum)，但sum在每次i循环都会被重置为0，而且sum只是单次赋值（不是累加），这个Reduction不仅没用，还会带来额外的线程同步开销。

（2）并行循环选择错误

并行的是最外层k循环，多个线程会同时修改同一个c[i][j]，虽然+=是原子操作，但隐式的同步锁会拖慢速度。同时，a[i][k]是按列访问，缓存命中率极低，内存瓶颈完全盖过了并行的优势。

3. 保留原循环结构的正确并行方式 #

如果必须保留原串行代码的k-i-j循环结构，正确的做法是并行中间层的i循环——每个线程负责不同的i行，计算c[i][*]，无数据竞争，同时还能优化缓存访问：

omp_set_num_threads(8);
#pragma omp parallel for
for (int i = 0; i < COLUMNS; i++) {  // 并行i循环，每个线程处理独立的行
    for (int k = 0; k < ROWS; k++) {
        int a_ik = a[i][k];  // 缓存a[i][k]，减少重复内存读取
        for (int j = 0; j < COLUMNS; j++) {
            c[i][j] += a_ik * b[k][j];
        }
    }
}

这个版本既保留了原循环结构，又避免了线程竞争，还通过缓存优化降低了内存开销，能有效提升并行性能。

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