为什么在2048x2048和2047x2047阵列乘法中会有巨大的性能损失？

正如上文所述，我正在制定一些矩阵乘法基准 为什么 MATLAB 的矩阵乘法这么快？

现在我还有另一个问题，当两个2048x2048矩阵相乘时，C # 和其他矩阵之间有很大的区别。当我尝试只乘2047x2047矩阵时，它似乎是正常的。还增加了一些其他的作为比较。

10秒。

10秒。

90秒。

300秒。

2049x2049-91秒

2500x2500-166秒

这是3.5分钟的差距，为2k 乘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;
}
}
7619 次浏览
小开

这可能与 CPU 缓存的大小有关。如果矩阵矩阵的2行不匹配，那么您将浪费时间从 RAM 交换元素。额外的4095个元素可能刚好足以防止行匹配。

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

我的猜测是，不同大小的矩阵在运行时间上的差异受操作系统利用可用缓存的效率的影响(有些组合就是有问题)。当然，这对我来说只是一种粗略的简化。

小开

可能是缓存效应。矩阵维度是2的大幂次方，缓存大小也是2的幂次方，您最终只能使用 L1缓存的一小部分，从而大大降低了速度。天真的矩阵乘法通常受到需要将数据提取到缓存中的限制。使用平铺(或缓存遗忘算法)的优化算法侧重于更好地利用 L1缓存。

如果你计算其他对(2 ^ n-1,2 ^ n)的时间，我希望你会看到类似的效果。

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

小开

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

无论问题出在哪里，你都不应该自己用 C # 编写矩阵乘法，而应该使用经过优化的 BLAS 版本。在任何现代机器上，这个矩阵的大小应该在一秒之内乘以。

小开

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

小开

假设时间在更大的尺寸下降，那么是否更有可能是缓存冲突，特别是对于有问题的矩阵大小，2的幂是否更有可能？我不是缓存问题的专家，但在缓存相关的性能问题 给你的优秀信息。

小开

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

我测试了1024x1024矩阵，它的速度大约是这个的两倍。对于2048x2048矩阵，它的速度要快十倍。

小开

我怀疑这是“ 连续性洪水”的结果。这是因为您正在尝试循环遍历比缓存大小稍大的对象列表，因此对列表(数组)的每个请求都必须从内存执行，而且不会得到一次缓存命中。

在您的例子中，您要循环访问数组2048索引2048次，但是您只有2047的空间(可能是由于数组结构的一些开销) ，所以每次访问数组 pos 时，它都需要从 ram 获得这个数组 pos。然后将其存储在缓存中，但在再次使用之前将其转储。因此，缓存基本上是无用的，导致执行时间长得多。

小开
最佳答案

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

Matice1上的缓存丢失不是问题，因为它们是按顺序访问的。 然而，对于 matice2，如果一个完整的列适合 L2(即当您访问 matice2[0,0] ，matice2[1,0] ，matice2[2,0] ... 等，没有什么被驱逐) ，比缓存丢失 matice2也没有问题。

现在深入了解缓存的工作原理，如果变量的字节地址是 X，那么它的缓存行应该是(X > > 6) & (L-1)。其中 L 是缓存中的缓存行总数。L 总是2的幂。 这6个字节来自于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的一小部分来存储一个列，因此实际上你不能在缓存中存储完整的列，因此你会得到糟糕的性能。

当 size 为2049时，差值为2049 * 4，而不是2的幂，因此冲突较少，列将安全地放入缓存中。

为了验证这个理论，你可以做几件事:

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

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

小开

路易斯•布兰迪(Louis Brandy)写了两篇博文，分析了这个问题:

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

小开

缓存别名

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

缓存的工作方式是使用低阶位索引和使用高阶位标记。

想象你的缓存有4个单词，你的矩阵是4 x 4。当访问一个列并且该行的长度为2的幂次方时，那么内存中的每个列元素将映射到同一个缓存元素。

二加一的幂实际上是这个问题的最优解。每个新列元素将精确地映射到下一个缓存槽，就像通过行访问一样。

在现实生活中，标记覆盖多个逐渐增加的地址，这些地址将在一行中缓存几个相邻的元素。通过偏移每个新行映射到的 bucket，遍历列不会替换前一个条目。当遍历下一列时，整个缓存将填充不同的行，适合缓存的每个行部分将被命中多个列。

因为高速缓存比 DRAM 快得多(主要是由于芯片上的)命中率就是一切。


提交答案