缓存优化

概述

缓存优化（Cache Optimization / Cache-Oblivious Algorithm）是设计对缓存层次结构友好的算法的技术。核心思想是通过分块（tiling/blocking）使数据重用最大化，减少缓存未命中。Cache-Oblivious 算法更进一步：不依赖缓存参数（大小、行大小），自动适应任意层级的缓存。经典应用包括分块矩阵乘法、缓存无关矩阵转置和扫描算法。

定义

形式化定义

缓存无关模型（Cache-Oblivious Model）由 Frigo、Leiserson、Prokop 和 Ramachandran 于 1999 年提出。模型假设：

• 机器具有两层存储：快缓存（容量 $Z$，行大小 $L$）和慢内存（容量无限）
• 算法不知道 $Z$ 和 $L$ 的具体值（这是”无关”的含义）
• 缓存采用理想替换策略（如 OPT/Belady 策略）

算法的缓存复杂度用缓存未命中次数（cache miss count）衡量。一个缓存无关算法在任何缓存参数下都能自动达到接近最优的缓存性能。

核心技术：分块（Tiling / Blocking）

分块是将大问题分解为适合放入缓存的小块，逐块处理以最大化数据重用：

矩阵乘法的分块：计算 $C=A\times B$ 时，将矩阵分为 $B\times B$ 的子块，逐块计算：

$C[i_B][j_B]+=A[i_B][k_B]\times B[k_B][j_B]$

其中 $i_B,j_B,k_B$ 为块索引，块大小 $B$ 的选择使得 $3B^2$ 个元素能放入缓存。

分块后，每个块被加载到缓存后可被重用 $B$ 次，缓存未命中从 $O(n^3/L)$ 降至 $O(n^3/(L\sqrt{Z}))$。

核心性质

性质	描述
自动适应性	缓存无关算法不依赖缓存参数，自动适应任意缓存层级
层次优化	对 L1、L2、L3 缓存同时有效，无需针对每层单独调优
可移植性	同一算法在不同硬件平台上都能获得良好的缓存性能
理论最优	缓存无关算法的缓存复杂度可达理论最优（相差常数倍）
分块是关键	分块（tiling）是缓存优化最核心的技术手段

缓存无关 vs 缓存感知：

维度	缓存感知（Cache-Aware）	缓存无关（Cache-Oblivious）
缓存参数	需要知道 $Z$、$L$	不需要知道
可移植性	差（换硬件需重新调参）	好（自动适应）
多级缓存	需针对每层单独优化	自动适应所有层级
实际性能	通常略优（可精确调参）	接近最优（常数倍差距）

应用场景

缓存优化在计算密集型任务中有广泛应用：

• 矩阵乘法的分块算法：标准矩阵乘法 $O(n^3)$ 的缓存无关版本，递归地将矩阵分为 4 个子矩阵分别相乘，缓存未命中 $O(n^3/L\sqrt{Z})$
• 矩阵转置：缓存无关的矩阵转置通过递归分块实现，将缓存未命中从 $O(n^2)$ 降至 $O(n^2/L)$
• 扫描算法：对数组进行前缀和等扫描运算的缓存无关实现，复杂度 $O(n/L)$
• 排序：缓存无关的归并排序（funnel sort），缓存复杂度 $O((n/L){\log }_{Z}n)$
• LU 分解：缓存无关的 LU 分解是 LAPACK 等数值库的重要优化方向

参见

• BLAS — 高效 BLAS 实现利用缓存层次结构的核心技术
• 并行计算模型 — 缓存优化在并行计算中的重要性
• 替换论证 — Belady 缓存替换策略最优性的证明方法
• PRAM模型 — 并行计算的理论模型（忽略缓存层次结构）
• 矩阵 — 缓存优化的主要应用对象