矩阵乘法：矩阵大小差异小，时序差异大

Question

我有一个矩阵乘法代码，如下所示：

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];

在此，矩阵的大小由表示dimension。现在，如果矩阵的大小为2000，则运行此代码需要147秒，而如果矩阵的大小为2048，则需要447秒。所以虽然没有区别。的乘积为（2048 * 2048 * 2048）/（2000 * 2000 * 2000）= 1.073，时间差为447/147
=3。有人可以解释为什么会这样吗？我希望它可以线性扩展，但不会发生。我不是在尝试制作最快的矩阵乘法代码，而只是在试图理解为什么会这样。

规格：AMD Opteron双核心节点（2.2GHz），2G RAM，gcc v 4.5.0

程序编译为 gcc -O3 simple.c

我也在英特尔的icc编译器上运行了此命令，并看到了类似的结果。

编辑：

正如评论/答案中所建议的那样，我运行的维度为2060的代码需要145秒。

这是完整的程序：

#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;
}

Answer 1

这是我的疯狂猜测： 缓存

可能是您可以将2行2000 doubles放入缓存中。略小于32kb L1缓存。（同时留出其他必要的空间）

但是，当您将其增加到2048时，它将使用 整个 缓存（并且由于需要其他空间而浪费了一些缓存）

假设高速缓存策略是LRU，则将高速缓存仅溢出一小部分将导致整个行被重复刷新并重新加载到L1高速缓存中。

另一种可能是由于2的幂导致的缓存关联性。尽管我认为处理器是2路L1关联的，所以在这种情况下我认为这并不重要。（但我还是会把这个想法丢掉）

可能的解释2： 由于L2缓存上的超对齐，冲突缓存未命中。

您的B数组正在列上进行迭代。这样访问就大步向前。2k x 2k每个矩阵的总数据大小约为32 MB。这比您的L2缓存大得多。

当数据不完全对齐时，您将在B上具有适当的空间局部性。尽管您要跳行并且每个高速缓存行仅使用一个元素，但是高速缓存行仍保留在L2高速缓存中，以供中间循环的下一次迭代重用。

但是，当数据完全对齐（2048）时，这些跃点将全部落在相同的“缓存方式”上，并且将远远超过您的L2缓存关联性。因此，所访问的缓存行B不会在下一次迭代中保留在缓存中。
相反，它们将需要从ram一直拉出。