并行计算基础（北大《多核软件开发技术》第二讲）

北京大学吴中海《多核软件开发技术》课程第二讲讲义，系统梳理并行计算的体系结构、计算模型、编程范式与性能评测框架。属于典型的”并行计算入门地图”式讲义：概念覆盖面广，适合建立术语体系和知识索引。

并行计算机体系结构

三大组成部分：节点（多处理器，可直接输入输出）、互联网络（节点间通信）、内存（多存储模块，与节点对称分布在互联网络两侧，或位于节点内部）。

内存墙：微处理器峰值运算速度每 18 个月翻一番（摩尔定律节奏），内存容量每年几乎翻一番，但内存访问速度远跟不上处理器——这一失衡催生了多级存储体系结构。

模型	内存位置	访问特性
UMA（Uniform）	内存模块与节点分离，分居互联网络两侧	所有节点访问任意存储单元时间相同；仲裁平等；典型 SMP
NUMA（Non-Uniform）	内存模块分布在各节点内部	全局可共享直访，但本节点快、远程慢；仲裁可能不等价
COMA（Cache-Only）	无存储层次，全是缓存	分布式缓存目录；数据运行时迁移到要用它的地方
NORMA（No-Remote）	所有存储器私有	绝大多数不支持远程访存，即消息传递机群路线

SIMD 同步模型：共享存储版即 PRAM（容量无限共享存储器 + 无限功能相同处理器，任意时刻可经共享单元交换数据）；分布存储版按拓扑分一维线性/网孔/树/树网/立方/立方环/洗牌交换/多级互联等变体。
MIMD 异步模型：
- 异步 PRAM：各处理器有本地存储、局部时钟、局部程序，经共享全局存储器通信，时间依赖需显式加同步路障（barrier）。
- BSP 模型：计算由全局同步分开的”超级步”（superstep）序列组成，每步 = 局部计算 + 收发消息 + 全局完成检查，周期为 L。
- LogP 模型：分布存储点到点多处理机，网络用四参数刻画——L（延迟）、o（协议栈收发开销）、g（连续收发的最小间隔）、P（处理器/存储模块数）。这组参数是后来很多通信建模（如 LogGP、PLogP）的基础。
- C3 模型（Computation, Communication, Congestion）：体系结构无关的粗粒度模型，显式考虑网络链路拥塞与处理器拥塞。

进程四元组表示 (P, C, D, S)：程序代码、控制状态、数据、执行状态。
进程五状态：非存在 → 就绪 → 运行 ⇄ 挂起 → 退出。
进程间信息交流三形式：通信（数据传递）、同步（相互等待）、聚集（局部结果综合）。
通信性能三影响因素：通信硬件、通信软件（协议结构与算法）、通信服务（消息传送/流控/失效处理/保护）。BCL（基础通信库）是优化关键，三种代表实现：双拷贝、单拷贝、零拷贝——即经典的用户缓冲区拷贝次数优化路线（与今天 RDMA/zero-copy 网络栈一脉相承）。
线程 = 把进程拆成”资源特征”（仍叫进程）与”执行特征”（叫线程）；一个进程可由多线程并行执行并共享全部资源。

自动并行：源于 70 年代自动向量化，核心技术是依赖分析（判断同一数据结构的引用对是否命中同一存储单元）。
HPF：数据并行语言，用注释形式指令控制数组数据布局。
OpenMP：与 FORTRAN 77/C 绑定的非正式接口，单机编译器上当注释忽略——渐进式并行的经典设计。实践惯例：OpenMP 用于节点内、MPI 用于节点间的混合并行。

并行程序墙上时间 = 计算 CPU 时间 + 通信 CPU 时间 + 同步开销时间 + 进程空闲时间（阻塞等其他进程消息时的 CPU 空转）。

加速比 S = Ts/Tp；效率 E = S/p。讲义给出三大定律：Amdahl 定律（串行分量 f 封顶加速比）、Gustafson 定律（按问题规模缩放重估）、Sun-Ni 定律（存储空间允许就增大问题规模换取更好/更精确的解，即规模驱动的扩展视角）。
浮点峰值性能 = 浮点乘加流水线条数 × 每流水线每周期浮点运算次数 × 主频。
串行优化手段：调高性能库、编译器优化选项、合理定义数组维数（连续内存遍历顺序）、嵌套循环顺序、数据分块、循环展开、指令调度/分支预测。
并行优化手段：减少通信量、提高通信粒度、全局通信走高效集合通信、挖掘并行度减少空闲、负载平衡、通信-计算重叠。