CPUキャッシュに収まるようにコードを設計しますか？

StackOverflow https://stackoverflow.com/questions/1822295

質問

シミュレーションを書くとき、私の相棒は、キャッシュに収まるように十分に小さなプログラムを書きたいと言っています。これには本当の意味がありますか？キャッシュはRAMやメインメモリよりも高速であることを理解しています。プログラムをキャッシュから実行するか、少なくとも変数をキャッシュにロードするかを指定できますか？シミュレーションを作成しているので、パフォーマンス/最適化のゲインは大きな利点です。

CPUキャッシュを説明する適切なリンクを知っている場合は、その方向を教えてください。

役に立ちましたか？

解決

少なくとも一般的なデスクトップCPUでは、キャッシュの使用量を直接指定することはできません。ただし、キャッシュに優しいコードを作成することもできます。コード側では、これは多くの場合、アンロールループ（たった1つの明らかな例）がほとんど役に立たないことを意味します-コードを拡張し、最新のCPUは通常ループのオーバーヘッドを最小化します。一般に、データ側でより多くのことを実行して、参照の局所性を改善し、誤った共有（たとえば、キャッシュの同じ部分を使用しようとするが、他の部分は未使用のままになる2つの頻繁に使用されるデータ）から保護します。

編集（いくつかのポイントをもう少し明確にするため）：

一般的なCPUには、さまざまなキャッシュがあります。最新のデスクトッププロセッサには、通常少なくとも2レベル、多くの場合3レベルのキャッシュがあります。 （少なくともほぼ）普遍的な合意により、「レベル1」キャッシュは「最も近い」キャッシュです処理要素に渡され、そこから数字が上がります（レベル2が次に、レベル3が続きます）

ほとんどの場合、（少なくとも）レベル1キャッシュは、命令キャッシュとデータキャッシュの2つの半分に分割されます（Intel 486は、私が知っているほとんど唯一の例外で、両方に1つのキャッシュがあります）指示とデータ-しかし、それは完全に時代遅れであるので、おそらく多くの考えに値しないでしょう。

ほとんどの場合、キャッシュは「ライン」のセットとして編成されます。キャッシュの内容は通常、一度に1行ずつ読み取り、書き込み、追跡されます。つまり、CPUがキャッシュラインの任意の部分のデータを使用する場合、そのキャッシュライン全体が次に低いレベルのストレージから読み取られます。 CPUに近いキャッシュは一般的に小さく、キャッシュラインが小さくなります。

この基本的なアーキテクチャは、コードの記述に重要なキャッシュの特性のほとんどをもたらします。可能な限り、何かをキャッシュに一度読み込み、それを使ってすべてを実行した後、他の何かに進みます。

これは、データを処理しているときに、通常、比較的少量のデータ（キャッシュに収まるのに十分な量）を読み取り、そのデータをできるだけ多く処理してから、データの次のチャンク。大量の入力を次第に小さな断片にすばやく分割するQuicksortなどのアルゴリズムは、これを多少自動的に行うため、キャッシュの詳細にほとんど関係なく、かなりキャッシュに優しい傾向があります。

これは、コードの記述方法にも影響します。次のようなループがある場合：

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つだけですが、ポインターとリンクされているデータ構造は、計算の複雑さの点でかなりの部分を獲得して、

他のヒント

ここにあるのは、キャッシュ/ Christer Ericssonによるメモリ最適化（God of War I / II / IIIの名声）。それは数年前ですが、まだ非常に関連性があります。

キャッシュについて知りたいと思った以上に役立つ有用な論文は、 What Every Programmerです。 Ulrich Drepperによる記憶について知っておくべき。 Hennessey は非常に徹底的にカバーしています。クリスターとマイク・アクトンは、これについてもたくさんの良いものを書いています。

データキャッシュについては、命令キャッシュよりも心配する必要があると思います＆＃8212;私の経験では、dcacheのミスはより頻繁に発生し、痛みを伴い、より効果的に修正されます。

更新：2014年1月13日 このシニアチップ設計者によると、キャッシュミスはコードパフォーマンスの圧倒的に支配的な要因であるため、ロード、ストア、整数の相対的なパフォーマンスのボトルネックに関しては、基本的に80年代半ばと286チップにまでさかのぼります。算術演算、キャッシュミス。

Cliff Click @ Azulによる現代のハードウェアのクラッシュコース 。 。 。 。 。

---定期的にスケジュールされたプログラムに戻ります---

例は、何かをする方法の説明よりも良い場合があります。その精神で、チップキャッシュでより適切に使用するためにコードを変更した方法の特に成功した例を次に示します。これはしばらく前に486 CPUで行われ、後者は第1世代のPentium CPUに移行しました。パフォーマンスへの影響は同様でした。

例：下付き文字のマッピング

これは、汎用ユーティリティを備えたチップのキャッシュにデータを適合させるために使用した手法の例です。

1,250要素長のダブルフロートベクトルがありました。これは非常に長い尾を持つ疫学曲線でした。 「興味深い」曲線の一部には約200個の一意の値しかありませんでしたが、CPUのパイプラインを混乱させるための両側のif（）テストは望ましくありません（したがって、モンテカルロの最も極端な値を下付き文字として使用できる長い尾コードが吐き出されます）、「ホットスポット」内の他の多数の条件付きテストに分岐予測ロジックが必要でした。コード内。

8ビット整数のベクトルを二重ベクトルの添字として使用するスキームに決めました。これを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の中間の倍数が関心の1/8パーセントに相当する可能性があります。最適化に1年以上費やしたプログラムで、午後に達成されたパフォーマンスの著しい向上でした。

私もJerryに同意します。私の経験でもありますが、コードを命令キャッシュに傾けることは、データキャッシュの最適化ほど成功していません。これは、AMDの一般的なキャッシュがIntelの個別のデータキャッシュと命令キャッシュほど有用ではないと思う理由の1つです。 IE：あまり役に立たないので、命令がキャッシュをいっぱいにしたくない。これは、CISC命令セットが元々CPUとメモリの速度の大きな違いを補うために作成されたためであり、80年代後半の異常を除いて、ほとんど常にそうでした。

データキャッシュを優先し、命令キャッシュを節約するために使用するもう1つのお気に入りの手法は、構造定義で多くのビット整数を使用し、一般的に可能な限り小さいデータサイズを使用することです。 4ビットのintをマスクして年の月を保持したり、9ビットを使用して年の日付などを保持するには、CPUがマスクを使用してビットが使用しているホスト整数をマスクする必要があります。データ、キャッシュとバスのサイズを効果的に増やしますが、より多くの命令が必要です。この手法は、合成ベンチマークではうまく機能しないコードを生成しますが、

ほとんどの場合、これはこのトピックの正義を行う時間を得るまでプレースホルダーとして機能しますが、私は真に画期的なマイルストーンであると考えるもの、つまり新しいIntel Hazwellマイクロプロセッサに専用のビット操作命令を導入したいと思います。

ここでStackOverflowにコードを書いて、PCの導入から30年以上経った4096ビット配列のビットを反転させると、マイクロプロセッサがビットにあまり注意を払わず、リソースを投入しなかったため、変わることを願っています。特に、まず最初に、bool型が、現在のとんでもないほど無駄なバイトではなく、C / C ++の実際のビットデータ型になることを楽しみにしています。

Hazwellの新しいビット操作手順

更新：2013年12月29日

最近、ミリ秒単位でシステム上の512の異なるリソースユーザーの要求を追跡するリングバッファーを最適化する機会がありました。ミリ秒ごとに起動するタイマーがあり、最新のスライスのリソース要求の合計を加算し、1,000番目のタイムスライスの要求を減算します。

Head、Tailベクトルはメモリ内で互いに隣り合っていました。ただし、最初にHead、次にTailがラップされ、配列の先頭から戻ったときを除きます。ただし、（ローリング）サマリースライスは、静的に割り当てられた固定の配列であり、特にどちらにも近くなく、ヒープからも割り当てられませんでした。

これについて考え、コードを研究して、いくつかの詳細に注目しました。

  1. 入ってくる要求は、HeadスライスとSummaryスライスに同時に追加され、コードの隣接する行で互いに隣り合わせになりました。

  2. タイマーが作動すると、TailがSummaryスライスから差し引かれ、予想どおり、結果がSummaryスライスに残されました

  3. タイマーが作動したときに呼び出される2番目の関数は、リングにサービスを提供するすべてのポインターを進めました。特に.... 頭が尾を上書きし、それにより同じ記憶場所を占有した 新しいTailは次の512個のメモリロケーションを占有、またはラップ

  4. ユーザーは、管理する要求の数を512から4098まで、またはそれ以上に柔軟にしたいと考えていました。これを行うための最も堅牢で馬鹿な方法は、1,000個のタイムスライスとサマリースライスの両方を1つの連続したメモリブロックとして割り当てて、サマリースライスが異なる長さになることを不可能にすることだと感じました他の1,000個のタイムスライスよりも少ない。

  5. 上記のことを考えると、Summaryスライスを1つの場所に残すのではなく、「ローミング」したほうがパフォーマンスが向上するのではないかと思い始めました。ヘッドとテールの間にあるため、新しい要求を追加するために常にヘッドのすぐ隣にあり、タイマーが作動し、サマリーからテールの値を減算する必要があるときは、テールのすぐ隣にありました。

私はこれを正確に行いましたが、その過程でいくつかの追加の最適化が見つかりました。ローリングサマリーを計算するコードを変更して、サマリースライスではなくテールに結果を残すようにしました。どうして？次の関数はmemcpy（）を実行して、Tailが占有しているメモリにSummaryスライスを移動するためです。 （奇妙だが真実、それがラップするとき、テールはリングの終わりまでヘッドを導く）。合計の結果をTailに残すことで、memcpy（）を実行する必要はなく、pTailをpSummaryに割り当てるだけでした。

同様の方法で、新しいヘッドが現在の古いSummaryスライスの古いメモリ位置を占有したため、pSummaryをpHeadに割り当て、memsetを使用してすべての値をゼロにゼロにしました。

リングの最後（実際にはドラム、512トラック幅）への道をリードしたのはテールでしたが、

ほとんどのC / C ++コンパイラは、「速度」よりもサイズを最適化することを好みます。つまり、一般に、キャッシュ効果のため、小さなコードは展開されたコードよりも高速に実行されます。

私があなただったら、コードのどの部分がホットスポットであるかを確認します。これを定義します

  • 関数呼び出しを含まないタイトループ。関数呼び出しがある場合、PCはその関数のほとんどの時間をその関数に費やしているため、
  • 実行時間のかなりの部分（＆gt; = 10％など）を占め、プロファイラーから判断できます。 （スタックを手動でサンプリングするだけです。）

このようなホットスポットがある場合、キャッシュに収まるはずです。どうやってそれをするように言っているのかわかりませんが、それは自動だと思います。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top