Roofline 直观有效
Roofline 模型用一张图展示了算法性能的两个上限：计算峰值和带宽峰值。
CS267 · 第 3 课 · Jim Demmel
Roofline 模型为我们提供了一个直观的可视化工具，用于理解算法性能是受限于计算峰值还是内存带宽。
m = 在快/慢内存间移动的元素数
tm = 每次慢内存操作时间（带宽的倒数）
f = 算术操作数
tf = 每次算术操作时间 (<< tm)
CI = f / m = 计算强度 (Computational Intensity)
最小时间 = f × tf（所有数据在快内存）
实际时间 = f × tf + m × tm = f × tf × (1 + tm/tf × 1/CI)Machine Balance = Peak FLOPS / Peak Bandwidth
Exact（模型内的分界）：当 CI = Machine Balance 时，两条 Roofline 上界相交；它是 bandwidth-bound 与 compute-bound 的分界，不表示实现已经达到最佳效率。
\[CI = \frac{f}{m} = \frac{2n^3}{(2N+2) \cdot n^2} \approx \frac{n}{N} = b \text{ (大 n 时)}\]
\[b \leq \sqrt{M/3}\]
因为 M 必须容纳 3 个 b×b 块。
定理 (Hong & Kung, 1981)：
任何重组矩阵乘法的算法（仅使用交换律和结合律），其计算强度 \(q = O(M_{\text{fast}}^{1/2})\)。
因此：
\[\text{\#words\_moved} = \Omega(n^3 / M_{\text{fast}}^{1/2})\]
分块矩阵乘法达到了这个下界，因此是最优的（在常数因子内）。
扩展到 P 个处理器：
性能模型是一个估算性能的公式，可用于：
Roofline 模型由三个部分组成：
| 组件 | 描述 | 来源 |
|---|---|---|
| 算术性能 | 峰值浮点运算率 (FLOPS) | 机器 |
| 内存带宽 | 峰值内存带宽 (Bytes/sec) | 机器 |
| 计算强度 | FLOPs / Bytes（算术强度） | 应用/算法 |
可达性能 (Attainable Performance)：
\[P_{\text{attainable}} = \min\begin{cases} P_{\text{peak}} \\ CI \times B_{\text{peak}} \end{cases}\]
其中 \(P_{\text{peak}}\) 是峰值计算性能，\(B_{\text{peak}}\) 是峰值内存带宽。
Attainable GFLOP/s
^
| /-------------
| / ← 计算受限 (Compute Bound)
| /
| / ← 带宽受限 (Bandwidth Bound)
| /
|---/------------------->
0 Machine Balance Computational Intensity (FLOP/byte)
Hardware-specific：下表是课程材料中的平台示例，只能在指定精度、内存层级和峰值口径下使用。新硬件应重新用 (P_{peak}/B_{peak}) 计算，不能套用一个“典型 GPU”常数。
| 平台 | Machine Balance (FLOP/byte) |
|---|---|
| Haswell | 10 |
| KNL (to DRAM) | 34 |
| KNL (to HBM) | 7 |
| Perlmutter CPU | 12 |
| 具体 GPU | 按 precision、memory tier 与官方规格重新计算 |
#pragma omp parallel for
for(i = 0; i < N; i++) {
Z[i] = X[i] + alpha * Y[i];
}for x,y,z in 0 to n-1
Next[x,y,z] = C0 * Current[x,y,z] +
C1 * (Current[x-1,y,z] + Current[x+1,y,z] +
Current[x,y-1,z] + Current[x,y+1,z] +
Current[x,y,z-1] + Current[x,y,z+1]);无缓存时：8 FLOPs，8 个 double 引用 → CI = 8/64 = 0.125 FLOP/byte
Napkin-math approximation：若理想的空间复用让相邻点大多由 cache 命中，并且只按一次 DRAM 读入与一次 write-back 计数，则可近似为 1 读 1 写 → CI ≈ 8/16 = 0.5 FLOP/byte。真实流量还受 write allocate、边界、cache 容量与遍历顺序影响。
重要：常数因子很重要！虽然 stencil 的渐近 CI 是 O(1)，但常数决定了实际性能。
| 操作 | FLOPs | 数据 | CI |
|---|---|---|---|
| Dot Product | \(O(n)\) | \(O(n)\) | \(O(1)\) |
| Matrix-Vector (BLAS2) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) |
| Matrix-Matrix (BLAS3) | \(O(n^3)\) | \(O(n^2)\) | \(O(n)\) |
| N-Body | \(O(n^2)\) | \(O(n)\) | \(O(n)\) |
| FFT | \(O(n \log n)\) | \(O(n)\) | \(O(\log n)\) |
实际可达性能可能低于理论峰值：
可以为不同层次的内存构建多条 Roofline：
| 算法 | 指数 | 年份 |
|---|---|---|
| 传统 | 3.0 | - |
| Strassen | 2.81 | 1969 |
| Coppersmith & Winograd | 2.37548 | 1987 |
| V. Williams | 2.37286 | 2011 |
| Le Gall | 2.3728639 | 2014 |
| Alman & Williams | 2.3728596 | 2020 |
| Williams, Xu, Xu, Zhou | 2.371552 | 2024 |
注意：除 Strassen 外，其他"快速"算法需要极大的 n 才有优势，实际中很少使用。
Q1：Roofline 模型的可达性能公式是什么？
Q2：若 Machine Balance = 10 FLOP/byte，算法 CI = 2 FLOP/byte，该算法处于什么状态？
Q3：根据 Hong & Kung 定理，矩阵乘法的通信下界是什么？
Q4：3D 7-point stencil 在理想缓存下的 CI 是多少？
Q5：为什么除 Strassen 外，其他快速矩阵乘法算法很少使用？
Roofline 模型用一张图展示了算法性能的两个上限：计算峰值和带宽峰值。
它是特定硬件、精度与内存层级的比值；必须按目标平台重新计算，不能把历史示例当成普适常数。
通过分块、融合等技术提升计算强度，使算法从带宽受限转向计算受限。
Hong & Kung 定理证明了分块矩阵乘法在通信量上是最优的。