0

我不确定问这个问题的最佳地点在哪里，但我目前正在使用 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 而不是按 C[0]、C[2]、C 的顺序访问 C 的空间局部性，代码将运行得更快[1]、C[3]（其中 C[0]、C[1]、C[2]、C[3] 在内存中是连续的）。

4

2 回答 2

6

您没有使用像 一样C[i][j]的 C 2D 数组，因此这与 C 如何存储任何内容无关，而是如何在此代码中手动n * idx_1 + idx_2完成 2D 索引，使用，您可以选择在内部循环和外部循环中循环。

但是，两个矩阵均未转置的 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[]，所以这真的很糟糕。

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

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

于 2021-05-30T19:02:03.913 回答
1

C 本质上不是行优先或列优先。

编写a[i][j]时，由您决定i是行索引还是列索引。

虽然首先编写行索引（使数组以行为主）是一种常见的约定，但没有什么能阻止你做相反的事情。

另外，请记住，这A × B = C相当于Bt × At = Ct（t意味着转置矩阵），并且读取行优先矩阵，就好像它是列优先（反之亦然）转置它，这意味着如果你想保持你的矩阵行优先，你只能颠倒操作数的顺序。

于 2021-05-30T17:02:35.660 回答