并行计算：从 SIMD 到 MPI / Parallel Computing from SIMD to MPI

并行不是“多开线程”。它要求算法有可分解的工作、数据有可承受的交换成本，并且每个计算资源持续有事可做。

本目录保留原并行计算入口，以兼容已有链接；当前统一课程位于计算系统目录。即使作为兼容入口，本文仍提供独立的判断框架，让读者知道下一步该研究依赖、硬件、编程模型还是性能测量。

并行化的判断顺序

问题能否拆分？
  ├─不能 -> 先改变算法或接受串行下限
  └─能
     -> 子任务是否共享可变状态？
     -> 数据移动是否小于节省的计算？
     -> 任务粒度能否覆盖调度成本？
     -> 负载能否保持均衡？
     -> 用基准与 Profile 验证

第一步不是选择线程库，而是画出依赖。独立元素变换可以直接 Map，并行归约需要安全合并局部结果，前缀计算包含阶段依赖，图遍历则常需要动态任务和去重。依赖形式决定可以获得的并行度，也决定正确同步的位置。

四种常见执行层次

SIMD 在一个核心内用宽指令处理多个数据元素，开销低但要求访问和控制流规则。多核线程共享内存，适合中等粒度任务，但需要关注锁、伪共享、缓存一致性和 NUMA。GPU 用大量线程隐藏内存延迟，适合高吞吐数据并行；分支发散、随机访问和频繁主机传输会削弱收益。MPI 把工作分到独立进程乃至多台机器，通过显式消息交换扩展规模，同时把延迟、带宽和分区边界变成主要成本。

它们可以组合：单节点内使用 SIMD 和线程，节点内 GPU 执行 Kernel，节点间用 MPI 交换边界数据。组合层次越多，正确性、调试和性能归因越困难，因此应从最简单、能够达到目标的层次开始。

依赖图决定并行上限

把程序看成任务与依赖组成的有向无环图，可以区分总工作量与关键路径。

        A
       / \
      B   C
      |  / \
      D E   F
       \|  /
        G

所有任务耗时之和是 Work。 最长依赖路径是 Span，也叫 Critical Path。

即使处理器数量无限，完成时间也不能短于 Span。 可用并行度可以粗略理解为 Work / Span。

减少总工作量和缩短关键路径是两种不同优化。 把一个串行阶段拆成更多任务，只在依赖允许时缩短关键路径。

常见依赖包括：

• Read After Write：消费者必须等待生产者；
• Write After Read：写入不能破坏尚未完成的读取；
• Write After Write：多个写入顺序影响最终值；
• 控制依赖：是否执行后续任务取决于前面结果；
• 资源依赖：任务竞争同一锁、队列、设备或内存预算。

有些依赖是算法本身要求的。 有些只是当前数据结构和实现方式造成的伪依赖。

例如把所有线程结果写入一个全局容器，会制造锁竞争。 改为线程局部结果再合并，可以减少实现依赖，但归约阶段仍然存在。

并行粒度

任务粒度是单个调度单元包含的工作量。

粒度太细时，以下开销会占主导：

• 创建和销毁任务；
• 入队与出队；
• 原子计数；
• 调度和偷取；
• Cache 同步；
• GPU Kernel 启动；
• MPI 消息延迟。

粒度太粗时，资源数量不足或负载不均。 最后一个大任务会决定整体完成时间。

too fine:
[1][1][1][1][1][1][1][1]  scheduling dominates

too coarse:
[          40          ][2] one worker becomes tail

balanced:
[8][8][8][8][8][8]         enough work per task

合适粒度需要测量。 可以先估计任务开销，再让每个任务包含明显高于开销的工作量。

动态任务系统适合输入成本不规则的场景。 规则数组循环通常使用静态分块，减少调度开销。

数据分解与任务分解

数据分解把输入空间划分给不同执行资源。

典型方式包括：

• 一维连续区间；
• 二维或三维块；
• 图或网格分区；
• 按 Key 哈希；
• 按空间区域；
• 按时间窗口；
• 按模型层或算子。

任务分解则按功能阶段拆分，例如读取、解析、计算、压缩和写入。

Pipeline:
Read -> Parse -> Compute -> Encode -> Write

Data Parallel:
Chunk 0 -> Compute
Chunk 1 -> Compute
Chunk 2 -> Compute

两者可以组合成流水线加数据并行。 但阶段之间需要有界队列和背压，避免上游生产速度超过下游。

SIMD 与向量化

SIMD 用一条指令处理多个数据元素。 编译器自动向量化需要证明循环迭代之间没有危险依赖。

for (std::size_t i = 0; i < n; ++i) {
    output[i] = alpha * input[i] + output[i];
}

连续访问、简单控制流和明确别名信息有利于向量化。

阻碍因素包括：

• 指针可能别名；
• 不规则 Gather/Scatter；
• 数据相关分支；
• 循环携带依赖；
• 数据未对齐；
• 工作量太小；
• 函数调用无法内联。

向量化报告和汇编用于确认编译结果。 源码看起来像向量循环，不代表最终生成了宽指令。

CPU 多线程

共享内存线程可以直接访问同一地址空间，通信方便，但同步错误也更隐蔽。

线程池通常比每个任务创建新线程更稳定。 它复用线程并控制并发数量。

常见调度策略：

• 静态分块；
• 中央任务队列；
• 每线程本地队列；
• Work Stealing；
• 优先级队列；
• NUMA 感知队列。

中央队列简单，但高并发时可能形成锁和 Cache 热点。 Work Stealing 改善不规则负载，却增加队列和窃取开销。

线程数不应机械等于逻辑核心数。 CPU 密集、内存带宽受限和包含阻塞 I/O 的任务有不同最优并发。

内存模型与数据竞争

当两个线程并发访问同一内存位置，至少一个是写入且缺少同步时，会形成数据竞争。 在 C++ 中数据竞争导致未定义行为。

互斥锁建立临界区和 Happens-Before 关系。 原子操作只保护对应原子对象，不自动保护周围普通数据。

std::mutex mutex;
State state;

void update(Input value) {
    std::lock_guard lock(mutex);
    state.apply(value);
}

锁的正确性优先于“无锁看起来更快”。 无锁结构还要解决 ABA、内存顺序和安全回收。

Cache 一致性与伪共享

不同线程修改不同变量，如果变量位于同一 Cache Line，仍可能发生一致性抖动。

struct alignas(64) Counter {
    std::atomic<std::uint64_t> value{0};
};

填充或分片可以缓解伪共享，但对齐大小和收益需要在目标硬件测量。

只读共享数据通常容易扩展。 频繁写共享状态会增加一致性流量和串行化。

NUMA

多插槽系统中，内存相对于 CPU 节点有本地和远端之分。

典型首次触碰策略意味着首次写页面的线程影响物理放置。 单线程初始化后再让所有节点计算，可能让大部分访问变成远端。

NUMA 优化包括：

• 并行初始化；
• 固定线程亲和性；
• 按节点分片数据；
• 减少跨节点共享写；
• 必要时复制只读数据；
• 测量互连和远端访问。

绑核不自动更快。 它限制调度器选择，应只在稳定且拓扑敏感的工作负载中使用。

GPU 执行模型

GPU 通过大量线程隐藏延迟，适合规则且吞吐导向的数据并行。

Grid
  -> Blocks assigned to SMs
  -> Warps execute instructions
  -> Threads access registers, shared and global memory

Block 是调度和协作边界。 同一 Block 线程可以使用共享内存和同步，跨 Block 通常需要多个 Kernel 或特殊机制。

GPU 性能需要同时考虑：

• 并行线程数量；
• Warp 分支发散；
• 全局内存合并访问；
• 共享内存冲突；
• 寄存器和 Occupancy；
• Host 与 Device 传输；
• Kernel 启动；
• Stream 并发与同步。

Kernel 快不代表端到端任务快。 小任务可能完全被传输和启动成本覆盖。

MPI 与分布式内存

MPI 进程拥有独立地址空间，通过消息交换协作。

点对点通信需要匹配发送方、接收方、Tag 和 Communicator。 集合通信表达 Broadcast、Reduce、Allreduce 和 Alltoall 等常见模式。

Domain Partition
  -> local compute
  -> exchange halo
  -> synchronize required dependencies
  -> next iteration

网络延迟惩罚小消息，带宽限制大消息。 常见优化是合并消息、重叠计算通信、减少全局同步和改善分区边界。

非阻塞调用不保证通信已经与计算重叠。 实现、缓冲区生命周期和后续等待位置都会影响实际行为。

常见并行模式

• Map：独立转换每个元素；
• Reduce：把局部结果合并为一个值；
• Scan：生成前缀结果；
• Stencil：访问规则邻域；
• Histogram：聚合到有限桶；
• Scatter/Gather：不规则读写；
• Pipeline：阶段并发；
• Task Graph：按依赖调度；
• Producer/Consumer：通过有界队列解耦；
• Bulk Synchronous：计算与通信分阶段。

识别模式能帮助选择数据布局、同步和编程模型。

浮点与确定性

浮点加法不满足结合律。 并行归约改变运算顺序，结果可能与串行略有差异。

数值程序需要定义合理容差和守恒检查。 逐位相等可能过严，无限放宽容差又会掩盖错误。

若业务要求可重复结果，可以固定归约树、使用更高精度累加或采用补偿求和。 这些措施会增加成本，需要明确权衡。

死锁与活锁

多个锁顺序不一致可能死锁。 MPI 双方都等待对方发送也会死锁。

统一锁顺序、作用域锁和结构化通信可以降低风险。 超时适合诊断，不能自动恢复已经破坏的共享状态。

活锁中线程持续重试却没有进展。 退避、随机化和公平队列用于改善竞争。

性能验证

报告并行性能时至少包含：

• 可靠串行基线；
• 输入规模和分布；
• 资源数量与拓扑；
• 初始化、传输和计算分项；
• 加速比；
• 并行效率；
• 强扩展与弱扩展；
• 正确性或数值误差；
• 峰值内存和通信量；
• 原始样本和统计方法。

Profile 需要区分计算、数据移动、同步、排队和空闲。 增加资源后总时间不降，应先定位是哪类成本增长。

分层路线

1. 并行计算基础：速度上限与依赖分析。
2. CPU 并行：线程、SIMD、Cache 一致性和 NUMA。
3. CUDA 编程模型：线程、Block、Grid 与内存协作。
4. 并行算法模式：Map、Reduce、Scan、Stencil 与任务图。
5. 分布式并行：MPI、集合通信、RDMA 与多机多卡。

CPU/GPU 的具体硬件细节不在此重复；性能验证由性能工程专题统一负责。

如何评价并行结果

加速比等于可靠串行基线时间除以并行时间。效率还要除以资源数量，用于判断增加的核心或 GPU 是否真正贡献工作。Amdahl 定律提醒固定问题中的串行比例形成上限，Gustafson 视角则说明扩大问题规模可能继续利用更多资源。两者都不能替代实际测量，因为内存带宽、通信和负载不均会引入模型之外的开销。

测量时固定输入、构建参数和线程亲和性，区分初始化、数据传输与稳态计算，重复运行并报告分布。并行结果还要通过测试或数值容差验证；一个产生错误答案的“十倍加速”没有意义。

本入口适合建立全景和定位旧链接。系统学习应转到计算系统中的权威文章，再进入性能工程完成“测量—假设—优化—回归”的闭环。

实践时至少完成一次串行基线、一次共享内存并行和一次数据移动分析，并保存可复现命令。这样才能把并行 API 的使用，转化为对依赖、粒度、局部性与扩展效率的工程判断。