虽然多核现在是主流架构，但很少有教科书涵盖并行多核体系结构。本书填补了这一空白，为研究生或高级本科体系结构课程提供了所有材料，重点是多核处理器的体系结构。这本书也适合作为从事多核编程或多核芯片设计的专业人员的参考书。

无

从大概10年前开始，处理器的设计方式发生了巨大的变化。从表面上看，似乎没有什么明显的变化：晶体管密度依然按照摩尔定律每18～24个月翻一番。但如果仔细分析，会发现很多地方都发生了显著的变化。曾经按照摩尔定律增长的处理器时钟频率开始变得停滞不前。处理器生产商开始从在管芯上设计单核处理器转向设计多核处理器，通常也被简称为多核（multicore）。这些多核芯片的发展标志了处理器行业的一个重要转变。从物理的角度来看，转向多核设计的原因在于设计更高性能（更深或更宽的流水线）的单核处理器所带来的功耗密度增长无法接受。这也是处理器设计第二次遭遇功耗的物理限制，第一次遭遇导致处理器设计由双极型晶体管全面转向采用更高功效的互补金属氧化物半导体（CMOS）晶体管。而这次没有可以替代CMOS晶体管的功效更高的技术，因此功耗限制需要通过体系结构的改变来解决，即从单核处理器转变为多核处理器。虽然并行体系结构已经出现了很长一段时间，但随着向多核处理器的转变，并行体系结构将会成为当代处理器的主流设计。
从处理器设计者的角度来看，理论上性能可以通过首先转向多核，之后增加管芯上的核心数来保持很长一段时间的增长。然而从编程人员的角度来看，转向多核会导致一个很重要的结果：性能的增长依赖于程序员编写并行代码的能力，以及如何调优并行代码使其具有较好的可扩展性。在多核处理器之前，程序员只需要关注增加可编程性或者编程抽象的层次，即便这样做会导致代码复杂度的增加以及执行效率的降低，因为他们知道处理器核会变得越来越快从而抵消这些不利影响。然而，现在程序员如果希望克服可编程性和抽象层次增加对性能的不利影响，需要考虑如何利用多核处理器所提供的并行优势来编写程序。换句话说，并行编程和性能调优对许多程序员而言已经成为不可或缺的能力。
尽管多核已经成为主流体系结构，但在写作本书时，市场上几乎没有任何教科书涵盖了并行多核体系结构。虽然有很多关于并行编程以及传统并行体系结构的教科书，也有一些与多核体系结构相关的特定主题的短篇讲义，但是笔者未找到完整的讲解多核体系结构的教科书。这方面的缺失促成了笔者完成本书。笔者希望本书关于多核体系结构的内容有助于当前教授计算机体系结构的教师讲授相关内容。笔者同时也希望本书能够帮助还没有教授多核体系结构的教师开设该课程。最后，笔者希望本书能够成为多核编程或者设计多核芯片的专家的工具书。
笔者在写作本书时面临一些重大的挑战。首先，微处理器技术的变化节奏非常快。本书涵盖的一些主题仍然处于不断变化中，导致笔者对相关内容进行了多次迭代。例如，在写作之初，一个典型的多核处理器包含两个处理器核并共享L2高速缓存，然而在完成本书写作时，管芯上的处理器核数量增加到了16个，并且具有更深、更复杂的存储层次。撰写变化如此之快的相关技术非常具有挑战性。此外，另一个重大的挑战是关于多核体系结构有太多的主题，单就一本教科书的厚度无法全部涵盖。因此，笔者在写作本书时需要做出决定：包含哪些主题和不包含哪些主题。因此非常遗憾，本书无法满足所有读者的需求，一些读者可能会发现他们感兴趣的主题并没有包含在内或者不够深入。然而，笔者尝试着涵盖多核体系结构中最基础的内容，并希望以此为跳板供读者继续阅读其他资料。笔者相信本书可以为读者提供预备知识，进而继续阅读多核体系结构领域的研究论文。
本书基于笔者在2009年写作并出版的《并行计算机体系结构基础：多芯片和多核系统》（Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems）。与该书相比，本书不仅扩展了所涵盖的有关多核体系结构的内容，而且将多核体系结构作为讨论的中心。
本书在写作过程中始终遵循以下理念。第一，本书的内容适用于研究生、高年级本科生，以及受过计算机科学或工程训练的专业人士。一些涉及操作系统（进程、线程、虚拟内存）和计算机组成（指令集、寄存器）的基本概念在书中只是简单提及，笔者假设读者已经了解相关基本概念。
第二，当介绍一个概念时，笔者首先构建一个场景并引导读者理解该问题，之后再引入相关概念。因此，对于有些读者来说本书的叙述可能有些烦琐，但对另一些读者来说这将有助于他们更清晰地理解相关问题和概念。
第三，除了一些特例之外，本书各章都设计得相对较短，因此读者利用一个周末完成一章的阅读并没有太大难度。笔者希望学生可以完整阅读本书，即使需要跳过本书的一些内容，也希望是跳过整章而不是一章的部分内容。为了缩短各章的长度，笔者将本书的内容分解为更多的章节（相对于本领域的典型教科书而言）。例如，关于高速缓存一致性（后文简称缓存一致性）的内容被划分为3章：第6章引出问题，第7章介绍了广播缓存一致性协议，第10章介绍了目录式缓存一致性协议和更多高级主题。
第四，笔者致力于让本书更具吸引力。一个独特的地方就是分散在本书不同地方的“你知道吗？”文本框，用于展示小的案例分析、不同的观点、例子，或者有趣的事实和讨论内容。另一个独特的地方就是在本书的最后包含了对并行多核体系结构领域的专家访谈，通过专家的视角介绍了多核体系结构的过去、现在和将来。这些访谈中提到的一些技术可能还不成熟，但仍然是有价值且能激发读者思考的。读者并不需要完全接受受访者以及笔者的观点，而应将这些观点作为跳板，并基于本书内容形成自己的思考。
本书包括网上的补充材料，有助于加深读者对内容理解的编程作业和解答也会发布在网上。
本书的组织
在对多核体系结构进行概述（第1章）之后，本书分为三个部分。第一部分包括第2～4章，介绍在共享存储多处理器中的编程问题，如编程模型、并行化规则和非规则应用的技术。第一部分的目标是让读者理解什么样的软件原语是重要的，以及需要什么样的硬件来支持这些软件原语。第一部分的目标并不是深入讨论并行编程，因为已经有很多教科书涵盖了并行编程的内容。
第二部分包括第5～12章，其中第5～11章是本书的核心，介绍了共享存储多处理器体系结构，包括存储层次、设计共享存储并行多处理器时的基本问题、缓存一致性、存储一致性、同步和互连网络；第12章由笔者的同事Huiyang Zhou撰写，该章介绍了主要用于图形处理单元（GPU）系统的单指令流多线程（SIMT）编程模型。
本书的最后一部分即对多核体系结构领域专家的访谈内容。笔者很高兴能邀请到以下专家通过访谈的形式为本书提供素材：
Josep Torrellas：并行多核体系结构访谈
Li-Shiuan Peh：片上网络设计访谈
Youfeng Wu：并行多核体系结构编译技术访谈
Paolo Faraboschi：以数据为中心的系统的未来内存和外存体系结构访谈
建议的课程安排
本书涵盖的内容要多于通常三学分学期制课程所能讲授的内容。因此，根据授课教师想要强调的主题，可根据不同的方式在课程中使用本书的内容。而剩余的内容则可以作为另一门课程的主要部分，如更高阶的研究生课程。在北卡罗来纳州立大学，笔者更加强调硬件部分的主题，课程的设置如下图左列所示。如果更加关注软件部分的主题，则课程的设置可以如下图右列所示。在这两列中，上半部方框所包含的内容更适合导论性质的研究生课程和三学分学期制课程。下半部方框所包含的内容更适合独立的、高阶的研究生课程。
根据笔者的经验，如果采用更强调硬件的课程设置，并行编程部分会占据课程内容的近三分之一，而并行体系结构部分会占据课程内容的剩余三分之二。

致谢
感谢选修NCSU 2006年秋季CSC/ECE 506课程的同学，你们激发了我完成本书前身的撰写。感谢选修CSC/ECE 506后续课程的同学对本书的反馈及鼓励。同时感谢所有已毕业的博士生，你们的鼓励使我完成了本书的撰写：Mazen Kharbutli（2005年）、Seongbeom Kim（2007年）、Fei Guo（2008年）、Brian Rogers（2009年）、Xiaowei Jiang（2009年）、Siddhartha Chhabra（2010年）、Fang Liu（2011年）、Ahmad Samih（2012年）、Anil Krishna（2013年）、Devesh Tiwari（2013年）和Ganesh Balakrishnan（2013年）。感谢Fang Liu、Ahmad Samih、Brian Rogers、Xiaowei Jiang、Sharad Bade、Asaf Ebgi和Venkata为本书提供了实验数据。
关于作者
汤孟岩（Yan Solihin）是北卡罗来纳州立大学电子与计算机工程系教授。1995年在万隆理工学院获得计算机科学学士学位，1995年在印尼公开大学获得数学学士学位，1997年在南洋理工大学获得计算机工程硕士学位，1999年和2002年在伊利诺伊大学香槟分校分别获得计算机科学硕士和博士学位。获得2005年和2010年IBM Faculty Partnership奖、2004年美国国家自然科学基金杰出青年基金、1997年AT&T领军人物奖。入选HPCA名人堂，排名第二（截至2015年）。IEEE高级会员。
自2002年开始参与计算机体系结构教学。研究兴趣包括计算机体系结构、计算机系统建模方法和图像处理。在计算机体系结构和性能建模领域发表过50多篇论文。相关研究受到美国国家自然科学基金、Intel、IBM、Samsung、Tekelec、Sun Microsystems和HP的资助。开源了若干软件，包括：ACAPP高速缓存性能模型工具集、HeapServer安全堆管理库、Scaltool并行程序可扩展性检测工具、Fodex文件检测工具集。撰写研究生教材《并行计算机体系结构基础：多芯片和多核系统》。
在北卡罗来纳州立大学期间，建立和领导了针对性能、可靠性和安全的体系结构研究小组。指导毕业博士生13人、硕士生8人，目前正在指导博士生5人。

计算机体系结构

本书成功地涵盖了并行多核体系结构和相应的编程模型，并在存储层次设计这个关键上下文中论述相应主题。本书可供计算机科学与技术专业高年级本科生和研究生使用，不仅内容丰富，而且在现代多核体系结构的设计原则和实现细节间达到了很好的平衡。
—— Robert van Engelen, 佛罗里达州立大学
作者首先讨论了硬件基础和多核体系结构的历史，接着讨论了如何分析代码以确定并行性（以及不同并行化技术的基本概念），然后讨论了如何编写共享存储并行程序的具体细节等。通过这种方式，主题可以更加集中在本书想要表达的内容上，即构建多核体系结构的细节。本书内容得到了精心的组织和安排，我相信学生会喜欢本书。
—— Daniel R. Reynolds, 南卫理公会大学
本书非常适合想要深入理解多核体系结构，并针对这些体系结构设计高效程序的学生和实践者。
—— Purushotham Bangalore, 阿拉巴马大学伯明翰分校

本书特点
从不同的视角向读者介绍共享存储并行程序是如何编写的。
帮助读者理解共享存储多核和多处理器所需要的软件基础及硬件支持。
讨论了存储层次、设计共享存储并行多处理器时的基本问题、高速缓存一致性、存储一致性、同步、互连网络，并向读者展示不同概念是如何交互和适配的。
探索图形处理单元（GPU）系统中经常使用的单指令流多线程（SIMT）编程模型。

[美]汤孟岩（Yan Solihin）著：汤孟岩（Yan Solihin） 北卡罗来纳州立大学电子与计算机工程系教授，长期从事计算机体系结构方向的研究工作。研究兴趣包括计算机体系结构、计算机系统建模方法和图像处理，在计算机体系结构和性能建模领域发表过大量高水平论文，相关研究受到美国国家自然科学基金、Intel、IBM、Samsung、Tekelec、SunMicrosystems和HP的资助。他于2017年被选为IEEE会士，并入选了高性能计算机体系结构国际会议（HPCA）名人堂（2015年）。此外，他还长期从事计算机体系结构的教学工作，具有丰富的教学经验。创立和领导了针对性能、可靠性和安全的体系结构研究小组，并且开源了大量针对多核体系结构性能建模和性能优化的软件工具。

随着“内存墙”和“能耗墙”的出现，提高单核处理器性能变得愈发困难，越来越多的研究者和制造商开始将视线转向多核体系结构，从而获得进一步的处理器性能提升。然而，基于多核体系结构的处理器并不是“免费的午餐”，软件开发人员需要充分了解多核体系结构的特点，并且编写与之相适应的并行程序，才能充分发挥多核体系结构的性能优势。随着多核逐渐成为未来处理器设计的主流架构，如何调整现有的计算机体系结构课程内容，讲授多核体系结构知识，对教学而言是很大的挑战。
本书的出现正好弥补了多核体系结构教材的缺失，基于多核体系结构领域多年的研究和教学实践经验，作者尽可能地涵盖多核体系结构最基础的内容，帮助读者掌握多核体系结构的精髓。本书大致可以分为两大部分，第一部分首先介绍了多核体系结构的由来，在此基础上引入了并行计算机的分类方法，并对未来多核体系结构进行了展望。第二部分主要针对共享存储多处理器体系结构，介绍了其中的核心知识，包括存储层次、缓存一致性、存储一致性、同步、互连网络，以及单指令流多线程编程模型等。本书的最后引用了作者与多核体系结构领域专家的访谈内容，通过专家的视角对多核体系结构的发展进行了总结和展望。此外，为了增加可阅读性，本书插入了不少简短的案例分析、有趣的事实或者讨论内容。同时在每章的结尾配备了课堂和课后习题，通过解题过程帮助读者掌握相关知识。
本书作者Yan Solihin为北卡罗来纳州立大学电子与计算机工程系教授，长期从事计算机体系结构方向的研究工作，研究兴趣包括计算机体系结构、计算机系统建模方法和图像处理，在计算机体系结构和性能建模领域发表过大量高水平论文，入选了高性能计算机体系结构（HPCA）国际会议名人堂（2015年）。此外，作者长期从事计算机体系结构的教学工作，具有丰富的教学经验；创立和领导了针对性能、可靠性和安全的体系结构研究小组，并且开源了大量针对多核体系结构性能建模和性能优化的软件工具。
书中有些术语目前还没有统一译法，所以在翻译过程中保留了其英文名称。由于时间和水平有限，译文中难免存在错误和不妥之处，恳请广大读者和同行不吝批评指正。
本书在翻译过程中得到了北京航空航天大学计算机学院老师和同学的大力支持。另外，本书的出版还得到机械工业出版社华章分社的大力帮助，在此对出版社同仁在排版和校对等环节的辛勤付出表示衷心的感谢。我们希望本书的出版能对国内体系结构的教学和人才培养起到促进作用。

钱德沛

译者序
前言
缩写词表
第1章　多核体系结构概述 1
1.1　多核体系结构的由来 2
1.2　并行计算机概述 9
1.2.1　并行计算机的Flynn分类法 12
1.2.2　MIMD并行计算机分类 13
1.3　未来的多核体系结构 14
1.4　习题 18
课堂习题 18
课后习题 18
第2章　并行编程概述 20
2.1　并行程序性能的限制因素 20
2.2　并行编程模型 23
2.2.1　共享存储与消息传递模型的对比 25
2.2.2　一个简单的例子 26
2.2.3　其他编程模型 29
2.3　习题 37
课后习题 37
第3章　共享存储并行编程 39
3.1　并行编程的步骤 39
3.2　依赖分析 40
3.2.1　循环级依赖分析 42
3.2.2　迭代空间遍历图和循环传递依赖图 42
3.3　识别循环结构中的并行任务 45
3.3.1　循环迭代间的并行和DOALL并行 45
3.3.2　DOACROSS：循环迭代间的同步并行 46
3.3.3　循环中语句间的并行 48
3.3.4　DOPIPE：循环中语句间的流水线并行 50
3.4　识别其他层面的并行 51
3.5　通过算法知识识别并行 53
3.6　确定变量的范围 55
3.6.1　私有化 56
3.6.2　归约变量和操作 57
3.6.3　准则 58
3.7　同步 59
3.8　任务到线程的映射 60
3.9　线程到处理器的映射 64
3.10　OpenMP概述 67
3.11　习题 72
课堂习题 72
课后习题 77
第4章　针对链式数据结构的并行编程 79
4.1　LDS并行化所面临的挑战 79
4.2　LDS并行化技术 80
4.2.1　计算并行化与遍历 80
4.2.2　针对数据结构的操作并行化 82
4.3　针对链表的并行化技术 89
4.3.1　读操作之间的并行 89
4.3.2　LDS遍历中的并行 91
4.3.3　细粒度锁方法 94
4.4　事务内存 98
4.5　习题 99
课堂习题 99
课后习题 101
第5章　存储层次结构概述 103
5.1　存储层次的意义 103
5.2　高速缓存体系结构基础 104
5.2.1　数据放置策略 105
5.2.2　数据替换策略 109
5.2.3　数据写策略 111
5.2.4　多级高速缓存中的包含策略 113
5.2.5　统一/分立/Banked高速缓存和高速缓存流水线 117
5.2.6　高速缓存寻址和旁路转换缓冲 119
5.2.7　非阻塞式高速缓存 121
5.3　高速缓存性能 122
5.3.1　高速缓存缺失的幂次定律 124
5.3.2　栈距离特性 125
5.3.3　高速缓存性能指标 126
5.4　预取 127
5.4.1　步长预取和顺序预取 128
5.4.2　多处理器系统中的预取 130
5.5　多核体系结构中的高速缓存设计 130
5.6　高速缓存的物理组成 131
5.6.1　集中式高速缓存 131
5.6.2　分布式高速缓存 133
5.6.3　混合式高速缓存 133
5.7　高速缓存的逻辑组成 135
5.7.1　散列函数 139
5.7.2　改善共享高速缓存的距离局部性 140
5.7.3　私有高速缓存结构中的容量共享 141
5.8　案例分析 143
5.8.1　IBM Power7的存储层次 143
5.8.2　AMD Shanghai和Intel Barcelona处理器存储层次的比较 146
5.9　习题 148
课堂习题 148
课后习题 150
第6章　共享存储多处理器简介 152
6.1　缓存一致性问题 153
6.2　存储一致性问题 155
6.3　同步问题 156
6.4　习题 160
课堂习题 160
课后习题 161
第7章　缓存一致性基础 163
7.1　概述 164
7.2　基于总线的多处理器缓存一致性问题 168
7.2.1　“写直达”缓存的一致性协议 168
7.2.2　“写回”缓存的MSI协议 170
7.2.3　“写回”缓存的MESI协议 175
7.2.4　“写回”缓存的MOESI协议 178
7.2.5　“写回”缓存基于更新的协议 183
7.3　缓存设计对缓存一致性性能的影响 186
7.4　性能及其他实际问题 187
7.4.1　预取和一致性缺失 187
7.4.2　多级缓存 187
7.4.3　侦听过滤 189
7.5　点对点互连网络上的广播式协议 189
7.6　习题 203
课堂习题 203
课后习题 207
第8章　对同步的硬件支持 209
8.1　锁的实现 209
8.1.1　对锁实现性能的评估 209
8.1.2　对原子指令的需求 210
8.1.3　TS锁 212
8.1.4　TTSL 214
8.1.5　LL/SC锁 215
8.1.6　Ticket锁 218
8.1.7　ABQL 219
8.1.8　各种锁实现的量化比较 221
8.2　栅障的实现 222
8.2.1　翻转感应集中式栅障 223
8.2.2　组合树栅障 225
8.2.3　硬件栅障实现 225
8.3　事务内存 227
8.4　练习 232
课堂习题 232
课后习题 236
第9章　存储一致性模型 238
9.1　程序员的直觉 238
9.2　保证顺序一致性的体系结构机制 242
9.2.1　在基于总线的多处理器中基本的SC实现 242
9.2.2　改善SC性能的技术 244
9.3　松弛的一致性模型 246
9.3.1　安全网 246
9.3.2　处理器一致性 246
9.3.3　弱序 248
9.3.4　释放一致性 250
9.3.5　惰性释放一致性 253
9.4　不同存储一致性模型中的同步 254
9.5　习题 256
课堂习题 256
课后习题 260
第10章　高级缓存一致性设计 262
10.1　目录式一致性协议 262
10.2　目录式一致性协议概览 262
10.3　目录式缓存一致性协议基础 268
10.4　实现正确性和性能 272
10.4.1　由目录状态不同步引起的竞争处理 272
10.4.2　由对请求非实时处理引起的竞争处理 274
10.4.3　写传播和事务串行化 280
10.4.4　同步支持 281
10.4.5　存储一致性模型 282
10.5　当前设计问题 283
10.5.1　处理不精确的目录信息 283
10.5.2　一致性粒度 286
10.5.3　系统划分 288
10.5.4　加速线程迁移 289
10.6　习题 291
课堂习题 291
课后习题 293
第11章　互连网络体系结构 295
11.1　链路、信道和延迟 296
11.2　网络拓扑 298
11.3　路由策略和算法 302
11.4　路由器体系结构 312
11.5　案例研究：Alpha 21364网络体系结构 315
11.6　多核设计的问题 317
11.7　习题 319
课堂习题 319
课后习题 321
第12章　SIMT体系结构 323
12.1　SIMT编程模型 323
12.2　将SIMT工作负载映射到SIMT核上 325
12.3　SIMT核体系结构 326
12.3.1　标量ISA 326
12.3.2　SIMD化/向量化：Warp构造 326
12.3.3　细粒度多线程（Warp级并行） 328
12.3.4　微体系结构 328
12.3.5　流水线执行 329
12.3.6　控制流处理 330
12.3.7　内存系统 331
12.4　习题 334
课堂习题 334
课后习题 335
第13章　专家访谈 337
参考文献 356
索引 361