シミュレーションを書くとき、私の相棒は、キャッシュに収まるほど小さいプログラムを書こうとするのが好きだと言います。これには本当の意味がありますか？キャッシュはRAMやメインメモリよりも高速であることを理解しています。プログラムをキャッシュから実行するか、少なくとも変数をキャッシュにロードするかを指定することはできますか？私たちはシミュレーションを書いているので、パフォーマンス/最適化の向上は大きなメリットです。
CPUキャッシングを説明する良いリンクを知っているなら、その方向に私を向けてください。
少なくとも一般的なデスクトップCPUでは、キャッシュの使用量について直接指定することはできません。ただし、キャッシュに適したコードを作成することはできます。コード側では、これは多くの場合、ループの展開（1つの明白な例）がほとんど役に立たないことを意味します-それはコードを拡張し、最新のCPUは通常ループのオーバーヘッドを最小限に抑えます。通常、データ側でより多くのことを実行して、参照の局所性を改善し、偽共有から保護することができます（たとえば、キャッシュの同じ部分を使用しようとし、他の部分は未使用のままにする2つの頻繁に使用されるデータ）。
編集（いくつかのポイントをもう少し明確にするため）：
一般的なCPUには、さまざまなキャッシュがあります。最新のデスクトッププロセッサには、通常、少なくとも2レベル、多くの場合3レベルのキャッシュがあります。（少なくともほぼ）普遍的な合意により、「レベル1」は処理要素に「最も近い」キャッシュであり、そこから数値が増加します（レベル2が次、レベル3がその後など）。
ほとんどの場合、（少なくとも）レベル1キャッシュは、命令キャッシュとデータキャッシュの2つに分割されます（Intel 486は、私が知っているほぼ唯一の例外であり、命令とデータの両方に1つのキャッシュがあります） -しかし、それは完全に時代遅れであり、おそらく多くの考えに値するものではありません）。
ほとんどの場合、キャッシュは一連の「行」として編成されます。キャッシュの内容は通常、一度に1行ずつ読み取られ、書き込まれ、追跡されます。つまり、CPUがキャッシュラインのいずれかの部分からのデータを使用する場合、そのキャッシュライン全体が次に低いレベルのストレージから読み取られます。CPUに近いキャッシュは、一般的に小さく、キャッシュラインも小さくなります。
この基本的なアーキテクチャは、コードの記述で重要なキャッシュの特性のほとんどにつながります。可能な限り、何かを一度キャッシュに読み込んで、それを使ってすべてを実行してから、別の何かに移りたいと考えています。
つまり、データを処理しているときは、通常、比較的少量のデータ（キャッシュに収まるほど少ない）を読み取り、そのデータに対してできるだけ多くの処理を行ってから、次のチャンクに移動する方がよいということです。データ。大量の入力を徐々に小さな部分にすばやく分割するクイックソートのようなアルゴリズムは、これを多かれ少なかれ自動的に実行するため、キャッシュの正確な詳細にほとんど関係なく、かなりキャッシュフレンドリーになる傾向があります。
これは、コードの記述方法にも影響を及ぼします。次のようなループがある場合：
for i = 0 to whatever
step1(data);
step2(data);
step3(data);
end for
一般に、キャッシュに収まる量まで、できるだけ多くのステップをつなぎ合わせる方がよいでしょう。キャッシュをオーバーフローさせた瞬間に、パフォーマンスが大幅に低下する可能性があります。上記の手順3のコードが十分に大きく、キャッシュに収まらない場合は、通常、ループを次のように2つに分割することをお勧めします（可能な場合）。
for i = 0 to whatever
step1(data);
step2(data);
end for
for i = 0 to whatever
step3(data);
end for
ループ展開はかなり熱く争われている主題です。一方では、CPUにはるかに適したコードにつながる可能性があり、ループ自体に対して実行される命令のオーバーヘッドが削減されます。同時に、コードサイズを増やすことができる（そして一般的にはそうする）ので、比較的キャッシュに不向きです。私自身の経験では、非常に大量のデータに対して非常に少量の処理を行う傾向がある合成ベンチマークでは、ループ展開から多くの利益を得ることができます。個々のデータに対してより多くの処理を行う傾向があるより実用的なコードでは、取得する量ははるかに少なくなります。また、キャッシュがオーバーフローして深刻なパフォーマンスの低下が発生することは、特にまれではありません。
データキャッシュのサイズも制限されています。これは、通常、できるだけ多くのデータがキャッシュに収まるように、データをできるだけ密にパックする必要があることを意味します。明らかな例の1つとして、ポインターとリンクされたデータ構造は、それらのポインターによって使用されるデータキャッシュスペースの量を補うために、計算の複雑さの点でかなりの量を獲得する必要があります。リンクされたデータ構造を使用する場合は、通常、少なくとも比較的大きなデータをリンクしていることを確認する必要があります。
ただし、多くの場合、数十年にわたって（ほとんど）廃止されてきた小さなプロセッサのごく少量のメモリにデータを収めるために最初に学んだトリックは、最新のプロセッサではかなりうまく機能することがわかりました。現在の目的は、メインメモリではなくキャッシュにより多くのデータを収めることですが、効果はほぼ同じです。かなりの数のケースで、CPU命令はほぼ無料であると考えることができ、全体的な実行速度はキャッシュ（またはメインメモリ）への帯域幅によって制御されるため、高密度フォーマットからデータを解凍するための追加の処理は、あなたの好意。これは、すべてがキャッシュに収まらないほど十分なデータを処理している場合に特に当てはまります。そのため、全体的な速度はメインメモリへの帯域幅によって決まります。この場合、あなたはたくさん実行することができますいくつかのメモリ読み取りを節約し、それでも先に出てくるように指示します。
並列処理はその問題を悪化させる可能性があります。多くの場合、並列処理を可能にするためにコードを書き直すと、パフォーマンスが実質的に向上しないか、場合によってはパフォーマンスが低下する可能性があります。全体的な速度がCPUからメモリまでの帯域幅によって支配されている場合、その帯域幅をめぐってより多くのコアが競合することは、何の役にも立たない可能性があります（そして実質的な害を及ぼす可能性があります）。このような場合、速度を向上させるために複数のコアを使用することは、多くの場合、データをより緊密にパックするためにさらに多くのことを行い、データをアンパックするためにさらに多くの処理能力を利用することになります。したがって、実際の速度の向上は、消費される帯域幅の削減によるものです。 、および追加のコアは、より高密度の形式からデータを解凍するために時間を無駄にすることを防ぎます。
並列コーディングで発生する可能性のあるもう1つのキャッシュベースの問題は、変数の共有（および偽共有）です。2つ（またはそれ以上）のコアがメモリ内の同じ場所に書き込む必要がある場合、そのデータを保持するキャッシュラインは、コア間を行き来して、各コアに共有データへのアクセスを許可することになります。その結果、多くの場合、コードはシリアルよりもパラレルで実行速度が遅くなります（つまり、シングルコアで実行されます）。これには「偽共有」と呼ばれるバリエーションがあり、異なるコアのコードが別々のデータに書き込んでいますが、異なるコアのデータは同じキャッシュラインに配置されます。キャッシュはデータの行全体に関して純粋にデータを制御するため、データはとにかくコア間でシャッフルされ、まったく同じ問題が発生します。
これは、Christer Ericsson（God of War I / II / IIIの名声）によるキャッシュ/メモリの最適化に関する非常に優れた論文へのリンクです。それは数年前ですが、それでも非常に関連性があります。
キャッシュについてこれまで知りたかった以上のことを教えてくれる便利な論文は、UlrichDrepperによるすべてのプログラマーがメモリについて知っておくべきことです。ヘネシーはそれを非常に徹底的にカバーしています。ChristerとMikeActonは、これについてもたくさんの良いことを書いています。
命令キャッシュよりもデータキャッシュについてもっと心配する必要があると思います。私の経験では、dcacheのミスはより頻繁で、より苦痛で、より便利に修正されます。
更新：2014年1月13 日この上級チップ設計者によると、キャッシュミスは現在、コードパフォーマンスの圧倒的に支配的な要因であるため、相対的なパフォーマンスの観点からは、基本的に80年代半ばと高速の286チップにまでさかのぼります。ロード、ストア、整数演算、およびキャッシュミスのボトルネック。
Cliffによる最新のハードウェアのクラッシュコース@Azulをクリックし ます。。。。。
---定期的にスケジュールされているプログラムに戻ります---
例は、何かを行う方法の説明よりも優れている場合があります。その精神で、これは私がチップキャッシュでよりよく使用するためにいくつかのコードを変更した方法の特に成功した例です。これは、しばらく前に486 CPUで行われ、後者は第1世代のPentiumCPUに移行されました。パフォーマンスへの影響も同様でした。
例：添え字マッピング
これは、汎用ユーティリティを備えたチップのキャッシュにデータを収めるために使用した手法の例です。
私は1,250要素の長さのダブルフロートベクトルを持っていました。これは非常に長いテールを持つ疫学曲線でした。曲線の「興味深い」部分には約200の一意の値しかありませんでしたが、両面if（）テストでCPUのパイプラインを混乱させたくありませんでした（したがって、長いテールは、下付き文字として最も極端に使用できます）モンテカルロコードが吐き出す値）、そしてコードの「ホットスポット」内にある他の12の条件付きテストの分岐予測ロジックが必要でした。
私は、8ビットintのベクトルを二重ベクトルの添え字として使用するスキームに落ち着きました。これを256要素に短縮しました。小さなintはすべて、ゼロの前に128、ゼロの後に128の前に同じ値を持っていたため、中央の256の値を除いて、すべてダブルベクトルの最初または最後の値を指していました。
これにより、ストレージ要件がdoubleの場合は2kに、8ビットの添え字の場合は1,250バイトに縮小されました。これにより、10,000バイトが3,298に縮小されました。プログラムはその時間の90％以上をこの内部ループに費やしたため、2つのベクトルが8kデータキャッシュからプッシュされることはありませんでした。プログラムはすぐにそのパフォーマンスを2倍にしました。このコードは、100万件以上の住宅ローンのOAS値を計算する過程で、約1,000億回ヒットしました。
曲線の裾に触れることはめったにないため、小さなintベクトルの中央の200〜300要素のみが実際にキャッシュに保持され、160〜240の中央のdoubleが関心の1/8パーセントを表す可能性があります。これは、私が1年以上かけて最適化したプログラムで、午後に達成されたパフォーマンスの著しい向上でした。
私の経験でもあるように、コードを命令キャッシュに向けて傾けることは、データキャッシュの最適化ほど成功しないというJerryに同意します。これが、AMDの共通キャッシュがIntelの個別のデータキャッシュや命令キャッシュほど役に立たないと思う理由の1つです。IE：あまり役に立たないので、命令がキャッシュを占有することは望ましくありません。これは、CISC命令セットが元々CPUとメモリの速度の大きな違いを補うために作成されたためであり、80年代後半の異常を除いて、それはほぼ常に当てはまります。
私がデータキャッシュを優先し、命令キャッシュを野蛮にするために使用するもう1つのお気に入りの手法は、構造体定義で多くのビット整数を使用し、一般に可能な限り最小のデータサイズを使用することです。年の月を保持するために4ビットのintをマスクする、または年の日を保持するために9ビットなどをマスクするには、CPUがマスクを使用して、ビットが使用しているホスト整数をマスクする必要があります。データは、キャッシュとバスのサイズを効果的に増やしますが、より多くの命令が必要です。この手法は、合成ベンチマークではうまく機能しないコードを生成しますが、ユーザーとプロセスがリソースを奪い合う忙しいシステムでは、すばらしい働きをします。
ほとんどの場合、これは、このトピックの正義を行う時間ができるまでプレースホルダーとして機能しますが、真に画期的なマイルストーンであると私が考えるもの、つまり新しいIntelHazwellマイクロプロセッサーでの専用ビット操作命令の導入を共有したいと思いました。
ここStackOverflowで、PCの導入から30年以上経過した後、マイクロプロセッサがビットにあまり注意やリソースを費やさない4096ビット配列のビットを反転するコードを書いたとき、痛々しいほど明白になりました。変化する。特に、まず、bool型が、現在の途方もなく無駄なバイトではなく、C /C++の実際のビットデータ型になることを望んでいます。
更新：2013年12月29日
私は最近、ミリ秒の粒度でシステムに対する512の異なるリソースユーザーの要求を追跡するリングバッファーを最適化する機会がありました。ミリ秒ごとに起動するタイマーがあり、最新のスライスのリソースリクエストの合計を加算し、1,000ミリ秒前のリソースリクエストを含む1,000番目のタイムスライスのリクエストを減算します。
Head、Tailベクトルは、最初にHead、次にTailがラップされ、配列の先頭に戻った場合を除いて、メモリ内で互いに隣接していました。ただし、（ローリング）Summaryスライスは、静的に割り当てられた固定の配列にあり、どちらにも特に近くはなく、ヒープからも割り当てられていませんでした。
これについて考え、コードを研究することで、いくつかの詳細が私の注意を引きました。
入ってくる要求は、コードの隣接する行で互いに隣接して、ヘッドとサマリースライスに同時に追加されました。
タイマーが起動すると、SummaryスライスからTailが差し引かれ、予想どおり、結果がSummaryスライスに残されました。
タイマーが起動したときに呼び出される2番目の関数は、リングにサービスを提供するすべてのポインターを進めました。特に....ヘッドがテールを上書きし、それによって同じメモリ位置を占有しました新しいテールが次の512個のメモリ位置を占有するか、ラップされました
ユーザーは、管理される要求の数を512から4098、またはそれ以上に柔軟にすることを望んでいました。これを行うための最も堅牢でばかげた方法は、1,000のタイムスライスとサマリースライスの両方を1つの連続したメモリブロックとして一緒に割り当てることで、サマリースライスが異なる長さになることは不可能だと感じました。他の1,000のタイムスライスより。
上記のことから、サマリースライスを1つの場所に残すのではなく、ヘッドとテールの間を「ローミング」して、常にヘッドのすぐ隣に配置すると、パフォーマンスが向上するのではないかと思い始めました。新しい要求を追加し、タイマーが起動してテールの値をサマリーから差し引く必要があったときに、テールのすぐ隣に追加します。
私はまさにこれを行いましたが、その過程でいくつかの追加の最適化が見つかりました。ローリングサマリーを計算するコードを変更して、サマリースライスではなくテールに結果が残るようにしました。なんで？次の関数はmemcpy（）を実行して、SummaryスライスをTailが占有しているメモリに移動したためです。（奇妙ですが本当です、尾はそれが包むときリングの終わりまで頭を導きます）。合計の結果をTailに残すことで、memcpy（）を実行する必要がなくなり、pTailをpSummaryに割り当てるだけで済みました。
同様に、新しいヘッドが古いサマリースライスの古いメモリ位置を占有していたため、ここでもpSummaryをpHeadに割り当て、memsetをゼロにしてすべての値をゼロにしました。
リングの終わり（実際にはドラム、幅512トラック）への道を導いたのはテールでしたが、その状態を検出するには、そのポインターを一定のpEndOfRingポインターと比較するだけで済みました。他のすべてのポインターには、その直前のベクトルのポインター値を割り当てることができます。IE：ポインターを正しくラップするには、1：3のポインターの条件付きテストのみが必要でした。
初期の設計では、キャッシュ使用量を最大化するためにバイト整数を使用していましたが、この制約を緩和することができました-ミリ秒あたりのユーザーあたりのリソース数を増やすというユーザーの要求を満たします-符号なしショートを使用し、3つ隣接している場合でもパフォーマンスが2倍になるため512個の符号なしショートのベクトルであるL1キャッシュの32Kデータキャッシュは、必要な3,720バイトを簡単に保持でき、その3分の2は使用されたばかりの場所にありました。テール、サマリー、またはヘッドがラップされた場合にのみ、8MBのL3キャッシュ内の重要な「ステップ」で区切られた3つのうちの1つでした。
このコードの合計実行時メモリフットプリントは2MB未満であるため、オンチップキャッシュが完全に不足し、4コアのi7チップでも、このプロセスの4つのインスタンスをパフォーマンスをまったく低下させることなく実行できます。 、および合計スループットは、5つのプロセスを実行するとわずかに増加します。これは、キャッシュ使用量に関するOpusMagnumです。
ほとんどのC/C ++コンパイラは、「速度」よりもサイズを最適化することを好みます。つまり、キャッシュ効果のため、通常、小さいコードは展開されたコードよりも高速に実行されます。
私があなたなら、コードのどの部分がホットスポットであるかを確認します。これを次のように定義します。
そのようなホットスポットがある場合は、キャッシュに収まるはずです。どのようにそれを行うように指示するかはわかりませんが、自動であると思われます。