c - 使用SIMD和openMP加速矩阵乘法

Question

我正在尝试加快矩阵乘法的速度，因此它的性能要比朴素的实现好得多。我的目标是将其速度提高到150倍。到目前为止，以下是我在实现过程中尝试过的事情:

在连续块中分配矩阵元素，以提高缓存效率。

转换要按列访问的第二个矩阵，以将列排列到连续的存储块中。

使用SIMD指令。

使用openMP并行化循环。

在第1步和第2步之后，我的mat mul变得比朴素的实现快4倍。使用SIMD之后，速度提高了17倍。使用openMP之后，速度提高了56倍。我原本希望通过openMP获得更大的速度提升，至少可以提高6到8倍。我可能会缺少什么？
我的代码大致如下所示:

#pragma omp parallel for collapse(2)
    for (int i = 0; i < result.rows; i += 1) {
        for (int j = 0; j < result.cols; j += 1) {
          double product = 0.0;
          for (int k = 0; i < matrix1.cols / 4 * 4; i += 4) {
             //Use _mm256_mul_pd and _mm256_add_pd to process 4 elements at a time. 
          }
          //Do _mm256_store_pd and set the product. 
          result.mat[r][c] = product;
          for (int k = matrix1.cols / 4 * 4; i < matrix1.cols; i += 1) {
             //Tail case 
          }
        }
     }

我想将速度提高至少100倍。即比我当前的基准速度快2倍。我还应该如何优化我的代码？

Answer 1

并行性只能给您带来很多好处。此外，顺序代码的优化程度越高，您从并行性中获得的感知 yield 就越小。不过，您可以改进的方法-将矩阵乘法划分为较小的块，这是我过去做过的事情，对改进有很大帮助。因此，矩阵乘法被 segmentation 为较小矩阵(平铺)的乘法。
因此，通过将矩阵乘法划分为较小的块，在其中执行较小的子矩阵的矩阵乘法，可以改善temporal locality和spatial locality缓存的使用。您需要根据所使用架构的缓存级别(例如L1，L2和L3)的大小对矩阵进行划分。您可以在these slides中详细了解有关缓存阻止和矩阵乘法的信息。 What Every Programmer Should Know About Memory?在附录中也有一个向量化的缓存阻止的matmul。
例如，如果您有一个Cache L3(在内核之间共享)，则可以将矩阵B的多列加载到L3缓存中，然后重复使用这些值来执行较小的图块的矩阵乘法，这些图块将适合缓存L1和L2 。您可以走得更远，并且在这些图块内部进一步划分图块，以便您可以利用寄存器。
在优化矩阵乘法的内存使用量之后，您可以尝试从多线程中获得额外的加速。如果您有一个多核集群，则可以尝试使用MPI + OpenMP并行化，当然在这一点上，您将遇到另一个瓶颈，即进程之间的通信。
这一切都取决于代码在其中运行的体系结构，如果您具有NUMA体系结构，那么您还必须考虑本地和非本地内存等因素。您还可以探索GPU路线:Matrix-Matrix Multiplication on the GPU with Nvidia CUDA。
看一看BLAS，深入了解高效代码。