并行计算概述
并行计算是通过使用多个处理器一起工作解决某个问题。
1.1并行 v.s. 分布式
并行计算
不同计算活动在同一时间发生；单个应用使用多核/多处理器/多进程来处理更大规模负载或同样规模负载算的更快；通常用于科学计算。
分布式计算
跨系统或不同位置的服务器；更专注于并发控制和资源共享；通常用于商业领域。
特性并行计算 (Parallel Computing)分布式计算 (Distributed Computing)目标通常解决单一的、紧耦合的计算任务，追求极致的速度提升（算得更快）或处理更大规模的问题。解决多个任务，更侧重于资源共享、高可用性和并发控制。内存模型处理器间通常通过共享内存紧密耦合，通信延迟极低。通常基于独立的节点，每个节点有自己的私有内存，通过网络进行消息传递，通信延迟相对较高。耦合度任务间高度耦合，需要频繁同步和通信。系统组件松散耦合。应用领域科学计算、数值模拟、大规模数据分析等。互联网服务、分布式数据库、区块链、商业应用等。1.2 为什么需要并行计算
节省时间与成本
通过并行处理，大幅缩短计算任务的运行时间。
解决更大规模的问题
如宇宙模拟（万亿级粒子）、气象预测、基因测序等。
充分利用并行硬件
现代处理器（CPU、GPU）本身就是高度并行的硬件。从多核CPU（如12核IBM Blade）到拥有数百甚至数千核心的GPU（如512核NVIDIA Fermi），如果不采用并行编程，这些硬件的巨大潜力将被浪费。
物理定律的推动——“摩尔定律”的终结
历史上，我们可以依赖摩尔定律 和**时钟频率 的提升来获得“免费”的性能增长。然而，大约从2005年开始，由于功耗墙 和散热 的限制，单纯提高CPU时钟频率变得不可持续。芯片设计的趋势转向了增加核心数量，即从“跑得更快”转向“跑得更多”。
1.3 并行计算在数据库领域的应用
并行查询 (DOP - Degree of Parallelism)：数据库通过将一个复杂的SQL查询（如扫描、连接、聚合）分解成多个子操作，分配给多个线程或进程并行执行，以加速分析类查询（OLAP）。openGauss 和 OceanBase 等现代数据库都深度支持并行查询，并提供了自动DOP（Auto DOP）功能，可以根据查询的成本和系统负载自动决定最佳并行度。HTAP：传统架构中，交易处理（OLTP）和分析处理（OLAP）通常由不同的系统处理，导致数据新鲜度低 。HTAP数据库旨在同一个系统内同时高效处理这两种负载。GPU加速数据库：利用GPU的大规模并行处理能力来加速数据密集型的分析查询，例如过滤、聚合和连接操作。通过将数据和计算任务卸载到GPU，可以获得相比纯CPU方案数量级的性能提升。
2.1 弗林分类法
这是1966年提出的一种经典的、基于指令流 和数据流对计算机体系结构进行分类的方法。
SISD (Single Instruction, Single Data)
描述：单指令流，单数据流。本质：传统的串行计算机。示例：早期的单核处理器。
SIMD (Single Instruction, Multiple Data)
描述：单指令流，多数据流 32。所有处理单元在同一时刻执行相同的指令，但处理的数据不同。本质：数据级并行 (Data-Level Parallelism)。示例：
GPU：图形处理器是SIMD架构的典型代表。向量处理器：CPU中的向量指令集，如SSE、AVX。例如，一条AVX指令可以同时对8个浮点数执行加法运算。
MISD (Multiple Instruction, Single Data)
描述：多指令流，单数据流。多个处理单元对同一个数据流执行不同的操作。本质：理论模型，在商业上非常罕见。
MIMD (Multiple Instruction, Multiple Data)
描述：多指令流，多数据流。每个处理器都可以独立执行不同的指令和处理不同的数据。本质：任务级并行 (Task-Level Parallelism)。示例：当今几乎所有的多核处理器和超级计算机集群都属于MIMD架构。这是最灵活也是最通用的并行架构。
2.2 存储系统分类
共享内存
所有处理器共享一个统一的物理地址空间。任何处理器都可以直接访问整个内存。
优点：
编程相对简单，因为数据共享是隐式的，程序员无需关心数据在何处。处理器间通信速度快，因为本质上是内存读写。
缺点：
可扩展性差：随着处理器数量增加，内存总线或互联网络会成为瓶颈，访问冲突加剧。需要复杂的缓存一致性协议来确保所有处理器看到的数据视图是一致的。
子分类：
UMA ：所有处理器访问任何内存位置的延迟是相同的。常见于对称多处理器（SMP）系统，如一台典型的多核服务器。
NUMA：物理内存被划分并附加到不同的处理器（或处理器组）上。处理器访问本地内存速度快，而访问远程内存（连接到其他处理器的内存）速度慢。NUMA是提升共享内存系统可扩展性的关键技术，常见于大型HPC服务器。
分布式内存
每个处理器都有自己私有的本地内存，地址空间不共享。
优点：
可扩展性好：可以通过网络连接成千上万个处理器节点。避免了共享内存的访问冲突和缓存一致性开销。
缺点：
编程复杂：程序员必须显式地通过网络发送和接收消息来管理数据通信。处理器间通信延迟远高于共享内存访问。
示例：大规模计算机集群、超级计算机、数据中心。
2.3 并行编程模型
1. 共享内存模型
单个进程可以有多个并行执行路径；
线程可以有局部数据，同时有共享资源；
线程之间通过异步地读写共享内存中的变量来进行通信；
线程可以被创建、销毁，但主线程一直在；
关键挑战：需要处理**竞争条件 **，即多个线程同时访问和修改同一块内存区域可能导致结果不确定。这通常通过锁、信号量等解决。
实现方式：
并行程序代码调用库函数；
#include
void print_message_function( void *ptr ){};
printf("Hello World\n");
int main()
{
pthread_t thread;
pthread_create(&thread, NULL,(void *) &print_message_function, NULL);
pthread_join(thread, NULL);
}
编译指导语句嵌入在串行/并行代码中；
如 OpenMP，程序员在代码中插入简单的#pragma指令，编译器会自动将指定的代码块（如循环）并行化。这种方式对原有串行代码的侵入性小，易于上手。
#include
int main() {
#pragma omp parallel
{
printf("Hello, World!\n");
}
}
2. 消息传递模型
任务（通常是进程）拥有各自的私有内存空间。它们之间通过显式地调用send()和recv()等函数来发送和接收消息进行通信。
MPI (Message Passing Interface) 是该模型的事实标准。它是一个库规范，定义了用于点对点通信（MPI_Send, MPI_Recv）和集体通信（MPI_Bcast, MPI_Reduce）等操作的API。!
特点：虽然最初为分布式内存系统设计，但MPI也可以高效地运行在共享内存机器上。
对比共享内存模型消息传递模型优点方便1.可以共享数据结构；2.通过loop实现3.和串行代码接近扩展性好1.局部性控制2.手工显示实现传输缺点1.局部性不可控2.可扩展性差3.访问冲突1.需要设计应用/数据结构2.代码复杂教授见解：选择哪种模型取决于问题特性和目标硬件。在单台多核服务器上，OpenMP是快速实现循环并行的绝佳选择。对于需要跨越多台机器的大规模计算，MPI几乎是唯一的选择。在现代HPC中，经常采用混合编程模型，即在节点间使用MPI进行通信，在节点内使用OpenMP或CUDA来利用多核/众核的计算能力。
3.1 性能衡量与基本定律
1. 加速比
加速比是衡量并行化效果的最核心指标。
Speedup(N)=TserialTparallel(N)
Speedup(N)=\frac{T_{serial}}{T_{parallel}(N)}
Speedup(N)=Tparallel(N)Tserial
其中，TserialT_{serial}Tserial是最优串行算法的执行时间，Tparallel(N)T_{parallel}(N)Tparallel(N)是使用N个处理器时并行算法的执行时间。
2.阿姆达尔定律
核心观点：并行计算的加速比受限于程序中无法并行化的串行部分的比例。
适用场景：固定问题规模。
Speedup(N)=1S+PN
Speedup(N)=\frac{1}{S+\frac{P}{N}}
Speedup(N)=S+NP1
其中，S是串行部分的比例，P是并行部分的比例（S+P=1），N是处理器数量。
推论：当 N→∞ 时，Speedupmax=1SSpeedup_{max}=\frac{1}{S}Speedupmax=S1。
启示：即使有无限的处理器，如果程序有10%的串行部分（S=0.1），最大加速比也无法超过10倍。因此，优化串行瓶颈至关重要。
3.古斯塔夫森定律
核心观点：对代码使用并行技术可以处理更大规模的问题.
适用场景：可扩展问题规模。
Speedup(N)=S+P×N=N−S×(N−1)
Speedup(N)=S+P×N=N−S×(N−1)
Speedup(N)=S+P×N=N−S×(N−1)
启示：对于可以扩展问题规模的应用（如科学模拟），只要串行部分的增长速度慢于问题规模的增长，我们就可以通过增加处理器数量获得近乎线性的加速比。这为大规模并行计算提供了理论支持。
3.2硬件性能极限理论值
1.最大浮点计算理论值
Intel Core i7-7920HQ，四核处理器，可达3.7GHz，单个处理器支持2个超线程，向量处理频率为8flop/周期，请问最大的浮点计算理论值(F)如何计算?
F=虚拟线程数×时钟频率×向量处理频率
F=虚拟线程数\times时钟频率\times向量处理频率
F=虚拟线程数×时钟频率×向量处理频率
计算虚拟核心数:
物理核心数：4个每个核心的超线程数：2个虚拟核心数 = 物理核心数 × 超线程数 = 4×2=8 个
确定时钟频率:
时钟频率：3.7 GHz，即 3.7×1093.7×10^93.7×109 Hz (次/秒)
确定向量处理频率:
向量处理频率：8 FLOPS/周期 (即每个时钟周期执行8次浮点运算)这里的“8 flop/周期”通常指在执行单精度 (32-bit) 浮点运算时的情况。因为该处理器支持AVX2指令集，其向量寄存器宽度为256位，可以同时处理8个单精度浮点数 (256÷32=8)。
代入公式计算:
F=8×(3.7×10910^9109 周期/秒)×(8 FLOPS/周期)F=236.8×10910^9109 FLOPSF=236.8 GFLOPS
因此，这颗 Intel Core i7-7920HQ 处理器的最大单精度浮点计算理论值为 236.8 GFLOPS (每秒 2368 亿次浮点运算)。
2.内存带宽的最大理论值
LPDDR3-2133内存(2133 MT/S)，双通道每次访问8个字节数，请问最大内存带宽理论值(B)如何计算?
B=数据传输速率×内存通道数×每次访问字节数×插槽数量
B=数据传输速率\times内存通道数\times每次访问字节数\times插槽数量
B=数据传输速率×内存通道数×每次访问字节数×插槽数量
2133×106×2×8×1=34128×106字节/秒=34.128 GB/秒
2133\times10^6\times2\times8\times1=34128\times10^6字节/秒=34.128\ GB/秒
2133×106×2×8×1=34128×106字节/秒=34.128 GB/秒
内存宽带最大理论值为34.128千兆字节/秒。
3.3 并行数据结构设计
结构数组 (AoS)
布局：[RGB], [RGB], [RGB], ...优点：有利于访问单个完整对象的所有属性。缺点：当并行处理某一特定属性（如所有R值）时，内存访问是不连续的，导致缓存效率低下和SIMD通道利用率不高。
数组结构 (SoA)
布局：[RRR...], [GGG...], [BBB...]优点：当并行处理同一属性时，内存访问是连续的，可以最大化内存带宽，完美匹配SIMD架构。缺点：访问单个完整对象的多个属性变得不方便。
结论：在高性能并行计算中，SoA通常是优选的数据布局，因为它更符合硬件的特性。
3.4 并行算法复杂度分析
并行算法的总执行时间 Tp 由两部分组成：计算时间 Tcomp 和通信时间 Tcomm 。
Tp=Tcomp+Tcomm
Tp=Tcomp+Tcomm
Tp=Tcomp+Tcomm
通信时间可以进一步建模为
Tcomm=q×(Tstartup+n×Tdata)
Tcomm=q×(Tstartup+n×Tdata)
Tcomm=q×(Tstartup+n×Tdata)
Tstartup：启动一次通信的延迟（网络延迟），通常是一个固定开销。
Tdata：传输单位数据的开销（网络带宽）。
n：消息的大小。
q：通信的次数。
教授见解：在并行算法设计中，最小化通信通常比优化计算更重要。因为 Tstartup 通常远大于 Tdata，所以减少通信的频率（即q） 比减少单次通信的数据量（即n）更为关键。应尽量设计能将计算和通信重叠的异步算法，以隐藏通信延迟。
例题一
例题二
3.5 成本最优算法
1.概念
**并行成本：**定义为并行执行时间 (Tp) 与所用处理器数量 (N) 的乘积，即求解一个问题的时间和使用单处理器求解问题的时间成比例。
Cost=Tp×N
Cost=Tp×N
Cost=Tp×N
成本最优 ：如果一个并行算法的成本与最优串行算法的执行时间 (Ts) 在同一数量级 (Big-O notation)，那么该并行算法就是成本最优的。
数学表达为：O(Tp)×N=O(Ts)O(Tp)×N=O(Ts)O(Tp)×N=O(Ts)。核心思想：一个成本最优的算法是高效的，它没有因为并行而引入过多的额外开销。并行系统所做的总工作量与高效的单处理器系统所做的工作量相当。
2.例题
基准：串行算法
解决问题的最优串行算法的执行时间为 Ts=O(NlogN)Ts=O(N\log N)Ts=O(NlogN)。这是判断并行算法是否“成本最优”的黄金标准。任何并行算法的成本都需要与 O(NlogN)O(N\log N)O(NlogN) 进行比较。
并行算法1：
执行时间 (Tp): O(logN)O(\log N)O(logN)。处理器数量 (N): NNN。成本计算:
Cost1=Tp×N=O(logN)×N=O(NlogN)Cost1=Tp×N=O(\log N)×N=O(N\log N)Cost1=Tp×N=O(logN)×N=O(NlogN)。
结论:
将计算出的成本 Cost1=O(NlogN)Cost1=O(N\log N)Cost1=O(NlogN) 与串行时间 Ts=O(NlogN)Ts=O(N\log N)Ts=O(NlogN) 进行比较。因为二者是同一数量级，所以并行算法1是成本最优的。
并行算法2：
执行时间 (Tp): O(1)O(1)O(1)，即常数时间。处理器数量 (N): N2N^2N2。成本计算:
Cost2=Tp×N=O(1)×N2=O(N2)Cost2=Tp×N=O(1)×N^2=O(N^2)Cost2=Tp×N=O(1)×N2=O(N2)。
结论:
将计算出的成本Cost2=O(N2)Cost2=O(N^2)Cost2=O(N2)与串行时间 Ts=O(NlogN)Ts=O(N\log N)Ts=O(NlogN) 进行比较。因为 O(N2)O(N^2)O(N2) 在渐近意义上远大于 O(NlogN)O(N\log N)O(NlogN)，所以该算法的成本远高于串行算法的工作量。因此，并行算法2不是成本最优的。
总结
这个例子清晰地表明：
并行算法1 虽然不是最快的，但它实现了高效的并行化。它在加速计算的同时，没有浪费计算资源。并行算法2 尽管执行时间最短，但它是通过“暴力”堆砌处理器实现的，效率极低，总计算成本过高，因此不是一个好的并行算法设计。
课后复习
Shared Memory 和Distributed Memory 特点是什么？NUMA和UMA有什么区别？
共享内存模型和消息传递模型的区别是什么？共享内存模型的两种常见的实现方法是什么？
为什么会有加速器的产生？（提示：一种常见的加速器叫GPU）
Linear array, Ring, Tree, Mesh, Torus, Hypercube拓扑结构的优缺点？适用于哪些场合？
### 1. 线性阵列 (Linear Array)
* **结构**: 节点以直线形式连接，首尾节点只有一个邻居，中间节点有两个。
* **优点**:
* 结构简单，易于实现和布线。
* 成本低，每个节点最多需要两个通信端口。
* **缺点**:
* 网络直径大 (N-1)，导致端到端通信延迟高。
* 可靠性差，任何一个连接中断都会导致网络分裂。
* 扩展性差，增加节点会线性增加最大通信延迟。
* **适用场合**: 非常适合流水线式（Pipeline）的计算任务，数据可以从一端顺序处理到另一端。
### 2. 环形 (Ring)
* **结构**: 在线性阵列的基础上将首尾节点连接起来，形成一个闭环。
* **优点**:
* 结构仍然简单，成本较低。
* 比线性阵列有更好的可靠性，因为节点间存在两条路径（顺时针和逆时针）。
* 网络直径减半 (N/2)，通信延迟有所改善。
* **缺点**:
* 扩展性仍然有限，网络直径随节点数线性增长。
* 对于大规模网络，通信延迟问题依然严重。
* **适用场合**: 历史上用于令牌环局域网，也适用于需要循环数据交换或轮询的算法。
### 3. 树形 (Tree)
* **结构**: 节点呈层级结构，有一个根节点，下分多个子节点。
* **优点**:
* 网络直径小（对数级别），通信延迟低。
* 非常适合具有层级特征的计算，如分治算法、广播和归约（Reduction）操作。
* **缺点**:
* 根节点和靠近根节点的上层连接容易成为通信瓶颈，所有跨子树的通信都必须经过它们。
* 靠近根节点的连接或节点如果失效，会对整个网络造成巨大影响，可靠性差。
* **适用场合**: 广播、聚合、搜索等分层级操作，以及具有主从（Master-Slave）结构的并行应用。
### 4. 网格 (Mesh)
* **结构**: 节点排列成二维或三维的网格，每个节点与其上下左右（及前后）的邻居连接。
* **优点**:
* 结构规整，非常适合模拟具有空间局部性的物理问题（如流体力学、气象模拟）。
* 节点间存在多条路径，可靠性优于简单拓扑。
* **缺点**:
* 边缘和角落的节点连接数少于内部节点，网络不对称。
* 网络直径相对较大，远距离通信延迟较高。
* **适用场合**: 科学与工程计算，如有限元分析、图像处理等在网格上进行计算的应用。
### 5. 环面 (Torus)
* **结构**: 在网格结构的基础上，将每一行和每一列的首尾节点连接起来，形成“卷绕式”连接。
* **优点**:
* 网络对称，所有节点的连接数相同，负载更均衡。
* 网络直径减半，平均通信延迟低于网格。
* 提供了更丰富的路径，可靠性更高。
* **缺点**:
* 布线比网格更复杂，成本更高，尤其是在三维或更高维度上。
* **适用场合**: 许多现代超级计算机的首选拓扑，适用于需要高性能、低延迟和均匀通信的通用并行计算。
### 6. 超立方体 (Hypercube)
* **结构**: N=2^k个节点分布在一个k维立方体的顶点上，如果两个节点的二进制编号只有一位不同，则它们之间存在连接。
* **优点**:
* 网络直径非常小（对数级别，k=log₂N），通信延迟极低。
* 连接性非常丰富，节点间路径多，拥塞少，可靠性极高。
* 能够很好地映射许多高效的并行算法（如快速傅里叶变换、排序）。
* **缺点**:
* 随着节点数增加，每个节点的连接端口数（度）也随之增加（k），导致硬件实现复杂且昂贵。
* 节点数必须是2的幂次方，限制了网络规模的灵活性。
* **适用场合**: 适合需要密集通信和低延迟的并行算法，在早期的并行计算机中非常流行。
假设串行程序的执行时间是10秒，通过使用4个计算核心使得程序执行时间降为了5秒，请问：程序的加速比是多少？系统效率是多少？
Speedup=TserialTparallel
Speedup=\frac{Tserial}{T_{parallel}}
Speedup=TparallelTserial
Efficiency=SpeedupN
Efficiency=\frac{Speedup}{N}
Efficiency=NSpeedup
在连接。
优点:
网络直径非常小（对数级别，k=log₂N），通信延迟极低。连接性非常丰富，节点间路径多，拥塞少，可靠性极高。能够很好地映射许多高效的并行算法（如快速傅里叶变换、排序）。
缺点:
随着节点数增加，每个节点的连接端口数（度）也随之增加（k），导致硬件实现复杂且昂贵。节点数必须是2的幂次方，限制了网络规模的灵活性。
适用场合: 适合需要密集通信和低延迟的并行算法，在早期的并行计算机中非常流行。
假设串行程序的执行时间是10秒，通过使用4个计算核心使得程序执行时间降为了5秒，请问：程序的加速比是多少？系统效率是多少？
Speedup=TserialTparallel
Speedup=\frac{Tserial}{T_{parallel}}
Speedup=TparallelTserial
Efficiency=SpeedupN
Efficiency=\frac{Speedup}{N}
Efficiency=NSpeedup