数据移动是瓶颈
性能损失主要来自数据移动而非计算。Load/Store 的开销是算术操作的 ~100x。
CS267 · 第 2 课 · Jim Demmel
大多数应用程序只发挥了峰值性能的不到 10%——损失的性能主要花在数据移动上。理解内存层次结构是释放硬件潜力的关键。
核心观点：并行化慢速串行代码只会产生慢速并行代码。
矩阵乘法的例子：通过串行优化（向量化、缓存优化等）可以在单核上获得 131x 加速。10 倍的串行优化收益很常见。
最初的理想化假设：
实际上，内存访问有两个成本：
移动 \(n\) 个连续字的时间：\(\alpha + n\beta\)
关键数值：
处理器频率: 1 GHz → 1 周期 = 1 ns
内存延迟: ~100 ns（加载/存储 1 个字）
Load/Store ≈ 100x 算术操作的开销编译器执行的关键优化：
程序具有高度的局部性：
| 层级 | 速度 | 大小 |
|---|---|---|
| Registers | 1 ns | ~1000 bytes |
| L1 Cache | 1-2 ns | 32-64 KB |
| L2 Cache | 3-10 ns | 256 KB - 1 MB |
| L3 Cache | 10-30 ns | 数 MB - 数十 MB |
| Main Memory (DRAM) | 100 ns | 数 GB - 数 TB |
| Disk/SSD | 10 ms / 100 μs | 数 TB |
来自排队论：\(\text{concurrency} = \text{latency} \times \text{bandwidth}\)
示例：延迟 = 10 ns，带宽 = 2 GB/s → 需要 20 字节在途才能达到带宽速度
这意味着需要找到 20 个独立操作来隐藏延迟。
以 Patterson 的"洗衣服"为例：
任务: 洗衣服
洗衣: 30 min
烘干: 40 min
折叠: 20 min
总延迟: 90 min
4 批衣服:
串行: 4 × 90 = 360 min
流水线: 30 + 4×40 + 20 = 210 min (≈ 1.7x 加速)
峰值带宽: 1/40 min = 1.5 loads/hour单指令多数据：一条指令同时处理多个数据元素。
| SIMD 扩展 | 寄存器宽度 | 双精度数 | 单精度数 |
|---|---|---|---|
| SSE2 | 128 bits | 2 | 4 |
| AVX | 256 bits | 4 | 8 |
| AVX-512 | 512 bits | 8 | 16 |
使用 SIMD 的要求：
乘加操作 \(x = y + c \times z\) 极其常见。FMA 指令：
假设只有两级内存（快/慢）：
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 → 典型值 5-10 Flops/Byte
{实现 y = y + A*x}
for i = 1:n
for j = 1:n
y(i) = y(i) + A(i,j)*x(j)分析：
{实现 C = C + A*B}
for i = 1 to n
for j = 1 to n
for k = 1 to n
C(i,j) = C(i,j) + A(i,k) * B(k,j)分析：
将 A, B, C 视为 N×N 个 b×b 子块的矩阵，块大小 \(b = n/N\)：
for i = 1 to N
for j = 1 to N
{将 C(i,j) 读入快内存}
for k = 1 to N
{将 A(i,k) 读入快内存}
{将 B(k,j) 读入快内存}
C(i,j) = C(i,j) + A(i,k) * B(k,j) {块矩阵乘法}
{将 C(i,j) 写回慢内存}分析（假设 3 个 b×b 块能放入快内存）：
关键洞察：CI 从 O(2) 提升到 O(b)。若 \(b\) 足够大，CI 可以接近 Machine Balance，使计算受限而非带宽受限。
递归矩阵乘法不需要知道缓存大小：
C = RMM(A, B, n)
if n == 1: C = A * B
else:
C00 = RMM(A00, B00, n/2) + RMM(A01, B10, n/2)
C01 = RMM(A00, B01, n/2) + RMM(A01, B11, n/2)
C10 = RMM(A10, B00, n/2) + RMM(A11, B10, n/2)
C11 = RMM(A11, B01, n/2) + RMM(A11, B11, n/2)内存移动分析：
\[W(n) = 8 \cdot W(n/2) + 4 \cdot 3(n/2)^2 \text{ if } 3n^2 > M_{\text{fast}}\]
\[W(n) = O(n^3 / M_{\text{fast}}^{1/2} + n^2)\]
优点：不需要知道 \(M_{\text{fast}}\) 即可工作，自动适应任意深度的内存层次。
ATLAS (Automatically Tuned Linear Algebra Software)：
| BLAS 级别 | 操作 | CI |
|---|---|---|
| BLAS1 (1970s) | 向量-向量 (dot, saxpy) | ~1 |
| BLAS2 (1980s) | 矩阵-向量 (matvec) | ~2 |
| BLAS3 (1980s) | 矩阵-矩阵 (matmul) | O(n) |
结论：尽可能使用 BLAS3 操作以获得最佳性能。
传统算法：\(O(n^3)\) 次乘法。Strassen：\(O(n^{\log_2 7}) \approx O(n^{2.81})\)。
2x2 矩阵乘法:
传统: 8 次乘法 + 4 次加法
Strassen: 7 次乘法 + 18 次加法
p1 = (a12 - a22) * (b21 + b22)
p2 = (a11 + a22) * (b11 + b22)
p3 = (a11 - a21) * (b11 + b12)
p4 = (a11 + a12) * b22
p5 = a11 * (b12 - b22)
p6 = a22 * (b21 - b11)
p7 = (a21 + a22) * b11
m11 = p1 + p2 - p4 + p6
m12 = p4 + p5
m21 = p6 + p7
m22 = p2 - p3 + p5 - p7Q1：朴素矩阵乘法的计算强度（CI）约为多少？
Q2：分块矩阵乘法中，若快内存大小为 M，最优块大小 b 是多少？
Q3：Cache-Oblivious 算法的主要优点是什么？
Q4：根据 Little 定律，若内存延迟为 100ns，带宽为 100 GB/s，需要多少数据在途才能充分利用带宽？
Q5：为什么 BLAS3 比 BLAS2 更快？
性能损失主要来自数据移动而非计算。Load/Store 的开销是算术操作的 ~100x。
CI = f/m，衡量每次内存访问的算术操作数。CI 越高，越接近计算峰值。
矩阵乘法的 CI 从 O(2) 提升到 O(b)，通过分块使 CI 接近 Machine Balance。
BLAS/LAPACK 经过高度优化，手写代码很难超越。优先使用库函数。