MESIプロトコル

MESIプロトコルは無効化ベースのキャッシュ コヒーレンス プロトコルであり、ライトバック キャッシュをサポートする最も一般的なプロトコルの 1 つです。イリノイ大学アーバナ シャンペーン校で開発されたため、イリノイ プロトコルとも呼ばれています。^{[1]ライトバック キャッシュは、}ライトスルー キャッシュで一般的に無駄になる帯域幅を大幅に節約できます。ライトバック キャッシュには常にダーティ状態が存在し、これはキャッシュ内のデータがメイン メモリ内のデータと異なることを示します。イリノイ プロトコルでは、ブロックが別のキャッシュに存在する場合、ミス時にキャッシュ間転送が必要です。このプロトコルは、MSI プロトコルと比較してメイン メモリ トランザクションの数を減らします。これにより、パフォーマンスが大幅に向上します。^[2]

頭字語 MESI の文字は、キャッシュ ラインをマークできる 4 つの排他的状態を表します (2 つの追加ビットを使用してエンコードされます)。

修正版（M）

キャッシュ ラインは現在のキャッシュにのみ存在し、ダーティです。つまり、メイン メモリの値から変更されています (M 状態) 。キャッシュは、(もはや有効ではない) メイン メモリ状態のその他の読み取りを許可する前に、将来のある時点でデータをメイン メモリに書き戻す必要があります。書き戻しにより、ラインは共有状態 (S) に変更されます。

独占（E）

キャッシュ ラインは現在のキャッシュにのみ存在しますが、クリーンであり、メイン メモリと一致します。読み取り要求に応じて、いつでも Shared 状態に変更される可能性があります。または、書き込み時に Modified 状態に変更される可能性もあります。

共有（S）

このキャッシュ ラインがマシンの他のキャッシュに格納される可能性があり、クリーンである(メイン メモリに一致する) ことを示します。このラインはいつでも破棄される (無効状態に変更される) 可能性があります。

無効（I）

このキャッシュ ラインが無効 (未使用) であることを示します。

任意のキャッシュ ペアの場合、特定のキャッシュ ラインの許可される状態は次のとおりです。

ブロックが M (変更済み) または E (排他的) としてマークされている場合、他のキャッシュ内のブロックのコピーは I (無効) としてマークされます。

MESI プロトコルは、2 つの刺激に基づいて 1 つの状態から別の状態に遷移する 有限状態マシンによって定義されます。

最初の刺激は、プロセッサ固有の読み取りおよび書き込み要求です。たとえば、プロセッサ P1 のキャッシュにブロック X があり、プロセッサからそのブロックの読み取りまたは書き込み要求があります。

2 番目の刺激は、プロセッサを接続するバスを通じて与えられます。特に、「バス側要求」は、キャッシュ ブロックまたはキャッシュに更新されたデータを持たない他のプロセッサから来ます。バス要求は、すべてのバス トランザクションを監視する Snoopers [4] の助けを借りて監視され ます^。

プロセッサ要求とバス側要求のさまざまなタイプを次に示します。

キャッシュへのプロセッサ要求には次の操作が含まれます。

1. PrRd: プロセッサがキャッシュ ブロックの読み取りを要求します。
2. PrWr: プロセッサがキャッシュブロックの書き込みを要求します

バス側の要求は次のとおりです。

1. BusRd:別のプロセッサによって要求されたキャッシュ ブロックへの読み取り要求があることを示すスヌープ要求
2. BusRdX:ブロックをまだ持っていない別のプロセッサによって要求されたキャッシュ ブロックへの書き込み要求があることを示すスヌープされた要求。
3. BusUpgr: すでにそのキャッシュ ブロックを自身のキャッシュ内に持っている別のプロセッサによって要求されたキャッシュ ブロックへの書き込み要求があることを示すスヌープされた要求。
4. フラッシュ: キャッシュ ブロック全体が別のプロセッサによってメイン メモリに書き戻されることを示すスヌープされた要求。
5. FlushOpt: キャッシュ ブロック全体が別のプロセッサに供給するためにバス上にポストされることを示すスヌープされた要求 (キャッシュ間転送)。

(このようなキャッシュ間転送では、メイン メモリからブロックを取得するレイテンシがキャッシュ間転送よりも大きい場合、読み取りミスレイテンシを削減できます。これは、バス ベースのシステムで一般的に当てはまります。 )

スヌーピング操作: スヌーピング システムでは、バス上のすべてのキャッシュがそのバス上のすべてのトランザクションを監視します。すべてのキャッシュには、保存されている物理メモリのすべてのブロックの共有ステータスのコピーがあります。ブロックの状態は、使用されているプロトコルの状態図に従って変更されます。(MESI 状態図については、上の画像を参照してください)。バスには両側にスヌーパーがあります。

1. プロセッサ/キャッシュ側をスヌーパーします。
2. メモリ側のスヌーピング機能はメモリ コントローラによって実行されます。

説明：

各キャッシュブロックには、独自の4つの状態の有限ステートマシンがあります（図1.1を参照）。さまざまな入力に対する状態遷移と特定の状態での応答は、表1.1と表1.2に示されています。

書き込みは、キャッシュ ラインが Modified または Exclusive 状態にある場合にのみ自由に実行できます。Shared 状態にある場合は、他のすべてのキャッシュされたコピーを最初に無効にする必要があります。これは通常、Request For Ownership (RFO)と呼ばれるブロードキャスト操作によって行われます。

Modified 状態のラインを保持するキャッシュは、対応するメイン メモリ位置のすべての試行された読み取り (システム内の他のすべてのキャッシュから) をスヌープ (傍受) し、保持しているデータを挿入する必要があります。これは、読み取りを強制的にバックオフ(つまり、後で再試行) し、データをメイン メモリに書き込み、キャッシュ ラインを共有状態に変更することで実行できます。また、Modified キャッシュから読み取りを実行しているキャッシュにデータを送信することでも実行できます。スヌープは読み取りミスに対してのみ必要であることに注意してください (プロトコルにより、他のキャッシュが読み取りヒットを実行できる場合は Modified が存在できないことが保証されます)。

Shared 状態のラインを保持するキャッシュは、他のキャッシュからの無効化または所有権要求のブロードキャストをリッスンし、一致した場合にはラインを破棄する (Invalid 状態に移行することによって) 必要があります。

Modified 状態と Exclusive 状態は常に正確です。つまり、システム内の実際のキャッシュ ライン所有権状況と一致します。Shared 状態は不正確な場合があります。別のキャッシュが Shared ラインを破棄すると、このキャッシュがそのキャッシュ ラインの唯一の所有者になることがあります。ただし、Exclusive 状態に昇格されることはありません。他のキャッシュはキャッシュ ラインを破棄するときに通知をブロードキャストしません。また、このキャッシュは共有コピーの数を保持せずにそのような通知を使用することはできません。

その意味で、排他状態は便宜的な最適化です。CPU が状態 S でキャッシュ ラインを変更する場合、他のすべてのキャッシュされたコピーを無効にするためにバス トランザクションが必要です。状態 E では、バス トランザクションなしでキャッシュ ラインを変更できます。

MESIプロトコル操作の図解

たとえば、次のような読み取り/書き込み参照のストリームがあるとします。すべての参照は同じ場所を指し、数字は参照を発行するプロセッサを指します。

ストリームは、R1、W1、R3、W3、R1、R3、R2 です。

最初はすべてのキャッシュが空であると想定されます。

注: 以下で言及されているスヌーピングという用語は、対称型マルチプロセッシング環境でキャッシュの一貫性を維持するためのプロトコルです。バス上のすべてのキャッシュは、バス上で要求されたデータ ブロックのコピーを持っている場合、バスを監視 (スヌープ) します。

• ステップ 1: キャッシュは最初は空なので、メイン メモリは P1 にブロックを提供し、排他状態になります。
• ステップ 2: ブロックはすでにキャッシュ内に存在し、排他的状態にあるため、バス命令なしで直接変更します。ブロックは変更された状態になります。
• ステップ 3: このステップでは、BusRd がバス上にポストされ、P1 のスヌーパがこれを感知します。次に、データをフラッシュし、状態を共有に変更します。P3 のブロックも、別のキャッシュからデータを受信したため、状態を共有に変更します。データはメイン メモリにも書き戻されます。
• ステップ 4: ここで、BusUpgr がバスに投稿され、P1 のスヌーパがこれを感知し、ブロックが別のキャッシュによって変更されるので無効にします。次に、P3 はブロックの状態を変更済みに変更します。
• ステップ 5: 現在の状態が無効であるため、バスに BusRd が送信されます。P3 のスヌーパはこれを感知し、データをフラッシュします。これで、P1 と P3 の両方のブロックの状態が共有されます。このとき、メイン メモリも以前に変更されたデータで更新されることに注意してください。
• ステップ 6: キャッシュにヒットがあり、共有状態にあるため、ここではバス要求は行われません。
• ステップ 7: P2 でキャッシュ ミスが発生し、BusRd がポストされます。P1 と P3 のスヌーパがこれを感知し、両方がフラッシュを試みます。最初にバスにアクセスした方がその操作を実行します。

所有権の読み取り(RFO)は、読み取りと無効化ブロードキャストを組み合わせたキャッシュ コヒーレンスプロトコルの操作です。この操作は、MESI プロトコルの共有 (S) または無効 (I) 状態にあるキャッシュ ラインに書き込もうとするプロセッサによって発行されます。この操作により、他のすべてのキャッシュは、そのようなラインの状態を I に設定します。所有権の読み取りトランザクションは、そのメモリ アドレスに書き込むことを目的とした読み取り操作です。したがって、この操作は排他的です。この操作は、キャッシュにデータをもたらし、このメモリ ラインを保持する他のすべてのプロセッサ キャッシュを無効にします。これは、上記の表では「BusRdX」と呼ばれています。

MESI の素朴で単純な実装では、2 つのパフォーマンス上の問題が見られます。まず、無効なキャッシュ ラインに書き込むと、そのラインが他の CPU からフェッチされるまでに長い遅延が発生します。次に、キャッシュ ラインを無効な状態に移動するには時間がかかります。これらの遅延を軽減するために、CPU はストア バッファと無効化キューを実装します。^[5]

ストア バッファは、無効なキャッシュ ラインに書き込むときに使用されます。いずれにせよ書き込みは続行されるため、CPU は読み取り無効メッセージを発行し (したがって、問題のキャッシュ ラインと、そのメモリ アドレスを格納する他のすべての CPU のキャッシュ ラインは無効になります)、書き込みをストア バッファにプッシュして、キャッシュ ラインが最終的にキャッシュに到着したときに書き込みが実行されるようにします。

ストア バッファが存在することの直接的な結果は、CPU が書き込みをコミットしても、その書き込みがすぐにキャッシュに書き込まれないことです。したがって、CPU がキャッシュ ラインを読み取る必要があるときはいつでも、同じラインが以前に同じ CPU によって書き込まれたが、まだキャッシュに書き込まれていない (前の書き込みがストア バッファで待機中である) 可能性があるため、最初に自身のストア バッファをスキャンして同じラインが存在するかどうかを確認します。CPU は自身のストア バッファにある以前の書き込みを読み取ることができますが、他の CPU はそれらの書き込みがキャッシュにフラッシュされるまでそれらの書き込みを見ることができないことに注意してください。つまり、 CPU は他の CPU のストア バッファをスキャンできないということです。

無効化メッセージに関しては、CPU は無効化キューを実装します。これにより、着信無効化要求は即座に確認されますが、すぐには処理されません。代わりに、無効化メッセージは無効化キューに入るだけで、その処理はできるだけ早く行われます (ただし、必ずしも即時ではありません)。その結果、無効化キューには受信されたがまだ適用されていない無効化が含まれているため、CPU はキャッシュ内のキャッシュ ラインが実際には無効であるという事実に気付かない場合があります。ストア バッファとは異なり、CPU と無効化キューは物理的にキャッシュの反対側にあるため、CPU は無効化キューをスキャンできないことに注意してください。

その結果、メモリバリアが必要になります。ストアバリアはストアバッファをフラッシュし、すべての書き込みがそのCPUのキャッシュに適用されていることを確認します。読み取りバリアは無効化キューをフラッシュし、他のCPUによるすべての書き込みがフラッシュCPUに見えるようにします。さらに、メモリ管理ユニットはストアバッファをスキャンしないため、同様の問題が発生します。この影響はシングルスレッドプロセッサでも見られます。^[6]

MESI とMSIの最も顕著な違いは、MESI プロトコルに存在する追加の「排他的」状態です。この追加の状態は、多くの利点があるために追加されました。プロセッサが他のプロセッサが持っていないブロックを読み取ってそれに書き込む必要がある場合、MSI の場合は 2 つのバス トランザクションが発生します。最初に、ブロックを読み取るための BusRd 要求が発行され、その後、ブロックに書き込む前に BusUpgr 要求が発行されます。このシナリオでは、他のキャッシュに同じブロックがないため BusRd 要求は役に立ちませんが、1 つのキャッシュがこれを知る方法はありません。したがって、MESI プロトコルは、排他的状態を追加することでこの制限を克服し、バス要求を節約します。これは、シーケンシャル アプリケーションの実行時に大きな違いをもたらします。1 つのデータに対して 1 つのプロセッサのみが作業するため、すべてのアクセスが排他的になります。この場合、MSI は追加のバス メッセージのためにパフォーマンスが大幅に低下します。データの共有が最小限の高度に並列化されたアプリケーションの場合でも、MESI の方がはるかに高速です。排他状態を追加しても、3 つの状態と 4 つの状態はどちらも 2 ビットで表現できるため、コストはかかりません。

特定のブロックに対してさまざまなキャッシュによって連続的な読み取りおよび書き込み操作が実行される場合、そのたびにデータをバスにフラッシュする必要があります。したがって、メインメモリはフラッシュのたびにこれを実行してクリーンな状態を維持します。ただし、これは必須ではなく、MESIを使用することによって発生する追加のオーバーヘッドにすぎません。この課題はMOESIプロトコルによって克服されました。^[7]

S (共有状態) の場合、複数のスヌーパが同じデータで FlushOpt で応答することがあります (上記の例を参照)。MESIF の F 状態はこの冗長性に対処します。

• コヒーレンスプロトコル
• MSI プロトコルは、MESI プロトコルの派生元となる基本プロトコルです。
• ライトワンス（キャッシュ一貫性）、MESI プロトコルの初期の形式。
• MOSIプロトコル
• MOESIプロトコル
• MESIFプロトコル
• MERSIプロトコル
• ドラゴンプロトコル
• ファイアフライプロトコル

• インタラクティブなMESIシミュレーション
• オープンソースの MESI コントローラ (Verilog)