内存一致性与缓存连贯性导论

本书系统阐述了多核处理器架构中内存一致性模型与缓存连贯性协议的核心原理及实现。全书从基础概念入手，在介绍内存一致性与缓存连贯性的本质区别与内在联系的基础上，深入解析连续一致性（SC）、全存储排序（TSO）及松弛内存模型等主流内存模型的设计哲学与实现策略，并通过监听协议和目录协议详尽剖析缓存连贯性协议的设计空间、状态机模型及性能优化方法。最后拓展讨论异构系统（特别是GPU）的一致性挑战、形式化验证方法以及前沿研究方向，为读者构建了从理论规范到硬件设计的完整知识体系。
本书适合需深入理解内存系统的相关技术人员参考，亦可作为高校计算机相关专业的教材。

无

第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