并行矩阵乘法加速比与并行效率超1异常问题咨询

问题背景 #

我实现了基于OpenMP的并行矩阵乘法，测试了1、2、4、8、16、32线程下的加速比与并行效率，发现并行效率超过了理论上限1。运行环境与代码如下：

运行环境 #

• 物理CPU：Intel i5（4核），16GB内存
• 虚拟机环境：Ubuntu 20.04.6（64位），gcc版本9.4.0 20210601

编译运行命令 #

gcc -fopenmp -o mul MatrixMul.c 
./mul 32  # 32为线程数，支持多参数，默认1线程

实现代码 #

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

// Number of threads
int n_threads = 1;

// Matrix dimensions
int n = 1000; // The number of rows of A
int m = 3000; // The number of columns for A and the number of rows for B
int p = 1000; // Number of columns for B
// Matrices A, B, C
int **A, **B, **C;

// Initialize the A and B matrices and allocate space to the C matrice
void init() {
    A = (int **)calloc(n, sizeof(int *));
    for (int i = 0; i < n; i++) {
        A[i] = (int *)calloc(m, sizeof(int));
        for (int j = 0; j < m; j++) {
            A[i][j] = i + 1 + j;
        }
    }
    B = (int **)calloc(m, sizeof(int *));
    for (int i = 0; i < m; i++) {
        B[i] = (int *)calloc(p, sizeof(int));
        for (int j = 0; j < p; j++) {
            B[i][j] = 1;
        }
    }
    C = (int **)calloc(n, sizeof(int *));
    for (int i = 0; i < n; i++) {
        C[i] = (int *)calloc(p, sizeof(int));
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
        }
    }
}


int main(int argc, char *argv[]) {
    // Set the number of threads
    if (argc >= 2) n_threads = atoi(argv[1]);
    // Set up the matrix dimensions
    if (argc >= 3) n = atoi(argv[2]);
    if (argc >= 4) m = atoi(argv[3]);
    if (argc >= 5) p = atoi(argv[4]);

    //Initialize the matrix
    init();

    // Set the number of threads
    omp_set_num_threads(n_threads);

    // The timer begins
    double ts = omp_get_wtime();

    // Calculate C
    #pragma omp parallel for
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            for (int k = 0; k < m; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }

    // 3 columns in the first 3 rows of output matrix C
    printf("Matrix C: \n");
    for(int i = 0; i < 3; i++){
        for(int j =0; j < 3; j++){
            printf("%d ",C[i][j]);
        }
        printf("\n");
    }

    //The timer ends
    double te = omp_get_wtime();
    printf("Time: %f s\n", te - ts);

    // Free up matrix memory
    for (int i = 0; i < n; i++) free(A[i]);
    free(A);
    for (int i = 0; i < m; i++) free(B[i]);
    free(B);
    for (int i = 0; i < n; i++) free(C[i]);
    free(C);

    return 0;
}

并行效率超过1的可能原因 #

并行效率=加速比/线程数，理论上不应超过1，出现超过1的情况通常由以下因素导致：

1. 测试基准不统一 #

如果单线程版本的编译未使用-fopenmp选项，而多线程版本使用了，会导致两者的编译优化级别不一致。GCC在启用OpenMP时可能默认开启某些优化，而单线程无-fopenmp时优化程度更低，最终单线程运行时间偏长，计算出的加速比偏高。

2. 计时误差 #

单次运行的计时结果容易受系统负载（如后台进程、虚拟机调度）影响。若单线程测试时系统负载较高，多线程测试时系统空闲，会导致单线程时间被高估，加速比计算失真。

3. 缓存与硬件特性 #

你的Intel i5是4核8线程处理器，超线程技术可能在特定内存访问模式下带来额外性能提升。此外，原代码的循环顺序（i->j->k）对矩阵B的访问是列优先（C语言内存是行优先存储），缓存命中率极低；多线程拆分任务后，可能因线程间的缓存行为巧合，反而提升了缓存利用率，导致实际性能超过单线程的线性扩展预期。

4. 编译器优化差异 #

即使使用相同编译选项，OpenMP的并行结构可能触发编译器的某些优化（如循环展开、向量化），而单线程版本未触发这些优化，导致并行版本的单线程实际性能优于基准单线程。

解决方案 #

1. 统一测试基准 #

所有线程数的测试都使用相同的编译命令，包括单线程版本：

# 单线程测试也用-fopenmp编译并开启最高优化
gcc -fopenmp -O3 -o mul MatrixMul.c
./mul 1  # 单线程运行

添加-O3开启最高级别优化，确保所有测试的代码优化程度一致。

2. 多次运行取平均 #

每次线程数的测试重复运行5-10次，取平均运行时间作为基准，减少系统负载带来的计时误差：

# 示例：单线程运行5次取平均
for i in {1..5}; do ./mul 1; done | grep "Time:" | awk '{sum+=$2} END {print "Average Time: " sum/5 " s"}'

3. 优化内存布局与循环顺序 #

原代码使用int**的指针数组，内存不连续，缓存效率低；同时循环顺序导致矩阵B的缓存命中率极低。优化如下：

内存布局优化：使用连续的一维数组模拟二维矩阵

// 初始化函数修改为连续内存分配
void init() {
    // 连续分配二维数组的内存
    A = (int **)malloc(n * sizeof(int *));
    A[0] = (int *)malloc(n * m * sizeof(int));
    for (int i = 1; i < n; i++) {
        A[i] = A[0] + i * m;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            A[i][j] = i + 1 + j;
        }
    }

    B = (int **)malloc(m * sizeof(int *));
    B[0] = (int *)malloc(m * p * sizeof(int));
    for (int i = 1; i < m; i++) {
        B[i] = B[0] + i * p;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            B[i][j] = 1;
        }
    }

    C = (int **)malloc(n * sizeof(int *));
    C[0] = (int *)malloc(n * p * sizeof(int));
    for (int i = 1; i < n; i++) {
        C[i] = C[0] + i * p;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
        }
    }
}

// 释放内存时只需释放首指针和数组指针
void free_matrices() {
    free(A[0]);
    free(A);
    free(B[0]);
    free(B);
    free(C[0]);
    free(C);
}

循环顺序优化：改为i->k->j，让矩阵B的访问变为行优先

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    for (int k = 0; k < m; k++) {
        int a_val = A[i][k];
        for (int j = 0; j < p; j++) {
            C[i][j] += a_val * B[k][j];
        }
    }
}

此调整能大幅提升矩阵B的缓存命中率，减少内存访问开销，同时提取A[i][k]到内层循环外，减少重复读取。

4. 控制线程数在硬件核心范围内 #

你的物理CPU是4核，超线程提供8个逻辑线程，线程数超过8后，会导致线程频繁切换，性能下降。建议测试线程数时以1、2、4、8为主，32线程属于过度超线程，无实际优化意义。

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