9

今日、コンピューター編成の授業をしていたとき、先生が面白いことを話してくれました。キャッシュメモリが機能する理由についての話になると、彼は次のように述べています。

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 番目の行で変更するのはよくありません。これについてどう思いますか。そして、なぜそれはそのようなものですか？

4

5 に答える 5

12

Red Hat と glibc で有名な Ulrich Drepper による非常に優れた論文、What Every Programmer Should Know About Memory があります。あるセクションでは、キャッシュについて詳しく説明しました。たとえば、SMP システムではキャッシュ効果があり、CPU が変更されたキャッシュ ラインの所有権を前後にスラッシングする可能性があり、パフォーマンスが大幅に低下します。

于 2008-10-20T14:22:41.247 に答える
9

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

実際には、大規模な最新のキャッシュでは、これが機能する前に行/列のサイズを適度に大きくする必要がありますが、それでも良い方法です。

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

于 2008-10-20T11:44:09.493 に答える
7

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

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

于 2008-10-20T11:40:12.560 に答える
2

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

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo
于 2008-10-20T11:52:55.340 に答える
1

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

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

于 2008-10-20T12:42:11.060 に答える