Courses

外观

性能模型：先判断哪里有机会，再增加并行度 ​

并行性能要回答两个不同问题：程序里有多少可同时执行的工作，以及硬件每秒能完成多少有效工作。Amdahl 与 work/span 讨论依赖和串行部分；Roofline 讨论运算与数据移动的上界。任何一个模型都不是实际计时的替代品。

Amdahl：串行部分限制总体加速 ​

设单处理器时间为 1，无法并行的比例为 s，其余部分理想分给 P 个处理器：

TP=s+1−sP,SP=1TP.

s=0.1、P=8 时，时间是 0.2125，加速约 4.706 倍；即使处理器无限多，上限也只有 10 倍。如果再增加线程创建、同步和通信开销 h，实际时间应加上 h，而不是仍用理想公式承诺速度。

这个公式针对固定工作负载。若增加机器的同时扩大问题规模，串行比例与任务结构也可能变化，应重新描述工作量，不能拿固定规模结论机械推断所有扩展场景。

work 与 span：关键路径决定下界 ​

把计算画成有向无环图，每个节点是一段不可再拆的工作，边表示依赖。work W 是所有节点工作的总量，span D 是最长依赖路径长度。在理想同速处理器模型中：

TP≥max(W/P,D),可利用并行度≈W/D.

例如 8 个各耗时 1 的独立任务，之后需要一个耗时 2 的汇总任务：W=10，D=3。4 个处理器即使完美安排，也要先用两个时间单位处理前 8 个任务，再花 2 汇总，总计 4；下界 max(2.5,3)=3 不保证可达到，它只是任何实现都不能违反的乐观界限。

flowchart LR
  S[开始] --> A[任务 A]
  S --> B[任务 B]
  S --> C[任务 C]
  S --> D[任务 D]
  A --> R[汇总]
  B --> R
  C --> R
  D --> R
  R --> E[结束]
查看流程图文本
flowchart LR
  S[开始] --> A[任务 A]
  S --> B[任务 B]
  S --> C[任务 C]
  S --> D[任务 D]
  A --> R[汇总]
  B --> R
  C --> R
  D --> R
  R --> E[结束]

减少 work 与减少 span 有时冲突。为了压短关键路径而重复计算，可能增加总体工作；并行归约将线性依赖链改成树，通常能把 span 从 O(N) 降为 O(log N)，同时保持 O(N) work，是很好的优化结构。

均匀分项不等于均匀分工 ​

仓库 benchmark 的前 1/4 项各执行 512 步，后 3/4 各执行 16 步。按每项一个单位计，平均工作约为 0.25×512+0.75×16=140 步。分给 4 个线程的连续等长区间后，最忙线程承担每总项 128 步的工作，其余线程各只承担 4 步。

忽略开销时，这种静态分法的加速上界约为 140/128=1.094，而不是 4。动态小块可以让后续空闲线程继续领取重区间的工作，降低最长线程负载，但每次领取又有原子竞争成本。这就是需要测量 grain 的原因。

Roofline：运算强度与带宽 ​

定义运算强度 I 为每移动一个字节所完成的运算量，必须明确字节在哪一层统计。以 DRAM 流量为例：

可达 FLOP/s≤min(计算峰值,内存带宽×I).

假设一台抽象机器有 100 GB/s 带宽，向量运算 y=a*x+y 每项约 2 FLOP、理想流量 12 字节，则 I≈1/6 FLOP/byte，对应带宽上界约 16.7 GFLOP/s。就算算术单元能达到 1 TFLOP/s，单纯增加乘加能力也无法突破这份数据流量限制。这里使用十进制 GB，且忽略缓存写策略等额外流量。

分块矩阵乘法通过复用 A/B tile 提高强度。一个 b×b tile 的理想运算约 2b³ FLOP，若只计算 A、B 读取和 C 写出，流量约 12b² 字节，I≈b/6。真实实现还要计算 C 累积、边界、缓存层次和容量限制，但这个估算解释了为何数据复用比盲目增加线程更关键。Roofline 原始技术报告

从模型到实验 ​

先写预测：该程序受关键路径、负载不均、调度开销还是内存流量限制？再设计只改变一个因素的实验：调整 P、grain、输入分布或布局。若预测失败，不应删除异常数据，而应检查模型漏掉了什么，例如线程迁移、频率变化、向量化、缓存工作集变化。

同时报告 speedup=T1/TP 与 efficiency=SP/P。效率较低不自动说明实现差：串行部分或带宽上界可能已经决定它；效率超过 1 也不自动违反物理规律，缓存容量变化或串行基线差异都可能造成超线性表现，需要解释基准条件。

自测：4 核时耗时 10 ms，8 核时 9 ms，下一步应直接尝试 16 核吗？

先检查各线程负载、同步时间、工作集与带宽。若临界路径或带宽已主导，增加核数可能作用很小。以证据选择下一步，而不是把核数当成唯一调节钮。

自测：work/span 下界为何不等于真实运行时间？

它忽略了有限任务粒度、调度、缓存、通信、处理器异质性等约束。它适合排除不可能的目标和比较算法依赖结构，不能替代实现测量。

课程对应：工作分配与调度。下一章：CPU、SIMD 与任务。