內存一致性與緩存連貫性導論

第1章 一致性與連貫性簡介    001
1.1 一致性（亦稱內存一致性、內存一致性模型或內存模型）    003
1.2 連貫性（亦稱緩存連貫性）    004
1.3 異構系統中的一致性與連貫性    006
1.4 定義並驗證內存一致性與緩存連貫性    007
1.5 一致性與連貫性小測驗    007
1.6 本書未涵蓋的內容    008
1.7 參考文獻    008

第2章 連貫性基礎    009
2.1 基準系統模型    010
2.2 問題：不連貫性是如何產生的    011
2.3 緩存連貫性接口    011
2.4 （一致性無關的）連貫性不變量    013
2.4.1 維護連貫性不變量    014
2.4.2 連貫性的粒度    014
2.4.3 連貫性何時與我們相關    016
2.5 參考文獻    016

第3章 內存一致性的動機以及連續一致性    017
3.1 共享內存行為的問題    018
3.2 什麼是內存一致性模型    021
3.3 一致性與連貫性的對比    021
3.4 連續一致性（SC）的基本思想    022
3.5 一點關於SC形式化的內容    025
3.6 樸素的SC實現    026
3.7 具有緩存連貫性的基本SC實現    027
3.8 具有緩存連貫性的優化SC實現    029
3.9 SC的原子操作    032
3.10 將它們放在一起：MIPS R10000    033
3.11 關於SC的進一步閱讀資料    034
3.12 參考文獻    035

第4章 全存儲順序以及x86內存模型    037
4.1 TSO/x86的動機    038
4.2 TSO/x86的基本思想    039
4.3 TSO/x86的形式化描述    042
4.4 實現TSO/x86    044
4.4.1 實現原子指令    045
4.4.2 實現FENCE    046
4.5 關於TSO的進一步閱讀資料    048
4.6 比較SC和TSO    048
4.7 參考文獻    049

第5章 松弛內存一致性    051
5.1 動機    052
5.1.1 重排序內存操作的機會    052
5.1.2 利用重排序的機會    054
5.2 一個松弛一致性模型（XC）示例    055
5.2.1 XC模型的基本概念    055
5.2.2 使用XC的FENCE的示例    056
5.2.3 形式化XC    057
5.2.4 展示XC正確運行的示例    058
5.3 實現XC    060
5.3.1 在XC中使用原子指令    062
5.3.2 在XC中的FENCE    062
5.3.3 一個警告    063
5.4 無數據競爭程序的連續一致性    063
5.5 一些松弛模型概念    067
5.5.1 釋放一致性    067
5.5.2 因果性和寫原子性    067
5.6 松弛內存模型案例研究    069
5.6.1 RVWMO    069
5.6.2 IBM POWER    072
5.7 進一步閱讀和商用松弛內存模型    075
5.7.1 學術文獻    075
5.7.2 商用模型    075
5.8 比較內存模型    076
5.8.1 松弛內存模型彼此之間以及與TSO和SC的關系    076
5.8.2 松弛模型有多好    077
5.9 高級語言模型    077
5.10 參考文獻    080

第6章 連貫性協議    082
6.1 概覽    083
6.2 定義連貫性協議    085
6.3 一個簡單連貫性協議的例子    085
6.4 連貫性協議的設計空間概述    087
6.4.1 狀態    088
6.4.2 事務    093
6.4.3 主要協議設計選項    094
6.5 參考文獻    095

第7章 監聽協議    097
7.1 監聽簡介    098
7.2 基準監聽協議    102
7.2.1 高級協議規範    102
7.2.2 簡單監聽系統模型：原子請求，原子事務    103
7.2.3 基準監聽系統模型：非原子請求、原子事務     107
7.2.4 運行示例    110
7.2.5 協議簡化    111
7.3 添加獨占狀態    112
7.3.1 動機    112
7.3.2 到達獨占狀態    112
7.3.3 協議的高級規範    113
7.3.4 詳細規範    115
7.3.5 運行實例    115
7.4 添加擁有狀態    118
7.4.1 動機    118
7.4.2 高層級協議規範    118
7.4.3 詳細協議規範    119
7.4.4 運行實例    121
7.5 非原子總線    122
7.5.1 動機    122
7.5.2 順序響應與亂序響應    122
7.5.3 非原子系統模型    123
7.5.4 使用分割事務總線的一個MSI協議    124
7.5.5 一個優化的、非阻塞的使用分割事務總線MSI協議    128
7.6 總線互連網絡的優化    131
7.6.1 用於數據響應的獨立非總線網絡    131
7.6.2 用於連貫性請求的邏輯總線    132
7.7 案例研究    133
7.7.1 SUN Starf?ire E10000    133
7.7.2 IBM Power5    134
7.8 監聽協議的未來    136
7.9 參考文獻    137

第8章 目錄連貫性協議    138
8.1 目錄協議介紹    139
8.2 基準目錄系統    140
8.2.1 目錄系統模型    141
8.2.2 高層次協議規範    141
8.2.3 避免死鎖    143
8.2.4 詳細協議規範    144
8.2.5 協議操作    146
8.2.6 協議簡化    148
8.3 添加獨占狀態    149
8.3.1 高層次協議規範    149
8.3.2 詳細協議規範    150
8.4 添加擁有狀態    153
8.4.1 高層次協議規範    153
8.4.2 詳細協議規範    153
8.5 表示目錄狀態    157
8.5.1 粗略目錄    157
8.5.2 有限指針目錄    158
8.6 目錄組織    158
8.6.1 基於DRAM的目錄緩存    159
8.6.2 包容性目錄緩存    160
8.6.3 空目錄緩存（無後備存儲）    162
8.7 性能和可擴展性優化    163
8.7.1 分布式目錄    163
8.7.2 非阻塞目錄協議    164
8.7.3 沒有點對點排序的互連網絡    164
8.7.4 靜默與非靜默逐出S狀態的數據塊    168
8.8 案例研究    169
8.8.1 SGI ORIGIN 2000    169
8.8.2 相幹超傳輸    170
8.8.3 超傳輸助手    172
8.8.4 INTEL QPI    172
8.9 討論和目錄協議的未來    174
8.10 參考文獻    174

第9章 連貫性高級話題    176
9.1 系統模型    177
9.1.1 指令緩存    177
9.1.2 轉換後備緩沖器（TLB）    178
9.1.3 虛擬緩存    178
9.1.4 寫直達緩存    179
9.1.5 連貫性DMA    180
9.1.6 多級緩存和層級結構連貫性協議    181
9.2 性能優化    183
9.2.1 遷移共享優化    183
9.2.2 偽共享優化    184
9.3 保持活躍度    185
9.3.1 死鎖    185
9.3.2 活鎖    188
9.3.3 饑餓    190
9.4 令牌連貫性    191
9.5 連貫性的未來    191
9.6 參考文獻    192

第10章 異構系統的一致性和連貫性    193
10.1 GPU的一致性和連貫性    194
10.1.1 早期的GPU：架構和編程模型    195
10.1.2 宏觀視角：GPGPU的一致性和連貫性    199
10.1.3 時間連貫性    200
10.1.4 釋放一致性導向的連貫性    209
10.2 不僅僅是GPU：探索更多的異構性    220
10.2.1 異構系統的一致性模型    220
10.2.2 異構系統的連貫性協議    222
10.3 進一步閱讀資料    228
10.4 參考文獻    229

第11章 內存一致性模型和緩存連貫性協議的定義與驗證    232
11.1 定義    233
11.1.1 操作化定義    234
11.1.2 公理化定義    238
11.2 探索內存一致性模型的行為    241
11.2.1 基準測試    241
11.2.2 探索    242
11.3 驗證實現    243
11.3.1 形式化方法    243
11.3.2 測試    246
11.4 歷史與進一步閱讀資料    247
11.5 參考文獻    248