ドラゴンプロトコル

ドラゴンプロトコル^[1]は、マルチプロセッサシステムで使用される更新ベースのキャッシュコヒーレンスプロトコルです。書き込みの伝播は、複数のプロセッサ間でキャッシュされたすべての値を直接更新することによって実行されます。ドラゴンプロトコルなどの更新ベースのプロトコルは、キャッシュブロックへの書き込みの後に他のプロセッサによる複数の読み取りが行われる場合に効率的に実行されます。これは、更新されたキャッシュブロックがすべてのプロセッサに関連付けられたキャッシュ間ですぐに利用できるためです。

各キャッシュ ブロックは、排他的クリーン、共有クリーン、共有変更、変更の 4 つの状態のいずれかになります。

• 排他クリーン (E) : これは、キャッシュ ブロックが最初に現在のプロセッサによってフェッチされ、それ以降他のプロセッサによってアクセスされていないことを意味します。
• 共有クリーン (Sc) : これは、キャッシュ ブロックが複数のプロセッサのキャッシュに確実に存在し、現在のプロセッサがブロックを書き込む最後のプロセッサではないことを意味します。状態 E と Sc はプロトコルによって個別に維持され、共有されていないキャッシュ ブロックの読み取り/書き込み操作によってバス トランザクションが発生し、実行速度が低下するのを防ぎます。これは、シングル スレッド プログラムでよく発生します。
• 共有変更 (Sm) : これは、ブロックが複数のプロセッサのキャッシュに存在し、現在のプロセッサがブロックを最後に変更したプロセッサであることを意味します。したがって、現在のプロセッサはブロックの所有者と呼ばれます。無効化プロトコルとは異なり、ブロックはメイン メモリ内で最新である必要はなく、プロセッサ内でのみ最新である必要があります。キャッシュ ブロックが削除されたときにメイン メモリを更新するのはプロセッサの責任です。
• 変更 (M) : これは、メモリ ブロックを持っているプロセッサが 1 つだけであり、メモリから取り込まれた値が変更されたことを意味しています。

任意のキャッシュ ペアについて、特定のキャッシュ ブロックの許可された状態は、他のキャッシュの状態と組み合わせると次のようになります (状態は上記の順序で省略されています)。

プロセッサ トランザクションは 4 つ、バス トランザクションは 2 つあります。

プロセッサ読み取り (PrRd) : これは、プロセッサがキャッシュ内に配置された特定のキャッシュ ブロックの読み取りを正常に完了したときに発生します。

プロセッサ書き込み (PrWr) : これは、プロセッサがキャッシュに配置された特定のキャッシュ ブロックへの書き込みを正常に完了したときに発生します。これにより、プロセッサはキャッシュ ブロックを最後に更新することになります。

プロセッサ読み取りミス (PrRdMiss) : これは、プロセッサがキャッシュからキャッシュ ブロックを読み取ることができず、メモリまたは別のキャッシュからブロックを取得する必要がある場合に発生します。

プロセッサ書き込みミス (PrWrMiss) : これは、プロセッサがキャッシュからキャッシュ ブロックへの書き込みに失敗し、メモリまたは別のキャッシュからブロックを取得して書き込みを行う必要がある場合に発生します。これにより、プロセッサはキャッシュ ブロックを最後に更新することになります。

バス読み取り (BusRd) : これは、プロセッサがメイン メモリまたは別のプロセッサのキャッシュからキャッシュ ブロックの最新の値を取得するためにバスを要求したときに発生します。

フラッシュ: これは、プロセッサがキャッシュ ブロック全体をバス上に配置したときに発生します。これは、プロセッサによってメイン メモリ内のキャッシュ ブロックに加えられた変更を反映するためです。

バス更新 (BusUpd) : これは、プロセッサがキャッシュ ブロックを変更し、他のプロセッサがそれぞれのキャッシュ ブロックを更新する必要がある場合に発生します。これは、書き込み更新プロトコルにのみ固有のものです。キャッシュへの書き込みはメモリへの書き込みよりも高速であるため、BusUpd はフラッシュ操作に比べて時間が短くなります。もう 1 つ注意すべき点は、キャッシュはキャッシュ ブロックのローカル コピーを更新してからバス更新を送信するようにバスに要求することはできないということです。これが発生すると、2 つのキャッシュがそれぞれローカル コピーを更新してからバスを要求する可能性があります。その場合、2 つの書き込みが同時に発生することになり、シーケンシャル一貫性が維持されなくなります。

共有ラインは、特定のキャッシュ ブロックが複数のキャッシュで使用可能かどうかを示すためにも必要です。これは、キャッシュの 1 つが他のブロックを更新せずにブロックを削除できるため必要です。共有ラインは、ブロックが 1 つのキャッシュでのみ使用可能でバス更新が不要な場合に、メモリとバスのトランザクションを減らすのに役立ちます。共有を検出するためのこのような専用ラインは、Firefly プロトコルなどの書き込み更新プロトコル全体で見られ、 Futurebus (IEEE 標準 P896.1)などのバス標準に基づいて実装されています。^[2]

ブロックの現在の状態とプロセッサによって開始されたトランザクションに基づいて、キャッシュ ブロックは次のいずれかの状態遷移を経ます。

• プロセッサの読み取りミス（PrRdMiss）が発生し、キャッシュブロックが共有されていない場合、状態は排他的状態に移行します。
• プロセッサの読み取りミス（PrRdMiss）が発生し、キャッシュブロックが共有されている場合、状態はShared Cleanに遷移します。
• プロセッサ書き込みミス ( PrWrMiss ) が発生し、キャッシュ ブロックが共有されている場合、状態はShared Modifiedに遷移し、プロセッサが所有者になります。
• プロセッサ書き込みミス（PrWrMiss）が発生し、キャッシュブロックが共有されていない場合、状態はModifiedに遷移します。
• プロセッサ読み取り（PrRd）ヒットがあった場合、キャッシュブロックの状態は変化せず、値を保持します。これは、読み取りコマンドのみであり、バストランザクションを生成しないためです。
• キャッシュ ブロックがModified状態にあり、プロセッサがブロックを書き込む ( PrWr ) 場合、ブロックは共有されていないため遷移は発生しません。
• キャッシュ ブロックがShared Modified状態にあり、プロセッサが書き込み ( PrWr ) を行っても共有ラインがアサートされていない場合、状態はModifiedに遷移します。
• 書き込み ( PrWr ) が発生し、共有ラインがアサートされたときにキャッシュ ブロックがShared Modified状態にある場合、バス更新 ( BusUpd ) が生成され、他のキャッシュ ブロックが更新されます。
• 書き込み ( PrWr ) が発生し、共有ラインがアサートされたときにキャッシュ ブロックがShared Clean状態にある場合、バス更新 ( BusUpd ) が生成されて他のキャッシュ ブロックが更新され、状態がShared Modifiedに変わります。
• ただし、書き込み ( PrWr ) が発生したときにキャッシュ ブロックがShared Clean状態であっても、共有ラインがアサートされていない場合は、状態はModifiedに遷移し、バス トランザクションは生成されません。
• ブロックが排他状態にあり、プロセッサがそれに書き込む ( PrWr ) と、ブロックは変更状態に変更されます。

ブロックの現在の状態とバスによって開始されたトランザクションに基づいて、キャッシュ ブロックは次のいずれかの状態遷移を経ます。

• キャッシュ ブロックがModified状態で、Bus Read ( BusRd ) が発行されると、ブロックが複数のキャッシュに存在するため、メイン メモリを更新するためにFlushが発行され、状態はShared Modifiedに遷移します。
• キャッシュ ブロックがShared Modified状態にあり、バス読み取り ( BusRd ) の場合、メイン メモリを更新するためにFlushが発行され、状態は同じままになります。
• キャッシュ ブロックがShared Modified状態にあり、バス更新 ( BusUpd ) トランザクションが発行されると、状態はShared Cleanに遷移し、すべてのキャッシュが更新されます。
• キャッシュ ブロックがShared Clean状態にあり、バス読み取り ( BusRd ) またはバス更新 ( BusUpd ) を受信した場合、値は共有されたままであるため、その状態が保持され続けます。ただし、Update の場合は、キャッシュ ブロック内の値が更新されます。
• キャッシュブロックが排他状態にあり、バスが値（BusRd）を読み取ると、ブロックが1つのキャッシュにのみ存在しなくなるため、状態はShared Cleanに遷移します。

キャッシュブロックがSm状態にあるプロセッサは、キャッシュブロックが置き換えられたときにメインメモリを更新する責任があります。しかし、バス更新トランザクションが発生するたびにメインメモリが更新される場合は、個別のSm状態とSc状態は必要なく、プロトコルは単一の共有状態を許容できます。ただし、これによりメモリトランザクションが大幅に増加し^[3]、特に複数のプロセッサが同じキャッシュブロックに書き込んでいる場合にシステムの速度が低下する可能性があります。

このプロトコルにより、Sc 状態のキャッシュ ブロックをバス アクティビティなしでサイレントに置き換えることができます。Sc ブロックが置き換えられていることを他のキャッシュに知らせるためのブロードキャストが行われた場合、他の共有者がいなければ、共有ラインをテストして状態 E に移行できます。ブロックを状態 E にしておくことの利点は、ブロックが後で書き込まれると M 状態になり、バス更新トランザクションを生成する必要がないことです。したがって、Sc ブロックの置き換えをブロードキャストするコストで、バス更新トランザクションを回避できます。また、置き換えのブロードキャストは時間的に重要ではないため、キャッシュが置き換えをすぐに処理する必要がなければ、デメリットはありません。一方、キャッシュが更新をすぐに処理しない場合は、順序どおりに更新されない可能性があります。このような場合、Fireflyプロトコルなどの 3 状態更新プロトコルにはパフォーマンス上の利点があります。

書き込み無効化は、キャッシュ コヒーレンスプロトコルの別のセットです。キャッシュ ブロックが変更されると、他のキャッシュにある同じブロックの他の値は更新されずに無効化されます。^[4]書き込み無効化プロトコルは、同じキャッシュ ブロックへの後続の書き込みが多数ある場合に、無効化が 1 回行われ、他のプロセッサによるそれ以上のバス トランザクションが回避されるため、より効率的です。ただし、ブロックへの書き込みの後に同じブロックへの複数の読み取りが続く場合は、書き込み更新プロトコルの方が効率的です。他のキャッシュされた値は書き込み後に更新されるため、すぐにデータにアクセスできます。このような場合、書き込み無効化プロトコルは非常に不利です。なぜなら、別のキャッシュでキャッシュ ブロックが変更されるたびに、残りのキャッシュでコヒーレンス ミスが発生し、新しい値を読み取るためにバス トランザクションを開始する必要があるためです。対照的に、書き込み更新プロトコルは、ブロックの値が必要以上に長く更新されたままになる傾向があり、これにより、競合や容量ミスなどの他の種類のミスが増加することになります。

Fireflyの場合、変更されたブロックのキャッシュ間転送も同時にメインメモリに書き戻されます。しかし、メインメモリへのアクセスはキャッシュに比べて桁違いに遅いため、別のバス操作として書き戻しを実行するという複雑さが増します。いずれにしても、パフォーマンスが低下します。^[5] Dragon プロトコルの場合、共有ブロックはメモリに書き戻されないため、この問題は完全に回避されます。ただし、これには 1 つの状態 (Shared-modified) が追加されるという犠牲が伴います。

• コヒーレンスプロトコル
• ファイアフライプロトコル
• MESIプロトコル
• MOSIプロトコル
• MOESIプロトコル
• MESIFプロトコル