キャッシュメモリの仕組み

Question

今日、私がコンピュータ組織のクラスにいたとき、先生は私にとって興味深い何かについて話しました。キャッシュメモリが機能する理由について話すとき、彼は次のように言いました。

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

2行目で最初の行を変更するのは良くありません。これについてのあなたの意見は何ですか？そして、なぜそうなのですか？

Answer 1

参照の局所性。データは行ごとに格納されるため、各行のj列は隣接するメモリアドレスにあります。通常、OSはメモリからページ全体をキャッシュにロードし、隣接するアドレス参照はおそらく同じページを参照します。内側のループの行インデックスでインクリメントする場合、これらの行は異なるページにある可能性があり（それぞれjダブルで区切られているため）、キャッシュは参照するメモリのページを常に取り込み、破棄する必要がある場合がありますデータ。これはスラッシングと呼ばれ、パフォーマンスに悪影響を及ぼします。

実際には、より大きな最新のキャッシュでは、行/列のサイズはこれが機能する前にかなり大きくする必要がありますが、それでもなお良い習慣です。

[編集]上記の答えはCに固有のものであり、他の言語では異なる場合があります。私が知っている唯一の違いはFORTRANです。 FORTRANは、列のメジャー順（上記は行メジャー）に格納します。FORTRANのステートメントの順序を変更するのは正しいでしょう。効率を望む/必要とするなら、あなたの言語がどのようにデータストレージを実装するかを知ることが重要です。

Answer 2

Red HatのUlrich Drepperとglibcの名声による非常に優れた論文があります。すべてのプログラマがすべきこと記憶について。キャッシュの詳細については、あるセクションで説明しました。たとえば、SMPシステムにはキャッシュ効果があり、CPUが変更されたキャッシュラインの所有権を前後にスラッシングし、パフォーマンスを大きく損なう可能性があります。

Answer 3

キャッシュはローカリティのようなものだからです。同じ数のメモリにアクセスしますが、さらに間隔をあけると、異なる「行」にヒットします。またはキャッシュを完全に見逃すことさえあります。したがって、選択の余地がある場合はいつでも、時間内に互いに近くで発生する可能性が高いアクセスが空間でも行われるようにデータを編成することをお勧めします。これにより、キャッシュヒットの可能性が高まり、パフォーマンスが向上します。

もちろん、このトピックに関する豊富な情報が利用可能です。たとえば、この地域のウィキペディアエントリをご覧ください。参照の。または、あなた自身のコースのテキスト本だと思います。 ：）

Answer 4

Cでは、n次元行列は行優先です。つまり、行列の最後のインデックスはメモリ内の隣接するスペースを表します。これは、他のいくつかの言語、たとえば列優先であるFORTRANとは異なります。 FORTRANでは、次のように2Dマトリックスを反復処理する方が効率的です。

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

キャッシュメモリは非常に高速で、CPUの近くにある非常に高価なメモリです。 CPUは毎回RAMから1つの小さなデータをフェッチするのではなく、データのチャンクをフェッチしてキャッシュに保存します。賭けは、あなたがちょうど1バイトを読んだ場合、あなたが読んだ次のバイトはその直後になる可能性が高いということです。この場合、キャッシュから取得できます。

ループをレイアウトどおりに配置することにより、メモリに格納されている順序でバイトを読み取ります。これは、それらがキャッシュ内にあり、CPUによって非常に迅速に読み取ることができることを意味します。 1行目と2行目を入れ替えると、すべての「N」を読みます。ループのたびにバイト。読み取り中のバイトはメモリ内で連続していないため、キャッシュ内にない可能性があります。 CPUは（遅い）RAMからそれらをフェッチする必要があるため、パフォーマンスが低下します。