描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787111610410
内容简介
虽然多核现在是主流架构,但很少有教科书涵盖并行多核体系结构。本书填补了这一空白,为研究生或高级本科体系结构课程提供了所有材料,重点是多核处理器的体系结构。这本书也适合作为从事多核编程或多核芯片设计的专业人员的参考书。
目 录
译者序
前言
缩写词表
第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 由对请求非实时处理引起的竞争处
前言
缩写词表
第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 由对请求非实时处理引起的竞争处
前 言
从大概10年前开始,处理器的设计方式发生了巨大的变化。从表面上看,似乎没有什么明显的变化:晶体管密度依然按照摩尔定律每18~24个月翻一番。但如果仔细分析,会发现很多地方都发生了显著的变化。曾经按照摩尔定律增长的处理器时钟频率开始变得停滞不前。处理器生产商开始从在管芯上设计单核处理器转向设计多核处理器,通常也被简称为多核(multicore)。这些多核芯片的发展标志了处理器行业的一个重要转变。从物理的角度来看,转向多核设计的原因在于设计更高性能(更深或更宽的流水线)的单核处理器所带来的功耗密度增长无法接受。这也是处理器设计第二次遭遇功耗的物理限制,次遭遇导致处理器设计由双极型晶体管全面转向采用更高功效的互补金属氧化物半导体(CMOS)晶体管。而这次没有可以替代CMOS晶体管的功效更高的技术,因此功耗限制需要通过体系结构的改变来解决,即从单核处理器转变为多核处理器。虽然并行体系结构已经出现了很长一段时间,但随着向多核处理器的转变,并行体系结构将会成为当代处理器的主流设计。
从处理器设计者的角度来看,理论上性能可以通过首先转向多核,之后增加管芯上的核心数来保持很长一段时间的增长。然而从编程人员的角度来看,转向多核会导致一个很重要的结果:性能的增长依赖于程序员编写并行代码的能力,以及如何调优并行代码使其具有较好的可扩展性。在多核处理器之前,程序员只需要关注增加可编程性或者编程抽象的层次,即便这样做会导致代码复杂度的增加以及执行效率的降低,因为他们知道处理器核会变得越来越快从而抵消这些不利影响。然而,现在程序员如果希望克服可编程性和抽象层次增加对性能的不利影响,需要考虑如何利用多核处理器所提供的并行优势来编写程序。换句话说,并行编程和性能调优对许多程序员而言已经成为不可或缺的能力。
尽管多核已经成为主流体系结构,但在写作本书时,市场上几乎没有任何教科书涵盖了并行多核体系结构。虽然有很多关于并行编程以及传统并行体系结构的教科书,也有一些与多核体系结构相关的特定主题的短篇讲义,但是笔者未找到完整的讲解多核体系结构的教科书。这方面的缺失促成了笔者完成本书。笔者希望本书关于多核体系结构的内容有助于当前教授计算机体系结构的教师讲授相关内容。笔者同时也希望本书能够帮助还没有教授多核体系结构的教师开设该课程。后,笔者希望本书能够成为多核编程或者设计多核芯片的专家的工具书。
笔者在写作本书时面临一些重大的挑战。首先,微处理器技术的变化节奏非常快。本书涵盖的一些主题仍然处于不断变化中,导致笔者对相关内容进行了多次迭代。例如,在写作之初,一个典型的多核处理器包含两个处理器核并共享L2高速缓存,然而在完成本书写作时,管芯上的处理器核数量增加到了16个,并且具有更深、更复杂的存储层次。撰写变化如此之快的相关技术非常具有挑战性。此外,另一个重大的挑战是关于多核体系结构有太多的主题,单就一本教科书的厚度无法全部涵盖。因此,笔者在写作本书时需要做出决定:包含哪些主题和不包含哪些主题。因此非常遗憾,本书无法满足所有读者的需求,一些读者可能会发现他们感兴趣的主题并没有包含在内或者不够深入。然而,笔者尝试着涵盖多核体系结构中基础的内容,并希望以此为跳板供读者继续阅读其他资料。笔者相信本书可以为读者提供预备知识,进而继续阅读多核体系结构领域的研究论文。
本书基于笔者在2009年写作并出版的《并行计算机体系结构基础:多芯片和多核系统》(Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems)。与该书相比,本书不仅扩展了所涵盖的有关多核体系结构的内容,而且将多核体系结构作为讨论的中心。
本书在写作过程中始终遵循以下理念。,本书的内容适用于研究生、高年级本科生,以及受过计算机科学或工程训练的专业人士。一些涉及操作系统(进程、线程、虚拟内存)和计算机组成(指令集、寄存器)的基本概念在书中只是简单提及,笔者假设读者已经了解相关基本概念。
第二,当介绍一个概念时,笔者首先构建一个场景并引导读者理解该问题,之后再引入相关概念。因此,对于有些读者来说本书的叙述可能有些烦琐,但对另一些读者来说这将有助于他们更清晰地理解相关问题和概念。
第三,除了一些特例之外,本书各章都设计得相对较短,因此读者利用一个周末完成一章的阅读并没有太大难度。笔者希望学生可以完整阅读本书,即使需要跳过本书的一些内容,也希望是跳过整章而不是一章的部分内容。为了缩短各章的长度,笔者将本书的内容分解为更多的章节(相对于本领域的典型教科书而言)。例如,关于高速缓存一致性(后文简称缓存一致性)的内容被划分为3章:第6章引出问题,第7章介绍了广播缓存一致性协议,第10章介绍了目录式缓存一致性协议和更多高级主题。
第四,笔者致力于让本书更具吸引力。一个独特的地方就是分散在本书不同地方的“你知道吗?”文本框,用于展示小的案例分析、不同的观点、例子,或者有趣的事实和讨论内容。另一个独特的地方就是在本书的后包含了对并行多核体
从处理器设计者的角度来看,理论上性能可以通过首先转向多核,之后增加管芯上的核心数来保持很长一段时间的增长。然而从编程人员的角度来看,转向多核会导致一个很重要的结果:性能的增长依赖于程序员编写并行代码的能力,以及如何调优并行代码使其具有较好的可扩展性。在多核处理器之前,程序员只需要关注增加可编程性或者编程抽象的层次,即便这样做会导致代码复杂度的增加以及执行效率的降低,因为他们知道处理器核会变得越来越快从而抵消这些不利影响。然而,现在程序员如果希望克服可编程性和抽象层次增加对性能的不利影响,需要考虑如何利用多核处理器所提供的并行优势来编写程序。换句话说,并行编程和性能调优对许多程序员而言已经成为不可或缺的能力。
尽管多核已经成为主流体系结构,但在写作本书时,市场上几乎没有任何教科书涵盖了并行多核体系结构。虽然有很多关于并行编程以及传统并行体系结构的教科书,也有一些与多核体系结构相关的特定主题的短篇讲义,但是笔者未找到完整的讲解多核体系结构的教科书。这方面的缺失促成了笔者完成本书。笔者希望本书关于多核体系结构的内容有助于当前教授计算机体系结构的教师讲授相关内容。笔者同时也希望本书能够帮助还没有教授多核体系结构的教师开设该课程。后,笔者希望本书能够成为多核编程或者设计多核芯片的专家的工具书。
笔者在写作本书时面临一些重大的挑战。首先,微处理器技术的变化节奏非常快。本书涵盖的一些主题仍然处于不断变化中,导致笔者对相关内容进行了多次迭代。例如,在写作之初,一个典型的多核处理器包含两个处理器核并共享L2高速缓存,然而在完成本书写作时,管芯上的处理器核数量增加到了16个,并且具有更深、更复杂的存储层次。撰写变化如此之快的相关技术非常具有挑战性。此外,另一个重大的挑战是关于多核体系结构有太多的主题,单就一本教科书的厚度无法全部涵盖。因此,笔者在写作本书时需要做出决定:包含哪些主题和不包含哪些主题。因此非常遗憾,本书无法满足所有读者的需求,一些读者可能会发现他们感兴趣的主题并没有包含在内或者不够深入。然而,笔者尝试着涵盖多核体系结构中基础的内容,并希望以此为跳板供读者继续阅读其他资料。笔者相信本书可以为读者提供预备知识,进而继续阅读多核体系结构领域的研究论文。
本书基于笔者在2009年写作并出版的《并行计算机体系结构基础:多芯片和多核系统》(Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems)。与该书相比,本书不仅扩展了所涵盖的有关多核体系结构的内容,而且将多核体系结构作为讨论的中心。
本书在写作过程中始终遵循以下理念。,本书的内容适用于研究生、高年级本科生,以及受过计算机科学或工程训练的专业人士。一些涉及操作系统(进程、线程、虚拟内存)和计算机组成(指令集、寄存器)的基本概念在书中只是简单提及,笔者假设读者已经了解相关基本概念。
第二,当介绍一个概念时,笔者首先构建一个场景并引导读者理解该问题,之后再引入相关概念。因此,对于有些读者来说本书的叙述可能有些烦琐,但对另一些读者来说这将有助于他们更清晰地理解相关问题和概念。
第三,除了一些特例之外,本书各章都设计得相对较短,因此读者利用一个周末完成一章的阅读并没有太大难度。笔者希望学生可以完整阅读本书,即使需要跳过本书的一些内容,也希望是跳过整章而不是一章的部分内容。为了缩短各章的长度,笔者将本书的内容分解为更多的章节(相对于本领域的典型教科书而言)。例如,关于高速缓存一致性(后文简称缓存一致性)的内容被划分为3章:第6章引出问题,第7章介绍了广播缓存一致性协议,第10章介绍了目录式缓存一致性协议和更多高级主题。
第四,笔者致力于让本书更具吸引力。一个独特的地方就是分散在本书不同地方的“你知道吗?”文本框,用于展示小的案例分析、不同的观点、例子,或者有趣的事实和讨论内容。另一个独特的地方就是在本书的后包含了对并行多核体
评论
还没有评论。