19

私は、一定数のデータ キャッシュ ミスと命令キャッシュ ミスを生成する任務を負っています。問題なくデータキャッシュ部分を処理できました。

そのため、命令キャッシュ ミスを生成する必要があります。これらの原因が何かわかりません。誰かがそれらを生成する方法を提案できますか?

LinuxでGCCを使用しています。

4

5 に答える 5

19

人々が説明したように、命令キャッシュ ミスは概念的にはデータ キャッシュ ミスと同じです - 命令はキャッシュにありません。これは、プロセッサのプログラム カウンタ (PC) が、キャッシュにロードされていない場所にジャンプしたか、キャッシュがいっぱいになったためにフラッシュ アウトされた場所にジャンプし、そのキャッシュ ラインが削除対象として選択された (通常は最も古い使用済み）。

データキャッシュミスを強制するよりも、命令ミスを強制するのに十分なコードを手作業で生成するのは少し難しいです。

少しの労力で多くのコードを取得する 1 つの方法は、ソース コードを生成するプログラムを作成することです。

たとえば、巨大な switch ステートメント (C 言語) を使用して関数を生成するプログラムを作成します [警告、テストされていません]:

printf("void bigswitch(int n) {\n    switch (n) {");
for (int i=1; i<100000; ++i) {
    printf("        case %d: n += %d;\n", n, n+i/2);
}
printf("    }\n    return n;}\n");

次に、これを別の関数から呼び出すことができ、キャッシュ ラインに沿ったジャンプの大きさを制御できます。

switch ステートメントのプロパティは、コードを強制的に逆方向に実行したり、パラメーターを選択してパターンで実行したりできることです。そのため、プリフェッチおよび予測メカニズムを使用したり、それらに対して作業を試みることができます。

同じ手法を適用して多くの関数を生成し、キャッシュを自由に「破棄」できるようにすることもできます。したがって、bigswitch001、bigswitch002 などがあるかもしれません。生成したスイッチを使用してこれを呼び出すこともできます。

各関数のサイズを (およそ) i-cache ラインの数にすることができ、さらにキャッシュに収まるよりも多くの関数を生成できる場合、命令キャッシュ ミスの生成の問題を制御しやすくなります。

アセンブラーをダンプする (gcc -S を使用) か、.o ファイルを objdump することにより、関数、switch ステートメント全体、または switch ステートメントの各レッグがどれだけ大きいかを正確に確認できます。case:したがって、ステートメントの数を調整することで、関数のサイズを「調整」できます。bigswitchNNN() のパラメータを適切に選択することで、ヒットするキャッシュ ラインの数を選択することもできます。

于 2012-03-20T23:58:28.390 に答える
10

ここで述べた他のすべての方法に加えて、命令キャッシュ ミスを強制するもう 1 つの非常に信頼できる方法は、自己修正コードを使用することです。

メモリ内のコードのページに書き込むと (これを許可するように OS を構成したと仮定して)、もちろん命令キャッシュの対応する行はすぐに無効になり、プロセッサはそれを強制的に再フェッチします。

ちなみに、icache ミスを引き起こすのは分岐予測ではなく、単に分岐です。最近実行されていない命令をプロセッサが実行しようとするたびに、命令キャッシュが失われます。最新の x86 は、命令を順番にプリフェッチするのに十分スマートであるため、1 つの命令から次の命令へと普通に進むだけで icache を見逃す可能性はほとんどありません。ただし、分岐 (条件付きまたはその他) は、順不同で新しいアドレスにジャンプします。新しい命令アドレスが最近実行されておらず、既に実行していたコードの近くにない場合は、キャッシュが不足している可能性があり、プロセッサは停止してメイン RAM から命令が来るのを待つ必要があります。これはまさにデータキャッシュのようなものです。

一部の非常に最新のプロセッサ (最近の i7) は、コード内の次の分岐を調べて、可能性のあるターゲットをプリフェッチする icache を開始できますが、多くのプロセッサ (ビデオ ゲーム コンソール) はできません。メイン RAM から icache へのデータのフェッチは、パイプラインの「命令フェッチ」ステージとはまったく異なります。これは、分岐予測に関するものです。

「命令フェッチ」は CPU の実行パイプラインの一部であり、オペコードを icache から CPU の実行ユニットに持ち込むことを指し、そこでデコードと作業を開始できます。これは、「命令キャッシュ」フェッチとは異なります。これは、何サイクルも前に発生する必要があり、バスを介していくつかのバイトを送信するようにメイン メモリ ユニットに要求するキャッシュ回路が含まれます。1 つ目は、CPU パイプラインの 2 つのステージ間の相互作用です。2 つ目は、パイプラインとメモリ キャッシュおよびメイン RAM の間の相互作用であり、これははるかに複雑な回路です。名前は紛らわしいほど似ていますが、まったく別の操作です。

したがって、命令キャッシュ ミスを引き起こすもう 1 つの方法は、コード セグメントが巨大になるように、非常に大きな関数を大量に作成 (または生成) することです。次に、ある関数から別の関数を乱暴に呼び出します。そのため、CPU の観点からは、メモリ全体でクレイジーな GOTO を実行していることになります。

于 2012-03-21T00:03:57.473 に答える
3

プロジェクトでは、ターゲット システムのキャッシュ ハードウェアを認識する必要があります。これには、キャッシュ サイズ (キャッシュ全体のサイズ)、キャッシュ ライン サイズ (キャッシュ可能な最小エンティティ)、連想性、および書き込みと置換のポリシーが含まれますが、これらに限定されません。キャッシュのパフォーマンスをテストするために設計された非常に優れたアルゴリズムは、これらすべてを考慮に入れる必要があります。すべてのキャッシュ構成を効果的にテストする単一の一般的なアルゴリズムは存在しないためです。特定のターゲットのキャッシュ アーキテクチャに関する十分な詳細が与えられた適切なテスト ルーチン。それにもかかわらず、以下の私の提案は非常に優れた一般的なケースのテストだと思いますが、最初に言及したかったのは次のとおりです。

「大きな整数配列 a[100].... [これは] 2 つの要素間の距離がキャッシュ ラインのサイズよりも大きくなるような方法で要素にアクセスする」を使用する実用的なデータ キャッシュ テストがあるとあなたは述べています。 (私の場合は 32 バイト)」テスト アルゴリズムが機能することをどのように判断したのか、他の刺激によって引き起こされたミスとは対照的に、アルゴリズムの結果であるデータ キャッシュ ミスの数をどのように判断したのか、興味があります。実際、100*sizeof(int) のテスト配列では、現在のほとんどの汎用プラットフォームで、テスト データ領域の長さは 400 バイトしかありません (64 ビット プラットフォームの場合はおそらく 800 バイト、プラットフォームの場合は 200 バイト)。 16 ビット プラットフォームを使用しています)。大部分のキャッシュ アーキテクチャでは、テスト配列全体が何倍もキャッシュに収まります。

命令キャッシュに関して: 他の人は、大規模な switch()-case ステートメントを使用するか、異なる場所にある関数への関数呼び出しを使用することを提案しています。どちらも、コードのサイズを慎重に (そして私は慎重に) 設計しない限り、予測通りに効果的ではありません。別々に配置された機能のそれぞれのケース ブランチまたは場所とサイズ。この理由は、メモリ全体のバイトが完全に予測可能なパターンでキャッシュに「折り畳まれる」(技術的には「互いにエイリアス」になる) ためです。switch()-case ステートメントの各分岐で命令の数を慎重に制御すると、テストでどこかを取得できる可能性がありますが、それぞれに無差別に大量の命令を投入するだけでは、

あなたはアセンブリ コードにあまり精通していないと思いますが、ここで私を信じなければなりません。このプロジェクトはそれを求めて叫んでいます。私は必要のないところでアセンブリ コードを使用する人間ではありません。可能な限り、STL とポリモーフィックな ADT 階層を使用して、OO C++ でプログラミングすることを強く好みます。しかし、あなたの場合、それを行うための絶対確実な方法は他にありません.アセンブリは、指定されたキャッシュヒット率を効果的に生成できるようにするために本当に必要なコードブロックサイズを完全に制御します. アセンブリの専門家になる必要はなく、C 言語のプロローグとエピローグ (Google で「C 呼び出し可能なアセンブリ関数」を意味します) を実装するために必要な命令と構造を学ぶ必要さえないでしょう。アセンブリ関数の extern “C” 関数プロトタイプをいくつか書きます。そして離れて行きます。何らかのアセンブリを学習したい場合は、アセンブリ関数に入れるテスト ロジックが多いほど、テストに課す「ハイゼンベルグ効果」が少なくなります。これは、テスト制御命令の行き先を慎重に制御できるためです (したがって、命令キャッシュへの影響)。しかし、テストコードの大部分については、一連の「nop」命令を使用するだけでよく (命令キャッシュは、含まれている命令をあまり気にしません)、おそらくプロセッサの「return」命令を各命令の最後に配置するだけです。コードのブロック。

ここで、命令キャッシュが 32K であるとしましょう (今日の基準ではかなり小さいですが、多くの組み込みシステムではまだ一般的です)。キャッシュが 4-way associative の場合、内容が同一の 8K アセンブリ関数を 8 つ作成できます (64K 相当のコードであり、キャッシュのサイズの 2 倍であることに気付いたと思います)。その大部分は単なる NOP 命令の集まりです。 . それらをすべてメモリ内で次々に分類します (通常は、ソース ファイルでそれぞれを 1 つずつ定義するだけです)。次に、慎重に計算されたシーケンスを使用してテスト コントロール関数からそれらを呼び出して、必要なキャッシュ ヒット率を生成します (関数はそれぞれ完全な 8K の長さであるため、かなり粗い粒度で)。1 番目、2 番目、3 番目、4 番目の関数を次々と呼び出すと、キャッシュ全体がそれらのテスト関数のコードでいっぱいになったことがわかります。この時点でそれらのいずれかを再度呼び出しても、命令キャッシュ ミスにはなりません (テスト制御関数自体の命令によって追い出された行を除く) が、他のいずれか (5 番目、6 番目、7 番目または 8 番目; 5 番目を選択) を選択すると、他の 1 つが削除されます (ただし、どれが削除されるかは、キャッシュの置換ポリシーによって異なります)。この時点で、あなたが呼び出して他の人を追い出さないことを知っているのは、あなたが今呼んだもの（5番目のもの）だけであり、あなたが呼び出して、あなたが別のものを追い出すことを知っている唯一のものは、あなたがまだ持っていないものです。呼ばれる（6番目、7番目、または8番目）。これを簡単にするには、テスト関数の数と同じサイズの静的配列を維持するだけです。エビクションをトリガーするには、配列の最後で関数を呼び出し、そのポインターを配列の先頭に移動し、他のポインターを下に移動します。エビクションをトリガーしないようにするには、最後に呼び出したもの (配列の一番上にあるもの。この場合、他のものを下にシフトしないようにしてください!) を呼び出します。より細かい粒度が必要な場合は、これにいくつかのバリエーションを加えます (おそらく、16 個の個別の 4K アセンブリ関数を作成します)。もちろん、これはすべて、テスト制御ロジックのサイズがキャッシュの各連想「ウェイ」のサイズに比べて取るに足らないものであることに依存しています。より積極的な制御を行うには、テスト制御ロジックをテスト関数自体に配置できますが、完全な制御を行うには、内部分岐なしで完全に制御ロジックを設計する必要があります (各アセンブリ関数の最後で分岐するだけです)。それはおそらく物事を複雑にしすぎているので、ここでやめます。この場合、他のものを下にシフトしないようにしてください!)。より細かい粒度が必要な場合は、これにいくつかのバリエーションを加えます (おそらく、16 個の個別の 4K アセンブリ関数を作成します)。もちろん、これはすべて、テスト制御ロジックのサイズがキャッシュの各連想「ウェイ」のサイズに比べて取るに足らないものであることに依存しています。より積極的な制御を行うには、テスト制御ロジックをテスト関数自体に配置できますが、完全な制御を行うには、内部分岐なしで完全に制御ロジックを設計する必要があります (各アセンブリ関数の最後で分岐するだけです)。それはおそらく物事を複雑にしすぎているので、ここでやめます。この場合、他のものを下にシフトしないようにしてください!)。より細かい粒度が必要な場合は、これにいくつかのバリエーションを加えます (おそらく、16 個の個別の 4K アセンブリ関数を作成します)。もちろん、これはすべて、テスト制御ロジックのサイズがキャッシュの各連想「ウェイ」のサイズに比べて取るに足らないものであることに依存しています。より積極的な制御を行うには、テスト制御ロジックをテスト関数自体に配置できますが、完全な制御を行うには、内部分岐なしで完全に制御ロジックを設計する必要があります (各アセンブリ関数の最後で分岐するだけです)。それはおそらく物事を複雑にしすぎているので、ここでやめます。もちろん、これはすべて、テスト制御ロジックのサイズがキャッシュの各連想「ウェイ」のサイズに比べて取るに足らないものであることに依存しています。より積極的な制御を行うには、テスト制御ロジックをテスト関数自体に配置できますが、完全な制御を行うには、内部分岐なしで完全に制御ロジックを設計する必要があります (各アセンブリ関数の最後で分岐するだけです)。それはおそらく物事を複雑にしすぎているので、ここでやめます。もちろん、これはすべて、テスト制御ロジックのサイズがキャッシュの各連想「ウェイ」のサイズに比べて取るに足らないものであることに依存しています。より積極的な制御を行うには、テスト制御ロジックをテスト関数自体に配置できますが、完全な制御を行うには、内部分岐なしで完全に制御ロジックを設計する必要があります (各アセンブリ関数の最後で分岐するだけです)。それはおそらく物事を複雑にしすぎているので、ここでやめます。

すぐに使用でき、テストされていないため、x86 のアセンブリ関数の 1 つの全体は次のようになります。

myAsmFunc1:
   nop
   nop
   nop  # ...exactly enough NOPs to fill one "way" of the cache
   nop  # minus however many bytes a "ret" instruction is (1?)
   .
   .
   .
   nop
   ret  # return to the caller

PowerPC の場合、次のようになります (これもテストされていません)。

myAsmFunc1:
   nop
   nop
   nop   # ...exactly enough NOPs to fill one "way" of the cache
   .     # minus 4 bytes for the "blr" instruction.  Note that
   .     # on PPC, all instructions (including NOP) are 4 bytes.
   .
   nop
   blr   # return to the caller

どちらの場合も、これらの関数を呼び出すための C++ および C プロトタイプは次のようになります。

extern "C" void myAsmFunc1();    // Prototype for calling from C++ code
void myAsmFunc1(void);           /* Prototype for calling from C code */

コンパイラによっては、アセンブリ コード自体の関数名の前にアンダースコアが必要になる場合があります (ただし、C++/C 関数プロトタイプでは必要ありません)。

于 2012-03-21T01:27:39.190 に答える
0

命令キャッシュ ミスの場合は、離れたコード セグメントを実行する必要があります。ロジックを複数の関数呼び出しに分割することは、そのための 1 つの方法です。

于 2012-03-20T20:01:52.870 に答える
-1

予測不可能な条件（入力データやランダムに生成されたデータなど）でのif elseのチェーンで、ifの場合とelseの場合の両方で、キャッシュラインよりもサイズが大きい命令の量が含まれます。

于 2012-03-20T19:59:03.757 に答える