为什么2048x2048与2047x2047阵列乘法相比会有巨大的性能损失？

Question

我正在进行一些矩阵乘法基准测试,如前面提到的 为什么MATLAB在矩阵乘法中如此之快？

现在我有另一个问题,当乘以两个2048x2048矩阵时,C#和其他矩阵之间存在很大差异.当我尝试只乘2047x2047矩阵时,看起来很正常.还添加了一些其他的比较.

1024x1024 - 10秒.

1027x1027 - 10秒.

2047x2047 - 90秒.

2048x2048 - 300秒.

2049x2049 - 91秒.(更新)

2500x2500 - 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;
   }
 }

Answer 1

这可能与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]分配你的数组matice2数组,并使用razmor = 1024,1025或任何大小运行,你应该会看到与之前相比非常糟糕的性能.这是因为您强制对齐所有列以相互冲突.

然后尝试matice2 [razmor,4097]并以任何大小运行它,你应该看到更好的性能.

Answer 2

可能是缓存效果.对于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高速缓存逐出,并从较慢的高速缓存或主存储器中获取数据.

Answer 3

这可能与您的cpu缓存大小有关.如果矩阵矩阵的2行不适合,那么您将浪费时间交换RAM中的元素.额外的4095个元素可能足以防止行装配.

在您的情况下,2047个2d矩阵的2行落在16KB的内存中(假设32位类型).例如,如果您有一个64KB的L1缓存(最接近总线上的cpu),那么您可以一次将至少4行(2047*32)放入缓存中.对于较长的行,如果需要任何填充将行对超过16KB,则事情开始变得混乱.此外,每次你'错过'缓存时,从另一个缓存或主内存交换数据会延迟事情.

我的猜测是,您使用不同大小的矩阵看到的运行时间差异会受到操作系统使用可用缓存的效率的影响(某些组合只是有问题).当然,这对我来说完全是一种简化.

Answer 4

Louis Brandy撰写了两篇博文,分析了这个问题:

更多缓存疯狂和计算性能 - 一个初学者案例研究,其中包含一些有趣的统计信息,并尝试更详细地解释行为,它确实归结为缓存大小限制.

Answer 5

鉴于时间在较大的大小下降不会更有可能是缓存冲突,特别是对于有问题的矩阵大小的2的幂？我不是缓存问题的专家,但这里有关于缓存相关性能问题的优秀信息.