摘要

許多現代計算機系統，包括同構架構（homogeneous architecture）和異構架構（heterogeneous architecture），在硬體上都支援共享記憶體（shared memory）。在共享記憶體系統中，每個處理器核心都能對一個共同的地址空間進行讀寫。而記憶體連貫性模型（consistency model）

［1］

就定義了共享記憶體機器中的，記憶體系統中可見的體系結構行為。

連貫性（consistency）定義了有關載入（load）和儲存（store）（或者記憶體讀寫（memory read/write））操作的規則，以及它們是如何作用到記憶體中的。作為連貫性模型的一部分，許多機器還提供了快取一致性協議（cache coherence protocol）

［1］

，以確保資料的多個快取副本（cached copies）能夠同時保持最新狀態。

本導論的目的就在於，讓讀者對連貫性和一致性

［1］

獲得一個基本的瞭解。其中既包括必須解決的問題，也包括各種問題的解決方案。在提供高層次抽象概念的同時，我們也會提供來自現實世界系統中的具體例子。

本書的第二版反映了自第一版以來，十年間發生的進展。除較小的改動外，第二版還增加了兩個新章節：一個關於非CPU加速器的連貫性和一致性（重點在於GPU），另一個則關於和連貫性和一致性相關的形式化（formalization）工作和工具。

關鍵詞：

computer architecture（計算機體系結構）， memory consistency（記憶體連貫性

［1］

）， cache coherence（快取一致性

［1］

）， shared memory（共享記憶體）， memory systems（記憶體系統）， multicore processor（多核處理器）， heterogeneous architecture（異構架構）， GPU（圖形處理單元）， accelerators（加速器

［2］

）， semantics（語義學

［3］

）， verification（驗證）

原書：《A Primer on Memory Consistency and Cache Coherence》（Second Edition）Vijay Nagarajan， Daniel J。 Sorin， Mark D。 Hill， David A。 Wood（Morgan&Claypool Publishers Synthesis Lectures On Computer Architecture）出版時間：Feb 2020

個人漢化了此書的目錄與前言，以便大家在搜尋相關中文關鍵詞時能獲得參考，但也僅供參考。如果幫到了您，那就再好不過了，希望能留個贊支援一下！（有支援才有動力嘛）

譯註

note0：本文中的多個術語，其目前的相關翻譯標準都非常混亂，所以請務必注意！交流時請暫時保留英文原名而不要進行翻譯，否則極易造成混亂。

note1：本文僅為個人翻譯，相關術語請以原文或已出版物中的翻譯為準。為幫助理解，我添加了大量註釋，以解釋某些可能看起來比較陌生的詞（僅為個人理解）。有任何疑問也可以在評論區提問，我儘量解答。

note2：

不少中文資料都混淆了連貫性（consistency）和一致性（coherence）

，很多地方會直接將兩者都翻譯為“一致性”，這導致了這些術語在中文方面的混亂。因此我認為幫助初學者對這兩種概念進行區分是有必要的，尤其是那些已經被混淆翻譯迷惑了的讀者。我會在本文中出現這兩術語的許多地方不斷重複引用它們的註釋

［1］

，還有它們的英文名詞

［4］

。

交流還時請暫時不要翻譯consistency和coherence，這方面的翻譯標準目前相當混亂。

note3：關於consistency和coherence，似乎很多地方都會將consistency或者coherence翻譯成一致性，但很少有地方會將coherence翻譯為連貫性。因此，似乎coherence更適合翻譯為一致性，然後consistency翻譯為連貫性。

note4：我們一般會將“memory”翻譯為“記憶體”，但實際上“記憶體”不一定為“內”。“memory”本身（在計算機領域）的含義應當是“儲存器”可指暫存器檔案、片內快取、片外快取、磁碟硬碟等任何帶儲存功能的器件。但為了方便，或者說讀起來更連貫，本文中許多地方還是會將“memory”翻譯為“記憶體”，請注意這不一定意味著它要處於什麼東西的“內部”。我甚至還看到某些地方說“記憶體（Memory）。。。。，也稱記憶體儲器和主儲存器”，非常具有迷惑性。我們知道，主儲存器（Main Memory）又是另一個術語了。初學者也可能會對這些翻譯感到迷惑，因此我在這裡做出一定解釋。

note5：根據“《計算機科學技術名詞 》第三版”，released consistency應該翻譯成“釋放一致性”，所以consistency到底應該翻譯成連貫性還是一致性呢？無奈，我只好不採用這一標準，在後文中將released consistency翻譯為釋放連貫性。

上面的說明略長，因此這裡將一些關鍵點進行總結：

本文中將“consistency”翻譯為“連貫性”。

本文中將“coherence”翻譯為“一致性”。

本文中將“relaxed consistency”翻譯為“鬆弛連貫性”，其中的“relaxd”翻譯為“鬆弛”或者“鬆弛的”。

本文中將“released consistency”翻譯為“釋放連貫性”，其中“released”翻譯為“釋放”或者“釋放的”。

本文中將“memory”翻譯為“記憶體”或者“儲存器”。

相關翻譯標準相當混亂，交流時請儘量使用英文原名。

本文中一切翻譯僅供參考！

如果讀者英文水平達標，建議直接閱讀原文。

如上，除技術內容本身外，有關這些術語該如何信達雅地翻譯，也是一件非常值得討論的問題。因此我在此拋磚引玉，還請各位各抒己見！

大家也可以說說在自己所接觸的中文材料中，這些術語是如何被翻譯的。這些都是非常有價值的參考資訊。

目錄（不展開）

■■1 有關連貫性和一致性

［1］

的介紹 Introduction to Consistency and Coherence

■■2 一致性基礎 Coherence Basics

■■3 記憶體連貫性的目的與順序連貫性 Memory Consistency Motivation and Sequential Consistency

■■4 全序儲存（TSO）

［5］

［6］

與x86記憶體模型 Total Store Order and the x86 Memory Model

■■5 鬆弛的記憶體連貫性 Relaxed Memory Consistency

■■6 一致性協議 Coherence Protocols

■■7 監聽一致性協議 Snooping Coherence Protocols

■■8 目錄一致性協議 Directory Coherence Protocols

■■9 一致性的高階主題 Advanced Topics in Coherence

■■10 異構系統的連貫性和一致性

［1］

Consistency and Coherence for Heterogeneous Systems

■■11 記憶體連貫性模型和快取一致性的規約化以及驗證 Specifying and Validating Memory Consistency Models and Cache Coherence

展開目錄較長，放在本文文末。

第二版序言

相較於近十年前的第一版（2011年），本書的第二版主要增加了兩篇新章節，同時還做出了一些其它改動。

新加的第10章涉及了有關非CPU加速器的新工作，主要是GPGPU，它們通常會同時實現連貫性和一致性。

新加的第11章則介紹了，自第一版以來，有關連貫性和一致性在形式化工作和工具方面的很大進展。

其它不那麼重要的變動包括：第2章闡述了一致性的定義，以接納第10章中關於類GPU的解決方案（GPU-like solution）；第3、4章分別討論了SC（Sequential Consistency）和TSO（Total Store Order）執行方面的最新進展；第5章新增了一個RISC-V的案例研究。

Vijay Nagarajan， Daniel J。 Sorin， Mark D。 Hill， and David A。 Wood

January 2020

第一版序言

本導論是為那些已非正式地接觸過記憶體連貫性和快取一致性

［1］

，但想進一步詳細瞭解它們的讀者所準備的。讀者範圍包括計算機行業中的專業人士，以及低年級研究生。

我們希望讀者能夠熟悉計算機體系結構的基礎知識，沒必要完整地記住Tomasulo演算法的每個具體內容，或者諸如此類的細節；但我們也確實希望讀者能夠理解諸如架構狀態、動態指令排程（亂序執行）、以及透過快取層次結構減少平均訪問延遲等這些問題和概念。

本導論的目的就在於，讓讀者對連貫性和一致性

［1］

獲得一個基本的見解。其中既包括必須解決的問題，也包括各種問題的解決方案。在提供高層次抽象概念的同時，我們也會提供來自現實世界系統中的具體例子。

本導論的第二個目標是：讓讀者明白，連貫性和一致性

［1］

是有多麼的複雜！即便讀者只是發現了他們所不知道的東西——而不是真正的學會——這種發現也仍然是一種具有實質性的收益。

此外，由於這些主題是如此的廣泛且複雜，以至於這些主題的詳盡介紹超出了本導論手冊的範圍。所以，我們的目標主要在於涵蓋基礎的知識，以讓讀者確定感興趣的方向，而不是去深入地涵蓋每個主題。

Daniel J。 Sorin， Mark D。 Hill， and David A。 Wood

November 2011

1 引言：有關連貫性

［1］

和一致性

［1］

的介紹

大多現代計算機系統和多核晶片（片上多處理器）在硬體上都支援共享記憶體。在共享記憶體系統中，每個處理器核心都可對同一個共享地址空間進行讀寫。這些各種設計都在尋求著各種優良的特性，如高效能、低功耗和低成本。

然而，僅提供這些優良特性而不提供

正確性（correctness）

［7］

的話，這些特性依舊是無法帶來價值的。

快取的正確性（correctness）

［7］

看起來似乎很簡單直觀（intuitive）。但實際上，正如本講座所顯示的：甚至，即便是在定義一個共享記憶體系統的正確性意味著什麼的時候，也存在著許多不易察覺的微妙問題；包括正確的共享快取（correct shared memory）在設計方面也是如此。

這些不易察覺的細節在硬體實現中應當加以考慮，因為錯誤的修復成本是非常昂貴的。即便是初學者也應該掌握這些細節，以使得自己設計方案更可能奏效。

要設計並評估一個正確的共享記憶體系統，架構師就必須對記憶體連貫性和快取一致性具有充分的瞭解，這也是本導論的兩個主題。

連貫性

［1］

記憶體連貫性

［8］

就是關於共享記憶體正確性（correctness）的定義，並且是精確且架構上可見的。連貫性定義了有關載入（loads）和儲存（stores）（或者記憶體讀寫（memory read/write））操作的規則，以及它們是如何作用到記憶體中的。

理想情況下，連貫性的定義應該是簡單且易於理解的。然而，共享記憶體的正確行為定義，實際上要比單執行緒處理器核心的正確行為定義要微妙得多。

單個處理器核心的正確性通常比較簡單，只需要在一個正確選擇和多個不正確選擇間做出選擇就行了。因為處理器的架構要求，對於給定的輸入狀態，執行緒的執行就應該產生單一且定義明確的輸出結果，即便亂序（out of order）核心也是如此。

［9］

但在共享記憶體連貫性模型的情況下，我們會涉及到多個執行緒的載入（load）和儲存（store）操作，這裡ISA可以允許多個執行緒的同時執行，因此可能會出現多種不同的正確執行（execution）

［10］

，通常是來自不同執行緒的指令間的多種合法交錯（interleaving）。

相較於僅需判斷單個執行是否正確的單核心（單執行緒），多執行的正確性（correctness）判斷要複雜得多。儘管如此，在某些情況下，為實現共享記憶體，或者編寫使用共享記憶體的正確程式，我們還是必須得掌握連貫性。

微架構（microarchitecture）——處理器核心與共享記憶體系統的硬體設計——必須去強制地執行它們所需的連貫性模型。

一致性

［1］

硬體還會提供快取上的快取一致性（或簡稱一致性），以作為這種連貫性模型支援的一部分。在帶有快取的共享記憶體系統中，只要其中一個處理器更新了它的快取中的值，這個快取值就可能變得過期（或不一致）

［11］

。而一致性的目的就是去防止這個問題出現，即確保共享記憶體系統的快取在功能上能與單核系統中的快取一樣：都是不可見的。關於此，可以透過將一個核心到快取的寫入廣播到其它快取的核心中，以實現這種一致性。

一致性和連貫性的區別

［1］

必須強調的是，一致性僅是用於支援連貫模型的一種手段，這與用於定義共享記憶體正確性（correctness）的架構規範的連貫性不同。

儘管連貫性（consistency）

［1］

是本導論的第一個重要主題，但我們還是會在第2章中首先簡要地介紹一遍一致性（cohorence）。因為一致性協議（coherence protocol）在提供連貫性方面能起到非常重要的作用。第2章的目標就是對一致性進行充分的解釋，以瞭解連貫性模型是如何與一致性快取互動的。但除此之外，第2章並不會具體討論有關一致性協議的具體內容或者實現，相關的這些主題將被推遲到本書的第二部分——第6～9章。

1。1 連貫性

［1］

（亦稱：記憶體連貫性、記憶體連貫性模型、記憶體模型）

［12］

連貫性模型定義了共享記憶體模型在載入（load）和儲存（store）操作（或者說記憶體讀寫操作）方面的正確行為，而不涉及快取或一致性。

（為幫助大家直觀理解連貫性模型，原書在這裡打了一個現實世界中的比方，但我覺得大家應該都比較熟悉，因此不翻譯這段。總之，連貫性模型定義了這方面行為的正確性（correctness），即哪些先後（因果）順序是正確的，哪些先後（因果）順序是錯誤的）感興趣的話請見原文！

總之，我們需要定義共享記憶體的正確性（correctness），或者說：“哪些共享記憶體行為是被允許的。”這樣，程式設計師才能知道它們可以期望什麼行為，實現者也才能知道他們應該提供什麼樣的限制。

共享記憶體的正確性是由記憶體連貫性模型（或者簡單來說就是，記憶體模型）指定的。記憶體模型規定了在共享記憶體上多執行緒程式執行中，哪些行為是被允許的。

對於在特定輸入資料下執行的多執行緒程式，記憶體模型（memory model）將指明：那些動態的載入操作可能返回的值；（可選的）以及記憶體可能的最終狀態

［13］

。與單執行緒執行不同的是，多執行緒通常可以允許多種正確的行為，從而使得記憶體連貫性模型的解讀和理解變得微妙。

第三章

第3章介紹了記憶體連貫性模型

［1］

的概念，並介紹了最強，也是最直觀的連貫性模型：順序連貫性（SC， Sequential Consistency）。在這章，我們首先說明了指定共享記憶體行為的必要性，並精確地定義了什麼是記憶體連貫性模型。

隨後便深入地研究了直觀的SC（Sequential Consistency）模型，該模型要求，（多核心的）多執行緒的執行，應當看起來就和在單核心上的多路複用（time-multiplex）執行下的多執行緒所表現一樣。

此外，本章還對SC進行了形式化（formalize），並同時探討了，帶一致性（coherence）的SC的簡單（simple）和激進（aggressive）的實現方式。在最後，我們以MIPS R10000的案例研究結束本章。

第四章

在第4章中，我們將注意力轉移到了SC之外：重點討論了歷史上的SPARC系統和x86所實現的記憶體連貫性模型

［1］

。他們實現的模型被稱之為全序儲存（TSO， Total Store Order），這種模型的目的是：希望在將結果寫入快取（cache）之前，能先用先進先出（FIFO， first in first out）的寫緩衝區（write buffers）來儲存已提交的儲存操作（committed store）。

這一最佳化

［14］

實際上違背了SC模型，但卻提供了非常大的效能優勢，而足以激勵我們在體系結構中定義TSO，以允許這種最佳化。在本章中，我們將展示：如何從SC的形式化中形式化出TSO；TSO會如何影響實現；以及SC與TSO間的比較。

第五章

最後，在第5章裡，我們介紹了所謂的“鬆弛”或者“弱”的記憶體連貫性模型（ “relaxed” or “weak memory consistency models）。這類模型基於這一觀察：“強模型中的大多數記憶體順序在實際上都是不必要的

［15］

”。

例如考慮一個這樣的程式片段：“首先更新10個數據項，然後再更新1個同步標誌。”很多時候程式設計師實際上並不關心這10個數據項間是否按照順序更新，而是隻要在同步標誌更新之前能更新所有資料項就行了。諸如此類的場景並不少見。鬆弛的模型就試圖去捕捉並利用這種次序的靈活性（flexibility），以獲得更高的效能，或者簡化實現。

基於這一動機，本章開發了一種稱之為XC的鬆弛連貫性模型，在該模型下，程式設計師必須主動地使用FENCE指令以獲得順序上的連貫性（例如，在最後一次資料更新後，標誌更新前，執行一個FENCE指令）

［16］

。

隨後，本章會對前兩章中的形式化（formalism）進行拓展，以處理SC，並討論XC的實現（在核心和一致性協議間進行大量的重新排序（reordering））。

然後，本章還討論了一種能讓程式設計師可以避免直接考慮鬆弛模型的一種辦法：只要新增足夠的FENCE，以確保程式無資料競爭（DRF， data-race free），大多鬆弛模型都可以表現為SC（Sequential Consistency）的。從而，程式設計師既可以得到（相對）簡單的正確性模型（即SC），又可以獲得XC的高效能。

對於那些想進一步深入思考的人，本章最後還總結了RELEASE和ACQUIRE的區別

［17］

，討論了寫入原子性（atomicity）和因果性（causality），並指出了相關的商業案例（包括一個IBM Power的案例研究），此外還涉及了高階語言模型（Java和CCC）。

（為幫助大家理解FENCE操作和弱連貫性（weak consistency），原作者又打了一個現實世界中的比方，同樣我也覺得大家應該都很熟悉這些東西，因此不翻譯。大意就是，透過執行一個FENCE操作，可以確保FENCE操作之前的操作對於FENCE之後的操作都是可見的）感興趣的話請見原文！

1。2 一致性

［1］

（亦稱：快取一致性）

除非非常小心敬慎，否則，在多個參與者（如，多個核心）可訪問同一資料的多個副本（如，在多個快取（cache）中），且至少有一個訪問是寫入（write）的情況下，肯定會出現一致性（coherence）的問題。

（為幫助大家理解一致性（coherence），作者在這裡又打了一個現實世界中的比方，我依舊認為大家很熟悉這些東西，因此不翻譯）感興趣的話請見原文！

可以用一致性協議（coherence protocol）來阻止對過期（或不一致）資料的訪問，一致性協議是一組規則，其由系統中的一組分散式的參與者實現

［18］

。正如第6～9章所討論的，一致性協議有很多變種，但都遵循了一些基本的思路。本質上，所有這些變體的思路都是：透過將一個處理器的寫操作廣播至所有快取上，以使另一個處理器可以看到該寫操作。這些協議的區別在於，進行同步（syncing）的時機和方式會有所不同。

這裡有兩類主要的一致性協議。在第一類方法中，一致性協議會確保讓寫入操作同步地廣播至所有快取中。在第二類方法中，一致性協議會將寫入操作非同步地廣播至所有快取中，但同時仍遵循連貫性模型 （consistency model）。本導論主要討論第一類一致性協議（第6～9章），第二類會在第10章中討論。

第六章

第6章介紹了快取一致性協議的總體情況（big picture），併為後續章節中有關特定一致性協議的詳細介紹奠定了基礎。

本章涵蓋了大多一致性協議中的共同主題，包括快取控制器和記憶體控制器的分散式操作，以及常見的MOESI一致性狀態：

M：modified（修改）

O：owned（自有）

E：exclusive（獨享/互斥）

S：shared（共享）

I：invalid（無效）

重要的是，本章還介紹了我們提出的表驅動法（table-driven methodology），其既可用於表示穩態一致性狀態（stable coherence states），也可用於表示瞬態一致性狀態（transient coherence states）

［19］

。

在實際實現（implementation）中是需要考慮瞬態的，因為現代系統中很少能有從一個穩態到另一個穩態間的原子（atomic）轉換（例如，對無效態（I， Invalid）進行讀取並缺失（read miss）後，需要花一些時間等待資料的響應，才能進入共享態（S， Shared））。一致性協議中的許多真正的複雜性（complexity）都隱藏在瞬態中，其程度類比於微架構狀態（micro-architectural states）所隱藏的處理器核心複雜性。

第七章

第7章涵蓋了監聽快取監聽一致性協議（snooping cache coherence protocols），其最初曾主導了商業市場。

在手勢訊號級別（hand-wave level），監聽協議（snooping protocols）都很簡單。一個核心的快取缺失（cache miss）發生時，其快取控制器會為共享匯流排進行仲裁，並廣播其請求。共享匯流排（shared bus）將確保所有控制器都能以相同的順序觀察所有請求，從而協調它們各自獨立的分散式操作，以確保它們能夠保持全域性一致連貫的狀態（globally consistent state）。

然而在實際情況中，系統可能會使用多條匯流排，並且現代匯流排也並不能原子地（atomically）處理請求。因而監聽（snopping）會變得很複雜。現代匯流排中，用於仲裁的佇列（queues for arbitration），對單播發送的響應可能會被流水線延遲和亂序所影響

［20］

。所有的這些特性，都會導致出現更多的瞬態一致性狀態（transient coherence states）。

在第7章的最後，我們還提供了關於SunUltraEnterprise E10000和IBM Power5的案例研究。

第八章

第8章對快取目錄一致性協議（directory cache coherence protocols）進行了深入的研究。相較於依賴於廣播（boardcast）的監聽協議，目錄協議能將承諾（promise）擴充套件至更多的處理器核心，以及其它的參與者上。

這裡有一個笑話（joke），就是說計算機科學中的所有問題都能透過間接的方式來解決。目錄協議支援這個笑話：快取缺失（cache miss）發生後，就會向下一級快取（或記憶體）的控制器傳送關於該記憶體位置（memory location）

［21］

的請求。

而該控制器則維護了一個，用於跟蹤哪些快取包含哪些位置（location）的表。根據所請求的記憶體位置對應的目錄項（directory entry），控制器會向請求者傳送響應資訊，或者將請求資訊轉發給其它一或多個，快取有該記憶體位置的接受者。

通常每個訊息都只有1個目的地（destination）（即，沒有廣播或者多播（multicast））， 但會存在非常多的瞬態一致性狀態，因為在從一個穩態一致性狀態過渡到另一個穩態一致性狀態的過程，將產生與系統中參與者數成比的資訊。

本章從一個基本的MSI目錄協議（MSI directory protocol）出發，隨後對其進行改進，以處理MOESI中的E和O狀態、分散式目錄、減少請求等待、近似目錄項表示等。

本章同時也探討了目錄本身的設計，包括目錄快取技術。最後，本章還提供了關於的較老的SGI Origin 2000和較新的AMD HyperTransport、Intel QuickPath Interconnect（QPI）的案例研究。

第九章

第9章討論了一些（不是全部）關於連貫性

［1］

的高階主題。為便於解釋，在其中前面有關一致性的章節中，我們會有意地將討論侷限於能解釋基本問題的最簡系統模型上。

第9章還深入討論了更復雜的系統模型和最佳化，重點是監聽（snooping）和目錄（directory）協議中的共同主題（topic）。基礎主題包括關於指令快取、多級快取、直寫快取（write-through cache）、快表（TLBs）、一致性直接記憶體訪問（coherence DMA（direct memory access））、虛擬快取和分層一致性協議（hierarchical coherence protocols）的處理。

最後，本章也深入討論了效能分析（如針對遷移共享（migratory sharing）和錯誤共享（false sharing）的）和被稱之為令牌一致性（TC， Token Coherence）的一族協議，其歸納了目錄和監聽協議。

1。3 異構系統中的連貫性和一致性

［1］

第十章

現代計算機系統中的大多數都是異構（heterogeneous）的。例如，如今的手機處理器中就同時包含了多核CPU、GPU和其它加速器（如神經網路硬體）等。為追求可程式設計性，這種異構系統也開始支援了共享記憶體（shared memory）。第10章就討論了這種異構處理器的連貫性和一致性。

本章首先關注GPU，它可以說是當下最流行的加速器（accelerator）了。本章注意到，GPU最初並沒有選擇支援硬體快取一致性，因為GPU主要是為麻煩的並行圖形工作負載（workload）所設計的，而這些工作負載並不需要同步或者共享那麼多的資料。

然而，一旦將GPU用於具有細粒度同步（fine-grained synchronization）和資料共享的工作負載，對硬體快取一致性支援的缺乏就會導致一些在可程式設計性或者效能方面的挑戰。本章就詳細討論了用於克服這些限制的，一些具有前途的一致性代替方案——特別是，解釋了為什麼候選的協議可以直接實現連貫性，而不是以一種連貫性不可知的方式實現一致性。

最後，本章還簡要地討論了CPU和加速器間的連貫性和一致性。

1。4 記憶體連貫性模型和快取一致性

［1］

的規約化以及驗證

第十一章

連貫性模型和一致性協議都是複雜且微妙的。但是，這種複雜性必須得到管理，以確保多核處理器是可程式設計的，並且它們的設計都能夠得到驗證（validate）。要實現這些目標，對連貫性模型進行正式的規約（specification）是至關重要的。形式化的規約可以允許程式設計師清楚、詳盡地（在工具的支援下）瞭解哪些行為是記憶體模型所允許的，而哪些行為則不允許。其次，一個精確的形式化規約對於實現的驗證來說也是必要的。

1。5 有關連貫性和一致性

［1］

的小測驗

我們很容易說服自己，認為自己對連貫性和一致性的瞭解已經足夠多了，從而沒必要閱讀本導論。為檢驗這種情況是否屬實，我們提供了以下小測驗：

問題一

［22］

：

在一個保持順序連貫性（SC， sequential consistency）的系統中，核心一定會按照程式順序發出一致性請求（issue coherence requests in program order）。請問這句話是對是錯？（答案見Section 3。8）

問題二

［23］

：

記憶體連貫性模型規定了一致性事務（coherence transactions）的合法順序（leagal orderings）。這句是對是錯？（Section 3。8）

問題三

［24］

：

要執行一個原子性的讀-修改-寫（atomic read-modify-write ）指令（如test-and-set），該核心必須始終與其它核心進行通訊（communicate）。這句是對是錯？（Section 3。9）

問題四

［25］

：

在帶有多執行緒核心的TSO系統中，執行緒可能會繞過寫緩衝區中的值，而不顧該值是哪個執行緒寫的。這句是對是錯？（Section 4。4）

問題五

［26］

：

在高階語言的連貫性

［1］

模型下（如Java），即便是不考慮架構的記憶體連貫性模型，程式設計師也可以寫出適當的同步程式碼。這句是對是錯？（Section 5。9）

問題六

［27］

：

在MSI監聽協議（MSI snooping protocol）下，快取塊只可能處於三種一致性狀態中的一種。請問這句話是對是錯？（Section 7。2）

問題七

［28］

：

監聽協議需要核心在總線上進行通訊。這句是對是錯？（Section 7。6）

問題八

［29］

：

GPU並不支援快取硬體一致性（hardware cache coherence），因此它無法強制地執行記憶體連貫性模型。這句是對是錯？（Section 10。1）

儘管本導論後面會為這些問題提供答案，但我們也鼓勵讀者在閱讀答案之前先嚐試回答問題。

1。6 本導論不會涉及的東西

本講座旨在成為連貫性和一致性

［1］

的入門課程。我們預計本材料能在研究生課堂中用大約10節75分鐘的課來講述（例如從第2章到第11章，每章1節課）。

基於這一目的，有很多東西實際上本導論並沒涵蓋。其中一些包括：

同步性（synchronization）。

一致性可使快取不可見，連貫性則可讓共享記憶體看起來就和單個記憶體模組一樣。然而，程式設計師可能還需要鎖（lock）、屏障（barrier）等其它同步技術來使得他們的程式有效。讀者可以參考有關共享記憶體同步的綜合講座［2］。

商用的鬆弛連貫性模型（Commercial Relaxed Consistency Models）。

本導論並沒有涵蓋ARM、PowerPC以及RISC-V的記憶體模型中的細節，但描述了它們用於提供執行順序的機制。

並行程式設計（Parallel programming）。

本導論並不討論並行程式設計的模型、方法以及工具。

分散式系統中的連貫性模型（Consistency in distributed systems）。

本導論僅侷限於共享記憶體多核中的連貫性，並不包括一般分散式系統中的連貫性模型及其實施。讀者可以參考有關資料庫複製［1］以及仲裁系統［2］的綜合講座。

1。7 參考文獻

［1］ B。 Kemme， R。 Jiménez-Peris， and M。 Patiño-Martínez。 Database Replication。 Synthesis Lectures on Data Management。 Morgan & Claypool Publishers， 2010。 DOI： 10。1007/978-1-4614-8265-9_110。8

［2］ M。 L。 Scott。 Shared-Memory Synchronization。 Synthesis Lectures on Computer Architecture。 Morgan & Claypool Publishers， 2013。 DOI： 10。2200/s00499ed1v01y201304cac023。7

［3］M。 Vukolic。 Quorum Systems： With Applications to Storage and Consensus。 Synthesis Lectures on Distributed Computing Theory。 Morgan & Claypool Publishers， 2012。 DOI： 10。2200/s00402ed1v01y201202dct009。8

目錄漢化（展開）

■■1 有關連貫性和一致性

［1］

的介紹 Introduction to Consistency and Coherence

■1 連貫性（亦稱：記憶體連貫性、記憶體連貫性模型、記憶體模型） Consistency （a。k。a。， Memory Consistency， Memory Consistency Model， or Memory Model）

■2 一致性（亦稱：快取一致性） Coherence （a。k。a。， Cache Coherence）

■3 異構系統中的連貫性和一致性 Consistency and Coherence for Heterogeneous Systems

■4 記憶體連貫性模型和快取一致性的規約化以及驗證 Specifying and Validating Memory Consistency Models and Cache Coherence

■5 有關連貫性和一致性的小測驗 A Consistency and Coherence Quiz

■6 本導論不會涉及的東西 What This Primer Does Not Do

■7 參考文獻 References

■■2 一致性基礎 Coherence Basics

■1 基準系統模型 Baseline System Model

■2 問題：不一致可能如何發生？ The Problem： How Incoherence Could Possibly Occur

■3 快取一致性介面 The Cache Coherence Interface

■4 （連貫性無關的）一致性不變數

［30］

（Consistency-Agnostic） Coherence Invariants

1 保持一致性不變數 Maintaining the Coherence Invariants

2 一致性的粒度 The Granularity of Coherence

3 一致性何時相關？ When is Coherence Relevant？

■5 參考文獻 References

■■3 記憶體連貫性的目的與順序連貫性 Memory Consistency Motivation and Sequential Consistency

■1 共享記憶體行為的問題 Problems with Shared Memory Behavior

■2 什麼事記憶體連貫性模型？ What is a Memory Consistency Model？

■3 連貫性vs一致性 Consistency vs。 Coherence

■4 關於順序一致性（SC）的基本思想 Basic Idea of Sequential Consistency （SC）

■5 關於SC的一些形式化 A Little SC Formalism

■6 簡單的SC實現 Naive SC Implementations

■7 在快取一致性下的基本SC實現 A Basic SC Implementation with Cache Coherence

■8 在快取一致性下的最佳化SC實現 Optimized SC Implementations with Cache Coherence

■9 原子操作與SC Atomic Operations with SC

■10 融會貫通：MIPS R10000 Putting it All Together： MIPS R10000

■11 關於SC的後續閱讀 Further Reading Regarding SC

■12 參考文獻 References

■■4 全序儲存（TSO）

［5］

［6］

與x86記憶體模型 Total Store Order and the x86 Memory Model

■1 TSO/x86的動機 Motivation for TSO/x86

■2 TSO/x86的基本思想 Basic Idea of TSO/x86

■3 關於TSO/x86的一些形式化 A Little TSO/x86 Formalism

■4 TSO/x86的實現 Implementing TSO/x86

實現原子指令 Implementing Atomic Instructions

實現圍牆（FENCE） Implementing Fences

■5 關於TSO的後續閱讀 Further Reading Regarding TSO

■6 SC與TSO的比較 Comparing SC and TSO

■7 參考文獻 References

■■5 鬆弛的記憶體連貫性 Relaxed Memory Consistency

■1 動機 Motivation

1 記憶體操作重排序的時機 Opportunities to Reorder Memory Operations

2 利用重排序的時機 Opportunities to Exploit Reordering

■2 一個鬆弛連貫性模型的例子（XC） An Example Relaxed Consistency Model （XC）

1 有關XC的基本想法 The Basic Idea of the XC Model

2 XC下使用圍牆（FENCE）的例子 Examples Using Fences Under XC

3 形式化XC Formalizing XC

4 一個XC正確操作執行的例子 Examples Showing XC Operating Correctly

■3 XC的實現 Implementing XC

1 XC下的原子指令 Atomic Instructions with XC

2 XC下的圍牆（FENCE） Fences With XC

3 一個忠告 A Caveat

■4 無資料競爭程式的順序一致性 Sequential Consistency for Data-Race-Free Programs

■5 一些鬆弛模型的概念 Some Relaxed Model Concepts

1 釋放連貫性 Release Consistency

2 因果性和寫原子性 Causality and Write Atomicity

■6 鬆弛記憶體模型的案例研究 Relaxed Memory Model Case Studies

1 RISC-V Weak Memory Order （RVWMO）

2 IBM Power

■7 有關商用鬆弛記憶體模型的後續閱讀 Further Reading and Commercial Relaxed Memory Models

1 學術文獻 Academic Literature

2 商業模型 Commercial Models

■8 記憶體模型的比較 Comparing Memory Models

1 鬆弛記憶體模型與TSO和SC分別的關係是什麼？ How Do Relaxed Memory Models Relate to Each Other and TSO and SC？

2 鬆弛模型有多好？ How Good Are Relaxed Models？

■9 高階語言模型 High-Level Language Models

■10 參考文獻 References

■■6 一致性協議 Coherence Protocols

■1 景圖 The Big Picture

■2 一致性協議的規約化 Specifying Coherence Protocols

■3 一個簡單的一致性協議例子 Example of a Simple Coherence Protocol

■4 有關一致性協議設計空間的總覽 Overview of Coherence Protocol Design Space

1 狀態 States

2 事務 Transactions

3 協議設計中的主要選項 Major Protocol Design Options

■5 參考文獻 References

■■7 監聽一致性協議 Snooping Coherence Protocols

■1 關於監聽的簡介 Introduction to Snooping

■2 基準監聽協議 Baseline Snooping Protocol

1 高層次的協議規約 High-Level Protocol Specification

2 簡單的監聽系統模型：原子請求，原子事務 Simple Snooping System Model： Atomic Requests， Atomic Transactions

3 基準監聽系統模型：非原子請求，原子事務 Baseline Snooping System Model： Non-Atomic Requests， Atomic Transactions

4 執行例子 Running Example

5 協議簡化 Protocol Simplifications

■3 引入獨享狀態 Adding the Exclusive State

1 動機 Motivation

2 進入獨享狀態 Getting to the Exclusive State

3 高層次的協議規約 High-Level Specification of Protocol

4 具體的規約 Detailed Specification

5 執行例子 Running Example

■4 引入自有狀態 Adding the Owned State

1 動機 Motivation

2 高層次的協議規約 High-Level Protocol Specification

3 具體的協議規約 Detailed Protocol Specification

4 執行例子 Running Example

■5 非原子匯流排 Non-Atomic Bus

1 動機 Motivation

2 順序響應vs亂序響應 In-Order vs。 Out-of-Order Responses

3 非原子系統模型 Non-Atomic System Model

4 分割式事務總線上的MSI協議 An MSI Protocol with a Split-Transaction Bus

5 分割式事務總線上的一個最佳化、無等待的MSI協議 An Optimized， Non-Stalling MSI Protocol with a Split-Transaction Bus

■6 針對互連網路匯流排的最佳化 Optimizations to the Bus Interconnection Network

1 用於資料響應的分立非匯流排網路 Separate Non-Bus Network for Data Responses

2 一致性請求的邏輯匯流排 Logical Bus for Coherence Requests

■7 案例研究 Case Studies

1 Sun Starfire E10000

2 IBM Power5

■8 關於監聽的未來討論 Discussion and the Future of Snooping

■9 參考文獻 References

■■8 目錄一致性協議 Directory Coherence Protocols

■1 關於目錄協議的簡介 Introduction to Directory Protocols

■2 基準目錄系統 Baseline Directory System

1 目錄系統模型 Directory System Model

2 高層次的協議規約 High-Level Protocol Specification

3 避免死鎖 Avoiding Deadlock

4 詳細的協議規約 Detailed Protocol Specification

5 協議操作 Protocol Operation

6 協議簡化 Protocol Simplifications

■3 引入獨享狀態 Adding the Exclusive State

1 高層次的協議規約 High-Level Protocol Specification

2 具體的協議規約 Detailed Protocol Specification

■4 引入私有狀態 Adding the Owned State

1 高層次的協議規約 High-Level Protocol Specification

2 詳細的協議規約 Detailed Protocol Specification

■5 目錄狀態的表示 Representing Directory State

1 粗目錄 Coarse Directory

2 有限指標目錄 Limited Pointer Directory

■6 目錄最佳化 Directory Organization

1 DRAM支援的目錄快取 Directory Cache Backed by DRAM

2 包容性目錄快取 Inclusive Directory Caches

3 空目錄快取（不帶輔助儲存） Null Directory Cache （With no Backing Store）

■7效能以及可擴充套件性的最佳化 Performance and Scalability Optimizations

1 分散式目錄 Distributed Directories

2 無暫停目錄協議 Non-Stalling Directory Protocols

3 無點到點順序的網際網路絡 Interconnection Networks Without Point-to-Point Ordering

4 S狀態塊的沉默與非沉默驅逐 Silent vs。 Non-Silent Evictions of Blocks in State S

■8 案例研究 Case Studies

1 SGI Origin 2000

2 Coherent HyperTransport

3 Hypertransport Assist

4 Intel QPI

■9 關於目錄協議的未來討論 Discussion and the Future of Directory Protocols

■10 參考文獻 References

■■9 一致性的高階主題 Advanced Topics in Coherence

■1 系統模型 System Models

1 指令快取 Instruction Caches

2 快表 Translation Lookaside Buffers （TLBs）

3 虛擬快取 Virtual Caches

4 直寫快取 Write-Through Caches

5 一致性直接記憶體訪問 Coherent Direct Memory Access （DMA）

6 多級快取和分層一致性協議 Multi-Level Caches and Hierarchical Coherence Protocols

■2 效能最佳化 Performance Optimizations

1 遷移共享最佳化 Migratory Sharing Optimization

2 錯誤共享最佳化 False Sharing Optimizations

■3 保持活性 Maintaining Liveness

1 死鎖 Deadlock

2 活鎖 Livelock

3 餓死 Starvation

■4 令牌一致性 Token Coherence

■5 關於一致性的未來 The Future of Coherence

■6 參考文獻 References

■■10 異構系統的連貫性和一致性

［1］

Consistency and Coherence for Heterogeneous Systems

■1 GPU連貫性和一致性 GPU Consistency and Coherence

1 早期的GPU：架構和程式設計模型 Early GPUs： Architecture and Programming Model

2 景圖：GPGPU連貫性和一致性 Big Picture： GPGPU Consistency and Coherence

3 時域一致性 Temporal Coherence

4 連貫性導向的釋放一致性

［31］

Release Consistency-directed Coherence

■2 比GPU還要異構 More Heterogeneity Than Just GPUs

1 異構連貫性模型 Heterogeneous Consistency Models

2 異構一致性協議 Heterogeneous Coherence Protocols

■3 後續閱讀 Further Reading

■4 參考文獻 References

■■11 記憶體連貫性模型和快取一致性的規約化以及驗證 Specifying and Validating Memory Consistency Models and Cache Coherence

■1 規約 Specification

1 操作規約 Operational Specification

2 公理規約 Axiomatic Specification

■2 探索記憶體連貫性模型的行為 Exploring the Behavior of Memory Consistency Models

1 試金石（檢驗測試） Litmus Tests

2 探索 Exploration

■3 實現的驗證 Validating Implementations

1 形式化方法 Formal Methods

2 測試 Testing

■4 歷史閱讀與後續閱讀 History and Further Reading

■5 參考文獻 References

參考

^

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

a

b

c

“Consistency”譯為“連貫性”，意思是執行的先後順序是一致的（特別要注意的是，這裡“先後順序”這一概念定義有一定的自由空間，比如可以定義為時間上事件發生的先後順序，也可定義為程式語義上的先後因果順序）。可以理解為時間上的的一致。“Coherence”譯為“一致性”，意思是資料（在不同地方）的多個副本（在某一致性模型下）是一致，或者說是相同的。可以理解為空間上的一致。 似乎很多地方把“Consistency”和“Coherence”都翻譯成了“一致性”，但這兩個術語是存在區別的，請注意區分！

^

硬體加速是指，在計算機中透過把計算量非常大的工作分配給專門的硬體，以減輕通用單元的負擔或提高效率的技術。

^

計算機科學領域下的語義學的研究物件包括機器對自然語言的理解。

^

關於consistency和coherence的翻譯，我也和別人爭論了一番。因為在單獨只出現consistency或者coherence的上下文情況下，它們翻譯成一致性的話會更貼切。但在這裡，必須要對consistency和coherence兩個概念進行區分。實際上也有人提議將consistency翻譯成一致性，coherence翻譯成連貫性。怎麼翻譯都行，但都翻譯成一致性的話肯定不行，因為這樣就混淆了。不過在本文，我還是將consistency翻譯成了連貫性，coherence翻譯成了一致性，因為很多（沒統一翻譯成一致性的）地方都是這麼翻譯的。總之，最重要的是要對這兩個概念進行區分，consistency≠coherence，至少在computer architecture這一領域中是如此。

^

a

b

這裡的“儲存（store）”不是儲存器（memory/storage）的簡稱，而是store操作的意思，store操作即向記憶體（memory）寫入資料，或者說就是記憶體寫入（memory write）操作的意思。

^

a

b

看起來“Total Store Order”這一術語的命名，源自“Store［計］”和“Total Order［數］”這兩個詞。原本我在這裡想介紹一下“Total Order（全序）”這一代數概念和TSO的關係，但是最終發現並沒有必要，因為這裡對“Total Order（全序）”這一概念的借用並不嚴謹，至少並不像數學家那樣嚴謹。因此，大家可以知道，在這一詞中，“Total Order”的意思是數學中的“全序”，這個詞本身的命名本身可能想表達的是，“所有Store操作能滿足全序關係（這裡的序關係特指執行的先後順序）”，但這裡並不值得深究。感興趣的話，可以在閱讀原文，瞭解TSO的概念之後，再去考慮它這一命名與“Total Order［數］”這一代數概念間的聯絡，反過來的話就不太好。

^

a

b

這裡所謂的“xx的正確性（correctness）”，就是一種用於判斷xx是否正確，或者說xx的行為是否正確的判斷標準。與之相對的就是 不正確/錯誤/不正確性。“正確性（correctness）”實際上才是本書的主題，後面介紹的連貫性和一致性都是實現正確性的具體手段。

^

記憶體連貫性（連貫性、記憶體連貫性模型，或記憶體模型）Memory consistency（consistency， memory consistency model， or memory model）

^

有人對這段翻譯不滿意，認為翻譯錯了。實際上我也對這段翻譯相當不滿意，其實因為不好翻譯，我直接主觀地將這一段重寫了一遍，所以這段翻譯的正確性可能存在爭議，還請以原文為準！如果有翻譯高手，也可以試著更好地翻譯這一段，給出的結果請發在評論區！總之，這裡給出原文：Shared memory consistency models， however， concern the loads and stores of multiple threads and usually allow many correct executions while disallowing many （more） incorrect ones。 The possibility of multiple correct executions is due to the ISA allowing multiple threads to execute concurrently， often with many possible legal interleavings of instructions from different threads。

^

原文這裡說的是“允許多個正確執行，同時還會有許多、更多（被駁回（disallowing）的）不正確執行”

^

out-of-date （or incoherent）

^

原標題：consistency （a。k。a。， memory consistency， memory consistency model， or memory model）

^

原文：For a multithreaded program executing with specific input data， the memory model specifies what values dynamic loads may return and， optionally， what possible final states of the memory are。

^

在將結果寫入快取（cache）之前，能先用先進先出（FIFO， first in first out）的寫緩衝區（write buffers）來儲存已提交的儲存操作（committed store）

^

原文：It motivates these models by showing that most memory orderings in strong models are unnecessary。

^

FENCE指令，簡單來說就是讓前面的操作對於後面的操作來說都可見。例如在這種鬆弛模型下，執行一個關於load和store的FENCE指令後，就能確保該FENCE指令後的所有指令都能看見該FENCE指令前的load和store操作，即能確保這些FENCE前的load和store操作都已經完成了資料修改。

^

這句話的原文是“the chapter concludes by distinguishing acquires from releases”。其中acquire和release是一對操作（operation），學過作業系統的應該會熟悉，比如訊號量（semaphore）中的acquire和release操作。

^

這句話的原文：Access to stale data （incoherence） is prevented using a coherence protocol， which is aset of rules implemented by the distributed set of actors within a system。

^

這裡的瞬態是指，從一個穩定狀態過渡到另一個穩定狀態的過程中，可能會出現的瞬態。穩態比如MOESI模型中的M、O、E、S、I五個狀態中的一個。

^

這句話的原文：Modern buses have queues for arbitration and can send responses that are unicast， delayed by pipelining， or out-of-order。

^

這個位置（location）指的是地址空間中的位置，可能會被對映到某個快取中。

^

原文：In a system that maintains sequential consistency， a core must issue coherence requests in program order。 True or false？ （Answer is in Section3。8）

^

原文：The memory consistency model specifies the legal orderings of coherence transactions。 True or false？ （Section3。8）

^

原文：To perform an atomic read–modify–write instruction （e。g。， test-and-set）， a core must always communicate with the other cores。 True or false？ （Section3。9）

^

In a TSO system with multithreaded cores， threads may bypass values out of the write buffer， regardless of which thread wrote the value。 True or false？ （Section4。4）

^

原文：A programmer who writes properly synchronized code relative to the high-level language’s consistency model （e。g。， Java） does not need to consider the architecture’s mem-ory consistency model。 True or false？ （Section5。9）

^

原文：In an MSI snooping protocol， a cache block may only be in one of three coherence states。 True or false？ （Section7。2）

^

原文：A snooping cache coherence protocol requires the cores to communicate on a bus。 True or false？ （Section7。6）

^

原文：PUs do not support hardware cache coherence。 Therefore， they are unable to enforce a memory consistency model。 True or False？ （Section10。1）

^

這裡，不變數（invariants）中的“量”指的是系統中的某些性質，即，這裡也可以將invariant翻譯為“不變的性質”。

^

這裡的“釋放（release）”指的是Release Consistency中的RELEASE操作，有關Release Consistency的介紹見本書5。5。1。