維基百科

Dragon協議

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

狀態

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

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


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

 E   Sc   Sm   M 
 E         
 Sc         
 Sm         
 M         

事務

有 4 個處理器事務和 2 個總線事務。

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

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

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

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

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

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

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

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

狀態轉換

 
Dragon 協議 - 處理器發起的事務

處理器發起的轉換

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

  • 當發生處理器讀取未命中 ( 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狀態。
 
Dragon 協議 - 總線發起的事務

總線發起的轉換

根據緩存塊的當前狀態和總線發起的事務，一個緩存塊會經歷以下狀態轉換之一：

  • 如果該緩存塊在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 狀態，並且協議可以提供單個共享狀態。但是，這會導致更多的內存事務[3] ，這可能會降低系統速度，尤其是當多個處理器寫入同一個緩存塊時。

廣播更換Sc塊

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

比較

Dragon vs 寫無效協議

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

Dragon vs Firefly 協議

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

參考

  1. ^ Atkinson, Russell R.; McCreight, Edward M. The Dragon Processor. Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS II (Los Alamitos, CA, USA: IEEE Computer Society Press). 1987-01-01: 65–69. ISBN 978-0818608056. doi:10.1145/36206.36185 (不活躍 28 February 2022). 
  2. ^ Stenström, Per. A Survey of Cache Coherence Schemes for Multiprocessors. Computer. 1990-06-01, 23 (6): 12–24. ISSN 0018-9162. doi:10.1109/2.55497. 
  3. ^ Culler, David; Singh, Jaswinder Pal; Gupta, Anoop. Parallel Computer Architecture, 1st Edition | David Culler, Jaswinder Pal Singh, Anoop Gupta |. store.elsevier.com. 1999 [2016-10-24]. ISBN 9781558603431. （原始內容存檔於2016-10-25）. 
  4. ^ Solihin, Yan. Fundamentals of Parallel Multicore Architecture. Chapman and Hall/CRC. 2015: 205–206, 231–232. ISBN 9781482211184. 
  5. ^ Archibald, James; Baer, Jean-Loup. Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model. ACM Trans. Comput. Syst. 1986-09-01, 4 (4): 273–298. ISSN 0734-2071. doi:10.1145/6513.6514. 

參見

取自 "https://zh.wikipedia.org/w/index.php?title=Dragon协议&oldid=79529218"