如何在C++中使用Openmp加速矩阵乘法？

Question

我想加速倍增打击：

这是我需要改进的代码：

void multiply(int size, int **matA, int **matB, int ** matC) {
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            int t = matC[i][j];
            for(int k=0;k<size;k++) {
                t += matA[i][k] * matB[k][j];
            }
            matC[i][j] += t;
        }
    }
}

我有两个矩阵和一个大小为 5000x5000 的结果矩阵。 巨大的矩阵可能意味着它们无法完全加载到缓存中？ for循环中是否出现过多页错误？我想知道如何加速乘法，以及如何组织数据（使用一维数组还是二维数组？）

我的答案代码是列表blow，我选择使用1d数组来模拟2d数组（每个矩阵使用

new []

一次），但我不确定使用2d数组时是否更快。 我使用临时矩阵来存储

matB

的转置矩阵，以避免 for 循环中的页面错误。 我添加 AVX2 以获得更高的性能。

使用大小为 5000x5000 的一维数组或二维数组哪个更好？ 还有其他想法或技巧吗？

int** allocate(int rows, int cols) {
    int ** mat;
    mat = new int*[rows];
    int *temp = new int[rows*cols];
    for(int i = 0; i<rows; i++) {
        mat[i] = temp + i * cols;
    }
    return mat;
}


void multiply(int size, int **matA, int **matB, int ** matC) {
int i;
int n = size*size; // total size


// column-major order
int **transMatB = allocate(size, size);
int *transArrB = transMatB[0];

//copy transposed data, maybe many page faults here.
#pragma omp parallel for
    for(i = 0; i < n; i++) {
        transMatB[i/size][i%size] = matB[i%size][i/size];
    }

#pragma omp parallel for
    for(i = 0; i < n; i ++) {
        int *row = matA[i / size];
        int *col = transMatB[i % size];
        int temp;
#ifdef __AVX2__
        temp = multiplyAndSumArrays(row, col, size);
#else
        temp = 0;
        for (int k = 0; k < size; k ++) {
            temp += row[k] * col[k];
        }
#endif
        matC[i / size][i % size] += temp;
    }
    // remove temp transposed mastrix
    delete[] transMatB[0];
    delete[] transMatB; transMatB = nullptr;
}

Answer 1

提供的矩阵乘法代码可以通过多种方式进行优化，以提高其性能，特别是对于 5000x5000 这样的大型矩阵。以下是优化及其影响的详细信息：

缓存阻塞：

矩阵乘法的简单实现，如所提供的代码所示，由于数据局部性较差而导致缓存未命中。缓存分块涉及将矩阵划分为适合 CPU 缓存的较小块，从而减少缓存未命中次数并提高性能。

数据布局：

对矩阵使用列优先顺序可以提高缓存性能，因为它减少了遍历列所需的内存访问次数。这是因为列中的连续元素存储在连续的内存位置中。

转置内矩阵：

转置内部矩阵（本例中为 matB）可以进一步提高缓存利用率，特别是对于大型矩阵。当内部矩阵转置时，它的列变成它的行，从而为内部循环带来更好的缓存局部性。

使用 AVX2 说明：

采用AVX2（高级矢量扩展2）指令可以显着加速内循环内的乘法和求和运算。 AVX2 指令可以同时对多个数据元素执行多个操作，从而增强矢量化操作的性能。

避免页面错误：

在使用转置矩阵 (matB) 之前将其复制到临时数组中可以帮助减少页面错误，尤其是对于大型矩阵。这可确保在访问整个转置矩阵之前将其加载到内存中，从而最大限度地减少计算期间的页面错误数量。

使用一维或二维数组：

一维和二维阵列都有各自的优点和缺点。一维数组的内存效率更高，但它们需要额外的索引计算来访问元素。二维数组提供对元素的直接访问，但可能具有更高的内存开销。一维和二维数组之间的选择取决于具体的使用情况和内存限制。

并行度：

利用并行处理技术（例如 OpenMP）可以通过将计算分布到多个内核或线程来进一步提高性能。这可以显着减少整体执行时间，尤其是对于大型矩阵。

通过合并这些优化，矩阵乘法代码可以实现显着的性能改进，特别是对于 5000x5000 等大型矩阵。