0

Ulrich Drepper からcpumemory.pdfを読んでいますが、6.2.1 章 (49-50 ページ) の行列乗算でのキャッシュ アクセスの最適化に関する次の部分を理解できません。

行列乗算の最初の単純な方法が示されています。

for (i = 0; i < N; ++i)
    for (j = 0; j < N; ++j)
        for (k = 0; k < N; ++k)
            res[i][j] += mul1[i][k] * mul2[k][j];

mul2列ごとにアクセスされるため、列ごとに 1 つのキャッシュ ラインが無駄になります。ウルリッヒは次のように述べています。

sizeof(double) が 8 の場合、これは、キャッシュ ラインを完全に利用するには、中央のループを 8 回展開する必要があることを意味します。

簡潔にするために、中間ループを 2 回だけ展開しました。

for (i = 0; i < N; ++i)
    for (j = 0; j < N; j += 2)
        for (k = 0; k < N; ++k) {
            res[i][j+0] += mul1[i][k] * mul2[k][j+0];
            res[i][j+1] += mul1[i][k] * mul2[k][j+1];
        }

これで、キャッシュ ラインが 2 つの double 値の幅である場合、完全に使用されることは明らかです。しかし、ウルリッヒは次のように続けます。

この考えを続けると、res 行列も効果的に使用する、つまり同時に 8 つの結果を書き込むには、外側のループも 8 回展開する必要があります。

簡潔にするために、外側のループを 2 回だけ展開しました。

for (i = 0; i < N; i += 2)
    for (j = 0; j < N; j+=2)
        for (k = 0; k < N; ++k) {
            res[i+0][j+0] += mul1[i+0][k] * mul2[k][j+0];
            res[i+0][j+0] += mul1[i+0][k] * mul2[k][j+0];
            res[i+1][j+0] += mul1[i+1][k] * mul2[k][j+0];
            res[i+1][j+1] += mul1[i+1][k] * mul2[k][j+1];
        }

mul1列によってアクセスされるようになったため、以前のバージョンよりもさらに悪いように思えます。ウルリッヒの意味を説明してください。

4

1 に答える 1

1

キャッシュ内には、左入力、右入力、および結果の 3 つのマトリックスがあります。

左の入力は行優先であるため、元のコードによって問題なくアクセスされ、最も内側のループは k をインクリメントするため、キャッシュ ラインを下降します。キャッシュ ラインが削除される前にキャッシュ ラインが使用されます。

問題は結果行列です..これも行優先ですが、キャッシュラインはkではなくjでインデックス付けされています..そしてあなたは正しい.. jはすでに展開されているため、キャッシュ上のすべての要素を使用します結果マトリックス内の行..したがって、2回目の展開によって得られるものは何もないように見えます..それが行うのは、2つの余分なキャッシュ行を追加することだけです..左のマトリックス用の追加と結果マトリックス用の追加! キャッシュラインの要素のカバレッジは改善されません!

ただし、たまたま右側のマトリックスのキャッシュ ラインを 2 回再利用することはあります。これにより、右側のマトリックスのラインを取り込む必要がある合計回数が減少し、左右のマトリックス キャッシュの回数は増加しません。行が持ち込まれる..おそらく、行全体の再利用が利点の由来です..問題は、これがキャッシュサイズに適切にブロックされているかどうか、およびキャッシュのセットアソシエティビティが何であるか..場合3 つすべての行列のすべての行がキャッシュに残っている場合、これには何の利点もありません.. (しかし、悪化することはありません!)

于 2014-02-04T04:08:30.767 に答える