caching - CPU キャッシュを最大限に活用してパフォーマンスを向上させるコードを作成するにはどうすればよいでしょうか?

Question

これは主観的な質問のように聞こえるかもしれませんが、私が探しているのは、これに関連して遭遇した可能性のある具体的な事例です。

コード、キャッシュを効果的/キャッシュフレンドリーにする方法 (キャッシュヒットを増やし、キャッシュミスをできるだけ少なくする)? 両方の観点から、データキャッシュとプログラムキャッシュ (命令キャッシュ)、つまり、データ構造とコード構造に関連するコード内の事柄は、キャッシュを有効にするために注意する必要があります。
コードキャッシュを有効にするために、使用/回避する必要がある特定のデータ構造はありますか、またはその構造のメンバーにアクセスする特定の方法などはありますか?
プログラム構造 (if、for、switch、break、goto、...)、コードフロー (if 内の場合、for 内の場合など) はありますか?

一般的にキャッシュ効率の高いコードを作成することに関連する個々の経験を聞くことを楽しみにしています。任意のプログラミング言語 (C、C++、アセンブリなど)、任意のハードウェアターゲット (ARM、Intel、PowerPC など)、任意の OS (Windows、Linux、Symbian など) などを使用できます。 .

多様性は、それをより深く理解するのに役立ちます。

score 127 · Accepted Answer

キャッシュは、メモリ要求が満たされるのを待って CPU がストールする回数を減らし (メモリのレイテンシを回避する)、2 つ目の効果として、転送する必要があるデータの全体量を減らすためにあります (メモリ帯域幅）。

通常、メモリフェッチレイテンシの影響を回避するための手法が最初に考慮され、場合によっては大いに役立ちます。限られたメモリ帯域幅も、特に多くのスレッドがメモリバスを使用する必要があるマルチコアおよびマルチスレッドアプリケーションの場合、制限要因になります。後者の問題に対処するには、別の一連の手法が役立ちます。

空間的局所性を改善するということは、キャッシュにマップされた後、各キャッシュラインが完全に使用されることを保証することを意味します。さまざまな標準的なベンチマークを調べたところ、キャッシュラインが削除される前に、フェッチされたキャッシュラインを 100% 使用できなかったベンチマークが驚くほど多いことがわかりました。

キャッシュラインの使用率を改善すると、次の 3 つの点で役立ちます。

より有用なデータがキャッシュに収まる傾向があり、実質的に有効なキャッシュサイズが増加します。
より有用なデータが同じキャッシュラインに収まる傾向があり、要求されたデータがキャッシュで見つかる可能性が高くなります。
フェッチが少なくなるため、メモリ帯域幅の要件が軽減されます。

一般的な手法は次のとおりです。

小さいデータ型を使用する
アラインメントホールを回避するためにデータを整理します (サイズを小さくして構造体メンバーを並べ替えるのも 1 つの方法です)。
標準の動的メモリアロケータに注意してください。これにより、ホールが発生し、ウォームアップ時にデータがメモリ内に拡散する可能性があります。
隣接するすべてのデータが実際にホットループで使用されていることを確認します。それ以外の場合は、ホットループがホットデータを使用するように、データ構造をホットコンポーネントとコールドコンポーネントに分割することを検討してください。
不規則なアクセスパターンを示すアルゴリズムとデータ構造を避け、直線的なデータ構造を優先します。

また、キャッシュを使用する以外にも、メモリレイテンシを隠す方法があることに注意してください。

最新の CPU: には、多くの場合、1 つ以上のハードウェアプリフェッチャーがあります。キャッシュ内のミスをトレーニングし、規則性を見つけようとします。たとえば、後続のキャッシュラインに数回ミスした後、ハードウェアプリフェッチャーは、アプリケーションのニーズを予測して、キャッシュラインをキャッシュにフェッチし始めます。通常のアクセスパターンを使用している場合、ハードウェアプリフェッチャーは通常、非常にうまく機能しています。また、プログラムで通常のアクセスパターンが表示されない場合は、プリフェッチ命令を自分で追加することで改善できます。

キャッシュで常にミスする命令が互いに近くに発生するように命令を再グループ化すると、CPU はこれらのフェッチをオーバーラップして、アプリケーションが 1 つのレイテンシヒットのみを維持できるようにすることがあります (メモリレベルの並列処理)。

全体的なメモリバスプレッシャーを軽減するには、時間的局所性と呼ばれるものへの対処を開始する必要があります。これは、データがまだキャッシュから追い出されていない間にデータを再利用する必要があることを意味します。

同じデータに触れるループをマージ (ループフュージョン) し、タイリングまたはブロッキングと呼ばれる書き換え手法を採用することで、これらの余分なメモリフェッチを回避しようとします。

この書き直しの演習にはいくつかの経験則がありますが、通常は、プログラムのセマンティクスに影響を与えないように、ループで運ばれるデータの依存関係を慎重に検討する必要があります。

これらのことは、通常、2 番目のスレッドを追加した後にスループットの大幅な向上が見られないマルチコアの世界で実際に成果を上げているものです。

score 59 · Accepted Answer

これ以上の答えがないなんて信じられません。とにかく、古典的な例の 1 つは、多次元配列を「裏返して」繰り返すことです。

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

これがキャッシュの非効率性である理由は、単一のメモリアドレスにアクセスすると、最新の CPU がメインメモリから「近い」メモリアドレスをキャッシュラインにロードするためです。内側のループで配列の "j" (外側) 行を反復処理しているため、内側のループを通過するたびに、キャッシュラインがフラッシュされ、[ に近いアドレスのラインがロードされます。 j][i] エントリ。これが同等のものに変更された場合:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

それははるかに速く実行されます。

score 45 · Accepted Answer

メモリとソフトウェアの相互作用に興味がある場合は、Ulrich Drepper による9 部構成の記事「すべてのプログラマがメモリについて知っておくべきこと」を読むことをお勧めします。104 ページの PDFとしても入手できます。

この質問に特に関連するセクションは、パート 2 (CPU キャッシュ) とパート 5 (プログラマーができること - キャッシュの最適化) です。

score 15 · Accepted Answer

データアクセスパターンとは別に、キャッシュに適したコードの主な要因はデータサイズです。データが少ないということは、より多くのデータがキャッシュに収まることを意味します。

これは主に、メモリにアラインされたデータ構造の要因です。「従来の」知恵では、CPU はワード全体にしかアクセスできないため、データ構造はワード境界で整列する必要があり、ワードに複数の値が含まれている場合は、追加の作業 (単純な書き込みではなく読み取り-変更-書き込み) を行う必要があると言われています。 . ただし、キャッシュはこの引数を完全に無効にする可能性があります。

同様に、Java ブール配列は、個々の値を直接操作できるようにするために、各値に 1 バイト全体を使用します。実際のビットを使用すれば、データサイズを 8 分の 1 に減らすことができますが、個々の値へのアクセスは非常に複雑になり、ビットシフトとマスク操作が必要になります (BitSetこれはクラスが行います)。ただし、キャッシュの影響により、配列が大きい場合は boolean[] を使用するよりもかなり高速になる可能性があります。IIRC 私はかつて、この方法で 2 倍または 3 倍の高速化を達成しました。

score 9 · Accepted Answer

キャッシュの最も効果的なデータ構造は配列です。CPU がキャッシュライン全体 (通常は 32 バイト以上) をメインメモリから一度に読み取るときに、データ構造が順番に配置されている場合、キャッシュは最適に機能します。

ランダムな順序でメモリにアクセスするアルゴリズムは、ランダムにアクセスされるメモリに対応するために常に新しいキャッシュラインを必要とするため、キャッシュを破棄します。一方、配列を順次実行するアルゴリズムは、次の理由で最適です。

これにより、CPU が先読みを行う機会が与えられます。たとえば、投機的により多くのメモリをキャッシュに入れ、後でアクセスできるようにします。この先読みにより、パフォーマンスが大幅に向上します。
大きな配列に対してタイトなループを実行すると、CPU はループ内で実行されているコードをキャッシュすることもでき、ほとんどの場合、外部メモリアクセスをブロックすることなく、キャッシュメモリからアルゴリズムを完全に実行できます。

score 7 · Accepted Answer

ユーザー1800 情報による「古典的な例」へのコメント (コメントするには長すぎます)

2 つの反復順序 (「外側」と「内側」) の時間差を確認したかったので、大きな 2D 配列を使用して簡単な実験を行いました。

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

forループが交換された2番目のケース。

遅いバージョン (「x first」) は 0.88 秒で、速いバージョンは 0.06 秒でした。それがキャッシングの力です:)

私は使用gcc -O2しましたが、ループは最適化されていませんでした。「最新のコンパイラのほとんどは、これを自分で理解できる」というリカルドのコメントは当てはまりません。

score 7 · Accepted Answer

それに触れた投稿は 1 つだけですが、プロセス間でデータを共有するときに大きな問題が発生します。複数のプロセスが同じキャッシュラインを同時に変更しようとすることは避けたいと考えています。ここで注意すべきことは、2 つの隣接するデータ構造がキャッシュラインを共有し、一方を変更すると他方のキャッシュラインが無効になる、「誤った」共有です。これにより、マルチプロセッサシステムでデータを共有するプロセッサキャッシュ間でキャッシュラインが不必要に行き来することがあります。これを回避する方法は、データ構造を整列およびパディングして、それらを異なる行に配置することです。

score 5 · Accepted Answer

(2) の答えとして、C++ の世界では、連結リストは CPU キャッシュを簡単に殺してしまう可能性があると言えます。可能な場合は、配列の方が優れたソリューションです。同じことが他の言語にも当てはまるかどうかについては経験がありませんが、同様の問題が発生することは容易に想像できます。

score 4 · Accepted Answer

コードを作成する方法、キャッシュを効果的にする方法、キャッシュに適した方法、その他のほとんどの質問は、通常、プログラムを最適化する方法を尋ねることです。これは、キャッシュがパフォーマンスに大きな影響を与えるため、最適化されたプログラムはキャッシュであるためです。効果的なキャッシュフレンドリー。

最適化について読むことをお勧めします。このサイトにはいくつかの良い答えがあります。本に関しては、私はComputer Systems：A Programmer's Perspectiveについてお勧めします。これには、キャッシュの適切な使用法に関するいくつかの細かいテキストがあります。

（ところで、キャッシュミスが発生する可能性があるのと同じくらい悪いですが、プログラムがハードドライブからページングしている場合はさらに悪いことになります...）

score 4 · Accepted Answer

キャッシュは「キャッシュライン」に配置され、(実際の) メモリはこのサイズのチャンクで読み書きされます。

したがって、単一のキャッシュラインに含まれるデータ構造はより効率的です。

同様に、連続したメモリブロックにアクセスするアルゴリズムは、ランダムな順序でメモリをジャンプするアルゴリズムよりも効率的です。

残念ながら、キャッシュラインのサイズはプロセッサによって大きく異なるため、あるプロセッサで最適なデータ構造が他のプロセッサでも効率的であることを保証する方法はありません。

score 2 · Accepted Answer

構造体とフィールドを整列させることに加えて、ヒープが割り当てられている場合は構造体が整列された割り当てをサポートするアロケータを使用することをお勧めします。そう_aligned_malloc(sizeof(DATA), SYSTEM_CACHE_LINE_SIZE);でなければ、ランダムな偽共有があるかもしれません。Windowsでは、デフォルトのヒープは16バイトの配置になっていることに注意してください。

caching - CPU キャッシュを最大限に活用してパフォーマンスを向上させるコードを作成するにはどうすればよいでしょうか?

15 に答える 15

Related

Reference