手写一个简单的 Tiling 策略：演示如何通过 L1/L2 缓存优化矩阵运算的访存局部性。

矩阵乘法（GEMM）是高性能计算中最基础且最核心的操作之一。然而，简单的三层循环实现（ijk顺序）往往效率低下，主要瓶颈在于CPU L1/L2缓存的频繁失效（Cache Miss）。这是因为在默认的行主序（Row-Major）存储中，访问矩阵 B 时，如果按列遍历，会导致巨大的步长，从而破坏了数据的空间局部性。

解决这个问题的高效策略之一是Tiling（或称Blocking，分块），它通过将大矩阵分解为适合缓存大小的小块（Tiles），确保在内部循环中所有必要的数据块都能常驻在L1/L2缓存中，从而最大化数据的复用率。

1. 基础矩阵乘法（ijk顺序）

假设我们计算 $C = A \times B$，所有矩阵大小均为 $N \times N$。

// 假设 N 很大，如 N=2048
// 循环顺序 i, j, k
void matrix_mul_basic(int N, const float* A, const float* B, float* C) {
    for (int i = 0; i < N; ++i) {          // 遍历 C 的行
        for (int j = 0; j < N; ++j) {      // 遍历 C 的列
            float sum = 0.0f;
            for (int k = 0; k < N; ++k) {  // 内部求和
                // 访问 A[i][k]：空间局部性好（A是行主序）
                // 访问 B[k][j]：空间局部性差（访问的是不同行相同列，步长为 N）
                sum += A[i * N + k] * B[k * N + j];
            }
            C[i * N + j] = sum;
        }
    }
}

2. Tiling 策略优化实现

Tiling 策略将原来的三层循环扩展为六层循环。外层三层循环负责遍历大块（Tiles），内层三层循环负责计算当前块内的乘法。

核心思想： 选择一个合适的块大小 BS（Block Size，通常设置为能容纳 $3 \times BS^2$ 个浮点数并在L1/L2缓存中的值，如32或64），在计算一个 $C_{ij}$ 块时，我们会反复使用 $A_{ik}$ 块和 $B_{kj}$ 块的数据，从而极大地提高了时间局部性。

// 假设 N=2048, 块大小 BS=64
#define BS 64 

void matrix_mul_tiled(int N, const float* A, const float* B, float* C) {
    // 外层循环：遍历块的坐标
    for (int ii = 0; ii < N; ii += BS) {        // 块行 (C, A)
        for (int jj = 0; jj < N; jj += BS) {      // 块列 (C, B)
            for (int kk = 0; kk < N; kk += BS) {    // 块深度 (A, B)

                // 内层循环：处理当前块 (BS x BS x BS)
                for (int i = ii; i < ii + BS && i < N; ++i) {
                    for (int j = jj; j < jj + BS && j < N; ++j) {
                        // 累计和初始化为 C[i][j] 的当前值
                        float sum = C[i * N + j]; 

                        for (int k = kk; k < kk + BS && k < N; ++k) {
                            // 在 BS x BS 的小范围内，A[i][k] 和 B[k][j] 都能保持在缓存中
                            sum += A[i * N + k] * B[k * N + j];
                        }
                        C[i * N + j] = sum;
                    }
                }
            }
        }
    }
}

3. 性能分析

通过 Tiling 策略，我们成功地将大矩阵操作分解成了更小的、对缓存友好的操作。

1. 时间局部性: 在最内层的 $i, j, k$ 循环中，由于迭代范围被限制在 $BS$ 内，我们对 $A_{ik}$ 块和 $B_{kj}$ 块的数据进行了高频、紧凑的重复使用，这显著提高了L1/L2缓存的命中率。
2. 空间局部性: 尽管 $B[k][j]$ 仍然是跨行访问，但由于 $k$ 的范围也被限制在 $BS$ 内，并且紧接着 $j$ 循环，使得数据块的访问更加紧凑，减少了缓存行被逐出的概率。

关键点： Tiling 策略的核心在于，当计算一个 $BS \times BS$ 大小的 C 块时，对应的 $A$ 块和 $B$ 块被加载进缓存并被充分利用 $BS$ 次，而不是像基础实现中那样，每次计算 $C[i][j]$ 都可能因为 $B[k][j]$ 访问而导致缓存失效。