維基百科

MESI協議

MESI協議是一個基於失效的緩存一致性協議，是支持寫回（write-back）緩存的最常用協議。也稱作伊利諾伊協議 (Illinois protocol，因為是在伊利諾伊大學厄巴納-香檳分校被發明的[1])。與寫直達（write through）緩存相比，回寫緩衝能節約大量帶寬。總是有「髒」（dirty）狀態表示緩存中的數據與主存中不同。MESI協議要求在緩存不命中（miss）且數據塊在另一個緩存時，允許緩存到緩存的數據複製。與MSI協議相比，MESI協議減少了主存的事務數量。這極大改善了性能。[2]

狀態

編輯

緩存行有4種不同的狀態:

已修改Modified (M)
緩存行是髒的（dirty），與主存的值不同。如果別的CPU內核要讀主存這塊數據，該緩存行必須回寫到主存，狀態變為共享(S).
獨占Exclusive (E)
緩存行只在當前緩存中，但是乾淨的（clean）--緩存數據同於主存數據。當別的緩存讀取它時，狀態變為共享；當前寫數據時，變為已修改狀態。
共享Shared (S)
緩存行也存在於其它緩存中且是乾淨的。緩存行可以在任意時刻拋棄。
無效Invalid (I)
緩存行是無效的

任意一對緩存，對應緩存行的相容關係:

 M   E   S   I 
 M         
 E         
 S         
 I         

當塊標記為 M (已修改), 在其他緩存中的數據副本被標記為I(無效).


操作

編輯
 
圖 1.1 MESI協議的狀態圖 紅色: 總線初始化事務； 藍色: 處理器初始化事務[3]

有限狀態自動機的狀態轉換結束兩種場景：緩存所在處理器的讀寫；其他處理器的讀寫。總線請求被總線窺探器（英語：Bus snooping）監視。[4]

處理器對緩存的請求:

  1. PrRd: 處理器請求讀一個緩存塊
  2. PrWr: 處理器請求寫一個緩存塊

總線對緩存的請求:

  1. BusRd: 窺探器請求指出其他處理器請求讀一個緩存塊
  2. BusRdX: 窺探器請求指出其他處理器請求寫一個該處理器不擁有的緩存塊
  3. BusUpgr: 窺探器請求指出其他處理器請求寫一個該處理器擁有的緩存塊
  4. Flush: 窺探器請求指出請求回寫整個緩存到主存
  5. FlushOpt: 窺探器請求指出整個緩存塊被發到總線以發送給另外一個處理器（緩存到緩存的複製）

解釋

圖1.1是MESI協議四種狀態的轉換圖。

表1.1 處理器操作帶來的狀態轉化
初始狀態 操作 響應
Invalid(I) PrRd
  • 給總線發BusRd信號
  • 其他處理器看到BusRd，檢查自己是否有有效的數據副本，通知發出請求的緩存
  • 狀態轉換為(S)Shared, 如果其他緩存有有效的副本
  • 狀態轉換為(E)Exclusive, 如果其他緩存都沒有有效的副本
  • 如果其他緩存有有效的副本, 其中一個緩存發出數據；否則從主存獲得數據
PrWr
  • 給總線發BusRdX信號
  • 狀態轉換為(M)Modified
  • 如果其他緩存有有效的副本, 其中一個緩存發出數據；否則從主存獲得數據
  • 如果其他緩存有有效的副本, 見到BusRdX信號後無效其副本
  • 向緩存塊中寫入修改後的值
Exclusive(E) PrRd
  • 無總線事務生成
  • 狀態保持不變
  • 讀操作為緩存命中
PrWr
  • 無總線事務生成
  • 狀態轉換為(M)Modified
  • 向緩存塊中寫入修改後的值
Shared(S) PrRd
  • 無總線事務生成
  • 狀態保持不變
  • 讀操作為緩存命中
PrWr
  • 發出總線事務BusUpgr信號
  • 狀態轉換為(M)Modified
  • 其他緩存看到BusUpgr總線信號，標記其副本為(I)Invalid.
Modified(M) PrRd
  • 無總線事務生成
  • 狀態保持不變
  • 讀操作為緩存命中
PrWr
  • 無總線事務生成
  • 狀態保持不變
  • 寫操作為緩存命中
表1.2 不同總線操作帶來的狀態轉化
初始狀態 操作 響應
Invalid(I) BusRd
  • 狀態保持不變，信號忽略
BusRdX/BusUpgr
  • 狀態保持不變，信號忽略
Exclusive(E) BusRd
  • 狀態變為共享
  • 發出總線FlushOpt信號並發出塊的內容
BusRdX
  • 狀態變為無效
  • 發出總線FlushOpt信號並發出塊的內容
Shared(S) BusRd
  • 狀態變為共享
  • 可能發出總線FlushOpt信號並發出塊的內容（設計時決定哪個共享的緩存發出數據）
BusRdX
  • 狀態變為無效
  • 可能發出總線FlushOpt信號並發出塊的內容（設計時決定哪個共享的緩存發出數據）
Modified(M) BusRd
  • 狀態變為共享
  • 發出總線FlushOpt信號並發出塊的內容，接收者為最初發出BusRd的緩存與主存控制器（回寫主存）
BusRdX
  • 狀態變為無效
  • 發出總線FlushOpt信號並發出塊的內容，接收者為最初發出BusRd的緩存與主存控制器（回寫主存）

寫操作僅在緩存行是已修改或獨占狀態時可自由執行。如果在共享狀態，其他緩存都要先把該緩存行置為無效，這種廣播操作稱作Request For Ownership (RFO).

緩存對已修改狀態的緩存行，要監聽各處理器對其的讀請求並插入其數據到總線。

緩存對共享狀態的緩存行，要監聽使其無效或請求擁有的廣播，當匹配時把該緩存行置為無效。

已修改狀態、獨占狀態是精確的，匹配於該緩存行在系統中的實際情況。共享狀態可以是不精確的: 如果別的緩存拋棄了該行，只有當前緩存擁有該行，但其狀態沒有變為獨占。其他緩存不需要廣播通知其拋棄操作。

獨占狀態是一個優化機會：處理器修改共享狀態的緩存行必須要先發出一個總線事務使得其他緩存中的該行失效；而獨占狀態下修改一行不需要總線事務。

MESI協議操作圖解[5]

假定下述讀/寫操作訪問同一主存位置的數據。操作流是 : R1, W1, R3, W3, R1, R3, R2. 最初所有緩存為空。

表 1.3 MESI工作舉例 所有操作引用同一緩存行 (例如: "R3" 值處理器3的讀操作)
本地 請求 P1 P2 P3 產生的

總線請求

數據提供者
0 最初 - - - - -
1 R1 E - - BusRd Mem
2 W1 M - - - -
3 R3 S - S BusRd P1's Cache
4 W3 I - M BusUpgr -
5 R1 S - S BusRd P3's Cache
6 R3 S - S - -
7 R2 S S S BusRd P1/P3's Cache

參見

編輯

參考文獻

編輯
  1. ^ Papamarcos, M. S.; Patel, J. H. A low-overhead coherence solution for multiprocessors with private cache memories. Proceedings of the 11th annual international symposium on Computer architecture - ISCA '84 (PDF). 1984: 348 [2013-03-19]. ISBN 0818605383. doi:10.1145/800015.808204. （原始內容存檔 (PDF)於2012-12-24）. 
  2. ^ MESI Cache Coherence Simulator for Teaching Purposes. CLEI ELECTRONIC JOURNAL. 
  3. ^ Culler, David. Parallel Computer Architecture. Morgan Kaufmann Publishers. 1997: Figure 5–15 State transition diagram for the Illinois MESI protocol. Pg 286. 
  4. ^ Bigelow, Narasiman, Suleman. An evaluation of Snoopy Based Cache Coherence protocols (PDF). ECE Department, University of Texas at Austin. （原始內容存檔 (PDF)於2020-05-18）. 
  5. ^ Solihin, Yan. Fundamentals of Parallel Multicore Architecture. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. 2015-10-09. ISBN 978-1-4822-1118-4. 

外部連結

編輯
取自「https://zh.wikipedia.org/w/index.php?title=MESI协议&oldid=74985964」