OpenMP矩阵乘法并行版本慢于串行问题排查及Strassen优化咨询

核心问题排查 #

• 计时函数使用错误
  你当前用clock()统计耗时，该函数统计的是进程总的CPU时间，多线程场景下会累加所有线程的CPU占用，所以你看到的并行100秒其实是4个线程的CPU时间总和，真实的墙钟耗时远低于该值。正确的并行计时应该用omp_get_wtime()，该函数返回真实的墙钟时间。
• 循环顺序不合理导致cache命中率极低
  当前三重循环采用row-col-transNumber（i-j-k）的顺序，C语言数组为行优先存储，访问secondMatrix[transNumber][col]时是跨列访问，每一次访问都会触发cache miss，这是串行和并行版本都很慢的核心原因。把循环顺序调整为row-transNumber-col（i-k-j）即可让secondMatrix的访问变为行连续，cache命中率提升百倍以上，性能会有数量级的提升。
• 并行拆分逻辑错误
  你当前的end计算逻辑有bug：前3个线程的end设置为start + thread_multi - 1，而循环判断条件为row < end，导致每个前线程少计算1行，最终结果错误。正确的拆分逻辑不需要区分最后一个线程，直接设置start = thread * thread_multi; end = (thread == THREAD_NUM -1) ? N : start + thread_multi;即可。
• 多余IO拖慢性能
  matrixMulti2里的printf是线程安全的IO操作，会触发全局锁竞争，严重拖慢并行性能，测试时直接删掉该行。
• 编译参数缺失
  编译时必须加上-fopenmp -O2 -march=native参数，否则OpenMP不生效、无编译器优化，性能会非常差。

优化后并行版本示例 #

// 优化后的矩阵乘法核心
void matrixMultiOpt(int start, int end) {
    for(int row = start ; row < end ; row++){
        for(int transNumber = 0 ; transNumber < N ; transNumber++) {
            double tmp = firstMatrix[row][transNumber];
            for(int col = 0; col < N ; col++){
                matrixMultiResult[row][col] += tmp * secondMatrix[transNumber][col];
            }
        }
    }
}

// 优化后的并行流程
void process1(){
    double t1 = omp_get_wtime(); 
    #pragma omp parallel num_threads(THREAD_NUM)
    {
        int thread = omp_get_thread_num();
        int thread_multi = N / THREAD_NUM;
        int start = thread * thread_multi;
        int end = (thread == THREAD_NUM - 1) ? N : start + thread_multi;
        matrixMultiOpt(start, end);
    }
    double t2 = omp_get_wtime(); 
    printf("parallel time: %lf s\n", t2-t1);
}

改完上述问题后，2048规模的矩阵乘法并行版本耗时应该在1秒以内，远低于当前的90秒串行耗时。

基础优化 #

可以在上述优化基础上增加**循环分块（Blocking）**优化，将矩阵拆分为3232或者6464的小块计算，进一步提升各级cache的命中率，性能还能提升30%以上。也可以开启编译器的SIMD优化，或者手动使用AVX2指令集做向量化计算。

Strassen矩阵乘法实现思路 #

1. 阈值设置：当矩阵规模小于设定阈值（通常为64~128）时，直接使用上述优化后的普通三重循环计算，避免递归开销抵消算法优势。
2. 分治拆分：将两个输入矩阵各拆分为4个大小相等的子矩阵，按照Strassen算法定义计算7个中间乘积，不需要做8次常规子矩阵乘法。
3. 结果合并：用7个中间乘积加减运算得到最终的4个结果子矩阵，合并得到完整的结果矩阵。
4. 非2幂次适配：如果矩阵大小不是2的幂次，可以先补0扩充到最近的2的幂次，计算完成后再裁剪掉多余的0元素，也可以直接实现支持任意大小的Strassen版本。
5. 并行适配：可以在Strassen的递归上层用OpenMP并行计算7个中间乘积，进一步提升多核利用率。

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