性能优化PPT8

Lecture 8 - Matrix–Matrix Multiplication

讲师：Anne Reinarz
主题：性能建模、内存访问、向量化优化等

---

Matrix–Matrix Multiplication

• 对于 n×n 的矩阵 A 和 B，计算 C = AB：

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        C[i*n + j] += A[i*n + k] * B[k*n + j]; // C和C++的二维矩阵可以用一维方式表示，所以要*n
  

---

Two-Level Memory Model

• m: 数据移动次数
• f: 浮点操作数
• tm: 内存访问时间
• tf ≪ tm: 浮点运算时间
• q = f/m: 每次慢速内存访问的平均 FLOPs

时间模型

• 最小时间：T_min = tf · f
• 典型时间：T_typical = f·tf (1 + (tm / tf) * (1/q))

---

Naive Matrix Multiply

• 三重循环实现
• 复杂度：O(n^3) flops
• 传输字节：3 * 8n^2
• 理论最优 q → n，但实际上是：

  m = n^3 + 3n^2
  q = 2n^3 / (n^3 + 3n^2) → 2
  

---

性能预测与建模

• 模型预测典型时间：

  T = f·tf (1 + tm / (2tf))
  

• 以 tf = 1, tm = 25 估算，T ≈ 13.5f·tf → 仅达到 7% 峰值性能

---

实测数据 (Example)

• 处理器支持：每周期 2 个 4-way FMA → 16 DP FLOPs/cycle 解释：
• 每个时钟周期，CPU 可以同时执行 2 个 宽度为 4 的 FMA 指令
• 每个 FMA 有 4 个元素（SIMD 向量）：4-way FMA = 对 4 个双精度（double precision）数做 FMA

• 每个 a * b + c 是 2 个 FLOPs,所以：2指令 × 4元素 × 2FLOPs = 16FLOPs/cycle

• 理论峰值：53.6 GFLOPs/s(计算方式：tf*f)
• 模型预测值：约 3.97 GFLOPs/s

---

提高数据重用：Block Matrix Multiply

• 将矩阵视为 N x N 的 b x b 块组成

• 三层循环外加块内循环共六重循环实现 block 矩阵乘法

• 数据移动降低为：

  m = 2n^2(N + 1), q ≈ n / N = b
  

• 限制条件：b 必须能放入 fast memory

---

机器特性与建模对比

• 若想达到 50% 峰值：

  q ≥ tm / tf
  

  例：tm = 25, tf = 1 → q ≥ 25，即 b ≈ 25

• 内存需求：3b² = 1875 doubles ≈ 14.6 KB

---

最优性理论

• Hong & Kung (1981)：最小数据移动为 Ω(n^3 / √M)
• 最优算法：GotoBLAS/OpenBLAS 采用分块、缓存优化等接近此下界

---

向量化 Vectorisation

向量操作形式

• Scalar: z = x + y
• Vector: z[i] = x[i] + y[i]

实现方式

• SIMD（大向量寄存器）
• SIMT（GPU Lockstepping）

---

向量寄存器扩展（x86 & ARM）

Arch	Extension	Width	float32	float64
SSE	128-bit	4	-
AVX	256-bit	8	4
AVX-512	512-bit	16	8
ARM SVE	128–2048-bit	4–64	2–32

---

编译器优化参数

• -march=native, -mavx2, -mavx512f 等
• 查看所有指令集支持：--help=target

---

向量化实践

1. 自动向量化（e.g. -fopt-info, -qopt-report）
2. 编译器指令如 #pragma ivdep, #pragma unroll
3. OpenMP SIMD 指令
4. 编译器内置函数（intrinsics）
5. 手写汇编

---

自动向量化要求

• 循环迭代数必须已知
• 不包含 break/continue/异常/函数调用
• 无 loop-carried 依赖
• 几乎无 if 语句
• 无嵌套循环

---

是否能向量化示例分析

• 示例：元素逐一相乘 → ✅
• 示例：转置式访问 → ✅
• 示例：带 if 或依赖前项计算 → ❌（loop-carried dependency）

---

指针别名问题（aliasing）

• 指针间可能别名，阻碍向量化

解决方法：

1. 使用 restrict 关键字（double * restrict）
2. 编译器参数 -fno-alias
3. 编译器内部多版本处理（运行时判断）

---

#pragma 指令示例

• #pragma GCC ivdep
• #pragma GCC unroll(<factor>)

提示：

• 使用 -fopenmp 时开启 OpenMP 向量指令
• 向量化需要内存连续

---