为何OpenMP矩阵乘法程序单线程运行快于多线程？

我用OpenMP实现了两种矩阵乘法算法，测试发现设置num_threads(1)时程序运行速度反而快于其他线程数。想请教这是数据传输开销过大导致，还是存在其他问题？

#include <omp.h>
#include <stdio.h>
#include <cstdlib>
#include <ctime>
int main(){
    const int n = 1024;
    const int m = 128;

    int** A = new int* [n];
    int** B = new int* [n];
    int** C = new int* [n];
    for (int i=0; i<n; i++){
        A[i] = new int[n];
        B[i] = new int[n];
        C[i] = new int[n];
    }

    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            A[i][j] = rand() % 10;
            B[i][j] = rand() % 10;
        }
    }

    clock_t start = clock();
    #pragma omp parallel for num_threads(6) schedule (dynamic,m)
    for (int j=0; j<n; j++){
        for (int i=0; i<n; i++){
            for (int k=0; k<n; k++)
                C[i][j] += A[i][k]*B[k][j];
        }
    }
    clock_t end = clock();
    printf("Time for j-i-k: %f\n", (double) (end - start) / CLOCKS_PER_SEC);

    start = clock();
    #pragma omp parallel for num_threads(6) schedule (dynamic,m)
    for (int k=0; k<n; k++){
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++)
                C[i][j] += A[i][k]*B[k][j];
        }
    }
    end = clock();
    printf("Time for k-i-j: %f\n", (double) (end - start) / CLOCKS_PER_SEC);

    for (int i=0; i<n; i++){
        delete[] A[i];
        delete[] B[i];
        delete[] C[i];
    }
    delete[] A;
    delete[] B;
    delete[] C;
}

核心原因分析 #

你的代码里多线程比单线程慢，主要不是单纯的“数据传输开销”，而是内存布局、缓存利用率、线程调度这三个核心问题叠加导致的：

1. 非连续内存布局彻底破坏缓存局部性
   你用int**创建的二维数组，本质是指针数组，每一行都是单独new出来的零散内存块，物理上不连续。矩阵乘法是内存密集型运算，对缓存友好性要求极高——这种非连续的内存访问会导致CPU缓存频繁失效，每次都要从内存加载数据，速度骤降。多线程下，多个线程同时竞争缓存资源，缓存命中率会进一步恶化，而单线程至少不会有额外的缓存竞争开销。

2. 循环顺序导致的非连续数据访问

   • 第一种j-i-k循环：访问B[k][j]是按列遍历，但C++默认是行优先存储，这意味着每次访问都要跳过n个int的地址，完全无法利用缓存的空间局部性。
   • 第二种k-i-j循环：虽然内层是j循环，但B[k][j]的访问依然是跨行的非连续操作，加上内存本身不连续，缓存失效的问题被放大。多线程下这种低效的内存访问带来的性能损失，远超过多线程并行的收益。

3. 动态调度的额外开销
   你用了schedule(dynamic, m)，动态调度需要线程间频繁分配任务、同步状态，当每个任务块的计算量（这里m=128）不够大时，调度的额外开销会直接抵消甚至超过多线程带来的计算收益。单线程完全没有这部分开销，自然跑得更快。

优化建议 #

要让多线程体现出优势，可以从这几个方向修改：

• 改用连续内存的二维数组：用一维数组模拟二维，比如int* A = new int[n*n];，然后用A[i*n + j]访问元素，保证内存连续，大幅提升缓存命中率。
• 调整循环顺序：优先用i-k-j的循环顺序，让A[i][k]和B[k][j]（如果提前转置B的话）都变成连续的行访问，最大化缓存利用率。
• 更换调度策略：去掉动态调度，改用默认的静态调度schedule(static)，或者直接省略调度参数，减少任务分配的开销。
• 初始化结果矩阵：C矩阵在new后没有初始化，里面是垃圾值，计算C[i][j] += ...会得到错误结果，记得在计算前把C的所有元素设为0。
• 尝试分块优化：把矩阵分成64x64或128x128的小块（根据CPU缓存大小调整），让每个小块能完全放进缓存，进一步提升缓存利用率，多线程下分块优化的收益会更明显。

内容的提问来源于stack exchange，提问作者Илья Анненков