行列の乗算。行列の大きさの差は小さく、タイミングの差は大きい

質問

次のような行列の掛け算のコードがあります。

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

Intelのiccコンパイラでも実行し、同様の結果を得ました。

EDITです。

コメント/回答で示唆されているように、dimension=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;
}

どのように解決するのですか？

私の勝手な推測です。 キャッシュ

2000の2列を収めることができるかもしれません。 double をキャッシュに収めることができます。これは、32kb の L1 キャッシュよりもわずかに少ないものです。(他の必要なもののためのスペースを残しながら)

しかし、2048まで上げると、それは 全体 キャッシュ (そして、他のもののためのスペースが必要なので、いくらかこぼれます)

キャッシュポリシーが LRU であると仮定すると、ほんの少しキャッシュをこぼしただけで、行全体が繰り返しフラッシュされ、L1 キャッシュに再ロードされることになります。

もう 1 つの可能性は、2 のべき乗によるキャッシュの関連付けです。しかし、そのプロセッサは 2 ウェイの L1 連想なので、このケースでは関係ないと思います。(しかし、私はとにかくこのアイデアをそこに投げます)。

考えられる説明 2: L2 キャッシュのスーパーアライメントによる競合キャッシュのミス。

あなたの B 配列はカラムに対して反復処理されています。そのため、アクセスはストライドされます。データの総サイズは 2k x 2k で、行列あたり約 32 MB です。これは L2 キャッシュよりもはるかに大きなサイズです。

行をホッピングし、キャッシュラインごとに 1 つの要素しか使用していませんが、キャッシュラインは L2 キャッシュに残り、次の中間ループの繰り返しで再利用されます。

しかし、データが完全に整列 (2048) されている場合、これらのホップはすべて同じ "cache way" に着地し、L2 キャッシュの連想性をはるかに超えることになります。そのため、アクセスされるキャッシュラインは B のアクセスされたキャッシュ行は次の反復のためにキャッシュに留まることはありません。 代わりに、それらはラムからずっと引き込まれる必要があります。