7

私は面接のために勉強していて、キャッシングについての記憶をリフレッシュしたいと思っています。CPU に LRU 置換ポリシーを備えたキャッシュがある場合、それは実際にどのようにチップに実装されているのでしょうか? 各キャッシュ ラインはタイムスタンプ ティックを格納しますか?

また、両方の CPU が 1 つのアドレスに同時に書き込むデュアル コア システムではどうなりますか?

4

2 に答える 2

14

ウェイが 2 つしかない従来のキャッシュの場合、セットごとに 1 ビットを使用して LRU を追跡できます。ヒットしたセットへのアクセスでは、ヒットしなかったウェイにビットをセットできます。

より大きな結合性では、状態の数が劇的に増加します: 方法の数の階乗です。したがって、4 ウェイ キャッシュには 24 の状態があり、セットごとに 5 ビットが必要であり、8 ウェイ キャッシュには 40,320 の状態があり、セットごとに 16 ビットが必要です。ストレージのオーバーヘッドに加えて、値を更新する際のオーバーヘッドも大きくなります。

4 ウェイ キャッシュの場合、次のような状態のエンコードは、適切に機能するように思われます: 最近使用されたウェイ番号の 2 ビット、次に最近使用されたウェイ番号の 2 ビット、および上位または上位のいずれかを示すビット。番号の小さい方が最近使用されました。

  • MRU ヒットでは、状態は変更されません。
  • 次の MRU ヒットでは、2 つのビット フィールドが交換されます。
  • 他のヒットでは、他の 2 つのウェイの番号がデコードされ、ヒットしたウェイの番号が最初の 2 ビット部分に配置され、以前の MRU ウェイ番号が 2 番目の 2 ビット部分に配置されます。最後のビットは、次の MRU ウェイ番号がヒットしなかった最近使用されていないウェイよりも大きいか小さいかに基づいて設定されます。
  • ミスの場合、LRU ヒットが発生したかのように状態が更新されます。

LRU 追跡にはこのようなオーバーヘッドがあるため、二分木疑似 LRU のような単純なメカニズムがよく使用されます。ヒットすると、関連するウェイの半分がヒットしたツリーの各分岐部分を更新するだけです。2 乗のウェイ数 W の場合、バイナリ ツリーの pLRU キャッシュは、セットごとに W-1 ビットの状態を持ちます。 . 8 ウェイ キャッシュ (3 レベルのバイナリ ツリーを使用) のウェイ 6 でヒットすると、ツリーのベースのビットがクリアされ、ウェイの下半分 (0、1、2、3) が少ないことが示されます。最近使用された場合、次のレベルで上位ビットをクリアして、それらのウェイの下半分 (4,5) が最近使用されていないことを示し、最終レベルで上位ビットを設定して、それらのウェイの上半分 (7) が使用されたことを示します。最近はあまり使用されていません。更新するためにこの状態を読み取る必要がないため、ハードウェアを簡素化できます。

さまざまな方法でさまざまなハッシュ関数を使用する歪んだ結合性については、省略されたタイム スタンプのようなものが提案されています (たとえば、"Analysis and Replacement for Skew-Associative Caches", Mark Brehob et al., 1997)。サイクル カウントよりもミス カウンターを使用する方が適していますが、基本的な考え方は同じです。

2 つのコアが同時に同じキャッシュ ラインに書き込もうとした場合に何が起こるかに関して、これは、ある時点で 1 つの L1 キャッシュのみがキャッシュ ラインを排他状態にできるようにすることで処理されます。効果的に競合が発生し、1 つのコアが排他的アクセスを取得します。書き込みコアの 1 つだけが既に共有状態のキャッシュ ラインを持っている場合、おそらく競合に勝つ可能性が高くなります。キャッシュ ラインが共有状態の場合、キャッシュは、キャッシュ ラインの他の潜在的な所有者に無効化要求を送信するだけで済みます。キャッシュ ラインが存在しない場合、書き込みは通常、データのキャッシュ ラインを要求するだけでなく、排他的状態を要求する必要があります。

異なるコアによる同じキャッシュ ラインへの書き込み (同じ特定のアドレスへの書き込み、またはフォールス シェアリングの場合はデータ ライン内の別のアドレスへの書き込み) は、異なるコアがキャッシュを無効にする「キャッシュ ライン ピンポン」を引き起こす可能性があります。他のキャッシュのラインを使用して (書き込みを実行するために) 排他的アクセスを取得し、キャッシュ ラインがピンポン球のようにシステム内を跳ね回るようにします。

于 2014-05-03T22:39:09.223 に答える
-1

さまざまなページ置換スキームについて説明している優れたスライド デッキページ置換アルゴリズムがあります。また、mxm 行列を使用した LRU の実装についても非常によく説明されています。

于 2014-09-14T17:02:41.457 に答える