824

「キャッシュに適していないコード」と「キャッシュに適した」コードの違いは何ですか?

キャッシュ効率の高いコードを確実に書くにはどうすればよいですか?

4

9 に答える 9

1081

予選

最新のコンピューターでは、最下位レベルのメモリ構造 (レジスター) のみが 1 クロック サイクルでデータを移動できます。ただし、レジスターは非常に高価であり、ほとんどのコンピューター コアには数十未満のレジスターしかありません。メモリ スペクトルの反対側 ( DRAM ) では、メモリは非常に安価です (つまり、文字通り何百万倍も安い) が、データを受信するために要求後数百サイクルかかります。超高速で高コスト、超低速で低コストのギャップを埋めるのがキャッシュ メモリです。、速度とコストを下げるために L1、L2、L3 と名付けられました。アイデアは、実行中のコードのほとんどが小さな変数セットを頻繁にヒットし、残り (はるかに大きな変数セット) を頻繁にヒットしないということです。プロセッサが L1 キャッシュでデータを見つけられない場合、L2 キャッシュを調べます。存在しない場合は L3 キャッシュ、存在しない場合はメイン メモリ。これらの「ミス」のそれぞれは、時間がかかります。

(例えるなら、キャッシュ メモリはシステム メモリであり、システム メモリはハードディスク ストレージです。ハードディスク ストレージは非常に安価ですが、非常に低速です)。

キャッシングは、レイテンシーの影響を軽減するための主要な方法の 1 つです。Herb Sutter の言葉を言い換えると (以下のリンクを参照):帯域幅を増やすのは簡単ですが、遅延から抜け出す方法はありません。

データは常にメモリ階層を介して取得されます (最小 == 最速から低速)。キャッシュ ヒット/ミスは通常、CPU のキャッシュの最高レベルでのヒット/ミスを指します。最高レベルとは、最大 == 最も遅いことを意味します。キャッシュ ミスのたびに RAM からデータがフェッチされるため (またはさらに悪いことに ...) 、多くの時間がかかります (RAM の場合は数百サイクル、HDD の場合は数千万サイクル)。それに比べて、(最高レベルの) キャッシュからのデータの読み取りには、通常、ほんの数サイクルしかかかりません。

現代のコンピュータ アーキテクチャでは、パフォーマンスのボトルネックは CPU ダイを離れることです (たとえば、RAM 以上へのアクセス)。これは時間の経過とともに悪化するだけです。現在、プロセッサ周波数の増加は、パフォーマンスの向上には関係ありません。問題はメモリアクセスです。そのため、現在、CPU のハードウェア設計の取り組みは、キャッシュ、プリフェッチ、パイプライン、および同時実行性の最適化に重点を置いています。たとえば、最新の CPU はダイの約 85% をキャッシュに費やし、最大 99% をデータの保存/移動に費やしています!

この件については、かなり多くのことが語られています。キャッシュ、メモリ階層、および適切なプログラミングに関するいくつかの優れたリファレンスを次に示します。

キャッシュに適したコードの主な概念

キャッシュに適したコードの非常に重要な側面は、局所性の原則に関するものです。この原則の目標は、関連データをメモリ内の近くに配置して、効率的なキャッシュを可能にすることです。CPU キャッシュに関しては、これがどのように機能するかを理解するために、キャッシュ ラインに注意することが重要です。キャッシュ ラインはどのように機能しますか?

次の特定の側面は、キャッシュを最適化するために非常に重要です。

  1. 時間的局所性: 特定のメモリ ロケーションがアクセスされた場合、近い将来に同じロケーションが再びアクセスされる可能性があります。理想的には、この情報はその時点でまだキャッシュされています。
  2. 空間的局所性: これは、関連するデータを互いに近くに配置することを指します。キャッシングは、CPU だけでなく、さまざまなレベルで発生します。たとえば、RAM から読み取る場合、プログラムがそのデータをすぐに必要とすることが非常に多いため、通常、具体的に要求されたものよりも大きなメモリ チャンクがフェッチされます。HDD キャッシュも同じ考え方に従います。特に CPU キャッシュでは、キャッシュ ラインの概念が重要です。

適切なコンテナーを使用する

キャッシュに適したものとキャッシュに適していないものの簡単な例は、c std::vectorとstd::list. の要素はstd::vector連続したメモリに格納されるため、コンテンツをあちこちに格納する の要素にアクセスするよりも、それらにアクセスする方がはるかにキャッシュ フレンドリーです。std::listこれは、空間的局所性によるものです。

この youtube クリップで、Bjarne Stroustrup が非常に優れた例を示しています(@Mohammad Ali Baydoun のリンクに感謝します!)。

データ構造とアルゴリズム設計でキャッシュを無視しない

可能な限り、キャッシュを最大限に活用できるようにデータ構造と計算順序を調整してください。この点に関する一般的な手法は、キャッシュ ブロッキング (Archive.org バージョン)です。これは、ハイ パフォーマンス コンピューティングで非常に重要です ( ATLASなどを参照)。

データの暗黙的な構造を知り、活用する

1 つの簡単な例は、2 次元配列を格納するための列優先 ( fortran 、など) と行優先 ( 、たとえば、次のマトリックスを考えてみます。

1 2
3 4

行優先順では、これは次のようにメモリに格納されます1 2 3 4。列優先順では、これは として保存され1 3 2 4ます。この順序付けを利用しない実装では、(簡単に回避できる!) キャッシュの問題がすぐに発生することは容易にわかります。残念ながら、私のドメイン (機械学習) では、このようなものをよく見かけます。@MatteoItalia は、彼の回答でこの例をより詳細に示しました。

行列の特定の要素をメモリからフェッチすると、その近くの要素もフェッチされ、キャッシュ ラインに格納されます。順序付けを悪用すると、メモリ アクセスが少なくなります (後続の計算に必要な次のいくつかの値が既にキャッシュ ラインにあるため)。

簡単にするために、キャッシュが 2 つの行列要素を含むことができる単一のキャッシュ ラインで構成され、特定の要素がメモリからフェッチされると、次の要素もフェッチされると仮定します。上記の例の 2x2 行列のすべての要素の合計を取りたいとします (これを と呼びましょうM):

順序付けを利用する (例: で最初に列インデックスを変更する):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

順序付けを利用しない (例: で最初に行インデックスを変更する):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

この単純な例では、順序付けを利用すると、実行速度が約 2 倍になります (メモリ アクセスには、合計の計算よりもはるかに多くのサイクルが必要なため)。実際には、パフォーマンスの差はさらに大きくなる可能性があります。

予測不可能な分岐を避ける

最新のアーキテクチャはパイプラインを備えており、コンパイラはメモリ アクセスによる遅延を最小限に抑えるためにコードを並べ替えるのが得意になってきています。重要なコードに (予測不可能な) 分岐が含まれている場合、データのプリフェッチは困難または不可能です。これは、間接的にキャッシュ ミスの増加につながります。

これはここで非常によく説明されています (リンクの @0x90 に感謝します):並べ替えられた配列の処理は、並べ替えられていない配列の処理よりも速いのはなぜですか?

仮想関数を避ける

のコンテキストでは、virtualメソッドはキャッシュ ミスに関して物議を醸す問題を表します (パフォーマンスの観点から、可能な場合は避けるべきであるという一般的なコンセンサスが存在します)。仮想関数はルックアップ中にキャッシュ ミスを引き起こす可能性がありますが、これは特定の関数が頻繁に呼び出されない場合にのみ発生するため (そうでない場合はキャッシュされる可能性があります)、一部の人はこれを問題ではないと見なしています。この問題に関する参考資料として、C++ クラスで仮想メソッドを使用する場合のパフォーマンス コストは何ですか? を参照してください。

一般的な問題

マルチプロセッサ キャッシュを使用する最新のアーキテクチャでよくある問題は、偽共有と呼ばれます。これは、個々のプロセッサが別のメモリ領域のデータを使用しようとし、それを同じキャッシュ ラインに格納しようとしたときに発生します。これにより、別のプロセッサが使用できるデータを含むキャッシュ ラインが何度も上書きされます。この状況では、事実上、異なるスレッドがキャッシュ ミスを誘発することで、互いに待機状態になります。も参照してください (リンクについては @Matt に感謝します): How and when to align to cache line size?

RAM メモリのキャッシングが不十分な場合の極端な症状 (これはおそらく、このコンテキストで意味するものではありません) は、いわゆるスラッシングです。これは、プロセスがディスク アクセスを必要とするページ フォールト (現在のページにないメモリへのアクセスなど) を継続的に生成する場合に発生します。

于 2013-05-22T18:39:16.423 に答える
157

@Marc Claesenの回答に加えて、キャッシュに適していないコードの有益な古典的な例は、行単位ではなく列単位でCの二次元配列（ビットマップ画像など）をスキャンするコードだと思います。

行内で隣接する要素はメモリ内でも隣接しているため、それらに順番にアクセスするということは、メモリの昇順でアクセスすることを意味します。キャッシュはメモリの連続ブロックをプリフェッチする傾向があるため、これはキャッシュ フレンドリーです。

代わりに、同じ列の要素はメモリ内で互いに離れているため (特に、それらの距離は行のサイズに等しい)、そのような要素に列単位でアクセスすることはキャッシュに適していません。したがって、このアクセス パターンを使用する場合は、メモリ内を飛び回っているため、メモリ内の近くの要素を取得するキャッシュの労力が無駄になる可能性があります。

そして、パフォーマンスを台無しにするのに必要なのは、

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

に

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

この効果は、キャッシュが小さいシステムや大きなアレイ (現在のマシンで 10 メガピクセル以上の 24 bpp イメージなど) を使用するシステムでは、非常に劇的 (数桁の速度) になる可能性があります。このため、多くの垂直スキャンを実行する必要がある場合は、最初に画像を 90 度回転させ、後でさまざまな分析を実行して、キャッシュに適していないコードを回転だけに限定する方がよい場合がよくあります。

于 2013-05-22T19:51:33.840 に答える
35

データ指向設計の世界へようこそ。基本的なマントラは、並べ替え、ブランチの削除、バッチ処理、virtual呼び出しの削除です。これらはすべて、より良いローカリティに向けたステップです。

質問に C++ のタグを付けたので、これは必須の典型的な C++ でたらめです。Tony Albrecht のPitfalls of Object Oriented Programmingも、このテーマの優れた入門書です。

于 2013-05-22T21:03:38.000 に答える
24

積み重ねるだけです。キャッシュに適していないコードとキャッシュに適したコードの古典的な例は、行列乗算の「キャッシュブロッキング」です。

単純な行列乗算は次のようになります。

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k=0;k<N;k++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

が大きい場合N、たとえばN * sizeof(elemType)がキャッシュ サイズより大きい場合、 へのすべてのアクセスがsrc2[k][j]キャッシュ ミスになります。

これをキャッシュ用に最適化するには、さまざまな方法があります。非常に簡単な例を次に示します。内側のループでキャッシュ ラインごとに 1 つのアイテムを読み取る代わりに、すべてのアイテムを使用します。

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

キャッシュ ラインのサイズが 64 バイトで、32 ビット (4 バイト) の float で操作している場合、キャッシュ ラインごとに 16 個の項目があります。そして、この単純な変換だけで、キャッシュ ミスの数は約 16 分の 1 に減少します。

高度な変換は 2D タイルで動作し、複数のキャッシュ (L1、L2、TLB) を最適化します。

「キャッシュブロッキング」をグーグルで検索した結果:

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

最適化されたキャッシュ ブロック アルゴリズムの素晴らしいビデオ アニメーション。

http://www.youtube.com/watch?v=IFWgwGMMrh0

ループ タイリングは非常に密接に関連しています。

http://en.wikipedia.org/wiki/Loop_tiling

于 2013-05-29T03:50:48.693 に答える
13

今日のプロセッサは、多くのレベルのカスケード メモリ領域で動作します。したがって、CPU には、CPU チップ自体に大量のメモリがあります。このメモリへのアクセスは非常に高速です。CPU上になく、アクセスが比較的遅いシステムメモリに到達するまで、次のキャッシュよりもアクセスが遅くなる（および大きくなる）さまざまなレベルのキャッシュがあります。

論理的には、CPU の命令セットに対しては、巨大な仮想アドレス空間のメモリ アドレスを参照するだけです。単一のメモリ アドレスにアクセスすると、CPU はそれを取得します。昔は、その単一のアドレスだけをフェッチしていました。しかし、今日では、CPU は要求されたビットの周囲に大量のメモリをフェッチし、それをキャッシュにコピーします。特定の住所を尋ねた場合、近いうちに近くの住所を尋ねる可能性が高いと想定しています。たとえば、バッファをコピーしている場合、連続したアドレスから読み書きします。

したがって、今日、アドレスを取得すると、キャッシュの最初のレベルをチェックして、そのアドレスが既にキャッシュに読み込まれているかどうかを確認します。見つからない場合、これはキャッシュ ミスであり、次のレベルのキャッシュに移動する必要があります。最終的にメインメモリに移動する必要があるまで、それを見つけるためにキャッシュします。

キャッシュに適したコードは、キャッシュ ミスを最小限に抑えるために、メモリ内でアクセスを近づけようとします。

たとえば、巨大な 2 次元のテーブルをコピーしたいとします。メモリ内でリーチ行が連続するように編成されており、その直後に 1 つの行が次の行に続きます。

要素を一度に 1 行ずつ左から右にコピーすると、キャッシュ フレンドリーになります。テーブルを一度に 1 列ずつコピーすることにした場合、まったく同じ量のメモリをコピーすることになりますが、キャッシュには適していません。

于 2013-05-22T19:58:06.483 に答える
5

データがキャッシュに適しているだけでなく、コードにとっても重要であることを明確にする必要があります。これは、分岐予測、命令の並べ替え、実際の分割の回避、およびその他の手法に加えて行われます。

通常、コードの密度が高いほど、それを格納するために必要なキャッシュ ラインは少なくなります。これにより、データに使用できるキャッシュ ラインが増えます。

関数は通常、1 つまたは複数の独自のキャッシュ ラインを必要とし、結果としてデータ用のキャッシュ ラインが少なくなるため、コードはあらゆる場所で関数を呼び出すべきではありません。

関数は、キャッシュ ライン アライメントに適したアドレスで開始する必要があります。これには (gcc) コンパイラ スイッチがありますが、関数が非常に短い場合、各関数がキャッシュ ライン全体を占有するのは無駄になる可能性があることに注意してください。たとえば、最も頻繁に使用される関数の 3 つが 1 つの 64 バイト キャッシュ ラインに収まる場合、それぞれが独自のラインを持つ場合よりも無駄が少なくなり、2 つのキャッシュ ラインが他の用途に使用できなくなります。一般的なアライメント値は 32 または 16 です。

そのため、コードを密にするために余分な時間を費やしてください。さまざまな構造をテストし、コンパイルして、生成されたコードのサイズとプロファイルを確認します。

于 2014-08-08T17:50:55.300 に答える