1.為何需要cache一致性

訪問memory數據的速度與core的運行速度相比，要花費更多的時鐘周期。為了減少這個差異計算機系統引進了存儲器層次結構，如圖1所示。在層次結構中，越往上，讀寫速度越快，價格越貴，存儲容量也越小。

圖1 存儲器結構層次

隨著摩爾定律的發展，人們試圖增加CPU的core數以提升系統整體性能，這類系統稱之為多core系統。一個包含多core的系統中，每個core可能都有自己的私有cache，并且有可能會對相同的memory地址進行修改。如果多個core同時對同一memory地址進行讀寫操作，很可能導致cache內容不一致，從而導致數據不一致，最終造成系統出錯和崩潰。因此，在設計多core系統時，必須考慮cache一致性(cache coherency)問題來確保數據的正確性和系統的穩定性。舉個例子，假設2個core的系統，每個core私有的L1 cache的cacheline大小是64Bytes。兩個core都讀取0x80地址數據，導致0x80開始的64Bytes數據都分別加載到core0和core1的私有L1 cache中。

圖2 兩core系統讀取0x80地址的數據

core0對0x80執行寫操作，寫入值為0x01。Core0的私有L1 cache更新對應cacheline的值。然后，core1讀取0x80的數據，core1發現命中自己私有L1 cache，然后返回0x00值，并不是core0寫入的0x01值，這就造成了core0和core1的私有L1 cache數據不一致現象。

圖3 core0更新0x80地址的數據

按照正確的處理流程，可以使用以下兩種方法保證多core cache的一致性：

• Core0修改0x80地址數據的時候，除了更新core0的私有cache之外，還應將修改的數據通知到core1的私有cache去更新0x80地址的數據。
• Core0修改0x80地址數據的時候，除了更新core0的私有cache之外，還應通知core1的私有cache將0x80地址所在的cacheline置為無效。保證core1讀取數據時不會命中自己的cache。這樣core1就必須重新從core0或memory中去讀取0x80地址最新的數據。

Cache一致性可以通過軟件和硬件來解決，通常來說，軟件維護cache一致性維護成本太高，會導致性能下降。現在的實現方案基本都是使用硬件來自動維護多核cache的一致性，并且對軟件和程序員來說是透明的。因此，本文只介紹硬件維護cache一致性。硬件維護cache一致性需要制定一致性協議，一致性協議是由系統內的各個分布式硬件參與者組件共同實現和維護的一組規則。一致性協議有許多版本，Arm的ACE(AXI Coherency Extensions)和CHI(Coherent Hub Interface)，AMD的Coherent HyperTransport（HT），Intel的QuickPath Interconnect(QPI)等等。

2.一致性協議的本質

雖然一致性協議眾多，但本質上講，所有一致性協議都通過將寫入的數據傳播到所有一致性cache來使一個core的寫入對其它core可見。具體來說有兩點原則：

• Single-Writer, Multiple-Read(SWMR)：在任意時刻，對于任意的memory地址A，只有一個core可以寫它(也可以讀它)，或者多個core讀它。因此，永遠不會有這樣的情況：一個core可以寫入memory地址A，而其它core可以同時讀取或寫入該memory地址A。如下圖4所示，可以把時間會切割為無限小的切片，在每個切片中，對于memory地址A，要么單個core具有讀寫訪問權限，要么若干core(可能為0)具有只讀訪問權限。比如T1和T4時刻，允許多個core對同一個memory進行讀取，但在T2和T3種，只能存在1個core擁有讀寫的權限。
• Data-Value：在時間切片中，上一個時間切片結束的數據值與下一個時間切片開始的數據值相同，即使同一個切片中，每個core讀取到的值必須相同。也就是memory地址的數據值需要被正確傳播。比如在T1時刻，如果core2和core5可以讀取到不同的值，那么就不符合一致性系統。同樣的，如果T3的core1沒有讀到T2的core3最后寫的數據值，或者T4的core1/core2/core3沒有讀到T3的core1最后寫的數據值，那么也不符合一致性系統。

圖4 不同core讀寫的時間順序

對于SWMR還有另一種有意思的方式來解釋，對于每個memory地址，存在固定數量的令牌，其數量至少與core數量一樣。如果一個core擁有所有的令牌，它就可以寫入memory地址，而且core必須至少有1個令牌，才能對memory地址進行讀取數據。因此，在任何給定的時刻，當有core正在讀寫memory地址的數據時，其它core正在寫入memory地址是不可能的。

一致性協議的兩點原則在設計一致性協議時至關重要。舉個比較常用的一致性無效協議(invalidate protocols)的設計方法：1.如果一個core想要讀取memory地址A，它會向其它core發送消息，以獲取memory地址A當前的最新值，并確保沒有其它core緩存該memory地址A的cacheline擁有寫權限的狀態。2.如果一個core想要寫入memory地址A，它會向其它core發送消息以獲取memory地址A的當前值，并確保沒有其它core緩存該memory地址A的cacheline擁有只讀或讀寫權限的狀態，也就是其它core都要無效掉自己緩存中memory地址A的cacheline。

3.一致性協議的類別

設計一致性協議決定了在每個參與一致性的組件控制器上可能擁有哪些cache狀態、發送或響應哪些一致性事務(transactions)操作、發生哪些事件(events)以及cache狀態轉換(transitions)等。設計一致性協議的方法有很多。

3.1 監聽和目錄

根據一個core的行為通知到其它core的方式可以分為監聽協議(Snooping protocol)和目錄協議(Directory protocol)。

3.1.1 監聽協議

監聽協議是第一類廣泛使用的協議，最初主導了商業市場，它們現在還有在各種小系統中使用。這種協議比較簡單，當cache miss發生時，cache的控制器會發出仲裁請求給共享總線廣播它的請求。共享總線確保所有cache控制器以相同的順序觀察到所有請求。監聽協議依賴共享總線以一致的順序向所有cache控制器發送廣播消息，因此分布式cache控制器能夠正確的更新自己的有限狀態機，這些有限狀態機共同代表了cache line的狀態。

要求以一致的總順序(total order)觀察廣播對于實現傳統監聽的共享總線具有重要意義。因為許多cache控制器可能同時嘗試發出一致性請求，共享總線必須將這些請求序列化成某種總順序(total order)。無論總線如何決定這個順序，這個機制被稱為監聽協議的保序點(serialization point或ordering point)。在一般情況下，一個cache控制器發出一個一致性請求，總線在保序點將它排序并廣播給所有cache控制器，包括發出請求的cache控制器，因此發出請求的cache控制器可以通過收到的監聽請求流來判斷它的請求在什么時候被處理了，在總順序中排在哪個位置。

舉個例子，監聽協議總線使用仲裁邏輯來確保一次只在總線上廣播一個請求。仲裁邏輯充當保序點，它有效地決定了各個一致性請求在總線上出現的順序。有個微妙的點是，cache控制器的一致性請求是在仲裁邏輯順序就排好序的，但是cache控制器只能通過監聽來觀察到這個順序，進而判斷自己請求的排序情況。因此，cache控制器的請求在保序點排好序后，可能會晚幾個周期才能被cache控制器觀察到請求順序。

監聽協議的latency比目錄協議低，而且實現也比較簡單，但是不易擴展。

圖5 監聽協議例子

3.1.2 目錄協議

目錄協議最初是為了解決監聽協議缺乏可擴展性的問題而開發的。目錄協議會創建一個目錄來維護每一個cacheline的一致性狀態的全局視圖。該目錄跟蹤各cache保存了哪些cacheline以及處于什么狀態。Cache控制器發出的一致性請求將直接單播給目錄控制器(通常也稱作home)。目錄控制器要么直接響應請求，要么根據目錄信息將請求轉發給一個或多個其它cache控制器，然后由后者響應。目錄協議使用間接層來避免有序廣播網絡和讓每個cache控制器處理每個請求。一致性請求傳輸流程通常包括兩個步驟(單播請求，然后是單播響應)或三個步驟(1個單播請求，K個轉發請求和K個響應，其中K是共享者的數量)。有些協議甚至還有第四部，因為響應間接通過目錄控制器，或者因為請求者在一致性流程完成時通知目錄控制器。相比之下，監聽協議將一個cacheline的狀態分布在所有cache控制器上，由于這種分布式狀態沒有中央單元記錄信息，一致性請求必須被廣播到所有cache控制器上。因此監聽協議的一致性請求流程總需要兩個步驟(廣播請求，然后是單播響應)。

在大多數目錄協議中，一致性請求在目錄控制器處排序，多個cache控制器可以同時向目錄控制器發送一致性請求，目錄控制器會序列化這些請求并排好序。如果兩個請求同時到達目錄控制器，目錄控制器會選擇首先處理哪個請求，第二個處理的請求的命運取決于目錄協議和請求的類型。第二個處理的請求可能：(a)在第一個請求之后立即得到處理；(b)暫時保存在目錄中等待第一個請求完成；(c)直接發送否定響應。在后一種情況下，目錄控制器向請求者發送否定確認響應，請求者必須重新發出其一致性請求。

目錄協議在目錄控制器上排序，因為大多數目錄協議不使用總順序的廣播，沒有序列化的全局概念。更確切說，一個一致性請求者相對于可能有副本的所有cache，必須單獨序列化。需要其它cache顯示的消息通知請求者的請求已被相關cache處理和序列化。比如說，對于想獲取寫權限的一致性請求，有共享副本的每個cache控制器一旦完成序列化了無效消息，都必須顯示地發送確認消息。

目錄協議需要更少的總線帶寬，實現了更大的可伸縮性，但代價是總線某些一致性請求的latency。

圖6 目錄協議例子

3.2 無效和更新

根據一個core決定寫cache line時，一致性協議中其它core的cache line副本如何處理，可以分為：無效協議(Invalidate protocol)和更新協議(Update protocol)。這個分類的選擇與協議是監聽還是目錄類型無關，它們可以兩兩交叉，組成4種類型的一致性協議。

3.2.1 無效協議

當一個core需要往某cacheline寫入一個值時，cache控制器會啟動一個一致性請求來使所有其它cache中對應的cacheline副本無效。一旦所有副本都無效后，請求者就可以將數據寫入該cacheline中，這樣就確保其它core不會讀取到舊值。如果另一個core希望在其副本無效后讀取該cacheline的值，則必須啟動一個新的一致性請求來獲取該cacheline的數據，并且它將從寫該cacheline的core處獲取副本，從而保證了數據一致性。

圖7 無效協議例子 (1->2->3->4->5->6)

3.2.2 更新協議

當一個core需要往某cacheline寫入一個值時，它會啟動一個一致性請求來更新所有其它cache中的副本，這樣所有cache用到的都是新值。

圖8 更新協議例子 (1->2->3->4->5->6)

這兩種協議的選擇需要權衡，更新協議減少了core讀取新值的latency，因為core不需要初始化并等待重讀一致性請求的完成。更新協議通常要比無效協議消耗更大的帶寬，因為更新協議除了傳輸地址，還要傳輸新值數據。此外，更新協議會使許多memory一致性模型的實現變得非常復雜。例如，當多個cache必須對一個cacheline的多個副本進行多個更新時，保持寫操作的原子性非常困難。由于更新協議的復雜性，它們很少被實現。

 監聽和目錄與無效和更新，這些可以檢查混合搭配，組成四種類型的一致性協議：監聽&&無效、監聽&&更新、目錄&&無效、目錄&&更新。Arm的ACE和CHI使用就是目錄&&無效組合。

4. 一致性協議的設計

4.1 狀態(states)選擇

4.1.1 狀態的特征

只有一個core的系統中，cache line的狀態要么有效要么無效。如果需要區分dirty狀態，則cacheline可能有兩種有效狀態。Dirty的cache line具有比memory更新的數據。具有多個core的系統也可以只使用這兩三種狀態，但通常需要區分不同類型的有效狀態。cache line狀態有四個主要特征：validity、dirtiness、exclusivity和ownership。后兩個特征是具有多core的系統所特有的。

• Validity：一個有效的cache line具有該cache line的最新值。Cache line可以被讀，但只有在它也是exclusivity的情況下才可以被寫。
• Dirtiness：如果一個cache line的值是最新的，且這個值與memory中的值不一致，那么這個cache line就是dirty的，緩存控制器負責最終用這個新值更新memory內容。Clean通常被用作dirty的反義詞。
• Exclusivity：如果一個cache line在系統中是唯一的cache line副本，則該cache line是exclusivity的，也就是該cache line除了可能在memory中，沒有任何其它cache擁有這個cache line的值。
• Ownership：如果cache控制器(或memory控制器)負責響應cache line的一致性請求，那么它就是這個cache line的owner。在大多數協議中，一個給定cache line始終只有一個owner。如果沒有將cache line的ownership交接給另一個一致性控制器，就算是由于cache容量或沖突缺失，這個cache line可能也不會從cache中被踢出去以騰出空間給另一個cache line。在某些協議中，非owned的cache line可能會被悄悄無效掉，不發送任何消息通知其它組件。

4.1.2 MOESI狀態模型

許多一致性協議使用經典的五態MOESI模型的子集。MOESI是cache中line的狀態，最基本的三種狀態時MSI，也可以使用O和E態，但是它們不是最基本的。O和E態通常是協議中優化某些場景使用的。這些狀態中的每一個都可以由上一小節描述的狀態特征組合而成。

• M(odified)：cache line是valid、exclusive、owned、并且可能是dirty的。這條line可以被讀或寫，且是cache中唯一的有效副本，擁有這條line的cache必須響應其它caches對這條line的請求，并且這條line在memory中的副本可能已經過期了。
• S(hared)：cache line是valid，但不是exclusive、dirty和owned的。這條line只能被讀，其它caches也可能具有這條line的有效只讀副本。
• I(nvalid) ：cache 里是invalid，cache要么不包含這條line，要么包含可能無法讀取或寫入的陳舊副本。
• O(wned) ：cache line是valid，owned、且可能是dirty的，但不是exclusive的。這條line只能被讀，并且擁有這條line的cache必須響應其它caches對這條line的請求。其它cache也可能有這條line的只讀副本，但它們不是owners。這條line在memory中的副本可能已經過期了。
• E(xclusive)：cache line是valid、owned、exclusive和clean的。這條line可以被讀或寫，沒有其它cache擁有這條line的有效副本，并且這條line和memory中的數據是一致的，memory中的副本是最新的。(需要注意的是，某些協議中，Exclusive不被視為owned的)

圖9用Venn圖展示了MOESI狀態。Venn圖可以展示哪些狀態共有哪些特征。除了I之外的所有狀態都有效。M、O和E是ownership狀態。M和E都是exclusivity，因為沒有其它cache擁有該line的有效副本。M和O都是表示該cache line可能是dirty的。M、O、E和S組成了V(alid)態。

圖9 MOESI狀態的Venn圖

MOESI狀態模型雖然很常見，但不是所有的狀態集合。例如，有些協議有F(orward)狀態，它類似與O狀態，除了它是clean的，即memory中的副本是最新的。Intel Core i7-9xx處理器中的QuickPath Interconnect(QPI)就使用了F狀態，QPI支持MESIF的5個狀態模型。

表1 MOESI的狀態特征

4.2 事務(transaction)選擇

一致性控制器組件的基本目標都是相似的，所以大多數一致性協議都有類似的transaction集合。例如，幾乎所有協議都有一個獲取Shared(只讀) cache line的transaction。表2列出了一組常見的transactions，并且對于每個transaction，描述發起transaction的請求者目標。這些transactions都是由cache控制器發起的，這些cache控制器響應來自其對應core的讀寫請求。表3列出了一個core可以像其cache控制器發出的讀寫請求，以及這些core請求如何引導cache控制器發起一致性transactions。

表2 常見的transactions

盡管大多數協議使用類似的transactions集合，但它們在一致性控制器如何交互以執行transaction方面存在相當大的差異。正如我們之前提到，在監視協議中，cache控制器通過向系統中所有一致性控制器廣播GetS請求來獲取目標的cache line，并且當前line的owner的控制器需要提供所需數據去響應請求者。相反，在目錄協議中，cache控制器通過向特定的目錄控制器發送單播GetS請求，目錄控制器可能直接響應，也可能將請求轉發給其它一致性控制器去響應請求者的line數據。

表3 core對cache控制器的常見請求

5.總結

為了彌補訪問memory速度太慢引進了cache。在多core系統中，每個core可能都有自己的私有cache，多個core會對自己的私有cache進行讀寫操作，如果不使用軟件或硬件來維護cache數據，必然會造成cache一致性問題。為了從硬件層面解決這個問題，現在大多數多core系統中都定義了一致性協議，讓各個一致性控制器遵照“ Single-Writer, Multiple-Read”和“ Data-Value”這兩條原則去維護存儲內容。在一致性協議設計中，根據core的行為如何通知其它core分為監聽協議和目錄協議，根據core決定寫cache line時，如何處理其它core的cache line副本，分為無效協議和更新協議。“監聽協議和目錄協議”與“ 無效協議和更新協議”可以兩兩交叉組成4種一致性協議，但目前最常用的是目錄協議和無效協議的組合。隨后抽象出cache line狀態的四個主要特征：validity、dirtiness、exclusivity和ownership，以及這四個特征如何對應到經典的MOESI狀態模型。最后介紹了一致性協議中常用的一致性transactions，以及core請求如何引導cache控制器發起一致性transactions。

本文沒有對cache狀態轉換(transitions)過程過多講述，也沒有講述異構系統和多芯片多處理器的一致性，現在計算機系統主要是異構的，不僅包含多core，還包含GPU和其它加速器(例如，神經網絡硬件)。為了追求可編程性，這些異構系統也開始支持共享內存。

希望本文能幫助大家了解更多的cache一致性知識。今天就寫到這里，后續會介紹memory consistency model，敬請期待。

本文轉載自微信公眾號「專芯致志er」，可以通過以下二維碼關注。轉載本文請聯系專芯致志er公眾號。