Dragon_protocol

**Dragon 協議**是一種用於多處理器系統的基於更新的緩存一致性協議。通過直接更新跨多個處理器的所有緩存值來執行寫傳播。基於更新的協議（例如 Dragon 協議）在寫入緩存塊之後由其他處理器進行多次讀取時會高效執行，因為更新的緩存塊很容易在與所有處理器關聯的緩存中使用。

## 狀態

每個緩存塊都處於以下四種狀態之一：Exclusive-clean、Shared clean 、Shared modified 和 Modify。

* **Exclusive-clean (E)** ：這意味著緩存塊首先由當前處理器獲取，並且此後沒有被任何其他處理器訪問過。
* **Shared clean (Sc)** ：這意味著緩存塊肯定存在於多個處理器的緩存中，並且當前處理器不是最後一個寫入該塊的處理器。狀態 E 和 Sc 由協議單獨維護，以防止對未共享的緩存塊的讀寫操作引發匯流排事務，從而減慢執行速度。這在單執行緒程序中很常見。
* **Shared modified (Sm)** ：這意味著該塊存在於多個處理器的緩存中，並且當前處理器是最後一個修改該塊的處理器。因此，當前處理器被稱為塊的所有者。與失效協議不同，塊不需要在主存儲器中是最新的，而只需在處理器中是最新的。當緩存塊被驅逐時，處理器負責更新主存。
* **Modify（M）** ：這意味著只有一個處理器擁有內存塊，並且它已經修改了從內存中引入的值。

 

對於任何給定的緩存對，給定緩存塊的允許狀態連同其他緩存狀態的狀態如下（按上述順序縮寫的狀態）：

## 事務

有 4 個處理器事務和 2 個匯流排事務。

**處理器讀取 (PrRd)** ：當處理器成功讀取放置在其緩存中的某個緩存塊時，就會發生這個事務。

**處理器寫入 (PrWr)** ：當處理器完成對放置在其緩存中的某個緩存塊的成功寫入時，就會發生這個事務。這使得處理器成為最新更新緩存塊的處理器。

**處理器讀取未命中 (PrRdMiss)** ：當處理器無法從其緩存中讀取緩存塊並需要從內存或另一個緩存中獲取塊時，就會發生這個事務。

**處理器寫入未命中 (PrWrMiss)** ：當處理器無法從其緩存中寫入緩存塊時，會發生這個事務，需要從內存或另一個緩存中獲取塊然後寫入。這再次使處理器成為最新更新緩存塊的處理器。

**匯流排讀取（BusRd）** ：當處理器請求匯流排獲取緩存塊的最新值時，會發生這個事務，無論它來自主存儲器還是另一個處理器的緩存。

**刷新（Flush）** ：當處理器將整個緩存塊放在匯流排上時會發生這個事務。這是為了反映處理器對主存中緩存塊所做的更改。

**匯流排更新（BusUpd）** ：當一個處理器修改一個緩存塊，而其他處理器需要更新它們各自的緩存塊時，就會發生這個事務。這是寫更新協議所獨有的。與 Flush 操作相比，BusUpd 需要更短的時間，因為對緩存的寫入比對內存的寫入要快。另一點需要注意的是，緩存不能更新其緩存塊的本地副本，然後請求匯流排發送匯流排更新事務。如果確實發生了這種情況，那麼兩個緩存可能會獨立更新它們的本地副本，然後請求匯流排。然後他們會同時看到兩個不遵循順序一致性的寫入。

還需要一條 **shared line** 來指示某個緩存塊在多個緩存中是否可用。這是必需的，因為其中一個緩存可以驅逐該塊而無需更新其他塊。在某些情況下，shared line 有助於減少內存和匯流排事務，其中塊僅在一個高速緩存中可用，因此不需要匯流排更新。這種檢測共享的專用線路在寫更新協議（如 Firefly 協議）中可以找到，並基於 Futurebus （IEEE 標準 P896.1）等匯流排標準實現。 

## 狀態轉換

### 處理器發起的轉換

根據塊的當前狀態和處理器發起的事務，緩存塊經歷以下狀態轉換之一：

* 當發生處理器讀取未命中 ( **PrRdMiss** ) 並且緩存塊未共享時，狀態轉換為 **Exclusive**
* 當發生處理器讀取未命中 ( **PrRdMiss** ) 並且緩存塊被共享時，狀態轉換到狀態 **Shared Clean**
* 當發生處理器寫入未命中 ( **PrWrMiss** ) 並且緩存塊被共享時，狀態轉換為 **Shared Modified** 並且處理器成為所有者。
* 當發生處理器寫入未命中 ( **PrWrMiss** ) 且緩存塊未共享時，狀態轉換為 **Modified**
* 當處理器讀取 ( **PrRd** ) 命中時，緩存塊的狀態不會改變，並保留該值。這是因為它只是一個讀取命令，它不會產生任何匯流排事務
* 如果緩存塊處於 **Modified** 狀態，並且處理器寫入（ **PrWr** ）該塊，則沒有轉換，因為該塊未被共享。
* 當高速緩存塊處於 **Shared Modified** 狀態時，處理器寫入 ( **PrWr** )，但 shared line 未激活，狀態轉換為 **Modified** 。
* 如果緩存塊在寫入 ( **PrWr** ) 發生並且 shared line 被激活時處於 **Shared Modified** 狀態，則會生成匯流排更新 ( **BusUpd** ) 以更新另一個緩存塊。
* 如果緩存塊在寫入 ( **PrWr** ) 發生並且 shared line 被激活時處於 **Shared Clean** 狀態，則會生成匯流排更新 ( **BusUpd** ) 以更新另一個緩存塊並且狀態更改為 **Shared Modified** 。
* 但是，如果緩存塊在寫入 ( **PrWr** ) 發生時處於 **Shared** **Clean** 狀態，但 shared line 未激活，則狀態轉換為 **Modified** ，並且不會生成匯流排事務。
* 當塊處於 **Exclusive** 狀態，並且處理器向其寫入（ **PrWr** ）時，它將更改為 **Modified** 狀態。

### 匯流排發起的轉換

根據塊的當前狀態和匯流排發起的事務，緩存塊經歷以下狀態轉換之一：

* 如果緩存塊在 **Modified** 中，並且發出了匯流排讀取 ( **BusRd** )，則發出 **Flush** 以更新主內存並且狀態轉換為 **Shared Modified** ，因為該塊現在位於多個緩存中。
* 如果緩存塊處於 **Shared Modified** 狀態，並且匯流排讀取（ **BusRd** ），則發出 **Flush** 以更新主內存，並且狀態保持不變。
* 如果緩存塊處於 **Shared Modified** 狀態，並且發出了匯流排更新 ( **BusUpd** ) 事務，則狀態轉換為 **Shared Clean** ，所有緩存都會更新。
* 如果緩存塊處於 **Shared Clean** 狀態，並且它接收到匯流排讀取 ( **BusRd** ) 或匯流排更新 ( **BusUpd** )，它會繼續保持其狀態，因為值仍然是共享的。但是，在更新的情況下，它將更新緩存塊中的值。
* 如果緩存塊處於 **Exclusive** 狀態並且匯流排讀取值 ( **BusRd** )，則狀態將轉換為 Shared Clean，因為該塊不再僅駐留在一個緩存中

## 底層設計選擇

### 消除共享修改狀態（Sm）

緩存塊處於 Sm 狀態的處理器負責在緩存塊被替換時更新內存。但是如果每當發生匯流排更新事務時就更新主存儲器，則不需要單獨的 Sm 和 Sc 狀態，並且協議可以提供單個共享狀態。但是，這會導致更多的內存事務 ，這可能會降低系統速度，尤其是當多個處理器寫入同一個緩存塊時。

### 廣播更換 Sc 塊

該協議允許在沒有任何匯流排活動的情況下靜默替換 Sc 狀態的緩存塊。如果進行廣播以讓其他緩存知道正在替換 Sc 塊，則它們可以測試 shared line 並在沒有其他共享者的情況下移動到狀態 E。有一個處於狀態 E 的塊的好處是，如果該塊稍後被寫入，它會進入 M 狀態，並且不需要生成匯流排更新事務。因此，以廣播 Sc 塊的替換為代價，我們能夠避免匯流排更新事務。而且由於廣播替換不是時間關鍵，如果不需要緩存來立即處理替換，則沒有缺點。另一方面，如果緩存不立即處理更新，則可能導致無序更新。在這種情況下，三態更新協議（如 Firefly 協議）可能具有性能優勢。

## 比較

### Dragon vs 寫無效協議

寫無效協議是另一套緩存一致性協議，一旦一個緩存塊被修改，其他緩存中相同塊的其他值不會被更新，而是失效。 寫入無效協議在對同一緩存塊有許多後續寫入的情況下更有效，因為無效發生一次，並且避免了其他處理器的進一步匯流排事務。但是，在對一個塊進行寫入之後對同一塊進行多次讀取的情況下，寫入更新協議更有效。由於我們在寫入後會更新其他緩存值，因此它們可以立即訪問數據。在這種情況下。寫無效協議是非常不利的，因為每次在另一個緩存中修改一個緩存塊時，其餘緩存需要會遇到一致性未命中，並啟動匯流排事務以讀取新值。相比之下，寫入更新協議有時會使塊的值保持更新的時間超過必要的時間，這將導致其他類型的未命中（即衝突和容量未命中）的增加。

### Dragon vs Firefly 協議

在 Firefly 的情況下，修改塊的緩存到緩存傳輸也會同時寫回主內存。但是，由於與高速緩存相比，對主存儲器的訪問要慢幾個數量級，因此需要增加執行回寫作為單獨匯流排操作的複雜性。在任何情況下，它都會導致性能下降。 在 Dragon 協議的情況下完全避免了這個問題，因為共享塊根本不會寫回內存。然而，這是以增加一個狀態（Shared-modified）為代價的。

## 參考

## 參見

* 快取一致性
* 螢火蟲協議
* MESI 協議
* MOSI 協議
* MOESI 協議
* MESIF 協議