为什么 2048x2048 与 2047x2047 数组乘法相比性能受到巨大影响

本文关键字：性能 影响 巨大 2048x2048 2047x2047 数组 为什么 | 更新日期: 2023-09-27 17:56:51

我正在做一些矩阵乘法基准测试，如前所述为什么 MATLAB 在矩阵乘法方面如此之快？

现在我遇到了另一个问题，当将两个 2048x2048 矩阵相乘时，C# 和其他矩阵之间存在很大差异。当我尝试仅乘以 2047x2047 矩阵时，这似乎很正常。还添加了其他一些进行比较。

1024x1024 - 10 秒。

1027x1027 - 10 秒。

2047x2047 - 90 秒。

2048x2048 - 300 秒。

2049x2049 - 91 秒。（更新）

2500x2500 - 166 秒

对于 2k x 2k 的情况，这是三分半钟的差异。

使用 2dim 阵列

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];
//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }

为什么 2048x2048 与 2047x2047 数组乘法相比性能受到巨大影响

这可能与 L2 缓存中的冲突有关。

matice1 上的缓存未命中不是问题，因为它们是按顺序访问的。但是对于 matice2，如果完整的列适合 L2（即当您访问 matice2[0， 0]、matice2[1， 0]、matice2[2， 0] ...等等，没有任何东西被逐出）比 matice2 的缓存未命中也没有问题。

现在更深入地了解缓存的工作原理，如果变量的字节地址是X，那么它的缓存行将是（X>> 6）和（L - 1）。其中 L 是缓存中的缓存行总数。L 始终是 2 的幂。这六个来自 2^6 == 64 字节是缓存行的标准大小。

这是什么意思呢？好吧，这意味着如果我有地址 X 和地址 Y 和（X>> 6） - （Y>> 6） 可被 L 整除（即 2 的一些大幂），它们将存储在同一个缓存行中。

现在回到你的问题，2048年和2049年有什么区别，

当 2048 年是你的尺码时：

如果取 &matice2[x， k] 和 &matice2[y， k] 差值 （&matice2[x， k]>> 6）

- （&matice2[y，k]>> 6） 将被 2048 * 4（浮点数大小）整除。所以2的大幂。

因此，根据L2

的大小，您将有很多缓存行冲突，并且仅利用L2的一小部分来存储列，因此您实际上无法在缓存中存储整个列，因此性能会很差。

当大小为 2049

时，差值为 2049 * 4，这不是 2 的幂，因此您的冲突会更少，您的列将安全地放入您的缓存中。

现在要测试这个理论，你可以做几件事：

像这样分配你的数组 matice2 数组 [razmor， 4096]，并以 razmor = 1024、1025 或任何大小运行，与以前相比，你应该会看到非常糟糕的性能。这是因为您强制对齐所有列以相互冲突。

然后尝试 matice2 [razmor， 4097] 并以任何大小运行它，您应该会看到更好的性能。

可能是缓存效果。 如果矩阵维度是 2 的大幂，而缓存大小也是 2 的幂，您最终只能使用一级缓存的一小部分，从而大大减慢速度。 朴素矩阵乘法通常受到将数据提取到缓存中的需求的约束。 使用平铺（或忽略缓存的算法）的优化算法侧重于更好地利用 L1 缓存。

如果你对其他对（2^n-1,2^n）进行计时，我希望你会看到类似的效果。

为了更全面地解释，在访问 matice2[m，k] 的内部循环中，matice2[m，k] 和 matice2[m+1，k] 很可能彼此偏移 2048*sizeof（float），从而映射到 L1 缓存中的同一索引。 使用 N 路关联缓存，您通常有 1-8 个缓存位置用于所有这些缓存位置。 因此，几乎所有这些访问都将触发 L1 缓存逐出，并从较慢的缓存或主内存中获取数据。

这可能与 CPU 缓存的大小有关。如果矩阵矩阵的 2 行不适合，那么您将失去从 RAM 交换元素的时间。额外的 4095 元素可能足以防止行适合。

在您的情况下，2047 个 2d 矩阵的 2 行落在 16KB 内存范围内（假设 32 位类型）。例如，如果您有 64KB 的 L1 缓存（最靠近总线上的 CPU），那么您一次至少可以将 4 行（2047 * 32）放入缓存中。对于较长的行，如果需要任何填充将行对推到 16KB 以上，那么事情就会开始变得混乱。此外，每次您"错过"缓存时，从另一个缓存或主内存交换数据都会延迟事情。

我的猜测是，您看到不同大小的矩阵的运行时间差异受操作系统利用可用缓存的效率的影响（某些组合只是有问题）。当然，这都是我的粗略简化。

Louis Brandy写了两篇博客文章来分析这个问题：

更多的缓存疯狂和计算性能 - 初学者案例研究，有一些有趣的统计数据，并试图更详细地解释行为，它确实归结为缓存大小限制。

鉴于时间在更大尺寸上下降，它是否更有可能是缓存冲突，尤其是对于有问题的矩阵大小，幂为 2？我不是缓存问题的专家，但这里有关于缓存相关性能问题的出色信息。

当您垂直访问 matice2 数组时，它将被更多地交换进出缓存。如果对角线镜像数组，以便可以使用[k,m]而不是[m,k]访问它，则代码的运行速度会快得多。

我针对 1024x1024 矩阵对此进行了测试，速度大约是原来的两倍。对于 2048x2048 矩阵，它的速度大约快十倍。

缓存别名

或者缓存抖动，如果我能创造一个术语。

缓存的工作原理是使用低阶位编制索引，并使用高阶位进行标记。

成像您的缓存有 4 个单词，您的矩阵是 4 x 4。当访问列并且该行的长度为 2 的任意幂时，内存中的每个列元素将映射到相同的缓存元素。

二加一的幂实际上是这个问题的最佳选择。每个新列元素将映射到下一个缓存槽，就像按行访问一样。

在现实生活中，标签覆盖多个按顺序递增的地址，这些地址将连续缓存多个相邻元素。通过偏移每个新行映射到的存储桶，遍历列不会替换上一个条目。遍历下一列时，整个缓存将填充不同的行，并且适合缓存的每个行部分将命中几列。

由于缓存比DRAM快得多（主要是由于片上），命中率就是一切。

您似乎已达到缓存大小限制，或者可能在计时中存在一些可重复性问题。

无论问题是什么，您都不应该自己在 C# 中编写矩阵乘法，而是使用 BLAS 的优化版本。 在任何现代机器上，矩阵的大小都应该在一秒内乘以。

有效利用缓存层次结构非常重要。 您需要确保多维数组具有良好的排列数据，这可以通过平铺来实现。 为此，您需要将 2D 数组存储为 1D 数组以及索引机制。 传统方法的问题在于，虽然同一行中的两个相邻数组元素在内存中彼此相邻，但同一列中的两个相邻元素将在内存中由 W 个元素分隔，其中 W 是列数。 平铺可以产生多达十倍的性能差异。

我怀疑这是所谓的"顺序洪水"的结果。这是您尝试遍历略大于缓存大小的对象列表，因此对列表（数组）的每个请求都必须从 ram 完成，并且您不会得到单个缓存命中。

在您的情况下，您循环遍历数组 2048 索引

2048 次，但您只有 2047 的空间（可能是由于数组结构的一些开销），因此每次访问数组 pos 时，它都需要从 ram 获取此数组 pos。然后它存储在缓存中，但在再次使用它之前，它会被转储。因此，缓存基本上是无用的，导致执行时间更长。

相关文章：