性能优化PPT7

📚 Session 6: Cache Blocking & Tiling

Anne Reinarz

---

🧮 Matrix Transpose (基础)

目标： 计算转置矩阵
给定两个 N×N 的矩阵 A 和 B，进行如下操作：

B[i*N + j] = A[j*N + i];

🔍 简单性能模型：

• N² 次存储（store）
• N² 次加载（load）
• 无计算操作

---

🧠 Loads vs. Stores

• 缓存局部性对 loads 和 stores 的影响不同：
  • Loads：提高 cache hit 率
  • Stores：涉及缓存一致性（cache coherence）与写入策略（writing policy）

🔗 参考资料：

• Cache coherence
• Writing policies
• Non-temporal stores

---

📊 性能数据：带宽 [GB/s]

Matrix Size	Bandwidth
128×128	22
256×256	13
512×512	13
1024×1024	5
2048×2048	1.6
4096×4096	0.9

📉 问题： A[j*N + i] 是 stride-N 访问，访问模式不利于缓存

---

📐 缓存局部性分析

• 行主序存储，cache line 大小为 L
• 读取 A 时使用的是跨行访问（stride-N）
• 想要充分利用 cache，需要进行访问重排

---

💡 改进思路：Block + Loop Reordering

核心方法：

1. Strip mining（分块遍历）
2. Loop reordering（重排迭代顺序）

---

🔧 Strip Mining 示例（单层循环）

for (int ii = 0; ii < N; ii += stride)
    for (int i = ii; i < min(N, ii + stride); i++)
        A[i] = f(i);

适用于嵌套循环，改善内存访问模式

---

🔁 Strip Mining 嵌套循环（原始 → 改进）

原始代码：

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        B[i*N + j] = A[j*N + i];

改进后：

for (int ii = 0; ii < N; ii += stridei)
    for (int i = ii; i < min(N, ii + stridei); i++)
        for (int jj = 0; jj < N; jj += stridej)
            for (int j = jj; j < min(N, jj + stridej); j++)
                B[i*N + j] = A[j*N + i];

---

🔁 Loop Reordering（进一步优化）

调换 i 和 jj 的顺序：

for (int ii = 0; ii < N; ii += stridei)
    for (int jj = 0; jj < N; jj += stridej)
        for (int i = ii; i < min(N, ii + stridei); i++)
            for (int j = jj; j < min(N, jj + stridej); j++)
                B[i*N + j] = A[j*N + i];

✅ 支持针对 L1/L2/L3 cache 调整 tile size
⚠️ 增加了一定的逻辑开销

---

📈 对比图示

• B 的迭代访问：before vs. after
• A 的迭代访问：before vs. after
• Tiled B vs. Tiled A 性能对比

---

🧪 Exercise 7: 实践 Tiled Matrix Transpose

1. 分组进行练习
2. 下载两个版本的代码
3. 测量不同矩阵大小下的带宽
4. 尝试不同的 tile size
5. 积极提问！