1.為何需要cache一致性

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

圖1 存儲器結構層次

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

圖2 兩core系統(tǒng)讀取0x80地址的數據

core0對0x80執(zhí)行寫操作，寫入值為0x01。Core0的私有L1 cache更新對應cacheline的值。然后，core1讀取0x80的數據，core1發(fā)現命中自己私有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一致性需要制定一致性協(xié)議，一致性協(xié)議是由系統(tǒng)內的各個分布式硬件參與者組件共同實現和維護的一組規(guī)則。一致性協(xié)議有許多版本，Arm的ACE(AXI Coherency Extensions)和CHI(Coherent Hub Interface)，AMD的Coherent HyperTransport（HT），Intel的QuickPath Interconnect(QPI)等等。

2.一致性協(xié)議的本質

雖然一致性協(xié)議眾多，但本質上講，所有一致性協(xié)議都通過將寫入的數據傳播到所有一致性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可以讀取到不同的值，那么就不符合一致性系統(tǒng)。同樣的，如果T3的core1沒有讀到T2的core3最后寫的數據值，或者T4的core1/core2/core3沒有讀到T3的core1最后寫的數據值，那么也不符合一致性系統(tǒng)。

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

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

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

3.一致性協(xié)議的類別

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

3.1 監(jiān)聽和目錄

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

3.1.1 監(jiān)聽協(xié)議

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

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

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

監(jiān)聽協(xié)議的latency比目錄協(xié)議低，而且實現也比較簡單，但是不易擴展。

圖5 監(jiān)聽協(xié)議例子

3.1.2 目錄協(xié)議

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

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

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

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

圖6 目錄協(xié)議例子

3.2 無效和更新

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

3.2.1 無效協(xié)議

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

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

3.2.2 更新協(xié)議

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

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

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

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

4. 一致性協(xié)議的設計

4.1 狀態(tài)(states)選擇

4.1.1 狀態(tài)的特征

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

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

4.1.2 MOESI狀態(tài)模型

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

• 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中的副本是最新的。(需要注意的是，某些協(xié)議中，Exclusive不被視為owned的)

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

圖9 MOESI狀態(tài)的Venn圖

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

表1 MOESI的狀態(tài)特征

4.2 事務(transaction)選擇

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

表2 常見的transactions

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

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

5.總結

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

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

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

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