并行计算机组成与设计

本书以简单易懂的方式讲解错综复杂的并行体系结构，引导读者了解并行计算机的工作原理，同时鼓励读者创新并实现自己的设计。全书共9章，内容涵盖底层电子工艺、微体系结构、存储结构、互连网络、多处理器、片上多处理器以及量化评估模型等。每一章都独立且完备，既包含全面的基本概念，也涵盖一些前沿研究点。本书适合作为高等院校计算机相关专业的教材，教师可根据课程及学生的层次选取不同的主题。同时，对于工程师和研究者，本书也是不可多得的有益参考。

Michel Dubois: 南加州大学谢明（Ming Hsieh）电子工程系教授。
Murali Annavaram：南加州大学谢明（Ming Hsieh）电子工程系副教授。
Per Stenstr?m,瑞典哥德堡查尔姆斯理工大学计算机工程教授

目　录
Parallel Computer Organization and Design

出版者的话
赞誉
译者序
前言
第1章　总述1
　1.1　什么是计算机体系结构2
　1.2　并行体系结构的基本组成3
　　1.2.1　处理器4
　　1.2.2　存储6
　　1.2.3　互连9
　1.3　并行体系结构10
　　1.3.1　指令级并行10
　　1.3.2　线程级并行10
　　1.3.3　向量和阵列处理器11
　1.4　性能12
　　1.4.1　基准测试集13
　　1.4.2　Amdahl定律15
　1.5　技术挑战19
　　1.5.1　功耗和能量19
　　1.5.2　可靠性19
　　1.5.3　连线延迟20
　　1.5.4　设计复杂度20
　　1.5.5　尺寸缩小极限和CMOS终点21
　习题22
第2章　工艺及其影响25
　2.1　概述25
　2.2　电学基本定律26
　　2.2.1　欧姆定律26
　　2.2.2　电阻26
　　2.2.3　电容27
　2.3　MOSFET晶体管和CMOS反相器27
　2.4　工艺变更30
　2.5　功耗和能耗31
　　2.5.1　动态功耗31
　　2.5.2　静态功耗35
　　2.5.3　功耗和能量指标37
　2.6　可靠性38
　　2.6.1　故障和错误38
　　2.6.2　可靠性指标39
　　2.6.3　故障率和老化40
　　2.6.4　瞬时故障42
　　2.6.5　间歇性故障44
　　2.6.6　永久性故障48
　　2.6.7　工艺偏差及其对故障的影响48
　习题49
第3章　处理器微结构51
　3.1　概述51
　3.2　指令集架构52
　　3.2.1　指令类型和操作码53
　　3.2.2　指令混合55
　　3.2.3　指令操作数55
　　3.2.4　异常、陷阱和中断58
　　3.2.5　存储一致性模型60
　　3.2.6　本书的核心ISA60
　　3.2.7　CISC和RISC61
　3.3　静态调度流水线63
　　3.3.1　经典五级流水线64
　　3.3.2　指令乱序完成69
　　3.3.3　超流水和超标量CPU72
　　3.3.4　分支预测73
　　3.3.5　静态指令调度73
　　3.3.6　静态流水线的优缺点77
　3.4　动态调度流水线78
　　3.4.1　解决数据相关：Tomasulo算法79
　　3.4.2　推测执行82
　　3.4.3　动态分支预测83
　　3.4.4　支持推测的Tomasulo算法87
　　3.4.5　动态内存歧义消除89
　　3.4.6　显式寄存器重命名91
　　3.4.7　指令发射后的寄存器读取93
　　3.4.8　推测指令调度94
　　3.4.9　打破数据流限制：值预测97
　　3.4.10　单周期多指令98
　　3.4.11　处理复杂ISA98
　3.5　超长指令字微结构99
　　3.5.1　动态和静态技术100
　　3.5.2　VLIW体系结构100
　　3.5.3　循环展开102
　　3.5.4　软件流水103
　　3.5.5　非循环VLIW调度108
　　3.5.6　谓词指令109
　　3.5.7　推测内存歧义消除110
　　3.5.8　异常110
　3.6　EPIC微结构112
　3.7　向量微结构113
　　3.7.1　算术/逻辑向量指令113
　　3.7.2　内存向量指令114
　　3.7.3　向量分段开采和链接115
　　3.7.4　条件语句116
　　3.7.5　scatter和gather操作117
　习题118
第4章　存储层次136
　4.1　概述136
　4.2　金字塔形存储层次137
　　4.2.1　访存局部性138
　　4.2.2　存储层次中的一致性138
　　4.2.3　存储包含139
　4.3　cache层次139
　　4.3.1　cache映射及组织方式139
　　4.3.2　替换策略142
　　4.3.3　写策略143
　　4.3.4　cache层次的性能144
　　4.3.5　cache失效的分类145
　　4.3.6　非阻塞cache145
　　4.3.7　cache预取和预加载147
　4.4　虚拟存储149
　　4.4.1　引入虚存的动机149
　　4.4.2　从操作系统视角看到的虚拟存储149
　　4.4.3　虚地址转换151
　　4.4.4　访存控制151
　　4.4.5　多级页表152
　　4.4.6　反向页表153
　　4.4.7　旁路转换缓冲153
　　4.4.8　带物理标识的虚地址cache154
　　4.4.9　带虚标识的虚地址cache157
　习题157
第5章　多处理器系统162
　5.1　概述162
　5.2　并行编程模型163
　　5.2.1　共享内存系统164
　　5.2.2　消息传递系统166
　5.3　基于消息传递的多处理器系统167
　　5.3.1　消息传递原语167
　　5.3.2　消息传递协议169
　　5.3.3　消息传递协议的硬件支持170
　5.4　基于总线的共享内存系统171
　　5.4.1　多处理器cache组织172
　　5.4.2　一个简单的侦听cache协议173
　　5.4.3　侦听cache协议的设计空间176
　　5.4.4　协议变种181
　　5.4.5　多阶段侦听cache协议的设计问题184
　　5.4.6　通信事件的分类188
　　5.4.7　TLB一致性190
　5.5　可扩展共享内存系统192
　　5.5.1　目录协议的基本概念和术语193
　　5.5.2　目录协议实现方法193
　　5.5.3　目录协议的扩展性197
　　5.5.4　层次化系统200
　　5.5.5　页面迁移和复制201
　5.6　全cache共享内存系统204
　　5.6.1　基本概念、硬件结构和协议204
　　5.6.2　平坦COMA206
　习题207
第6章　互连网络214
　6.1　概述214
　6.2　互连网络的设计空间215
　　6.2.1　设计概念综述215
　　6.2.2　延迟和带宽模型217
　6.3　交换策略221
　6.4　拓扑结构223
　　6.4.1　间接网络223
　　6.4.2　直接网络226
　6.5　路由技术229
　　6.5.1　路由算法229
　　6.5.2　死锁避免和确定性路由231
　　6.5

前　言Parallel Computer Organization and Design在飞速发展的技术驱动下，计算机体系结构成为一个快速发展的领域。自20世纪90年代中期以来，计算系统的速度和可靠性显著增强，这主要得益于技术的发展、更快的主频和更深的流水线。这些改进将高性能计算机带给大众，对社会产生了深远影响，促进了网络创新和人类活动中生产力的大幅提升。我们所处的信息革命如同18世纪的工业革命，没有人会否认这次革命得益于技术的发展和微处理器体系结构的发展。
但是，这样快速的发展在未来可能无法维持下去，流水线深度已经达到可用的极限，由于功耗限制，主频也无法大幅突破。随着技术的发展以及片上资源的变少，可靠性、复杂性和功耗成为计算机设计考虑的首要问题，而不再是传统上考虑的成本、面积和性能。这些趋势促进了并行处理和并行体系结构的发展，因为这是解决当前和未来可能面临的体系结构问题的一条新的甚至可能是唯一的途径。人们普遍认为，我们需要利用并行处理才能使计算机领域呈现一片新的景象，而这个巨大的改变会产生深远的社会影响。因此，无论是工业界还是学术界，对并行体系结构的兴趣都已从工程上的好奇转换为实在的任务。
随着时间的流逝，各层次的并行化已经成为现代计算机系统发展的瓶颈。多处理器结构通过连接多个处理器提供了可扩展的性能表现，并已在高端系统领域称霸数十载。多处理器开发线程级并行（TLP），允许大型应用拥有很多线程，如计算机图形、科学/工程计算、数据库管理以及通信服务。随着体系结构和编译器技术的发展，微体系结构则开发指令级并行（ILP），并且获得了良好的性能表现。内存系统结构为了跟上指令吞吐量的需求，通过允许同时访问大量数据并保证执行的正确性而获得了快速发展。互连和相关的协议也不断改进，可以有效连接成百上千个处理器以及主频为几GHz的芯片。最近，微处理器的体系结构集成了系统级并行结构的范例，如向量处理和多处理器。在片上多处理器时代，每个微处理器都有多个核或CPU，每个核可以并发执行多个线程。
并行体系结构很难设计也很难编程，我们必须理解并行体系结构带来的问题。本书针对最新的指令级并行和线程级并行技术给出了清晰易懂的讲解，此外，还将可靠性和功耗作为设计目标进行讲解。先前计算机体系结构方面的教材主要将性能作为设计考虑的核心问题。然而，现在尽管性能依旧是设计中的一个主要问题，但是复杂性、功耗和可靠性等其他问题也成为很重要的设计因素，这本关于并行计算机体系结构的新书将会讲解这些内容。
本书的基本目的是解释并行体系结构如何工作以及分析当今并行体系结构的正确设计，尤其是在技术受限的情况下。我们一般不会给出性能数据，并且尽力回避系统的具体细节描述。我们鼓励读者阅读发布在相关会议或期刊上的资料，详细的参考书目和历史发展回顾将会发布在网上。这会留下更多空间来讲解设计的基本问题，同时鼓励学生思考、创新、实现自己的设计。为了达到实践和创新的层次，全面了解现存的设计和实际问题以及限制因素是必需的过程。本书利用丰富的例子来解释概念，并且激发读者自己思考。此外，本书还用两章（第8章和第9章）的篇幅描述了一些工业界和学术界使用的系统和工具。
习题是学习的重要部分，每章之后的习题都采用问答题形式，有些很长很难的题目被分成了多个子问题。习题的主要目的是给学生创造机会以对每章的概念有深刻的理解，并且培养学生的抽象思维能力。
本书适合对计算机体系结构感兴趣的计算机、电子工程和计算机科学专业的高年级本科生以及研究生阅读，也适合计算机行业中的工程师参考。由于本书涵盖了从微处理器到多处理器的大量知识，既包括基本内容也包含一些前沿的研究点，因此在教学时，可以通过选择不同的章节来适应不同的难度级别。学生可以学到硬件结构和组成多处理器的各个部分，以及技术发展趋势对于体系结构的影响，还有与性能、功耗、可靠性和功能正确性相关的设计问题等。本书可以用于研究生的基础课程，也可以用于接下来的高阶研究课程。本书的预修课程是计算机体系结构及组成，涵盖指令集和简单流水线处理器体系结构等内容。例如五级流水线及其控制相关的知识，包括前递、停顿和刷新等问题，这些可以帮助学生理解微处理器章节中更复杂的硬件问题。为了体现完整性，本书也包括了基本的指令集、流水线和存储等相关概念。由于现代微体系结构会影响多处理器的特征，因此了解其工作原理是必需的，此外还需要一定的编程知识。
内容纲要本书整体内容完备，同时我们也尽力保证每一章都是独立且完备的，这可能会导致一些重复。本书共9章。第1章给出了计算机体系结构领域的基本观点，概述处理器、内存、互连网络、性能问题（主要是如何评判计算机系统）以及讨论技术发展对未来体系结构的影响。
对工艺实现细节的理解也是非常重要的，因为很多体系结构的设计决策都受底层工艺的影响。因此在第2章中，我们对CMOS进行回顾并探讨相关问题。有VLSI设计背景的学生可以略过某些讲解。这一章主要是针对计算机科学专业的学生，他们可能对电子工程和CMOS技术