为什么2048×2048与2047x2047arrays乘法相比，会有巨大的性能下降？
我正在做一些matrix乘法基准testing，正如之前为什么MATLAB在matrix乘法中如此之快？
现在我又遇到了另外一个问题，当乘以两个2048x2048matrix时，C＃和其他的有很大的区别。 当我尝试只乘以2047x2047matrix时，这似乎是正常的。 还增加了一些其他的比较。
1024×1024 – 10秒。
1027×1027 – 10秒。
2047×2047 – 90秒。
2048×2048 – 300秒。
2049×2049 – 91秒。 （更新）
2500×2500 – 166秒
对于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; } } 这可能与L2caching中的冲突有关。
matice1上的caching未命中不是问题，因为它们是按顺序访问的。 但是对于matice2来说，如果一个完整的列适合L2（即，当你访问matice2 [0，0]，matice2 [1,0]，matice2 [2,0] …等等，没有东西被驱逐）比没有问题caching与matice2错过。
现在要深入了解caching的工作原理，如果variables的字节地址是X，那么它的caching行将是（X >> 6）＆（L – 1）。 其中L是caching中caching行的总数。 L始终是2的幂。六个来自事实，2 ^ 6 == 64字节是标准大小的caching行。
现在这是什么意思？ 那么这意味着如果我有地址X和地址Y且（X >> 6） – （Y >> 6）可以被L整除（即2的大幂），它们将被存储在相同的caching行中。
现在回到你的问题2048年和2049年有什么区别，
当2048是你的尺寸时：
（＆matice2 [x，k] >> 6） – （＆matice2 [y，k] >> 6）将会被2048 * 4（size的浮动）。 那么2的一个大的力量。
因此，根据你的L2的大小，你将有很多caching行冲突，并且只能利用你的L2的一小部分来存储一个列，因此你不会实际上能够在caching中存储完整的列，因此你将得到不好的性能。
当大小是2049，那么差异是2049 * 4这不是2的幂，因此你将有较less的冲突，你的列将安全地适合你的caching。
现在来testing这个理论，你可以做几件事情：
像这个matice2 [razmor，4096]分配您的数组matice2数组，并与razmor = 1024,1025或任何大小运行，你应该看到非常糟糕的性能相比，你以前。 这是因为你强制alignment所有列相互冲突。
然后尝试matice2 [razmor，4097]并运行任何大小，你应该看到更好的性能。
可能是caching效果。 如果matrix的维度是2的大幂，caching的大小也是2的幂次，那么最终只能使用L1caching的一小部分，从而使得速度变慢。 原始matrix乘法通常受到将数据提取到caching中的需求的限制。 使用平铺（或caching忽略algorithm）的优化algorithm专注于更好地使用L1caching。
如果你计算其他对（2 ^ n-1,2 ^ n），我希望你会看到类似的效果。
为了更完整地解释，在内部循环中，如果你访问matice2 [m，k]，matice2 [m，k]和matice2 [m + 1，k]可能会相互偏移2048 * sizeof（float）并因此映射到L1caching中的相同索引。 对于N路关联caching，您通常会拥有1-8个caching位置。 因此，几乎所有这些访问都会触发L1caching逐出，并从较慢的caching或主存储器中获取数据。
这可能与你的cpucaching大小有关。 如果matrixmatrix的2行不匹配，那么您将放宽从RAM中的元素交换时间。 多余的4095个元素可能足以防止行assembly。
在你的情况下，2047 2dmatrix的2行落入16KB的内存（假设32位types）。 例如，如果您有一个64KB的L1高速caching（最靠近总线上的cpu），那么您至less可以将4行（2047 * 32的）一次写入高速caching。 有了更长的行，如果有任何填充需要将行对推到16KB以上，那么事情开始变得混乱。 而且，每次你错过caching时，从另一个caching或主内存中交换数据都会延迟。
我的猜测是，用不同大小的matrix看到的运行时间的变化受操作系统如何有效利用可用caching（以及一些组合只是有问题）的影响。 当然这对我来说完全是一种粗略的简化。
Louis Brandy写了两篇博客文章分析了这个问题：
更多caching的疯狂和计算性能 – 初学者的案例研究与一些有趣的统计数据，并试图更详细地解释行为，它确实归结为caching大小的限制。
考虑到时间在更大的尺寸的下降不会更容易成为caching冲突，尤其是对于有问题的matrix大小的2次幂。 我不是caching问题方面的专家，但是在这里有关caching相关性能问题的绝佳信息。
当你正在垂直访问matice2数组的时候，它将会被matice2进和退出caching。 如果你对angulararrays镜像，那么你可以使用[k,m]而不是[m,k]来访问它，代码将运行得更快。
我testing了这个对于1024x1024matrix，这是两倍的速度。 对于2048x2048matrix，它快了十倍。
caching别名
或caching颠簸 ，如果我可以投一个学期。
高速caching的工作方式是使用低位索引和高位标记。
想象你的caching有4个字，而你的matrix是4×4。当一个列被访问，并且这个行的长度是2的任何幂，那么存储器中的每个列元素将映射到相同的caching元素。
这个问题实际上是一个“两加一”的function。 每个新的列元素都将映射到下一个caching槽，就像按行访问一样。
在现实生活中，一个标签覆盖了多个顺序递增的地址，这些地址将caching一行中的几个相邻元素。 通过偏移每个新行映射到的存储桶，遍历列不会replace先前的条目。 当遍历下一列时，整个caching将被填充不同的行，并且适合caching的每个行部分将会打到多个列。
由于caching比DRAM快得多（主要是由于片上），命中率就是一切。
您似乎遇到了caching大小限制，或者在您的计时中可能存在可重复性问题。
无论什么问题，你都不应该在C＃中自己写matrix乘法，而应该使用BLAS的优化版本。 在任何现代机器上，这个matrix的大小应该在一秒之内倍增。
有效利用caching层次非常重要。 你需要确保multidimensional array有一个很好的安排数据，这可以通过平铺来完成。 要做到这一点，你需要将二维数组作为一维数组与索引机制一起存储。 传统方法的问题在于，虽然在同一行中的两个相邻数组元素在内存中彼此相邻，但是在同一列中的两个相邻元素将被存储器中的W元素分隔开，其中W是列数。 平铺可以达到十倍的性能差异。
我怀疑这是“ 顺序泛滥 ”的结果。 这是什么，你是试图循环通过略大于caching大小的对象的列表，因此每一个列表（数组）的请求必须从内存中完成，你不会得到一个caching击中。
在你的情况下，你正在循环你的数组2048个索引2048次，但是你只有2047的空间（可能是由于数组结构的开销），所以每次你访问一个数组pos时，它需要得到这个数组pos从公羊。 然后将其存储在caching中，但在再次使用之前将其转储。 所以caching本质上是无用的，导致更长的执行时间。
