优化 C 中矩阵运算的嵌套循环

Question

我正在致力于用 C 实现 Stassen 的矩阵乘法算法，并且遇到了一些嵌套循环的性能瓶颈。该算法是一个更大项目的一部分，我正在该项目中对大小为 N*N 的矩阵实现快速矩阵乘法，其中 N 是 2 的幂。

该代码涉及将每个矩阵划分为块（第一个矩阵为 a11、a12、a21、a22；第二个矩阵为 b11、b12、b21、b22；结果矩阵为 c11、c12、c21、c22）。我特别关心以下循环的效率：

// Loop 1
for (register int i = 0; i < half; i++) {
    for (register int j = 0; j < half; j++) {
        register int index = i * half + j;
        a11[index] = m1[i * n + j];
        // ... similar operations for a12, a21, a22, b11, b12, b21, b22
    }
}

// Loop 2
for (register int i = 0; i < half; i++) {
    for (register int j = 0; j < half; j++) {
        register int index = i * half + j;
        c11[index] = p1[index] + p4[index] - p5[index] + p7[index];
        // ... similar operations for c12, c21, c22
    }
}

// Loop 3
for (register int i = 0; i < half; i++) {
    for (register int j = 0; j < half; j++) {
        register int index = i * half + j;
        result[i * n + j] = c11[index];
        // ... similar operations for the rest of the result matrix
    }
}

其他背景：

我正在使用的矩阵是 N*N，其中 N 是 2 的幂。 系统规格如下： 架构：x86_64 CPU：英特尔(R) 至强(R) 金牌 5420+ CPU 系列：6 缓存：L1d (192 KiB)、L1i (128 KiB)、L2 (8 MiB)、L3 (210 MiB) 我尝试过的： 我尝试通过将它们分解成更小的部分来优化这些循环，而不是一起运行它们。然而，这种修改并没有带来我预期的性能提升。

问题： 如何在 C 语言的 Stassen 算法的上下文中优化这些嵌套循环以获得更好的性能？考虑到矩阵大小和提供的系统规格，是否有可以应用于此处的特定技术或优化？

（编辑：n 将是 512/1024/2048/4096）

Answer 1

在担心循环之类的事情之前，算法需要引起注意。

您需要的是 a) 一个截止大小，低于该大小您可以执行“正常”O(n³) 矩阵乘法，以及 b) 高效的正常矩阵乘法代码，最好利用处理器上的 SIMD。

截止值需要通过实验确定，因为它会随机器和编译器的不同而变化。典型的截止值是 n × n 矩阵，其中 n 等于几百到几千。

请参阅：使用递归提高 ATLAS 的性能有关截止测试的示例。