如果 C 是行优先顺序，为什么 ARM 内在代码采用列优先顺序？

Question

我不确定问这个问题的最佳地点在哪里，但我目前正在使用 ARM 内在函数并遵循本指南：https : //developer.arm.com/documentation/102467/0100/Matrix-multiplication-example

但是，那里编写的代码假设数组是按列优先顺序存储的。我一直认为 C 数组是按行优先存储的。他们为什么要这样假设？

编辑：例如，如果不是这样：

void matrix_multiply_c(float32_t *A, float32_t *B, float32_t *C, uint32_t n, uint32_t m, uint32_t k) {
    for (int i_idx=0; i_idx < n; i_idx++) {
        for (int j_idx=0; j_idx < m; j_idx++) {
            for (int k_idx=0; k_idx < k; k_idx++) {
                C[n*j_idx + i_idx] += A[n*k_idx + i_idx]*B[k*j_idx + k_idx];
            }
        }
    }
}

他们这样做了：

void matrix_multiply_c(float32_t *A, float32_t *B, float32_t *C, uint32_t n, uint32_t m, uint32_t k) {
    for (int i_idx=0; i_idx < n; i_idx++) {
        for (int k_idx=0; k_idx < k; k_idx++) {
            for (int j_idx=0; j_idx < m; j_idx++) {
                C[n*j_idx + i_idx] += A[n*k_idx + i_idx]*B[k*j_idx + k_idx];
            }
        }
    }
}

由于按 C[0]、C[1]、C[2]、C[3] 的顺序而不是按 C[0]、C[2]、C 的顺序访问 C 的空间局部性，代码将运行得更快[1]、C[3]（其中 C[0]、C[1]、C[2]、C[3] 在内存中是连续的）。

Answer 1

你没有使用像 那样的 C 2D 数组C[i][j]，所以这不是 C 如何存储任何东西的问题，而是如何在这段代码中手动完成 2D 索引，使用n * idx_1 + idx_2，并选择在内循环和外循环中循环。

但是，两个矩阵都未转置的 matmul 的难点在于，您需要为两个输入矩阵做出相反的选择：天真的 matmul 必须跨越其中一个输入矩阵的远处元素，因此它本质上是一团糟。这就是为什么仔细的缓存阻塞/循环平铺对于矩阵乘法很重要的一个主要部分。（O(n^3) 处理 O(n^2) 数据 - 每次将其带入 L1d 缓存和/或寄存器时，您都希望充分利用它。）

如果操作正确，循环交换可以加快速度以利用最内层循环中的空间局部性。

请参阅每个程序员应该了解的关于内存的内容中的缓存阻塞 matmul 示例。它遍历内部几个循环中所有 3 个输入中的连续内存，选择未在 3 个矩阵中的任何一个中缩放的索引作为内部. 看起来像这样：

  for (j_idx)
    for (k_idx)
      for (i_idx)
          C[n*j_idx + i_idx] += A[n*k_idx + i_idx]*B[k*j_idx + k_idx];

请注意，B[k * j_idx + k_idx]它在循环内循环中是不变的，并且您正在dst[0..n] += const * src[0..n]对连续内存（这很容易进行 SIMD 向量化）进行简单的操作，尽管您仍在为每个 FMA 执行 2 次加载 + 1 次存储，所以这不会发生最大化您的 FP 吞吐量。

与缓存访问模式分开，这也避免了将长依赖链转换为单个累加器（C 元素）。但这对于优化的实现来说并不是真正的问题：您当然可以使用多个累加器。由于舍入误差，FP 数学不是严格关联的，但多个累加器更接近成对求和，并且与连续添加行 x 列点积的每个元素相比，FP 舍入误差可能更小。按照标准简单 C 循环的顺序添加会产生不同的结果，但通常更接近确切的答案。

您建议的循环顺序 i,k,j 是最糟糕的。

您正在内部循环中跨越 3 个矩阵中的 2 个的遥远元素，包括对 C[] 的不连续访问，这与您在上一段中所说的相反。

随着j作为最内层的循环，你会访问C[0]，C[n]，C[2n]，等在第一外迭代。和 一样B[]，所以这真的很糟糕。

交换i和j循环将使您能够连续访问C[]中间循环，而不是跨步访问，并且仍然可以在最内层循环中访问一个行，另一个列。所以这将是一个严格的改进：是的，你是对的，这个天真的例子比它需要的更糟糕。

但关键问题是对内部循环中某些内容的跨步访问：这是性能灾难；这就是为什么仔细的缓存阻塞/循环平铺对于矩阵乘法很重要的一个主要部分。从未与比例因子一起使用的唯一索引是i。