matrix乘法：matrix大小差异小，时序差异大
我有一个matrix乘法代码，看起来像这样：
for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; 这里，matrix的大小由dimension表示。 现在，如果matrix的大小是2000，运行这段代码需要147秒，而如果matrix的大小是2048，则需要447秒。 所以虽然没有区别 （2048 * 2048 * 2048）/（2000 * 2000 * 2000）= 1.073，时间差为447/147 = 3。有人可以解释为什么会发生这种情况吗？ 我预计它会线性扩展，这是不会发生的。 我不是想做出最快的matrix乘法代码，只是想明白为什么会发生。
规格：AMD Opteron双核心节点（2.2GHz），2G RAM，gcc v 4.5.0
程序编译为gcc -O3 simple.c
我已经在Intel的icc编译器上运行了这个，并且看到了类似的结果。
编辑：
正如评论/答案中所build议的那样，我运行了维度= 2060的代码，这需要145秒。
inheritance人完整的程序：
#include <stdlib.h> #include <stdio.h> #include <sys/time.h> /* change dimension size as needed */ const int dimension = 2048; struct timeval tv; double timestamp() { double t; gettimeofday(&tv, NULL); t = tv.tv_sec + (tv.tv_usec/1000000.0); return t; } int main(int argc, char *argv[]) { int i, j, k; double *A, *B, *C, start, end; A = (double*)malloc(dimension*dimension*sizeof(double)); B = (double*)malloc(dimension*dimension*sizeof(double)); C = (double*)malloc(dimension*dimension*sizeof(double)); srand(292); for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) { A[dimension*i+j] = (rand()/(RAND_MAX + 1.0)); B[dimension*i+j] = (rand()/(RAND_MAX + 1.0)); C[dimension*i+j] = 0.0; } start = timestamp(); for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; end = timestamp(); printf("\nsecs:%f\n", end-start); free(A); free(B); free(C); return 0; }
这是我疯狂的猜测： caching
这可能是因为你可以将两行2000个double精度值放入caching中。 这比32kb一级caching略小。 （同时留下其他必要的东西）
但是，当你碰到2048年，它使用整个caching（和你溢出一些，因为你需要空间的其他东西）
假设高速caching策略是LRU，只需要很less的一点点溢出就会导致整个行重复刷新并重新加载到L1高速caching中。
另一种可能性是由于二次幂导致的caching关联性。 虽然我认为处理器是2路L1联想，所以我不认为在这种情况下很重要。 （但是我会把这个想法抛出去）
可能的解释2：由于二级高速caching上的超级alignment导致冲突caching未命中。
您的B数组正在该列上迭代。 所以访问是跨越的。 您的总数据大小为2k x 2k ，每个matrix约为32 MB。 这比你的二级caching大得多。
当数据没有完全alignment时，您将在B上拥有可观的空间局部性。尽pipe您正在跳转行，并且每个caching行只使用一个元素，但caching行保留在L2caching中，以便在中间循环的下一次迭代中重用。
但是，当数据完全alignment（2048）时，这些跳都将落在相同的“cachingpath”上，并且将远远超过您的L2caching关联性。 因此， B被访问的caching行将不会留在caching中以用于下一次迭代。 相反，他们将需要从公羊拉到一路。
你肯定会得到我所说的caching共振 。 这与别名类似，但不完全相同。 让我解释。
高速caching是硬件数据结构，用于提取地址的一部分，并将其用作表中的索引，与软件中的数组不同。 （实际上，我们把它们称为硬件arrays。）cachingarrays包含数据caching行和标签 – 有时候数组中的每个索引都有一个这样的条目（直接映射），有时候还有几个这样的（N路集合关联性）。 地址的第二部分被提取并与存储在数组中的标签进行比较。 索引和标签一起唯一标识一个caching行内存地址。 最后，其余的地址位标识了高速caching行中哪些字节被寻址，以及访问的大小。
索引和标签通常是简单的位字段。 所以一个内存地址看起来像
...Tag... | ...Index... | Offset_within_Cache_Line
（有时索引和标签是散列值，例如一些其他位的XOR位于索引的中间位中，更为less见的是，有时候索引和更less的标签都是以cache行地址为模素数这些更复杂的指数计算是试图解决共振问题，我在这里解释，所有这些都受到某种forms的共振，但是最简单的位域提取scheme在共同的访问模式上受到共鸣，就像你发现的那样）。
所以，典型的价值观……有许多不同型号的“Opteron Dual Core”，我在这里没有看到任何指定你拥有的东西。 随机select一个，这是我在AMD网站上看到的最新手册， 针对AMD系列15h型号的Bios和Kernel Developer's Guide（BKDG） ，2012年3月12日00h-0Fh 。
（家庭15小时=推土机家族，最近的高端处理器 – BKDG提到了双核心，虽然我不知道产品编号是否正是你所描述的，但无论如何，共鸣的想法适用于所有的处理器，只是caching大小和关联性等参数可能会有所不同。）
从p.33：
AMD系列15h处理器包含一个具有两个128位端口的16KB 4路预测L1数据caching。 这是一个直写caching，每个周期最多支持两个128字节的加载。 它分为16个银行，每个银行16个字节。 […]在一个周期内只能从L1caching的给定库执行一个加载。
总结一下：
-
64字节高速caching行=>高速caching行中的6个偏移位
-
16KB / 4路=>共振是4KB。
即地址位0-5是高速caching行偏移量。
-
caching中的16KB / 64Bcaching行=> 2 ^ 14/2 ^ 6 = 2 ^ 8 = 256caching行。
（漏洞修复：我最初错误地计算为128.，我已经修复了所有依赖项。） -
4路联合=> 256/4 = 64个索引在cachingarrays中。 我（英特尔）称这些“套”。
即你可以认为caching是32个入口或者数组的集合，每个入口包含4个caching行和他们的标签。 （这比这更复杂，但没关系）。
（顺便说一下，术语“set”和“way”有不同的定义 。）
-
在最简单的scheme中有6个索引位，位6-11。
这意味着索引位（bit 6-11）中具有完全相同值的任何caching行将映射到同一组caching。
现在看看你的程序。
C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];
循环k是最内层的循环。 基本types是双倍的，8个字节。 如果维数= 2048，即2K，那么循环访问的B[dimension*k+j]连续元素将相距2048 * 8 = 16K字节。 它们将全部映射到L1caching的相同集合 – 它们将在caching中具有相同的索引。 这意味着，高速caching中没有256个高速caching行，而只有4个高速caching的“4路关联”。
也就是说，你可能会在这个循环中每4次迭代就会发生一次caching缺失。 不好。
（实际上情况稍微复杂一些，但是以上是一个很好的理解，上面提到的B的地址是一个虚拟地址，所以物理地址可能会略有不同，另外Bulldozer有一个预测caching的方法，可能使用虚拟地址位，这样就不需要等待虚拟地址到物理地址的转换，但是无论如何：你的代码有16K的“共振”，L1数据caching有16K的共振。 。）]
如果只是稍微改变维度，例如2048 + 1，那么arraysB的地址将分布在所有的caching集合中。 而且你将获得明显更less的caching未命中。
对arrays进行填充是一个相当常见的优化，例如将2048改为2049，以避免这种共振。 但“caching阻塞是一个更重要的优化。papers/lam-asplos91.pdf
除了caching线共振之外，还有其他一些事情正在发生。 例如，L1caching有16个存储区，每个存储区16个字节。 在维数= 2048的情况下，内循环中的连续B访问将总是到达同一个库。 所以他们不能并行 – 如果A访问发生在同一家银行，你会输。
我不认为，看这个，这和caching共振一样大。
而且，是的，可能会出现走样。 例如，STLF（Store to Load Forwardingcaching）可能只是比较一个小的比特字段，并得到错误的匹配。
（实际上，如果你想一想，caching中的共振就像是混叠，与位域的使用有关，共振是由多个caching行映射到同一个集合引起的，而不是泛泛而谈。位。）
总的来说，我的调整build议是：
-
尝试高速caching阻止，无需进一步分析 我这样说是因为caching阻塞很容易，而这很可能是你需要做的。
-
之后，使用VTune或OProf。 或者Cachegrind。 要么 …
-
更好的是，使用一个良好的调整库例程做matrix乘法。
有几种可能的解释。 一个可能的解释是Mysticial提出的：耗尽有限的资源（caching或TLB）。 另一个可能的可能性是一个错误的混叠失速，当连续的存储器访问被一些二的幂数（通常是4KB）分隔时，可能会发生这种情况。
您可以开始通过绘制一系列值的时间/维度^ 3来缩小工作内容。 如果你已经吹起了caching或用尽TLB的范围，你会看到一个或多或less的平坦部分，然后在2000年和2048年之间急剧上升，其次是平坦的部分。 如果您看到与锯齿有关的摊位，您将会看到一个或多或less的平坦graphics，并在2048向上窄幅攀升。
当然，这具有诊断能力，但并不是定论。 如果你想确切地知道什么是放缓的根源，你会想了解性能计数器 ，这可以明确地回答这类问题。
我知道这太老了，但我会咬一口。 这是（如前所述）caching问题是什么导致了两个大国的放缓。 但是还有另一个问题：太慢了。 如果你看看你的计算循环。
for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];
最内层的循环将k每次迭代改变1次，这意味着你访问距离你使用A的最后一个元素只有两倍， 但是整个“维度”离开B的最后一个元素加倍。这没有任何优势B的元素的caching
如果您将其更改为：
for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k];
你得到完全相同的结果（模加双加关联性错误），但它是一个更多caching友好（ 本地 ）。 我试了一下，它给了实质性的改进。 这可以概括为
不要按照定义来乘以matrix，而应该按行
加速的例子（我改变了你的代码把维度作为参数）
$ diff ac bc 42c42 < C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; --- > C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k]; $ make a cc ac -oa $ make b cc bc -ob $ ./a 1024 secs:88.732918 $ ./b 1024 secs:12.116630
作为一个奖励（这是什么使这个问题相关）是这个循环不受到以前的问题。
如果你已经知道这一切，那么我表示歉意！
几个答案提到了二级caching问题。
您实际上可以使用caching模拟进行 validation 。 Valgrind的cachegrind工具可以做到这一点。
valgrind --tool=cachegrind --cache-sim=yes your_executable
设置命令行参数，使它们与CPU的L2参数匹配。
使用不同的matrix大小进行testing，您可能会发现L2缺失率突然增加。
