キャッシュ包含ポリシー

マルチレベルキャッシュは、あるキャッシュの内容が他のレベルのキャッシュに存在するかどうかによって、様々な設計が可能です。上位レベルキャッシュのすべてのブロックが下位レベルキャッシュにも存在する場合、下位レベルキャッシュは上位レベルキャッシュを包含すると言われています。下位レベルキャッシュに上位レベルキャッシュに存在しないブロックのみが含まれている場合、下位レベルキャッシュは上位レベルキャッシュを排他的であると言われています。下位レベルキャッシュの内容が厳密に上位レベルキャッシュを包含も排他もしない場合、それは非包含非排他的（NINE）キャッシュと呼ばれます。^[1]^[2]

包括的政策

2 レベルのキャッシュ階層の例を考えてみましょう。この階層では、L2 は L1 を含むか、含まないか、または 9 になります。L2 が L1 を含む場合を考えます。プロセッサからブロック X の読み取り要求があったとします。ブロックが L1 キャッシュで見つかった場合、データは L1 キャッシュから読み取られ、プロセッサに返されます。ブロックが L1 キャッシュに見つからないが、L2 キャッシュに存在する場合、キャッシュブロックは L2 キャッシュからフェッチされ、L1 に配置されます。これによりブロックが L1 から追い出される場合は、L2 は関与しません。ブロックが L1 にも L2 にも見つからない場合は、メインメモリからフェッチされ、L1 と L2 の両方に配置されます。ここで、L2 からの追い出しがあった場合、L2 キャッシュは L1 キャッシュに無効化を送り返すため、包含は違反されません。

図 1 に示すように、最初は L1 キャッシュと L2 キャッシュの両方が空であるとします (a)。プロセッサが読み取り X 要求を送信すると仮定します。この要求は L1 と L2 の両方でミスとなるため、(b) に示すように、ブロックはメインメモリから L1 と L2 の両方に持ち込まれます。次に、プロセッサが読み取り Y 要求を発行すると仮定します。この要求は L1 と L2 の両方でミスとなります。したがって、(c) に示すように、ブロック Y は L1 と L2 の両方に配置されます。ブロック X を L1 から追い出す必要がある場合、(d) に示すように、ブロック X は L1 からのみ削除されます。ブロック Y を L2 から追い出す必要がある場合、(e) に示すように、ブロック Y は L1 に無効化要求を送り返し、したがってブロック Y は L1 から追い出されます。

包含関係が成立するためには、特定の条件を満たす必要があります。L2の結合度は、セット数に関わらず、L1の結合度以上である必要があります。L2のセット数は、L2の結合度に関わらず、L1のセット数以上である必要があります。L1からのすべての参照情報は、L2に渡され、置換ビットを更新できるようにします。

インクルーシブキャッシュの一例としては、4x256KBのL2キャッシュと8MB（含む）のL3キャッシュを備えたIntelクアッドコアプロセッサがあります。 ^[3]

独占ポリシー

L2がL1を排他的に扱うケースを考えてみましょう。プロセッサからブロックXの読み取り要求があったとします。ブロックがL1キャッシュ内に見つかった場合、データはL1キャッシュから読み出され、プロセッサに返されます。ブロックがL1キャッシュ内に見つからず、L2キャッシュ内に存在する場合、キャッシュブロックはL2キャッシュからL1キャッシュに移動されます。これによりL1からブロックが追い出される場合は、追い出されたブロックはL2に配置されます。これがL2にデータが配置される唯一の方法です。ここで、L2は犠牲キャッシュのように動作します。ブロックがL1にもL2にも見つからない場合、メインメモリから取得され、L2ではなくL1に配置されます。

図2に示すように、最初はL1キャッシュとL2キャッシュの両方が空であると仮定します(a)。プロセッサが読み取りX要求を送信したと仮定します。この要求はL1とL2の両方でミスとなり、(b)に示すようにブロックはメインメモリからL1に読み込まれます。次に、プロセッサは再び読み取りY要求を発行しますが、これはL1とL2の両方でミスとなります。そのため、(c)に示すようにブロックYはL1に配置されます。ブロックXをL1から追い出す必要がある場合、(d)に示すようにブロックXはL1から削除され、L2に配置されます。

排他キャッシュの例としては、L1キャッシュを除く512KB（コアあたり）のL2キャッシュを搭載したAMD Opteronが挙げられます。 ^[3]

9つのポリシー

L2 が L1 を包含せず、排他的でない場合を考えてみましょう。プロセッサからブロック X の読み取り要求があったとします。ブロックが L1 キャッシュ内に見つかった場合、データは L1 キャッシュから読み出され、プロセッサに返されます。ブロックが L1 キャッシュ内に見つからず、L2 キャッシュ内に存在する場合、キャッシュブロックは L2 キャッシュからフェッチされ、L1 に配置されます。これによりブロックが L1 から追い出される場合は、包含ポリシーの場合と同様に、L2 は関与しません。ブロックが L1 と L2 の両方に見つからない場合は、メインメモリからフェッチされ、L1 と L2 の両方に配置されます。ここで、L2 からの追い出しがあった場合、包含ポリシーとは異なり、バック無効化は発生しません。

図3に示すように、最初はL1キャッシュとL2キャッシュの両方が空であると仮定します(a)。プロセッサが読み取りX要求を送信したと仮定します。この要求はL1とL2の両方でミスとなり、(b)に示すように、ブロックはメインメモリからL1とL2の両方に取り込まれます。次に、プロセッサは再び読み取りY要求を発行しますが、これはL1とL2の両方でミスとなります。そのため、(c)に示すように、ブロックYはL1とL2の両方に配置されます。ブロックXをL1から追い出す必要がある場合、(d)に示すように、L1からのみ削除されます。ブロックYをL2から追い出す必要がある場合、(e)に示すように、L2からのみ削除されます。

非包括的非排他的キャッシュの例としては、6MB（共有）の非包括的L3キャッシュを備えたAMD Opteronが挙げられます。 ^[3]

比較

包括的ポリシーのメリットは、プロセッサごとにプライベートキャッシュを持つ並列システムにおいて、キャッシュミスが発生した場合、他のピアキャッシュでブロックがチェックされることです。下位レベルキャッシュが上位レベルキャッシュを包含し、下位レベルキャッシュでミスが発生した場合、上位レベルキャッシュを検索する必要がありません。これは、排他的キャッシュやNINEキャッシュと比較して、包括的キャッシュのミスレイテンシが短いことを意味します。 ^[1]

包括的ポリシーの欠点は、キャッシュの固有メモリ容量が下位レベルのキャッシュによって決まることです。排他的キャッシュの場合とは異なり、排他的キャッシュでは、固有メモリ容量は階層内のすべてのキャッシュの合計容量になります。^[4]下位レベルキャッシュのサイズが小さく、上位レベルキャッシュのサイズと同程度である場合、包括的キャッシュでは無駄なキャッシュ容量が多くなります。排他的キャッシュは固有メモリ容量が大きいですが、ミスが発生した場合にのみ新しいブロックで満たされる NINE キャッシュと比較して、新しいブロックが満たされる速度 (上位レベルキャッシュのミスの速度に等しい) が高いため、より多くの帯域幅を使用します。したがって、包括的キャッシュ、排他的キャッシュ、および NINE キャッシュの選択を活用する際には、コストと利益の相対的な評価を行う必要があります。

値の包含：ブロックが上位レベルキャッシュと下位レベルキャッシュの両方にキャッシュされている場合、包含は維持されますが、ブロックのデータ値が同じである必要はありません。ただし、データ値が同じであれば、値の包含は維持されます。^[1]これは、使用されている書き込みポリシーに依存します。ライトバックポリシーでは、上位レベルキャッシュのブロックに加えられた変更が下位レベルキャッシュに通知されないためです。ただし、ライトスルーキャッシュの場合は、このような問題はありません。

参考文献

^ abc Solihin, Yan (2016).並列マルチコアアーキテクチャの基礎. Chapman and Hall/CRC. pp. 146– 150. ISBN 9781482211184。
^ Culler, David; Gupta, Anoop; Singh, Jaswinder Pal (1999).並列コンピュータアーキテクチャ：ハードウェア／ソフトウェアアプローチ. サンフランシスコ: Morgan Kaufmann Publishers. pp. 369–372. ISBN 1558603433。
^ abc 「x86-64マルチコアSMPシステムにおけるキャッシュアーキテクチャとコヒーレンシプロトコルの比較」第42回国際マイクロアーキテクチャシンポジウム議事録。MICRO'09。
^ Ying Zheng; Davis, BT; Jordan, M. (2004). 「排他的キャッシュ階層の性能評価」. IEEE International Symposium on - ISPASS Performance Analysis of Systems and Software, 2004. pp. 89– 96. doi :10.1109/ISPASS.2004.1291359. ISBN 0-7803-8385-0. S2CID 10784219。

[:1-1] Solihin, Yan (2016).並列マルチコアアーキテクチャの基礎. Chapman and Hall/CRC. pp. 146– 150. ISBN 9781482211184。

[2] Culler, David; Gupta, Anoop; Singh, Jaswinder Pal (1999).並列コンピュータアーキテクチャ：ハードウェア／ソフトウェアアプローチ. サンフランシスコ: Morgan Kaufmann Publishers. pp. 369–372. ISBN 1558603433。

[:0-3] 「x86-64マルチコアSMPシステムにおけるキャッシュアーキテクチャとコヒーレンシプロトコルの比較」第42回国際マイクロアーキテクチャシンポジウム議事録。MICRO'09。

[4] Ying Zheng; Davis, BT; Jordan, M. (2004). 「排他的キャッシュ階層の性能評価」. IEEE International Symposium on - ISPASS Performance Analysis of Systems and Software, 2004. pp. 89– 96. doi :10.1109/ISPASS.2004.1291359. ISBN 0-7803-8385-0. S2CID 10784219。