【分析解答】
第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
图8.13 字符型设备中断方式下的I/O过程
(7) 根据对各种数据的分析, 可以得到以下 4 个结论: ① 对于查询方式, 定时查询比独占查询的 CPU 利用率高, 但是定时查询的时间间隔必须和外设的数据传输率和接口缓存情况相匹配。② 对于快速设备, 因为查询方式和中断方式的 CPU 开销大, 使得 CPU 来不及处理外设传输的数据而导致数据丢失, 因而快速设备不能采用这两种方式。③ 对于块传送设备, 因为不需要每个字节都启动一次外设, 所以传送相同字节个数所用的时间比字符型设备的时间短。例如, 对于 1000 字节的传送, 独占查询方式下, 块传送设备的时间是 $20.00104\mathrm{ms}$ , 而字符型设备是 $20.02102\mathrm{ms}$ ; 中断方式下, 块传送设备的时间是 $20\mathrm{ms}$ , 而字符型涉设备是 $20.102\mathrm{ms}$ 。④ 外设速度越快, CPU 用于外设 I/O 操作的时间所占比例越大, 因此, 对于快速设备应尽量减少 CPU 介入 I/O 的程度, 即采用 DMA 方式更合适。
补充说明：在计算CPU占用时间百分比时也可用另一种方法计算得到。例如，对于(3)中断方式的计算，可以先求出一秒内该外设请求的中断次数为 $1 / (1\mathrm{B} / 50\mathrm{kB}) = 50\mathrm{k}$ ，然后得到一秒内CPU用于数据I/O的时钟周期数为 $50\times 1000\times (2 + 1200) = 6.01\times 10^{7}$ ，因此，在该设备传输过程中，CPU用于该设备I/O操作的时间占整个CPU时间的百分比为 $6.01\times 10^{7} / 10^{9} = 6.01\%$ 。
<!-- page: 281 -->
## 9.1 教学目标和内容安排
主要教学目标：使学生初步了解并行处理计算系统所涉及的主要技术问题，以及各种并行处理系统的基本结构和基本原理，为后续的计算机体系结构和并行程序设计等课程的学习打下基础。本章主要内容包括 UMA 多处理器和 NUMA 多处理器系统的基本结构及其互连、多核处理器和硬件多线程技术、共享存储器的同步控制、集群多计算机系统的互连和交换机制、向量处理机和 SIMD 技术、GPU 基本结构和基本的并行处理编程模式等。
### 基本学习要求：
1. 了解并行处理系统的基本分类方案。
2. 了解按指令和数据处理方式划分的 Flynn 分类方式。
3. 了解按主存地址空间访问方式划分的并行处理系统分类方式。
4. 了解按处理单元的位置及其互连方式划分的并行处理系统分类方式。
5. 了解 UMA 多处理器中处理器与共享存储器之间的几种连接方式。
6. 理解在 UMA 多处理器系统中为何存在 cache 一致性问题。
7. 理解 UMA 多处理器系统和 NUMA 多处理器系统的异同点。
8. 理解 CC-NUMA 多处理器系统中基于目录的 cache 一致性机制。
9. 了解多核处理器的基本结构。
10. 了解硬件多线程技术的基本实现原理。
11. 理解什么是存储器一致性模型，并能区分顺序一致性模型、宽松一致性模型和释放一致性模型三者的差别。
12. 了解 ISA 架构如何提供支持存储器一致性模型的底层机制。
13. 了解如何通过共享区域加锁机制实现事务处理和操作原子性需求。
14. 了解集群多计算机系统的互连和节点之间的信息交换方式。
15. 了解向量计算机中向量处理指令和普通标量处理指令之间的区别。
16. 了解 SIMD 指令的基本概念。
17. 了解 GPU 和 CPU 在功能上和结构上的基本区别。
18. 了解基于共享存储变量的多线程并行程序设计模式，如 Pthread、OpenMP 等并行编程接口。
<!-- page: 282 -->
(19) 了解用于集群的基于消息传递并行程序设计方式，如 MPI 并行编程接口。
(20) 了解用于集群的 MapReduce 并行计算编程框架。
(21) 了解用于 GPU+CPU 并构系统的 C/C++ 语言可扩展并行编程模型 CUDA。
并行处理系统相关内容涉及面非常广，而且相关概念和知识体系比较复杂深入，主教材只是对并行处理系统最基础的内容进行了简要介绍，在计算机组成课程中讲解这部分内容，仅是作为后续的计算机体系结构和并行程序设计等课程的导引，为后续相关课程的教学做一些铺垫。
本章涉及内容涵盖多处理器系统、多计算机系统、多核处理器和硬件多线程技术，以及向量处理和 SIMD 等数据级并行处理技术、GPU 基本架构和并行编程模式等方面的基本概念。
因为这部分内容仅仅是为后续课程做铺垫，而对学生理解和掌握本课程前面的内容没有影响，因此，在课时有限的情况下，这部分内容可让学生自学。如果作为课堂教学内容进行介绍，则可以根据学时的多少，选择仅对主要的概念进行解释说明，还是针对每个概念和知识点通过举例和讨论等形式展开来进行详细介绍。显然，不管这部分内容在本课程中如何实施教学，这里都不是其终点，一定要有后续的相关课程在深度和广度上细化相关知识点，并最终形成针对并行处理系统的设计实现能力以及并行编程能力。
## 9.2 主要内容提要
### 1. Flynn 分类
根据 Flynn 分类法，并行处理计算系统有 SIMD 和 MIMD 两种并行计算模式，其中，SIMD 是一种数据级并行计算模式，而 MIMD 是一种并行程度更高的线程级或以上级的并行计算模式。MIMD 系统可分为多处理器系统和多计算机系统。前者是共享存储多处理器系统的简称，具有共享的单一地址空间，因此，每个处理器都可以通过 LOAD 指令和 STORE 指令访问系统中的存储器，也被称为共享存储系统；后者每个计算节点都具有各自私有的存储器，并且各自具有独立的主存地址空间，通过消息传递方式进行数据传送，因此，也称为消息传递系统。
### 2. 多处理器系统
多处理器系统有 UMA、NUMA 和 CC-NUMA 三类。UMA 多处理器系统中，每个处理器对所有存储单元的访问时间是均匀的，因此，UMA 多处理机就是对称多处理机 SMP。NUMA 多处理器系统中共享的存储空间分布在不同的处理器节点上，因而不同的处理器对同一个存储单元的访问时间可能不同。处理器中带有一致性高速缓存时的 NUMA 称为 CC-NUMA，采用基于目录的 cache 一致性机制的 CC-NUMA 多处理器系统中，每个处理器节点都用一个目录来记录本地存储器中每个主存块与高速缓存中 cache 行的对应关系，主存地址中带有一个节点号字段，CPU 执行指令时根据节点号了解所访问的是哪个节点中的存储单元。
与多处理器系统一样，在多核处理器系统中，多个处理器核也都要访问共享存储器，由于处理器核在执行程序中存在各种随机情况，从而导致多个核的程序之间的访存顺序存在不确定性，因此，在多处理器系统或多核处理器系统中必须确定存储器一致性模型。三种代
<!-- page: 283 -->
表性存储器模型是顺序一致性模型、宽松一致性模型和释放一致性模型。
## 3. 多计算机系统
多计算机系统的典型代表是集群和网格。集群是采用局域网络连接的通过消息传递进行通信的紧耦合多计算机系统。数据库系统、文件服务器、Web服务器等大型系统都适合采用集群系统。网格多计算机系统是利用互联网把分散在不同地理位置的多个异构的计算机组成一台逻辑上的“虚拟超级计算机”。
## 4. 数据级并行技术
向量计算机面向向量型数据进行并行计算，在向量各分量上执行彼此无关、各自独立的数据运算。有些处理器架构采用SIMD指令进行数据级并行处理，通过SIMD指令可处理向量数据，也可处理标量数据。图形处理器GPU采用了类似SIMD的指令执行模式SIMT，即单指令多线程模式。
## 5. 并行处理编程模式
针对不同特点的应用问题和不同的并行处理硬件架构，可以有不同的并行编程模型，主要分为共享存储变量、消息传递、MapReduce，以及适合于CPU+GPU的CUDA编程模型等几种并行编程模式。
## 9.3 基本术语解释
### 单指令流单数据流(Single Instruction stream and Single Data stream, SISD)
单指令流单数据流是传统的串行计算机处理方式，通常仅包含一个处理器和一个存储器，处理器在一段时间内仅执行一条指令流，按指令流规定的顺序串行完成指令流中若干条指令的执行，并且每条指令最多仅对两个数据(双目运算)或一个数据(单目运算)进行处理。
### 单指令流多数据流(Single Instruction stream and Multiple Data stream, SIMD)
单指令流多数据流指一个指令流同时对多个数据流进行处理，对应的机器结构由一个指令控制部件、多个处理单元和多个存储器组成，各处理单元和各存储器之间通过系统内部的互连网络进行通信，指令控制部件执行的是一个串行的指令流，所有处于执行状态的处理单元同时执行相同的指令，所需的数据从连接在各个处理单元上专用的局部存储器中取得，因此，不同处理单元执行的同一条指令所处理的数据是不同的。
### 多指令流多数据流(Multiple Instruction stream and Multiple Data stream, MIMD)
多指令流多数据流指同时有多个指令分别处理多个不同的数据，这种系统中一定包含多个计算机或多个处理器。MIMD方式是目前大多数并行处理计算系统的处理方式。
### 均匀存储器访问(Uniform Memory Access, UMA)
均匀存储器访问指每个处理器对所有存储单元的访问时间是一致的。如果所有处理器都共享一个存储器，那么每个处理器通过LOAD指令和STORE指令访问任何一个存储单元时，访问时间都相同，与处理器和存储器的相对位置没有关系。因此，UMA多处理机就是对称多处理机(SMP)。根据处理器与共享存储器之间的连接方式，分为基于总线、基于交叉开关网络和基于多级交换网络连接等几种UMA多处理器系统。
### 非均匀存储器访问(Non-Uniform Memory Access, NUMA)
非均匀存储器访问指处理器对不同的存储单元的访问时间可能不一致，访问时间与存
<!-- page: 284 -->
储单元的位置有关，若是本地存储器访问时间就短，若是其他处理器所连接的存储器则访问时间就长。如果在NUMA结构中引入高速缓存一致性确认机制，则称为高速缓存一致的非一致性内存访问(Cache-Coherent NUMA,CC-NUMA)。
## 对称多处理器(Symmetric MultiProcessor,SMP)
对称多处理器指将多个相同类型的CPU通过总线互连，并等同地位地共享系统所有资源，即多个CPU对称工作，无主次或从属关系。因为各CPU共享相同的物理内存，每个CPU访问内存中的任何地址所需时间是相同的，因此，对称多处理器就是一种UMA结构多处理器。多核处理器系统、高档微机、工作站或服务器多用SMP结构。
## 片级多核处理器(Chip-level MultiProcessing,CMP)
在一个CPU芯片中包含多个处理单元，每个处理单元称为一个核(Core)，所有核可能共享一个末级高速缓存(Last-Level Cache,LLC)，并共享主存储器。通常将多核芯片称为片级多处理器。
## 大规模并行处理 (Massive Parallel Processing, MPP)
大规模并行处理指以专用内联网络连接数量众多处理单元而构成的一种并行计算系统。例如，可以通过专用互连网络(如Mesh、交叉开关)将数量达几百个甚至几千个对称多处理器(SMP)连接成大规模并行处理机，众多SMP服务器协同工作，完成相同的任务，从用户角度来看MPP是一个服务器系统，每个SMP服务器称为一个节点，每个节点只能直接访问自己的本地资源(内存、磁盘等)，因而大多数MPP是消息传递系统。
## 硬件多线程(hardware multi-threading)
硬件多线程是一种共享单个处理器核内功能部件的技术。每个硬件线程相当于一个指令序列，用于指令执行的功能部件和高速缓存在每个核内仅有一套。为了支持多线程并发执行，必须为每个线程提供单独的通用寄存器组和程序计数器等用于存放现场信息的硬件资源，并提供快速的线程切换机制。
## 细粒度多线程(fine-grained multi-threading)
细粒度多线程通过在多个线程之间轮流交叉执行指令来实现多线程，处理器核可在每个时钟周期切换线程。例如，在第 $i$ 时钟周期，将线程1中的多条指令发射到多个发射槽中执行，在第 $i + 1$ 时钟周期，将线程2中的多条指令发射到多个发射槽中执行。
## 粗粒度多线程(coarse-grained multi-threading)
粗粒度多线程仅在某个线程出现了较大开销的阻塞时才切换线程。例如，发生L2cache缺失时才切换线程。这种方式下，当发生流水线阻塞时必须将被阻塞的流水线冻结或清空，新线程的指令开始执行前需要重填流水线，因此，与细粒度多线程相比，其线程切换开销更大。
## 同时多线程(Simultaneous MultiThreading,SMT)
同时多线程是细粒度多线程和粗粒度多线程两种技术的变种，它利用多发射动态调度处理器核中更多的功能部件，在实现指令级并行的同时，实现线程级并行。SMT能在同一个时钟周期内，在不同的发射槽中发射不同线程中的指令。例如，Intel处理器中的超线程(Hyper-threading)即为同时多线程。
## 存储器一致性模型(memory consistency model)
在多处理器系统和多核处理器系统中，每个处理器核有一个或多个指令流（硬件多线程
<!-- page: 285 -->
情况下)在执行，不同处理器核共享同一个主存储器，如果同一段时间内多个核都要访问共享存储器，那么，由于处理器核在执行程序时存在流水线阻塞、功能部件冲突、指令顺序调度等各种随机情况，因而多个核的程序之间的访存顺序就存在不确定性，从而造成执行结果的不确定，必须有相应的同步控制机制保证正确的存储访问，以使同一个程序在任何时刻执行都得到确定一致的结果。这种保证正确的存储访问的同步控制机制称为存储器一致性模型。指令集体系结构(ISA)必须规定所用的存储器一致性模型，并提供与所规定模型相匹配的一套同步指令。
## 顺序一致性模型(sequential consistency model)
顺序一致性模型要求每个处理器核完全按照程序指定的顺序执行，即使多条访存指令访问的地址不同，也不可以改变访存指令的执行顺序。
## 宽松一致性模型(relaxed consistency model)
宽松一致性模型比顺序一致性要求更宽松，允许改变程序中对于不同存储器地址的访存指令的执行顺序，因而程序运行性能更高。为了在某些必要情况下保证访存指令的执行顺序，采用宽松一致性模型的ISA需要提供特殊的存储器屏障(memory FENCE)指令，相当于设置一个同步点，以保证在FENCE指令之前的访存指令执行的结果，一定比FENCE之后的访存指令执行的结果先被观测到。即在FENCE之前的访存指令一定先执行完，才能执行FENCE之后的访存指令。
## 释放一致性模型(release consistency model)
宽松一致性模型系统中存储器屏障指令在两个方向上都有限制，即要求FENCE之前的访存指令不能推迟到FENCE之后，而FENCE之后的访存指令不能提前到FENCE之前。如果再放松要求，只限定一个方向的访存指令执行顺序，就是更加宽松的释放一致性模型。释放一致性模型采用以下获取-释放(acquire-release)机制实现：提供一种获取指令，用于拦截它之后的所有访存指令，保证不能提前执行；同时，还提供一种释放指令，用于拦截它之前的所有访存指令，保证必须在它之前执行完。
## 集群(cluster)
集群是通过高性能网卡将若干普通PC或SMP服务器或工作站连接而成的并行处理系统。集群中的每个计算节点(PC、SMP或工作站)都有各自的主存储器和磁盘，主存地址空间都是计算节点各自私有的，因此，集群是一种典型的紧密耦合的同构多计算机系统。显然，集群属于消息传递系统。
## 网格(grid)
网格指用因特网等广域网络连接起来的、远距离分布的、一组异构计算机系统构成的分布式并行处理系统，是一种松散耦合的异构多计算机系统。云计算(cloud computing)服务器就是由网格发展而来的。
## 向量计算机(vector computer)
向量计算机是面向向量型数据的并行计算机，在向量各分量上执行的运算操作一般都彼此无关、各自独立，因而可按多种方式并行执行，有流水线方式和阵列方式两种，大多以流水线结构为主。主存容量的大小限定了机器的解题规模，而向量计算机主要用于求解大型问题，必须具有大容量的主存，而且应该是集中式的公共存储器。当高速运算流水线运行时，需源源不断地供给操作数并源源不断地取走运算结果，因此，还要求主存具有很高的数
<!-- page: 286 -->
据传输率，否则便不能维持高速运算。
## 图形处理器(Graphics Processing Unit, GPU)
早期图形处理器主要用于3D图形的绘制、着色和渲染等图形处理，随着以CUDA为代表的GPU通用计算框架的普及，GPU的应用领域得到了极大的拓展，被广泛应用于石油勘探、天文计算、流体力学模拟、分子动力学仿真、生物计算等科学计算领域，并在很多应用中获得了几十倍乃至上百倍的加速比。因此，GPU的含义也从原来专门的图形处理器转变为GPGPU(General-Purpose computing on GPU)。GPGPU计算通常采用CPU+GPU的异构模式，由CPU负责执行复杂逻辑处理和事务管理等不适合数据并行的计算，而GPU负责计算密集型的大规模数据并行计算。一个GPU芯片中通常包含成千上百个流处理器，因此，GPU也被称为众核(many core)处理器。
## 9.4 常见问题解答
1. 并行处理计算系统中主要涉及哪些技术问题？
答：根据所采用的硬件体系结构的不同，每种并行处理计算系统所涉及的主要技术问题有所不同，概括起来主要包括系统互连、数据一致性、存储器同步控制、任务的分解和数据划分、并行程序设计、资源调度和管理、容错性和系统安全性等。
2. 并行处理计算系统有哪几种分类方式？
答：并行处理计算系统按Flynn分类法，有SIMD和MIMD两种并行计算模式：按主存地址空间访问方式区分，有采用统一主存地址空间的多处理器系统和采用各自独立主存地址空间的多计算机系统；对于多处理器系统，按照存储访问时间是否一致来区分，分为一致性内存访问(UMA)和非一致性内存访问(NUMA)两类；按处理单元的位置及其互连方式来分，可以分为多核(multi-core)、众核(many core)、对称多处理器(SMP)、大规模并行处理机(MMP)、集群和网格等。
3. UMA、NUMA 和 CC-NUMA 三者之间的区别是什么？
答：这三种多处理器系统都具有统一的主存地址空间，只是在UMA多处理器系统中，所有处理器节点的存储访问时间一致，而在NUMA多处理器系统中，各处理器访问本地主存储器的时间快于访问其他节点的主存储器。
4. 基于目录协议的 cache 一致性方式的主要思想是什么？
答：基于目录协议的 cache 一致性方式主要用在基于目录的 CC-NUMA 多处理器结构中。其基本思想是，每个处理器采用一个目录记录本地存储器中每个主存块与高速缓存中 cache 行的对应情况。每个主存块对应一个目录项，目录项中有专门的一位有效位，表示对应的主存块是否在某 cache 行中，若为 1，则表示在 cache 中，目录项中记录对应的 cache 行所在的节点号；该位为 0，则说明不在 cache 中。CC-NUMA 多处理器中，每个处理器节点带有各自独立的主存储器，且所有节点的主存储器采用统一的地址空间，因此主存地址被划分为节点号 $x$、主存块号 $y$ 和块内偏移 $\pmb{z}$ 三个字段，表示访问节点 $x$ 对应存储器中主存块 $y$ 内第 $\pmb{z}$ 单元。某处理器节点 $i$ 执行指令进行访存时，首先根据主存块号 $y$ 访问对应的目录项，若其有效位为 0，则说明访问的主存块不在 cache 中，因此向节点 $x$ 发送一个消息，指示节点 $x$ 将其中的主存块 $y$ 取出送到节点 $i$；若其有效位为 1，则将目录项中的节点号 $j$ 改为
<!-- page: 287 -->
$i$，并向节点 $j$ 发送一个消息，指示节点 $j$ 将高速缓存中的主存块 $y$ 取出送到节点 $i$，并使其自身高速缓存中对应的 cache 行无效。基于目录协议的 cache 一致性机制是一种简单处理方式，每个主存块只能被高速缓存在一个节点中，显然这种方式会带来更多的网络通信开销。
5. 为什么在对性能稳定性要求较高的场合要关闭多核和硬件多线程功能？
使用多核处理器或硬件多线程有可能会带来性能干扰问题。对多核处理器来说，不同的处理器核之间会共享 LLC、内存带宽、I/O 带宽等资源，而对于硬件多线程，则同一个核心上的多个硬件线程之间还会共享超标量处理器中包括发射队列、ROB、访存队列、分支预测器和 L1 cache 等资源。当处理器核或线程的负载较高时，就会在这些资源上产生竞争现象，竞争不到资源的处理器核或线程将会被阻塞而受到干扰，从而造成性能下降。因此，在一些对性能稳定性要求较高的场合会限制使用甚至关闭多核和硬件多线程功能。
6. 在多核处理器系统的程序中，可以采用哪些方式来对共享存储区“上锁”，以支持事务处理的原子性需求？
可以用两种方式解决“上锁”问题：一种是通过原子操作方式，另一种是通过互斥操作方式。原子操作方式下，针对用普通的 Load/Store 指令会引起一个完整的“读锁-写锁”过程被打断的问题，可在指令集中引入原子操作指令，以保证“读锁-写锁”过程不被打断。互斥操作方式下，指令集中可以提供一对互斥操作指令：互斥读(Load-Exclusive)指令和互斥写(Store-Exclusive)指令。互斥读指令的功能与普通的主存读(Load)指令类似，都是从主存单元中取出数据送寄存器；而互斥写指令的功能与普通的主存写(Store)指令不同，它的写操作不一定能成功执行，结果寄存器中会存放是否成功的标志信息。
7. 集群中的节点之间是如何交换信息的？
集群中每个节点内都有一块网卡，通过网卡将节点和交换机相连。在每个网卡中都设有一个缓冲区，网卡中通常包含多个 DMA 通道或专门的 I/O 处理器，主要用于提供可靠的比特流传送、将信息块发送到多个目的地、压缩和解压缩、加密和解密等功能。每个 DMA 通道相当于一个 DMA 控制器，能够控制完成在网卡缓冲区与主存之间的 DMA 传送。在节点之间传输的消息从一个节点内的用户空间，通过内核中的缓存，然后送到网卡缓冲区，再经过网络连线和交换机被传送到另一个节点的网卡缓冲区，最后再通过目的节点的内核缓存被送到用户空间中，从而完成两个节点的用户程序之间的通信。
8. 向量处理指令和标量处理指令之间的主要差别是什么？
向量处理指令中指定的操作数寄存器为向量寄存器，其中存放的是由若干相同类型数据组成的一个向量，一条指令可以并行地对向量寄存器中的若干数据执行同一种操作，而标量处理指令中指定的操作数寄存器为标量寄存器，其中只有一个操作数，每条标量指令只能对一个或一对操作数进行某种操作。
9. CPU 和 GPU 之间的主要差别是什么？
CPU 是一种通用处理器，实现某种指令集体系结构(ISA)规定的功能，所有功能都通过执行特定 ISA 规定的指令来实现，通过增加特定的图形处理指令集（如 Intel 80x86 架构中的 MMX、SSE 和 AVX 指令集）也能实现图形处理，但 CPU 本身主要是用于通用处理而不是专用于图形处理的，其图形处理速度和效果都很难满足要求，因此，就出现了专门进行图形处理的 GPU 芯片。早期 GPU 主要用于 3D 图形绘制、着色和渲染等图形处理，但随着以
<!-- page: 288 -->
CUDA 为代表的 GPU 通用计算框架的普及，GPU 的应用领域得到了极大的拓展，出现了通用 GPU(GPGPU)计算模型。GPGPU 计算采用 CPU+GPU 的异构模式，由 CPU 负责执行复杂逻辑处理和事务管理等不适合数据并行的计算，而 GPU 负责计算密集型的大规模数据并行计算。