并行计算：从 SIMD 到 MPI / Parallel Computing from SIMD to MPI
并行不是“多开线程”。它要求算法有可分解的工作、数据有可承受的交换成本，并且每个计算资源持续有事可做。
并行化首先是依赖分析。两个任务只有在没有未满足的数据依赖，或依赖能够通过明确同步处理时，才能同时执行。把串行循环机械改成并行循环，可能产生数据竞争；即使结果正确，也可能因为任务太小、同步太频繁或内存带宽饱和而更慢。
统一成本模型
并行总时间
= 最长计算路径
+ 数据移动与通信
+ 同步和调度
+ 负载不均造成的空闲
+ 串行部分这个模型可以同时解释 SIMD、线程、GPU 与 MPI。SIMD 要求多份数据执行相近指令；CPU 线程共享地址空间，通信方便但会竞争缓存和锁；GPU 提供大量吞吐，却要求显式关注设备内存和规则执行；MPI 用消息连接独立进程，扩展到多机的同时也暴露网络延迟和数据划分成本。
从问题形状选择并行方式
规则数组变换通常适合 Map 和 SIMD，求和或统计适合 Reduce，前缀依赖适合 Scan，网格邻域计算常表现为 Stencil，不规则依赖则更接近任务图。模式决定了数据如何分片、局部结果如何合并，以及同步发生在哪里。先识别模式，再选择 OpenMP、线程池、CUDA 或 MPI，比从工具出发更可靠。
并行粒度必须足够大。任务执行只有几十纳秒时，创建任务、入队和同步的成本可能超过计算本身；GPU Kernel 若计算量太小，启动与传输会占主导；MPI 消息太碎会被网络延迟限制。常见改进是合并小任务、批处理传输、减少全局屏障，并让分区尽量均衡。
本目录的归档职责
本目录保存课程合并前的并行计算正文。 它用于追溯旧文章、旧链接、示例和术语，不是第二套独立演进的权威课程。
Historical parallel articles
-> preserve original explanation and examples
-> compare with current unified course
-> migrate verified details when needed
-> keep source traceability新内容和勘误优先进入当前权威课程。 历史正文只有在修复断链、安全问题或注明版本边界时才应修改。
原文集合的组织逻辑
原文从依赖和硬件开始，逐步进入编程模型、算法模式、性能和案例。
Foundations
-> Processor and Memory
-> CPU Parallelism
-> GPU Architecture
-> CUDA
-> Heterogeneous Systems
-> Distributed Memory
-> Patterns and Performance
-> Applications and Projects这个顺序仍然有价值，因为每一层都建立下一层的成本模型。
并行基础原文
基础文章关注三个问题：
- 工作能否拆分；
- 依赖形成多长关键路径；
- 并行开销是否小于节省的时间。
需要掌握 Work、Span、Speedup 和 Efficiency。
Speedup(P) = T1 / TP
Efficiency(P) = Speedup(P) / P这些公式只有在基线和工作量一致时才有意义。 如果并行版本更换算法或降低精度，需要单独说明。
处理器体系结构原文
处理器文章解释：
- 流水线；
- 乱序执行；
- 分支预测；
- 指令级并行；
- SIMD；
- 多核；
- Cache 与一致性；
- NUMA。
并行程序最终运行在具体硬件上。 线程数量和任务划分必须考虑执行宽度、内存层次和拓扑。
CPU 并行原文
CPU 部分连接语言并发与硬件行为。
核心主题包括：
- 线程生命周期；
- 线程池；
- 静态与动态调度；
- OpenMP；
- SIMD；
- 锁和原子；
- 伪共享；
- 负载均衡；
- 线程亲和性。
共享内存让通信容易，但也让数据竞争和隐藏依赖更危险。
内存层次原文
内存文章从数据位置解释性能。
Registers
-> L1 / L2 / LLC
-> Local DRAM
-> Remote NUMA Memory
-> Storage or Network算法需要估算实际字节流量，而不仅是算术次数。
规则连续访问更容易预取和向量化。 随机依赖访问更受延迟和 TLB 限制。
GPU 架构原文
GPU 通过大量线程隐藏延迟并追求吞吐。
需要理解：
- Grid、Block、Warp；
- SM 调度；
- 寄存器；
- 共享内存；
- 全局内存；
- 分支发散；
- 合并访问；
- Occupancy；
- Host/Device 互连。
GPU 的高峰值只有在工作规则、规模足够且数据供应匹配时才能利用。
CUDA 编程模型原文
CUDA 文章把算法映射为 Kernel 和线程层次。
host prepares data
-> copies or maps device input
-> launches kernels
-> synchronizes required results
-> copies output正确性需要检查索引、边界、同步和内存生命周期。 性能需要包含传输、启动和同步，不能只测 Kernel 内部。
并行算法模式原文
模式文章帮助从问题结构选择实现：
- Map；
- Reduce；
- Scan；
- Stencil；
- Histogram；
- Scatter/Gather；
- Pipeline；
- Task Graph；
- Producer/Consumer。
模式决定分区、局部状态、合并和同步位置。
异构计算原文
异构计算不是把全部代码移到 GPU。 它设计 CPU、GPU 和其他设备之间的职责与数据流。
适合 CPU 的工作包括复杂控制、操作系统交互和小任务。 适合 GPU 的工作包括规则、批量和高算术密度 Kernel。
边界应减少往返和细粒度同步。
分布式并行原文
分布式内存使用消息交换协作。
重点包括：
- 进程与 Communicator；
- 点对点通信；
- 集合通信；
- 域分解；
- Halo/Ghost；
- 消息延迟和带宽；
- 计算通信重叠；
- 故障与 Checkpoint。
小消息受延迟限制，大消息受带宽限制。 全局集合通信还可能受最慢进程和网络拓扑限制。
性能工程原文
性能文章建立测量闭环：
goal
-> workload
-> baseline
-> profile
-> hypothesis
-> minimal change
-> verify and guard regression并行性能报告需要：
- 串行基线；
- 输入规模；
- 核心、GPU 或节点数量；
- 初始化和传输；
- 加速比；
- 并行效率；
- 强扩展；
- 弱扩展；
- 正确性或数值容差；
- 原始样本。
应用案例原文
应用文章把模式映射到真实问题。
典型案例包括：
- 稠密与稀疏线性代数；
- 图像与信号处理；
- 粒子与 N-body；
- 网格 Stencil；
- CFD 通量和迭代；
- FEA 组装与求解；
- 图遍历；
- 数据分析；
- 深度学习训练；
- 分布式服务。
案例应说明为什么选择某种并行方式，以及数据移动和同步在哪里发生。
学习项目原文
项目用于把单个 API 知识连接成完整工程。
一个合格项目包含：
- 串行正确版本；
- 自动测试；
- 代表性数据；
- 至少一种并行实现；
- Profile；
- 扩展曲线；
- 资源指标；
- 失败和取消；
- 可复现构建；
- 结果报告。
项目不应只提交最终快代码。 推导、失败实验和适用边界同样重要。
与当前课程的映射
历史原文可能和当前课程使用不同编号或术语。
查阅顺序建议：
- 在当前课程确认概念定义；
- 在历史目录寻找旧案例和图示；
- 检查代码依赖版本；
- 核对链接和 API；
- 用标准或官方资料验证变化内容；
- 将仍有价值的细节补回权威文章。
不要在两个目录同时维护同一新结论。
历史内容的版本边界
以下内容容易过时：
- GPU 型号与峰值；
- CUDA Toolkit API；
- 编译器选项；
- MPI 实现和网络；
- 性能工具界面；
- 云实例和成本；
- 框架封装；
- 驱动要求。
引用时标注原环境和日期。 旧数据用于说明当时现象，不能直接代表当前硬件。
归档完整性
归档需要保持：
- 文件集合完整；
- 单文件内容完整；
- 代码块不截断；
- 图示不损坏；
- 来源提交可追溯；
- 原路径或重定向可用；
- 修改有明确说明。
归档不是只读神龛。 断链和安全问题可以修复，但不能悄悄把历史结论改成现代版本后仍称为原文。
查证命令
可以使用 Git 检查来源：
git show f2cdf30:path/to/original.md
git diff f2cdf30 -- path/to/original.md
git log --follow -- path/to/original.md查证时注意文件可能经过移动。 --follow 适合单文件历史，但复杂重组仍需结合提交查看。
阅读完成标准
读完本目录后，应能够：
- 解释并行上限来自依赖和成本；
- 区分 SIMD、线程、GPU 与 MPI；
- 画出数据分区和通信；
- 识别数据竞争与浮点差异；
- 设计强弱扩展实验；
- 区分历史事实与当前保证；
- 找到对应权威课程；
- 用 Git 验证原文来源。
分层路线
- 并行计算基础：速度上限与依赖分析。
- CPU 并行：线程、SIMD、Cache 一致性和 NUMA。
- CUDA 编程模型：线程、Block、Grid 与内存协作。
- 并行算法模式：Map、Reduce、Scan、Stencil 与任务图。
- 分布式并行：MPI、集合通信、RDMA 与多机多卡。
CPU/GPU 的具体硬件细节不在此重复；性能验证由性能工程专题统一负责。
正确性先于加速比
数据竞争、错误归约、浮点顺序变化和取消期间的资源释放，是并行程序常见问题。锁能保护共享状态，却可能形成竞争或死锁；无锁结构也不是自动更快，它需要严格的内存顺序和回收协议。浮点加法不满足结合律，并行归约可能产生与串行略有差异的结果，因此数值程序应定义误差容限，而不是只比较文本完全相等。
性能报告需要同时给出串行基线、输入规模、资源数量、加速比、并行效率和正确性验证。强扩展固定总问题规模，观察增加资源能缩短多少时间；弱扩展随资源增加问题规模，观察单位工作成本是否稳定。只展示最大规模或最好一次运行，无法证明方案可靠。
完成本路线后，应能画出任务依赖图和数据分区，估算串行部分与通信下限，为 CPU、GPU 或集群选择合适实现，并通过 Profile 区分计算不足、数据移动、同步和负载不均。