cover.png#计组学习笔记7

并行处理系统概述

单个处理器性能提升有极限。

早期提升性能主要依靠：

• 提高主频
• 扩大字长
• 提高集成度
• 加深流水线
• 超标量
• 乱序执行
• 分支预测
• cache 层次优化

但主频提升遇到功耗和散热限制。

指令级并行也受到数据相关、控制相关和硬件复杂度限制。

因此现代计算系统越来越依赖并行处理。

并行处理的基本思想是：

把一个大任务划分成多个子任务，让多个处理单元同时工作，从而提高处理速度或系统吞吐率。

并行可以从很小的粒度开始，例如一条流水线中同时存在多条处在不同阶段的指令。程序表面上仍是一条指令流，但硬件内部已经在重叠执行取指、译码、执行、访存和写回等阶段。多核、多线程和 SIMD 可以看作更高层次的并行扩展。

加深流水线可以提高理想情况下的吞吐率，但并不意味着深度越大越好。阶段拆得越细，同时在流水线中的指令越多，结构冒险、数据冒险和控制冒险出现的机会也越多。实际处理器需要在频率、硬件复杂度和冒险开销之间折中。

并行处理的主要问题

并行不是简单地“多放几个 CPU”。

真正的问题在于多个计算模块如何协同。

互连

并行系统中有多个处理器、存储器和 I/O 模块。

这些模块之间必须通过某种互连结构通信。

互连结构可能是：

• 共享总线
• 交叉开关
• 多级交换网络
• 环形网络
• 星形网络
• 网格网络
• 立方体网络
• 局域网或互联网

互连决定数据能否快速到达需要它的处理单元。

互连带宽不足时，处理器再多也会被通信拖慢。

数据一致性

多个处理单元可能缓存或访问同一份数据。

如果一个处理器修改了某个数据，其他处理器怎样看到这个新值，就是一致性问题。

典型场景：

• 多个 CPU 有各自 cache，但共享主存
• 多个线程访问同一变量
• NUMA 节点各自有本地内存
• 多个计算节点需要同步中间结果

数据一致性处理不好，会导致程序结果不确定。

同步控制

并行程序中经常需要控制执行顺序。

例如：

• 多个线程不能同时修改同一个共享变量
• 一个线程必须等另一个线程生成数据后才能读取
• Map 阶段全部完成后才能进入 Reduce 阶段
• GPU kernel 之间有先后依赖时必须设置同步栅

同步机制包括：

• 锁
• 信号量
• 屏障
• 原子操作
• 消息等待
• acquire / release 机制

同步太少会出错。

同步太多会降低并行度。

任务划分

并行程序需要把大任务拆成子任务。

任务划分包括：

• 算法分解
• 数据划分

算法分解把不同处理逻辑分开。

数据划分把大数据集拆成多个块，让不同处理单元处理不同数据。

例如矩阵加法可以按行划分。

图像处理可以按像素块划分。

网页词频统计可以按文档集合划分。

并行程序设计

程序员或编译器必须说明哪些部分可以并行，哪些部分有先后关系。

常见方式：

• 多线程编程
• 编译指导语句
• 消息传递接口
• MapReduce 框架
• CUDA kernel

并行程序设计比串行程序复杂。

因为它还要考虑共享数据、通信、同步、负载均衡和容错。

在静态多发射一类处理器中，编译器还要负责相关性分析、指令打包和代码调度。这样可以减少硬件动态检测的复杂度，但编译器必须了解目标处理器的结构限制，生成的二进制代码也会更强地绑定具体体系结构。

资源调度和管理

并行系统中资源更多，调度更复杂。

需要决定：

• 哪个子任务放在哪个处理器上
• 数据放在哪个存储模块中
• 哪些任务可以同时运行
• 通信和计算如何重叠
• 故障节点怎样替换

操作系统、运行时系统和并行框架都可能参与调度。

容错性和安全性

系统规模越大，节点失效概率越高。

并行系统需要考虑：

• 节点故障检测
• 数据冗余
• 任务重启
• 检查点
• 错误恢复
• 访问权限控制

集群和数据中心尤其重视容错。

单个节点失效不能导致整个系统不可用。

性能分析与评估

并行系统常用加速比衡量性能： \[ S=\frac{T_1}{T_p} \]

其中：

• \(T_1\) 是单处理器执行时间
• \(T_p\) 是使用 \(p\) 个处理单元的执行时间

理想情况下： \[ S=p \]

但实际加速比通常小于 \(p\)。

原因包括：

• 串行部分无法并行
• 通信开销
• 同步开销
• 负载不均衡
• cache 和内存带宽瓶颈
• 调度开销

并行效率为： \[ E=\frac{S}{p} \]

效率越接近 1，说明处理单元利用越充分。

增加发射宽度并不能自动得到成倍加速。双发射的理论目标是让 CPI 接近 0.5，但实际还受指令配对、数据相关、结构资源和分支预测影响。只要配对失败或发生冒险，发射槽就会空着。

Amdahl 定律

并行系统必须面对 Amdahl 定律。

如果程序中可并行部分比例为 \(f\)，使用 \(p\) 个处理单元并行执行，则理论加速比为： \[ S=\frac{1}{(1-f)+\frac{f}{p}} \]

当 \(p \to \infty\) 时： \[ S_{max}=\frac{1}{1-f} \]

如果程序有 10% 不能并行，即 \(f=0.9\)，那么即使用无限多个处理器： \[ S_{max}=\frac{1}{0.1}=10 \]

因此并行性能受串行部分严格限制。

这也是并行程序设计必须尽量减少串行瓶颈的原因。

并行处理系统分类

并行处理系统可以从多个角度分类。

Flynn 分类

Flynn 分类按指令流和数据流划分。

SISD

SISD 是单指令流单数据流。

传统单处理器属于 SISD。

它一次执行一个指令流，处理一个数据流。

现代单核处理器内部虽然可能有流水线、超标量和乱序执行，但从程序可见角度看仍可归入 SISD。

课件中把超流水、超标量、动态调度看作 SISD 内部的指令级并行。

SISD 并不等于处理器内部完全串行。经典单核处理器对程序员表现为顺序执行一条指令流，但内部可能同时处理多条处于不同阶段的指令。流水线、转发、暂停和分支预测都是为了在保持程序语义的前提下提高内部并行度。

数据相关还要结合流水线是否按序进入、按序完成来判断。在经典按序流水线中，后面的指令不能先于前面的指令写回，因此 WAR 和 WAW 通常不会形成实际冲突。若允许乱序执行或乱序完成，就必须额外处理这些相关关系。

SIMD

SIMD 是单指令流多数据流。

一条指令同时对多个数据执行相同操作。

典型例子：

• 向量处理机
• MMX
• SSE
• AVX
• GPU 中的部分执行模型

SIMD 适合数据级并行。

例如数组加法、图像处理、矩阵计算、音视频编码等。

MISD

MISD 是多指令流单数据流。

多个指令流处理同一个数据流。

这种结构实际应用很少。

有时可以在容错系统或特殊流水处理场景中看到类似思想。

MIMD

MIMD 是多指令流多数据流。

多个处理器各自执行不同指令流，处理不同数据流。

多处理器系统和多计算机系统大多属于 MIMD。

MIMD 并行程度更高，也更复杂。

按地址空间分类

MIMD 系统可按地址空间访问方式分为：

• 多处理器系统
• 多计算机系统

多处理器系统

多处理器系统共享统一编址的存储器。

所有处理器可以通过普通 load / store 指令访问共享内存。

它也称共享存储多处理器。

特点：

• 单一地址空间
• 处理器间通过共享变量通信
• 编程相对方便
• 需要 cache 一致性和同步机制

SMP、多核处理器、UMA、NUMA 都属于这一类。

多计算机系统

多计算机系统中，每个计算节点有独立编址的存储器。

一个节点不能直接用 load / store 访问另一个节点的私有内存。

节点之间通过消息传递通信。

特点：

• 地址空间分离
• 每个节点有自己的主存和磁盘
• 通过网络交换消息
• 扩展性较好
• 编程更复杂

集群和网格属于多计算机系统。

按访存时间分类

共享存储多处理器还可按访存时间是否一致分为：

• UMA
• NUMA

UMA

UMA 是一致性内存访问结构。

每个处理器访问任意存储单元的时间相同。

也就是访问时间与存储器位置无关。

SMP 通常是一种 UMA 多处理器。

UMA 的优点：

• 编程模型简单
• 所有处理器地位对称
• 软件看到统一共享内存

缺点：

• 规模受限
• 总线或互连网络容易成为瓶颈
• cache 一致性开销随处理器数增加

NUMA

NUMA 是非一致性内存访问结构。

所有存储器仍统一编址。

但处理器访问本地存储器比访问远程存储器快。

NUMA 的特点：

• 保持单一地址空间
• 本地访问快
• 远程访问慢
• 可扩展性比 UMA 好
• 编程和调度需要考虑数据位置

NUMA 程序仍可使用 load / store 访问全部共享内存。

但如果频繁访问远程内存，性能会下降。

CC-NUMA

CC-NUMA 是 cache coherent NUMA。

它在 NUMA 基础上支持 cache 一致性。

多个处理器节点可以缓存共享数据，系统负责维护这些副本的一致性。

CC-NUMA 常使用基于目录的 cache 一致性机制。

每个节点维护本地存储块的目录信息。

目录记录该主存块是否被其他节点缓存，以及缓存在哪些节点。

当某个节点读写共享块时，目录负责协调：

• 提供数据
• 更新目录
• 使其他副本无效
• 或通知其他节点转发数据

按互连方式分类

按处理单元位置和互连方式，可分为：

类型	特点
多核芯片	一个 CPU 芯片内有多个核，共享 LLC 和主存
众核芯片	一个芯片中有大量简单核，如 GPU
对称多处理器 SMP	多个相同 CPU 对称共享资源
大规模并行处理机 MPP	大量处理单元通过专用网络连接
集群	多台普通计算机通过高速网络连接
网格	跨地域异构计算机通过互联网连接

多核、SMP、NUMA 多属于多处理器系统。

集群、网格属于多计算机系统。

GPU 属于众核处理器，常用于数据级并行。

UMA 多处理器

UMA 多处理器中，每个处理器访问所有存储单元时间一致。

根据处理器和共享存储器之间连接方式，可以分为：

• 基于总线
• 基于交叉开关
• 基于多级交换网络

基于总线的 UMA

基于总线的 UMA 中，多个 CPU 模块通过一条共享总线连接到共享存储器。

如果 CPU 不带 cache，每次访存都通过总线访问主存。

结构简单，但总线容易成为瓶颈。

如果 CPU 带 cache，读共享数据可以从 cache 命中，减少总线压力。

但写共享数据时必须维护各 cache 副本一致。

基于总线的 UMA 常采用侦听协议。

每个 cache 控制器监听总线上的读写事务。

当看到其他处理器写某个块时，就更新或失效自己的副本。

常见策略是写无效。

即一个处理器写某共享块时，使其他 cache 中对应副本无效。

MESI

MESI 是典型 cache 一致性协议。

每个 cache 行有四种状态：

状态	含义
M	Modified，已修改，仅本 cache 有，主存旧
E	Exclusive，独占未修改，仅本 cache 有，和主存一致
S	Shared，共享，多个 cache 可有，和主存一致
I	Invalid，无效

MESI 通过状态转换和总线侦听维护一致性。

例如一个处理器要写共享行时，需要让其他处理器中该行变为 I。

这样之后其他处理器再读该行时会发生缺失，从最新来源获取数据。

基于交叉开关的 UMA

交叉开关把 \(m\) 个 CPU 模块和 \(n\) 个存储模块互连。

每个 CPU 到每个存储模块都有可能建立连接。

开关数量约为： \[ m \times n \]

优点：

• 并行访问能力强
• 不同 CPU 可同时访问不同存储模块

缺点：

• 硬件成本随规模快速增长
• 连接和控制复杂

因此适合中小规模系统。

基于多级交换网络的 UMA

多级交换网络使用多级小规模交换器连接 CPU 和存储模块。

例如使用多个 \(2 \times 2\) 交换器组成网络。

优点：

• 比完整交叉开关成本低
• 比单总线扩展性好

缺点：

• 访问路径可能经过多级交换器
• 可能发生网络阻塞
• 控制和路由更复杂

数据访问消息中通常需要携带：

• 存储模块号
• 地址
• 读写操作类型

NUMA 多处理器

UMA 要保证每个处理器访存时间相同。

这限制了系统规模。

为了构建更大规模共享存储系统，可以放宽“访存时间一致”要求。

这就是 NUMA。

NUMA 基本结构

NUMA 系统中，每个节点通常包括：

• CPU
• 本地存储器
• 本地 cache
• 本地互连接口

所有节点的存储器统一编址。

从逻辑上看，它们构成一个共享地址空间。

但从物理上看，存储器分布在不同节点。

访问本地内存快。

访问远程节点内存慢。

NUMA 的软件影响

UMA 程序可以在 NUMA 上运行。

因为地址空间仍统一。

但性能可能变差。

如果线程在节点 A 上运行，却频繁访问节点 B 的内存，会产生大量远程访问。

所以 NUMA 系统中要关注：

• 线程绑定
• 内存分配位置
• 数据和计算的亲和性
• 远程访问比例

操作系统和运行时系统通常会尽量让线程靠近它使用的数据。

基于目录的 CC-NUMA

CC-NUMA 中常用目录维护 cache 一致性。

目录项可记录：

• 主存块是否被缓存
• 缓存在哪些节点
• 块状态
• 是否被修改

简单目录可以记录某个块当前在哪个节点 cache 中。

更复杂目录可以记录多个共享副本。

读缺失时：

• 请求节点根据物理地址找到主存所在节点
• 主存节点查目录
• 如果块未被其他 cache 修改，从主存读取并返回
• 更新目录，记录新副本

写缺失或写共享块时：

• 请求节点向主存节点发写请求
• 目录找到其他缓存副本
• 向这些节点发送失效或写回请求
• 其他副本失效后，写请求节点获得写权限

基于目录的协议比总线侦听更适合大规模系统。

因为大规模 NUMA 没有单一共享总线供所有 cache 侦听。

多处理器互连网络

多处理器互连网络可以有多种拓扑。

常见结构：

拓扑	特点
星形	中心节点连接所有节点，中心可能成瓶颈
环形	节点首尾相连，结构简单，延迟随距离增加
网格	节点按二维网格连接，适合大规模布局
立方体	多维连接，路径较短，布线复杂
交叉开关	任意输入到任意输出，带宽高，成本高
多级网络	多级交换器组成，成本和性能折中

网络设计要考虑：

• 带宽
• 延迟
• 可扩展性
• 成本
• 容错性
• 路由复杂度

多核处理器

多核处理器是在一个 CPU 芯片中集成多个处理器核。

多个核通常共享最后一级 cache 和主存。

从软件角度看，多核系统可以看作片级多处理器。

为什么转向多核

处理器发展遇到两个重要限制：

• 功耗墙
• 指令级并行墙

功耗近似关系： \[ P=C V^2 f \]

其中：

• \(C\) 与集成度和电路电容有关
• \(V\) 是电压
• \(f\) 是主频

主频和集成度提高会导致功耗和散热问题。

2004 年前后，单纯提高主频的路线难以继续。

处理器厂商转向多核架构。

多核通过线程级并行提高总体吞吐率。

多核的特点

多核处理器通常具有：

• 多个处理器核
• 每个核私有 L1 cache
• 每个核可能有私有 L2 cache
• 多核共享 LLC
• 多核共享内存控制器和主存
• 核间通过片上互连通信

从连接结构和软件角度看，很多桌面多核处理器接近 UMA。

所有核共享同一主存地址空间。

硬件多线程

从 CPU 角度看，一个线程就是一个指令序列。

硬件多线程为多个线程提供独立的线程状态。

每个线程通常需要：

• PC
• 通用寄存器组或寄存器映射
• 状态寄存器
• 线程切换控制

硬件多线程的目标是隐藏流水线停顿和访存延迟。

一个物理核心可以看成一套执行引擎，包含取指、译码、执行、访存和写回等部件。逻辑处理器是操作系统看到的可调度执行单元。开启超线程后，一个物理核心可能对应多个逻辑处理器，但它们并不等价于多个完整物理核心。

细粒度多线程

细粒度多线程在多个线程之间轮流发射指令。

它可以在每个时钟周期切换线程。

优点：

• 能隐藏长延迟
• 单个线程停顿时影响较小

缺点：

• 单线程性能可能下降
• 需要维护多个线程上下文

粗粒度多线程

粗粒度多线程只在当前线程发生较大阻塞时切换线程。

例如 cache 缺失时切换。

优点：

• 实现较简单
• 对单线程连续执行影响较小

缺点：

• 对短停顿隐藏能力有限
• 切换时可能有流水线清空开销

同时多线程

同时多线程 SMT 可以在同一时钟周期发射来自不同线程的指令。

Intel 超线程就是典型 SMT。

SMT 在单核内部提供多套线程状态，但共享 cache、执行部件和发射资源。

目标是在实现指令级并行的同时利用线程级并行。

当一个线程无法填满所有发射槽时，另一个线程可以使用空闲资源。

超线程主要复用昂贵的执行部件，而不是简单复制整套核心。它能提高空闲资源利用率，但当两个线程同时争用整数、浮点、乘除等执行部件时，性能不会翻倍。

共享存储器同步控制

多核和多处理器系统共享内存。

多个核同时访问共享变量时，执行顺序可能不确定。

为了让程序结果可预测，需要存储器一致性模型和同步指令。

存储器一致性模型

存储器一致性模型规定多核系统中访存操作对其他处理器可见的顺序。

它是 ISA 对软件和硬件之间的约定。

不同一致性模型在直观性和性能之间取舍。

顺序一致性模型

顺序一致性要求：

• 每个处理器按程序顺序执行访存
• 所有处理器的访存结果等价于某个全局串行顺序
• 该全局顺序保持每个处理器内部程序顺序

它最直观，最容易理解。

但它限制硬件和编译器重排访存指令。

因此性能优化空间较小。

实际高性能系统很少完全采用严格顺序一致性。

宽松一致性模型

宽松一致性允许硬件或编译器改变某些访存操作顺序。

例如两个没有依赖的内存访问可以重排。

这能提高性能。

但如果程序需要特定顺序，就必须使用屏障指令。

屏障指令也称 fence。

它约束屏障前后的访存顺序。

例如：

• fence 前的写必须先完成
• fence 后的读写不能提前到 fence 前

RISC-V 基础指令集提供了 fence 指令来约束访存顺序。

释放一致性模型

释放一致性进一步把同步操作分为：

• acquire，获取
• release，释放

release 保证临界区内前面的写入先于释放锁对外可见。

acquire 保证获取锁之后的访问不会跑到获取之前。

这种方式比普通 fence 更精确。

它只在同步点施加必要顺序约束。

因此性能更好。

例子

假设核 0 写入数据块，然后设置标志位。

核 1 等待标志位变为 1，再读取数据块。

如果访存可以乱序：

• 核 0 的标志位写入可能先于数据块写入对外可见
• 核 1 看到标志位为 1 后，可能读到旧数据

解决方法：

• 在数据写入和标志写入之间加 fence
• 或用 release 写标志，用 acquire 读标志

同步指令的作用就是告诉硬件和编译器：这里不能随意重排。

共享区域加锁

多个线程访问共享数据时，经常需要互斥。

互斥的目标是：

同一时刻只有一个处理器进入临界区。

实现锁需要硬件支持原子性。

否则两个处理器可能同时看到锁为空，并同时进入临界区。

原子操作方式

原子操作指一组读改写动作不可分割。

例如原子交换：

• 读出内存中的旧锁值
• 把新值写入锁
• 整个过程不能被其他处理器插入

如果旧锁值为 0，说明锁空闲，获取成功。

如果旧锁值非 0，说明锁已被占用，需要继续等待。

RISC-V RV32A 提供原子操作指令，如 amoswap。

互斥读写方式

另一种方式是成对使用互斥读和互斥写。

RISC-V 中对应：

• lr.w：load-reserved
• sc.w：store-conditional

lr.w 读取锁变量，并建立保留。

sc.w 尝试写入。

如果从 lr.w 到 sc.w 之间没有其他处理器修改该地址，则 sc.w 成功。

如果该地址被其他处理器修改，sc.w 失败。

失败时程序重新尝试。

这种机制可以实现自旋锁。

锁的代价

锁能保证正确性，但也有代价：

• 自旋等待浪费处理器周期
• 临界区串行化降低并行度
• 锁竞争会增加 cache 一致性流量
• 锁使用不当可能导致死锁

并行程序设计中要尽量缩小临界区，减少共享可写数据。

多计算机系统

多计算机系统由多个独立计算节点组成。

每个节点有自己的处理器、主存和 I/O 设备。

节点间通过网络传递消息。

多计算机系统不提供统一共享地址空间。

因此一个节点不能直接 load 另一个节点内存。

集群

集群是用局域网或专用网络连接的紧耦合同构多计算机系统。

每个节点通常是普通 PC、工作站或 SMP 服务器。

每个节点有：

• 自己的 CPU
• 自己的主存
• 自己的磁盘
• 网卡

节点之间通过消息传递通信。

集群特点

集群特点：

• 成本相对低
• 可扩展性好
• 适合数据库、文件服务器、Web 服务、大规模计算
• 单个节点故障可通过冗余和调度恢复
• 通信延迟比多处理器系统大

多处理器系统中存储访问可能是纳秒级。

集群中节点间通信常是微秒级或更高。

因此集群程序必须减少节点间频繁细粒度通信。

集群互连

集群中每个节点通过网卡连接交换机。

网卡可能包含：

• DMA 通道
• 缓冲区
• 协议处理逻辑
• 甚至专门 I/O 处理器

交换机负责在节点之间转发消息。

交换机制主要有：

• 存储转发分组交换
• 电路交换

集群中常采用分组交换。

分组交换

分组交换把大消息拆成多个小分组。

每个交换机收到完整分组后，再转发到下一跳。

这叫存储转发。

若路径经过多个交换机，每一跳都可能有转发延迟。

若输出端口忙，分组还需要在输出队列等待。

分组交换优点：

• 灵活
• 容易共享网络带宽
• 成本低
• 适合多个消息并发传输

缺点：

• 有转发延迟
• 有排队延迟
• 延迟不稳定

Google 集群例子

教材和课件以 Google 数据中心为例说明集群。

数据中心由大量普通服务器组成。

服务器放在机架中。

机架通过集群交换机连接。

多个机架构成大规模集群。

这种系统也称 WSC，Warehouse Scale Computer。

它强调：

• 大量廉价节点
• 通过软件实现容错
• 高效网络互连
• 大规模数据处理
• 能耗和冷却成本控制

数据中心不是单台超级计算机。

它是大量普通机器通过网络和软件组织起来的并行系统。

网格

网格计算用互联网把不同地理位置、不同管理域中的异构计算机连接起来。

从逻辑上看，它希望形成一台虚拟超级计算机。

网格节点可能属于不同机构，硬件和软件环境也不同。

网格特点

网格特点：

• 地理位置分散
• 异构性强
• 松耦合
• 需要中间件管理资源
• 通过广域网通信
• 目标是资源共享和协同计算

网格中每台计算机运行特殊管理程序。

中间件负责：

• 用户认证
• 远程登录
• 资源发布
• 资源发现
• 作业调度
• 结果收集

网格的困难

网格设想很好，但广泛应用困难。

原因包括：

• 管理域不同
• 安全和认证复杂
• 网络延迟高且不稳定
• 节点异构
• 资源可用性变化大
• 作业调度困难
• 数据迁移成本高

云计算中的一些思想和网格有联系。

但实际工程中，集中管理的数据中心集群更常见。

向量处理机和 SIMD

SIMD 技术适合处理大量结构相同的数据。

典型代码：

for (i = 0; i < 64; i++) {
    c[i] = a[i] + b[i];
}

每次循环执行相同操作，只是数据元素不同。

这类程序适合数据级并行。

向量处理机

向量处理机面向向量型数据。

向量的各个分量彼此独立，可以并行执行相同运算。

它曾广泛用于科学计算，如：

• 空气动力学
• 原子物理
• 气象模拟
• 矩阵运算
• 傅里叶变换
• 偏微分方程求解

向量处理基本思想

向量处理机通常有：

• 向量寄存器
• 向量装入/存储指令
• 向量运算流水线
• 高带宽主存
• 多模块交叉存储器

对数组加法：

for (i = 0; i < 64; i++) {
    c[i] = a[i] + b[i];
}

标量处理器需要循环执行很多指令。

如果每次循环包含 load、load、add、store、地址更新、分支等，大约要数百条指令。

向量处理机可以用类似下面 4 条指令完成：

v_lw  $v_t1, 0($s1)
v_lw  $v_t2, 0($s2)
v_add $v_t3, $v_t1, $v_t2
v_sw  $v_t3, 0($s3)

每条向量指令处理 64 个数据元素。

这样减少了取指和译码次数，也减少了循环控制开销。

向量处理优势

向量处理的优势：

• 一条指令表达大量重复操作
• 减少指令开销
• 运算流水线可连续处理向量元素
• 数据相关主要出现在向量起始处
• 适合规则数组和矩阵计算

缺点：

• 对不规则控制流不友好
• 需要高内存带宽
• 向量长度和数据布局会影响效率

循环展开可以为编译器提供更多可重排的指令，减少分支开销，并改善发射槽利用率。代价是代码体积变大，并且常常需要配合寄存器重命名避免新的名字依赖。

Intel SIMD 技术

Intel 架构中，SIMD 技术从 MMX、SSE 发展到 AVX。

它们本质上都是一条指令同时处理多个小数据。

MMX

MMX 使用 64 位寄存器。

它可以同时处理：

• 8 个字节
• 4 个字
• 2 个双字
• 1 个 64 位数据

MMX 主要面向多媒体整数运算。

SSE

SSE 使用 128 位 XMM 寄存器。

它可以同时处理：

• 16 个字节
• 8 个 16 位字
• 4 个 32 位整数或单精度浮点数
• 2 个 64 位双精度浮点数

SSE、SSE2、SSE3、SSE4 等逐步扩展了浮点、整数、数据转换和多媒体处理能力。

AVX

AVX 把 SIMD 寄存器宽度扩展到 256 位。

更宽的向量寄存器意味着一条指令可以处理更多数据。

但实际性能还取决于：

• 数据是否对齐
• 内存带宽
• 编译器向量化能力
• 指令延迟和吞吐
• 程序是否有足够数据级并行

SIMD 例子

课件中的例子比较普通字节加法和 SSE 字节加法。

普通指令每次循环只完成一个字节加法。

SSE 指令使用 128 位 XMM 寄存器，每次可以同时处理 16 个字节。

因此循环次数从 \(2^{26}\) 降为 \(2^{22}\)。

理论加速接近 16 倍。

实际测试也接近这一比例。

这说明 SIMD 对规则、独立、可批量处理的数据很有效。

GPU 架构

GPU 最初用于图形处理。

图形渲染包含大量相同类型的并行计算，例如顶点处理、像素着色、纹理采样。

这些计算天然适合数据级并行。

随着 CUDA 等 GPGPU 编程框架普及，GPU 被用于通用计算。

应用包括：

• 石油勘测
• 天文计算
• 流体模拟
• 分子动力学
• 生物计算
• 神经网络

CPU 和 GPU 分工

CPU 适合：

• 复杂控制逻辑
• 操作系统和事务处理
• 分支多的程序
• 低延迟任务
• 串行或少量并行任务

GPU 适合：

• 大量线程
• 数据级并行
• 相同操作处理大量数据
• 高吞吐计算

GPGPU 通常采用 CPU + GPU 异构模式。

CPU 负责控制和调度。

GPU 负责大规模并行计算。

Tesla GT200 结构

教材和课件以 NVIDIA Tesla GT200 为例。

其结构包括：

• 流处理器阵列 SPA
• 线程处理器群 TPC
• 流多处理器 SM
• 流处理器 SP
• 特殊功能单元 SFU
• 双精度单元 DPU
• 存储控制系统
• 纹理 cache、指令 cache、常数 cache

一个 TPC 包含多个 SM。

一个 SM 包含多个 SP。

SP 可以看作执行标量运算的简单核心。

SFU 执行倒数、平方根倒数、正弦、余弦等特殊函数。

DPU 用于双精度浮点和 64 位整数乘加等运算。

SIMT

NVIDIA 把 GPU 执行模型称为 SIMT。

SIMT 是 single instruction multiple thread。

它和传统 SIMD 相似，都让多个执行单元执行同一条指令。

但编程模型不同。

传统 SIMD 中，向量宽度通常显式体现在指令和寄存器宽度中。

CUDA 中，程序员写的是线程程序。

大量线程被组织成线程块和网格。

硬件把线程分组执行。

这种模型比显式 SIMD 对程序员更灵活。

GPU 的限制

GPU 不是所有任务都快。

它适合：

• 大量数据
• 相同操作
• 少分支
• 高算术强度
• 规则内存访问

不适合：

• 串行依赖强
• 分支复杂
• 数据量太小
• 频繁 CPU-GPU 数据传输
• 随机访存严重

GPU 计算的瓶颈常常不是算力，而是显存带宽、访存合并、分支发散和数据搬运。

并行编程模式

不同并行硬件适合不同编程模型。

常见编程方式：

• 共享存储变量方式
• 消息传递方式
• MapReduce
• Spark
• CUDA

共享存储变量方式

共享存储变量方式用于共享存储多处理器系统。

多个线程共享同一个地址空间。

线程之间通过共享变量通信。

这种方式适合多核 CPU、SMP、UMA 和 NUMA 系统。

Pthread

Pthread 是较低层的多线程编程接口。

它通过在串行程序中加入线程函数调用实现并行。

常见操作：

• 创建线程
• 等待线程结束
• 设置线程属性
• 使用锁和条件变量同步

每个 Pthread 线程有：

• 线程标识符
• PC 和寄存器上下文
• 栈
• 调度属性

Pthread 灵活，但需要程序员显式管理线程和同步。

OpenMP

OpenMP 通过编译指导语句实现并行。

例如：

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    a[i] = b[i] + c[i];
}

这告诉编译器把循环编译成多线程并行代码。

OpenMP 适合把已有串行程序逐步并行化。

它常用于共享内存多核系统。

编程时需要指定：

• 线程数量
• 私有变量
• 共享变量
• 规约变量
• 调度策略

消息传递方式

消息传递方式用于分布式存储系统，例如集群。

每个进程有自己的地址空间。

进程之间不能直接访问对方内存。

数据交换必须通过发送和接收消息完成。

MPI

MPI 是 Message Passing Interface。

它是最典型的消息传递并行编程标准。

MPI 程序通常是多进程并行。

所有进程可以运行同一个程序，但根据进程编号处理不同数据。

典型函数：

• MPI_Init
• MPI_Comm_size
• MPI_Comm_rank
• MPI_Send
• MPI_Recv
• MPI_Finalize

MPI_Comm_size 得到进程总数。

MPI_Comm_rank 得到当前进程编号。

根据编号不同，每个进程可以处理不同数据块。

共享存储和消息传递比较

项目	共享存储	消息传递
通信方式	共享变量	显式发送/接收
地址空间	统一	分离
典型系统	多核、SMP、NUMA	集群
编程难点	数据竞争、锁、cache 一致性	数据划分、通信、同步
扩展性	中等	较好

共享存储编程更像普通程序，但容易出现数据竞争。

消息传递通信显式，程序员要自己组织数据交换。

MapReduce

MapReduce 是面向大规模数据处理的并行计算框架。

它由 Google 提出。

程序员只需要实现：

• Map
• Reduce

框架负责数据划分、任务调度、中间结果收集、容错和负载均衡。

Map

Map 操作对输入记录做重复处理，输出键值对。

例如 WordCount 中：

输入：

the weather is good

Map 输出：

(the, 1), (weather, 1), (is, 1), (good, 1)

Shuffle

Reduce 之前必须把相同 key 的中间结果收集到一起。

这个阶段称为 aggregation 和 shuffle。

它本质上是一次全局数据重排。

Reduce 开始前，需要等待所有 Map 完成。

所以这里有一个同步屏障。

Reduce

Reduce 对相同 key 的值进行规约。

例如：

(good, 1), (good, 1), (good, 1)

Reduce 输出：

(good, 3)

MapReduce 特点

优点：

• 编程接口简单
• 容错性好
• 负载均衡好
• 适合海量数据离线处理

缺点：

• 中间结果常写磁盘
• I/O 开销大
• 不适合低延迟迭代计算

Spark

Spark 是大规模并行计算框架。

它改进了 MapReduce 频繁读写磁盘的问题。

Spark 提出 RDD，也就是弹性分布式数据集。

中间工作集可以存放在分布式内存中。

这样迭代计算不需要每轮都写磁盘再读磁盘。

RDD 可通过：

• 从 HDFS 加载
• 从内存数据分片
• 由已有 RDD 转换

常见 transformation：

• map
• filter
• join
• reduceByKey

Spark 还支持广播变量等共享数据机制。

CUDA

CUDA 是 NVIDIA GPU 的并行编程模型。

它用于 CPU + GPU 异构系统。

CUDA 对 C/C++ 扩展了：

• 层次结构线程组
• 同步栅
• 共享内存

CUDA 层次

CUDA 的执行层次：

• grid
• thread block
• thread

一个 kernel 启动一个 grid。

grid 中有多个 thread block。

每个 thread block 中有多个 thread。

线程块内线程可以通过共享内存通信，并使用块内同步。

不同线程块之间一般不能直接同步。

CUDA 和 GPU 硬件对应

课件中给出一种对应关系：

CUDA 概念	GPU 硬件层次
grid	一次 kernel 任务
thread block	可调度到 SM 的线程块
thread	在 SP 上执行的线程

硬件层次如：

• TPC
• SM
• SP

CUDA 编程时，需要设置 grid 维度和 block 维度。

例如：

kernelA<<<6, 32>>>(params);

表示 6 个一维线程块，每个线程块 32 个线程。

二维配置例子：

kernelB<<<(6, 4), (8, 3)>>>(params);

表示 grid 为 \(6 \times 4\) 个线程块，每个线程块为 \(8 \times 3\) 个线程。

CUDA 同步

同一个线程块内可以同步。

不同 kernel 之间如果有顺序依赖，需要在 kernel 调用之间设置同步。

例如任务 B 必须等任务 A 完成：

• 启动 kernelA
• 等待 kernelA 完成
• 再启动 kernelB

如果没有同步，后续 kernel 可能读到未完成的数据。

CUDA 适用场景

CUDA 适合：

• 大量数据元素
• 每个元素处理逻辑类似
• 计算密集或高吞吐
• 线程间通信较少
• 内存访问较规则

应用例子：

• 地震图像建模
• 分子动力学
• 脑神经电路模拟
• 超声图像处理
• 深度学习

并行系统的统一比较

多处理器和多计算机

项目	多处理器系统	多计算机系统
地址空间	共享统一编址	各节点独立编址
通信方式	load/store 共享变量	消息传递
典型系统	多核、SMP、NUMA	集群、网格
通信延迟	较低	较高
扩展性	有限到中等	较好
编程难点	同步和一致性	数据划分和通信

UMA 和 NUMA

项目	UMA	NUMA
地址空间	统一	统一
访存时间	与位置无关	本地快，远程慢
典型规模	较小	较大
一致性	常用总线侦听	常用目录协议
编程关注点	锁和共享变量	还要关注数据位置

SIMD 和 MIMD

项目	SIMD	MIMD
指令流	单个	多个
数据流	多个	多个
并行类型	数据级并行	线程级或任务级并行
适合任务	数组、图像、矩阵	多任务、服务、复杂并行
例子	SSE、AVX、向量机	多核、集群

典型题型整理

分类题

判断系统类型时抓关键点：

• 是否共享地址空间
• 是否用 load/store 访问共享数据
• 访存时间是否一致
• 是否通过消息传递通信
• 是数据级并行还是线程级并行

例如：

• 多核 CPU：多处理器，通常共享存储
• SMP：UMA
• CC-NUMA：共享地址空间，访存时间不一致，有 cache 一致性
• 集群：多计算机，消息传递
• SSE/AVX：SIMD
• MPI 程序：消息传递

加速比题

基本公式： \[ S=\frac{T_1}{T_p} \]

效率： \[ E=\frac{S}{p} \]

Amdahl 定律： \[ S=\frac{1}{(1-f)+\frac{f}{p}} \]

做题时要区分：

• 给的是执行时间还是吞吐率
• 是否有串行部分
• 是否考虑通信和同步开销
• 使用的是几个处理器

cache 一致性题

共享 cache 一致性题要看：

• 哪些处理器缓存了同一块
• 谁执行读
• 谁执行写
• 写时是更新还是失效
• 当前块状态是什么

MESI 中写共享块通常要让其他副本失效。

CC-NUMA 中则通过目录找到副本所在节点并发送消息。

存储器一致性题

判断并发程序结果时，要看：

• 硬件是否允许重排
• 是否有 fence
• 是否使用 acquire/release
• 读写是否访问同一共享变量
• 是否存在数据竞争

没有同步时，不要默认其他核一定按自己看到的顺序观察到写入。

GPU / CUDA 题

CUDA 配置题要分清：

• grid 有多少 block
• 每个 block 有多少 thread
• 总线程数是多少

例如：

kernel<<<(6, 4), (8, 3)>>>();

block 数： \[ 6 \times 4 = 24 \]

每个 block 线程数： \[ 8 \times 3 = 24 \]

总线程数： \[ 24 \times 24 = 576 \]

小结

第九章的核心是并行处理。

并行系统要解决的不只是计算资源变多，还包括互连、数据一致性、同步、任务划分、调度和容错。

本章重点：

• Flynn 分类包括 SISD、SIMD、MISD、MIMD
• SIMD 是数据级并行，适合数组、矩阵、图像等规则数据
• MIMD 包括多处理器和多计算机
• 多处理器共享地址空间，通过 load/store 访问共享内存
• 多计算机地址空间分离，通过消息传递通信
• UMA 访存时间一致，SMP 是典型 UMA
• NUMA 保持统一地址空间，但本地访问快于远程访问
• CC-NUMA 用目录协议维护 cache 一致性
• 多核是片级多处理器，硬件多线程用于隐藏延迟和提高资源利用率
• 共享存储系统必须考虑存储器一致性和同步控制
• 原子操作、lr.w / sc.w 可实现锁
• 集群通过局域网连接节点，常用消息传递
• 网格通过广域网连接异构资源，工程难度较大
• 向量处理机、SSE、AVX 和 GPU 都利用数据级并行
• CUDA 用 grid、block、thread 组织 GPU 并行程序
• Pthread、OpenMP、MPI、MapReduce、Spark、CUDA 是不同层次的并行编程方式

理解并行处理系统时，可以抓住三个问题：

• 并行的是指令、数据、线程还是任务
• 处理单元之间怎样通信
• 共享数据怎样保持正确和一致

这三个问题决定了系统结构、编程模型和性能瓶颈。