緩存一致性協議

緩存一致性協議的場景是，多核 CPU 中，每個核心都有自己的緩存，爲了保證這些緩存的數據一致，設計了緩存一致性協議。本文內容涵蓋 MESI 協議、MOESI 協議、MESIF 協議、基於目錄的緩存一致性、ACE 協議、CHI 協議等。

1. 理論分析

首先從理論的角度，分析如何設計一個緩存一致性協議。

1.1 Write-invalidate 和 Write-update

最基礎的緩存一致性思想有兩種：

a) Write-invalidate：寫入數據的時候，將其他 Cache 中這條 Cache Line 設爲 Invalid

b) Write-update：寫入數據的時候，把新的結果寫入到有這條 Cache Line 的其他 Cache

1.2 MESI 協議

MESI 協議定義了四種狀態：

Modified：數據與內存不一致，並且只有一個緩存有數據

Exclusive：數據與內存一致，並且只有一個緩存有數據

Shared：數據與內存一致，可以有多個緩存同時有數據

Invalid：不在緩存中

當 Read hit 的時候，狀態不變。

當 Read miss 的時候，首先會檢查其他緩存的狀態，如果有數據，就從其他緩存讀取數據，並且都進入 Shared 狀態，如果其他緩存處於 Modified 狀態，還需要把數據寫入內存；如果其他緩存都沒有數據，就從內存裏讀取，然後進入 Exclusive 狀態。

當 Write hit 的時候，進入 Modified 狀態，同時讓其他緩存進入 Invalid 狀態。

當 Write miss 的時候，檢查其他緩存的狀態，如果有數據，就從其他緩存讀取，否則從內存讀取。然後，其他緩存都進入 Invalid 狀態，本地緩存更新數據，進入 Modified 狀態。

值得一提的是，Shared 狀態不一定表示只有一個緩存有數據：比如本來有兩個緩存都是 Shared 狀態，然後其中一個因爲緩存替換變成了 Invalid，那麼另一個是不會收到通知變成 Exclusive 的。Exclusive 的設置是爲了減少一些總線請求，比如當數據只有一個核心訪問的時候，只有第一次 Read miss 會發送總線請求，之後一直在 Exclusive/Modified 狀態中，不需要發送總線請求。

1.3 MOESI 協議

MOESI 定義了五個狀態：

Modified：數據經過修改，並且只有一個緩存有這個數據

Owned：同時有多個緩存有這個數據，但是隻有這個緩存可以修改數據

Exclusive：數據沒有修改，並且只有一個緩存有這個數據

Shared：同時有多個緩存有這個數據，但是不能修改數據

Invalid：不在緩存中

狀態中，M 和 E 是獨佔的，所有緩存裏只能有一個。此外，可以同時有多個 S，或者多個 S 加一個 O，但是不能同時有多個 O。

它的狀態轉移與 MESI 類似，區別在於：當核心寫入 Owned 狀態的緩存時，有兩種方式：1）通知其他 Shared 的緩存更新數據；2）把其他 Shared 緩存設爲 Invalid，然後本地緩存進入 Modified 狀態。在 Read miss 的時候，則可以從 Owned 緩存讀取數據，進入 Shared 狀態，而不用寫入內存。它相比 MESI 的好處是，減少了寫回內存的次數。

AMD64 文檔裏採用的就是 MOESI 協議。AMBA ACE 協議其實也是 MOESI 協議，只不過換了一些名稱，表示可以兼容 MEI/MESI/MOESI 中的一個協議。ACE 對應關係如下：

UniqueDirty: Modified

SharedDirty: Owned

UniqueClean: Exclusive

SharedClean: Shared

Invalid: Invalid

需要注意的是，SharedClean 並不代表它的數據和內存一致，比如說和 SharedDirty 緩存一致，它只是說緩存替換的時候，不需要寫回內存。

1.4 MESIF 協議

MESIF 定義了五個狀態：

Modified：數據經過修改，並且只有一個緩存有這個數據

Exclusive：數據沒有修改，並且只有一個緩存有這個數據

Shared：同時有多個緩存有這個數據，但是不能修改數據

Invalid：不在緩存中

Forward：同時有多個緩存有這個數據，但是不能修改數據，且這個緩存負責響應請求

MESIF 相比 MESI 的區別是，添加了 Forward 狀態：Forward 其實是特殊的 Shared，主要是考慮到有多個緩存處於 Shared 狀態的時候，如果來了一個讀請求，那麼哪個 Shared 緩存負責響應是不確定的。MESIF 協議中，Forward 就是負責響應的那一個 Shared，所以 Forward 最多隻有一個，其他 Shared 都不會響應。這樣的好處是簡化了在片上網絡的傳輸。

如果多個 Cache 屬於 Shared 狀態，沒有 Forward，那麼新的 Cache 請求就會發送到內存裏，由於 Shared 的數據沒有經過修改，所以內存中的數據和 Shared 是一致的。同時，這個新的 Cache 會進入 Forward 狀態。

1.5 基於目錄的緩存一致性

上面的緩存一致性協議中，經常有這麼一個操作：向所有有這個緩存行的緩存發送 / 接受消息。簡單的方法是直接廣播，然後接受端自己判斷是否處理。但是這個方法在覈心很多的時候會導致廣播流量太大，因此需要先保存下來哪些緩存會有這個緩存的信息，然後對這些緩存點對點地發送。這樣就可以節省一些網絡流量。

怎麼記錄這個信息呢？一個簡單的辦法（Full bit vector format）是，有一個全局的表，對每個緩存行，都記錄一個大小爲 N（N 爲核心數）的位向量，1 表示對應的核心中有這個緩存行。但這個方法保存數據量太大：緩存行數正比於 N，還要再乘以一次 N，總容量是 (O(N^2)) 的。

一個稍微好一些的方法（Coarse bit vector format）是，我把核心分組，比如按照 NUMA 節點進行劃分，此時每個緩存行都保存一個大小爲 M（M 爲 NUMA 數量）的位向量，只要這個 NUMA 節點裏有這個緩存行，對應位就取 1。這樣相當於是以犧牲一部分流量爲代價（NUMA 節點內部廣播），來節省一些目錄的存儲空間。

但實際上，通常情況下，一個緩存行通常只會在很少的核心中保存，所以這裏有很大的優化空間。比如說，可以設置一個緩存行同時出現的緩存數量上限（Limited pointer format），然後保存核心的下標而不是位向量，這樣的存儲空間就是 (O(N\log_2N))。但是呢，這樣限制了緩存行同時出現的次數，如果超過了上限，需要替換掉已有的緩存，可能在一些場景下性能會降低。

還有一種方式，就是鏈表 (Chained directory format)。目錄中保存最後一次訪問的核心編號，然後每個核心的緩存裏，保存了下一個保存了這個緩存行的核心編號，或者表示鏈表終止。這樣存儲空間也是 (O(N\log_2N))，不過發送消息的延遲更長，因爲要串行遍歷一遍，而不能同時發送。類似地，可以用二叉樹（Number-balanced binary tree format）來組織：每個緩存保存兩個指針，指向左子樹和右子樹，然後分別遍歷，目的還是加快遍歷的速度，可以同時發送消息給多個核心。

2. 協議分析

下文結合實際的協議，分析緩存一致性協議是如何在硬件中實現的。

2.1 ACE 協議

ACE 在 AXI 協議的基礎上，實現了緩存一致性協議。首先列出 ACE 的緩存狀態模型，它定義了這麼五種狀態，其實就是 MOESI 的不同說法：

UniqueDirty: Modified

SharedDirty: Owned

UniqueClean: Exclusive

SharedClean: Shared

Invalid: Invalid

spec 中的定義如下：

大致理解的話，Unique 表示只有一個緩存有這個緩存行，Shared 表示有可能有多個緩存有這個緩存行；Clean 表示它不負責更新內存，Dirty 表示它負責更新內存。下面的很多操作都是圍繞這些狀態進行的。

文檔中也說，它支持 MOESI 的不同子集：MESI, ESI, MEI, MOESI，所以也許在一個簡化的系統裏，一些狀態可以不存在，實現會有所不同。

換位思考，作爲協議的設計者，應該如何添加信號來實現緩存一致性協議？從需求出發，緩存一致性協議需要實現：

  1. 讀或寫 miss 的時候，需要請求這個緩存行的數據，並且更新自己的狀態，比如讀取到 Shared，寫入到 Modified 等。

  2. 寫入一個 valid && !dirty 的緩存行的時候，需要升級自己的狀態，比如從 Shared 到 Modified。

  3. 需要 evict 一個 valid && dirty 的緩存行的時候，需要把 dirty 數據寫回，並且降級自己的狀態，比如 Modified -> Shared/Invalid。如果需要 evict 一個 valid && !dirty 的緩存行，可以選擇通知，也可以選擇不通知下一級。

  4. 收到 snoop 請求的時候，需要返回當前的緩存數據，並且更新狀態。

  5. 需要一個方法來通知下一級 Cache/Interconnect，告訴它第一和第二步完成了。

首先考慮上面提到的第一件事情：讀或寫 miss 的時候，需要請求這個緩存行的數據，並且更新自己的狀態，比如讀取到 Shared，寫入到 Modified 等。

AXI 已經有 AR 和 R channel 用於讀取數據，那麼遇到讀或者寫 miss 的時候，可以在 AR channel 上捎帶一些信息，讓下一級的 Interconnect 知道自己的意圖是讀還是寫，然後 Interconnect 就在 R channel 上返回數據。

具體要捎帶什麼信息呢？“不妨” 用這樣一種命名方式：操作 + 目的狀態，比如讀 miss 的時候，需要讀取數據，進入 Shared 狀態，那就叫 ReadShared；寫 miss 的時候，需要讀取數據（通常寫入緩存的只是一個緩存行的一部分，所以先要把完整的讀進來），就叫 ReadUnique。這個操作可以編碼到一個信號中，傳遞給 Interconnect。

再來考慮上面提到的第二件事情：寫入一個 valid && !dirty 的緩存行的時候，需要升級自己的狀態，比如從 Shared 到 Modified。

這個操作，需要讓 Interconnect 把其他緩存中的這個緩存行數據清空，並且把自己升級到 Unique。根據上面的 操作 + 目的狀態 的命名方式，可以講其命名爲 CleanUnique，即把其他緩存都 Clean 掉，然後自己變成 Unique。

接下來考慮上面提到的第三件事情：需要 evict 一個 valid && dirty 的緩存行的時候，需要把 dirty 數據寫回，並且降級自己的狀態，比如 Modified -> Shared/Invalid。

按照前面的 操作 + 目的狀態 命名法，可以命名爲 WriteBackInvalid。ACE 實際採用的命名是 WriteBack。

第四件事情：收到 snoop 請求的時候，需要返回當前的緩存數據，並且更新狀態。

既然 snoop 是從 Interconnect 發給 Master，在已有的 AR R AW W B channel 裏沒辦法做這個事情，不然會打破已有的邏輯。那不得不添加一對 channel：規定一個 AC channel 由 Interconnect 發送 snoop 請求，一個 C channel 讓 Master 發送響應。這就相當於 TileLink 裏面的 B channel（Probe 請求）和 C channel（ProbeAck 響應）。實際 ACE 和剛纔設計的實際有一些區別，把 C channel 拆成了兩個：CR 用於返回所有響應，CD 用於返回那些需要數據的響應。這就像 AW 和 W 的關係，一個傳地址，一個傳數據；類似地，CR 傳狀態，CD 傳數據。

那麼 AC channel 上要發送什麼請求呢？回顧一下上面已經用到的請求類型：需要 snoop 的有 ReadShared，ReadUnique 和 CleanUnique，不需要 snoop 的有 WriteBack。那麼直接通過 AC channel 把 ReadShared，ReadUnique 和 CleanUnique 這三種請求原樣發送給需要 snoop 的 Cache 即可。Cache 在 AC channel 收到這些請求的時候，再做相應的動作。

第五件事情：需要一個方法來通知下一級 Cache/Interconnect，告訴它第一和第二步完成了。TileLink 添加了一個額外的 E channel 來做這個事情，ACE 更加粗暴：直接用一對 RACK 和 WACK 信號來分別表示最後一次讀和寫已經完成。關於 WACK 和 RACK 的討論，詳見 What's the purpose for WACK and RACK for ACE and what's the relationship with WVALID and RVALID? 。

這時候已經基本把 ACE 協議的信號和大體的工作流程推導出來了。從信號上來看，ACE 協議在 AXI 的基礎上，添加了三個 channel：

  1. AC: Coherent address channel, Input to master: ACADDR, ACSNOOP, ACPROT

  2. CR: Coherent response channel, Output from master: CRRESP

  3. CD: Coherent data channel, Output from master: CDDATA, CDLAST

此外，已有的 Channel 也添加了信號：

  1. ARSNOOP[3:0]/ARBAR[1:0]/ARDOMAIN[1:0]

  2. AWSNOOP[3:0]/AWBAR[1:0]/AWDOMAIN[1:0]/AWUNIQUE

  3. RRESP[3:2]

  4. RACK/WACK

ACE 協議還設計了一個 ACE-Lite 版本：ACE-Lite 只在已有 Channel 上添加了新信號，沒有添加新的 Channel。因此它內部不能有 Cache，但是可以訪問一致的緩存內容。

2.2 CHI 協議

2.2.1 介紹

CHI 協議是 AMBA 5 標準中的緩存一致性協議，前身是 ACE 協議。最新的 CHI 標準可以從 AMBA 5 CHI Architecture Specification 處下載。

相比 AXI，CHI 更加複雜，進行了分層：協議層，網絡層和鏈路層。因此，CHI 適用於片上網絡，支持根據 Node ID 進行路由，而不像 AXI 那樣只按照物理地址進行路由。CHI 的地位就相當於 Intel 的環形總線。CHI 也可以橋接到 CCIX 上，用 CCIX 連接 SMP 的的多個 Socket，或者連接支持 CCIX 的顯卡等等。

2.2.2 緩存行狀態

首先回顧 ACE 的緩存行狀態，共有五種，與 MOESI 相對應：

UniqueDirty: Modified

SharedDirty: Owned

UniqueClean: Exclusive

SharedClean: Shared

Invalid: Invalid

在此基礎上，CHI 考慮緩存行只有部分字節有效的情況，即 Full，Partial 或者 Empty。因此 CHI 的緩存行狀態共有七種：

  1. UniqueDirty: Modified

  2. UniqueDirtyPartial: 新增，可能有部分字節合法，在寫回的時候，需要和下一級緩存或者內存中的合法緩存行內容進行合併

  3. SharedDirty: Owned

  4. UniqueClean: Exclusive

  5. UniqueCleanEmpty: 新增，所有字節都不合法，但是本緩存佔有該緩存行，如果要修改的話，不需要通知其他緩存

  6. SharedClean: Shared

  7. Invalid: Invalid

可以看到，比較特別的就是 UniqueDirtyPartial 和 UniqueCleanEmpty。CHI 標準在 4.1.1 章節給出了使用場景：如果一個 CPU 即將要寫入一片內存，那麼可以先轉換到 UniqueCleanEmpty 狀態中，把其他緩存中的數據都清空，這樣後續寫入的時候，不需要詢問其他緩存，性能比較好。但此時因爲數據還沒寫進去，所以就是 Empty，只更新狀態，不佔用緩存的空間。另一方面，如果 CPU 只寫了緩存行的一部分字節，其他部分沒有碰，那麼引入 UniqueDirtyPartial 以後，可以把合併新舊緩存行數據這一步，下放到比較靠近內存的層級上，減少了數據搬運的次數。

2.2.3 CHI 網絡節點

CHI 的節點組織成一個網絡，可能是片上網絡，也可能是片間的連接。CHI 的節點分成三種類型：

  1. Request Node：發起 CHI 請求的節點，對應 CPU 的緩存，或者是網卡等外設

  2. Home Node：管理 Request Node 來的請求，對應最後一級緩存

  3. Subordinate Node：處理 Home Node 來的請求，對應內存或者顯存等有內存的外設

在這種設計下，Node 之間可以互相通信，因此方便做一些新的優化。例如傳統的緩存層次裏，請求是一級一級下去，響應再一級一級上來。但是 CHI 可能是 Request Node 發給 Home Node 的請求，響應直接由 Subordinate Node 發送回 Request Node 了。

2.2.4 讀請求

CHI 提供了複雜性的同時，也帶來了很多的靈活性，也意味着潛在的性能優化的可能。例如在 CHI 中實現一個讀操作，可能有很多種過程（CHI 標準第 2.3.1 章節）：

第一種是 Home Node 直接提供了數據（Combined response from home）：

第二種是 Home Node 把響應拆成兩份，一份表示讀取結果，一份攜帶讀取的數據（Separate data and response from Home）：

第三種是 Home Node 沒有數據，轉而詢問 Subordinate，Subordinate 把結果直接發回給了 Requester（Combined response from Subordinate）：

第四種是 Home Node 沒有數據，轉而詢問 Subordinate，但這次提前告訴 Requester 讀取的結果，最後 Subordinate 把結果發回給了 Requester（Response from Home, Data from Subordinate）：

第五種是數據在其他的 Requester Node 中，此時 Home 負責 Snoop（Forwarding snoop）：

第六種是 MakeReadUnique，此時只更新權限，不涉及數據的傳輸（MakeReadUnique only）：

2.2.5 寫請求

CHI 標準第 2.3.2 描述了寫請求的流程。和讀請求一樣，寫請求也有很多類型，下面進行介紹。與讀請求不同的點在於，寫入的時候，並不是直接把寫入的地址和數據等一次性發送過去，而是先發一個寫消息，對方回覆可以發送數據了（DBIDResp），再把實際的數據傳輸過去（NCBWrData）。當然了，也可以中途反悔（WriteDataCancel）。

第一種是 Direct Write-data Transfer，意思是數據要從 Requester 直接傳到 Subordinate 上：

第二種比較常規，就是把數據寫給 Home Node，其中 Comp 表示讀取結果，DBIDResp 表示可以發寫入的內容了：

第三種是把第二種的 DBIDResp 和 Comp 合併成一個響應：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7-TBini-53UY8MoVYmfLqg

猜你喜歡