期末速通

并行计算

谁不想急头白脸地参加并行计算考试呢

并行计算概述

并行计算基本概念

基本概念 内容
计算 数学计算、数据处理、IT服务
性能 FLOPS（浮点计算数/秒）
浮点计算能力 计算机主频每时钟周期的浮点指令数
产生原因 满足不断增长的计算力需求：用多个处理器同时解决一个问题
计算机硬件与网络技术的发展
单处理器性能提升受限
存储、I/O速率远低于处理器

并行化方法

域分解

首先确定数据如何划分到各个处理器，然后确定每个处理器所需要做的事情。

域分解

任务分解

首先将任务划分到各个处理器，然后确定各个处理器需要处理的数据。

任务分解

流水线

将一个任务拆分成多个步骤，通过不同步骤在时间上的重叠达到“并行”的效果。

并行计算的硬件环境

PRAM模型

PRAM全称为Parallel Random Access Machine，它具备以下特点：

  1. 每个处理器可同时从共享的内存中读取数据到自己的寄存器
  2. 每个处理器执行计算过程，数据存储在本地寄存器
  3. 每个处理器可同时将数据写入到共享的内存（存在潜在冲突）

PRAM模型

PRAM模型可以衍生出以下模型：

模型 特点
EREW 任意两个处理器不能并发读，也不能并发写
CREW 可以并发读，但不能并发写
CRCW 可以并发读，也可以并发写

根据PRAM模型，可以对前缀求和作出并行算法设计：

前缀求和

处理器

SIMD体系

SIMD是一条指令同时操作多个数据，适合数据级并行的计算机体系结构。

Flynn分类法（Flynn’s Taxonomy）是计算机体系结构领域最经典的分类方法之一。它根据指令流（Instruction Stream）——机器执行的指令序列，和数据流（Data Stream）——由指令流调用的数据序列两个维度的"单"（Single）或"多"（Multiple）组合，将计算机体系结构分为四类：

类型 全称 指令流 数据流 典型代表 特征
SISD Single Instruction Single Data 单 单 早期单核CPU（如Intel 8086）、传统冯·诺依曼架构 顺序执行，一次处理一个任务的一> 份数据
SIMD Single Instruction Multiple Data 单 多 GPU、向量处理器、Intel SSE/AVX指令集 一条指令同时操作多个数据，适合数据级并行
MISD Multiple Instruction Single Data 多 单 极少见，主要用于容错系统（如航天器冗余控制） 多个指令同时处理同一数据，理论意义大于实际
MIMD Multiple Instruction Multiple Data 多 多 多核CPU、分布式计算集群、高性能服务器 多个独立指令流处理多个数据流，实现任务级并行

多核处理器

进入21世纪，曾预言“CPU主频18个月翻一番”的摩尔定律不再适用于当下处理器的发展方向。

限制单核性能主要有以下几个方面：

  1. 功耗墙：CPU越小，单位面积产生的热量越多，散热越困难。
  2. 存储墙：CPU缓存占据了70%以上的芯片面积，限制了性能的进一步提升。

多核处理器的特点：

  1. 多个复杂度适中，相对低功耗的处理核心并行工作。
  2. CPU时钟频率基本不变、

GPU

GPU将更多元件用于数据处理，而非控制和存储。

可以将GPU视作超大规模并行协处理器和SPMD（单程序多数据）模式，实现了数据并行。

互连网络

静态互连网络：处理单元之间有固定连接的一类网络，在程序执行期间这种点到点的链接保持不变：

分类 特点
一维线性阵列 每个节点只与其左右近邻相连（$N$个节点用$N-1$条边串接）
二维网孔 每个节点只与其上、下、左、右的近邻相连（边界结点除外）
二叉树 与完全二叉树的结构类似
超立方 更为复杂的空间结构

动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态。包括总线、交叉开关等

内存访问模式

并行计算系统的体系结构

体系结构 特点
PVP（Parallel Vector Processor） 含有为数不多、功能强大的定制向量处理器
SMP（Symmetric Multiprocessor） 多个处理器通过总线或交叉开关连接到共享存储器
MMP（Massively Parallel Processor） 处理节点采用微处理器，系统中有物理上的分布式存储器

并行计算的性能评测

并行计算的性能

指标 内容
Performance 通常是指机器的速度，定义为程序执行时间的倒数
程序执行时间 用户的相应时间（访问存储器的时间、CPU时间、I/O时间以及操作系统的开销）
CPU时间 表示CPU的工作时间，不包括I/O等待时间和运行其他任务的时间

计算量的度量

工作负载：计算量/任务量

并行计算执行时间：$t_p = t_{comp} + t_{paro} + t_{comm}$

其中 $t_{comp}$ 为计算时间，$t_{paro}$ 为并行开销时间，$t_{comm}$ 为相互通信时间

性能指标

加速比：串行执行时间与并行执行时间的比值

$$S(n) = \frac{t_s}{t_p}$$

计算/通信比：

$$\frac{t_{comp}}{t_{comm}}$$

效率：

$$E = \frac{t_s}{t_p \times n} = \frac{S(n)}{n}$$

代价：

$$\frac{t_s}{E}$$

内存系统对性能的影响

对很多应用而言，瓶颈在于内存系统，而不是CPU。它包括两个方面：

  1. 延迟：处理器向内存发起访问直至获取数据所需要的时间。
  2. 带宽：内存系统向处理器传输数据的速率。

将内存想象为水龙头，则延迟可视为打开水龙头到水流出之间的时间；带宽可视为水开始流出后每秒流出的水量。

如果想尽可能快地出水，应当减少延迟；如果想尽快地获得更多的水，应当提升带宽。

考虑利用时间局部性和空间局部性原理减少延迟

加速比定律

参数 定义
$P$ 处理器数目
$W$ 问题规模，$W_s$ 表示串行部分，$W_p$ 表示可以并行的部分，则有 $W_s + W_p = W$
$T_s$ 串行执行时间
$T_p$ 并行执行时间
$S$ 加速比
$E$ 效率

Amdahl 定律

在计算负载不变、通过增加处理器的执行速度达到加速目的的条件下，不断增加并行计算机和处理器的数目，不可以无限制地提升加速比。

固定负载的加速公式：

$$S = \frac{W_s + W_p}{W_s + \displaystyle \frac{W_p}{P}} = \frac{f+(1-f)}{f+\displaystyle \frac{1-f}{P}} = \frac{P}{1+f(P-1)}$$

当 $P \rightarrow \infty$ 时，$\displaystyle S = \frac{1}{f}$

若有额外开销 $W_o$

$$S = \frac{W_s + W_p}{W_s + \displaystyle \frac{W_p}{P} + W_o} = \frac{P}{1+f(P-1)+W_o \cdot \displaystyle \frac{P}{W}}$$

Gustafson 定律

在提升并行计算机数目的同时增加计算量，可以无限制地提升加速比。

$$S = \frac{W_s + P \cdot W_p}{W_s + P \cdot \displaystyle \frac{W_p}{P}} = \frac{W_s + P \cdot W_p}{W_s + W_p} = f+P(1-f) = P - f(P-1)$$

加入额外开销：

$$S = \frac{W_s + P \cdot W_p}{W_s + W_p + W_o} = \frac{f + P(1-f)}{1+\displaystyle \frac{W_o}{W}}$$

Sun and Ni 定律

令因子 $G(p)$ 表示存储容量增加到 $P$ 倍时工作负载的增加量，所以扩大后的工作负载 $W = fW + (1-f) \cdot G(p) \cdot W$

$$S = \frac{f W + (1-f) \cdot G(p) \cdot W}{fW + (1-f) \cdot G(p) \cdot \displaystyle \frac{W}{p}} = \frac{f+(1-f) \cdot G(p)}{f+(1-f) \cdot \displaystyle \frac{G(p)}{p}}$$
  1. $G(p) = 1$，就是Amadahl定律
  2. $G(p) = p$，就是Gustafson定律
  3. $G(p) > p$，相当于计算机负载比存储要求增加得快，此时Sun and Ni加速比更快

可扩放性评测

可扩放性反映了计算机系统性能随处理器数的增加而按比例提高的能力。

增加规模有利于提高加速比的因素

  1. 较大的问题可以提高较高的并发度
  2. 额外开销的增加可能慢于有效计算的增加
  3. 算法中的串行分量比例不是固定不变的，随问题规模的增加而减小

并行程序设计方法

以下提供一些并行计算的程序设计方法。请注意，这些方法通常不会单一出现，而是综合使用。

并行设计方法大体上分为两类：共享内存型（Pthread、OpenMP，CUDA）和分布式计算型（MPI、MapReduce）。

并行算法设计

算法：计算指令序列（逻辑）

串行算法：只有一组计算指令

并行算法：一些可同时执行的计算任务的集合，这些计算任务分工合作获得给定问题的求解。

设计思想

  1. 并行算法设计并不是串行算法设计的进阶：串行算法的设计思想，一般都基于冯式架构，指令逻辑顺序清晰；并行计算硬件环境没有统一的体系结构。
  2. 并行算法中部分计算过程可以是串行算法，串行算法中的部分计算过程也可以并行化
  3. 并行算法的设计，与问题本身以及硬件平台均相关：问题类型与硬件平台类型的组合，能够形成并行算法（程序）设计的模式
  4. 并行算法的类型：计算密集or数据密集
  5. 数据结构与算法密不可分

一般策略

串行算法的直接并行化

分析现有串行算法中固有的并行性，直接将其并行化：该方法并不是对所有问题都可行，但对很多应用问题仍不失为一种有效的方法。

由串行算法直接并行化的方法是并行算法设计的最常用方法之一，但需要注意以下方面：

  1. 不是所有的串行算法都可以直接并行化；
  2. 一个好的串行算法未必能并行化为一个好的并行算法；
  3. 许多数值串行算法可以并行化为有效的数值并行算法。

重新设计并行算法

从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法：这种方法有一定难度，但所设计的并行算法通常更高效。

利用已有的并行算法

借助已有的并行算法求解新问题。

PCAM方法学

设计并行程序的四个阶段

阶段 任务
划分（Partitioning） 分解成小的任务，开拓并发性
通讯（Communication） 确定诸任务间的数据交换，监测划分的合理性
组合 （Agglomeration） 依据任务的局部性，组合成更大的任务
映射 （Mapping） 将每个任务分配到处理器上，提高算法的性能

划分

充分开拓算法的并发性和可扩放性；

  1. 先进行数据分解（域分解），再进行计算功能的分解（功能分解）；
  2. 使数据集和计算集互不相交；
  3. 划分阶段忽略处理器数目和目标机器的体系结构；

通讯

通讯是PCAM设计过程的重要阶段；

  1. 划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流，从而产生了通讯；
  2. 功能分解确定了诸任务之间的数据流；
  3. 诸任务是并发执行的，通讯则限制了这种并发性；

通讯模式：

  1. 局部/全局通讯
  2. 结构化/非结构化通讯
  3. 静态/动态通讯
  4. 同步/异步通讯

组合

组合是由抽象到具体的过程，将组合的任务能在一类并行机上有效的执行

合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程。

增加任务的粒度和重复计算，可以减少通讯成本。保持映射和扩展的灵活性，降低软件工程成本

映射

每个任务要映射到具体的处理器（计算资源），定位到运行机器上；

  1. 任务数大于处理器数时，存在负载平衡和任务调度问题；
  2. 映射的目标：减少算法的执行时间
  3. 并发的任务分配到不同的处理器，任务之间存在高通讯的分配到同一处理器

映射实际是一种权衡，属于NP完全问题

静态映射模式

  1. 基于数据划分的映射
  2. 基于任务图划分的映射
  3. 复合的映射

动态映射模式（也称为动态负载均衡，因为负载均衡是动态调度的主要动机）可以是集中式的和分布式的。

映射的原则：最小化交互开销

  1. 最大化数据局部性：只要可能就复用中间数据，重建计算以使数据在较小的窗口内得到重用
  2. 最小化数据交换量
  3. 最小化交互的频度
  4. 最小化竞争和热点
  5. 计算与通信重叠：使用非阻塞式通信；多线程；预取以隐藏时延
  6. 使用成组通信而非点对点通信
© 2025 - 2026 RunicDolphin806
网站总访客数：Loading

使用 Hugo 构建
主题 Stack 由 Jimmy 设计