3. 缓存友好的矩阵转置

任务目标

实现一个按行主序存储的矩阵转置，通过分块（blocking）策略提升缓存局部性，并与朴素转置对比缓存未命中次数（使用Cachegrind模拟）。

核心实现

#include <vector>
#include <cstdint>

// 朴素转置：按列访问源矩阵，缓存不友好
void transpose_naive(const std::vector<float>& src,
                     std::vector<float>& dst,
                     int n) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dst[j * n + i] = src[i * n + j];
}

// 分块转置：块内行/列访问均连续，提升缓存命中
void transpose_blocked(const std::vector<float>& src,
                       std::vector<float>& dst,
                       int n, int block = 16) {
    for (int i0 = 0; i0 < n; i0 += block) {
        for (int j0 = 0; j0 < n; j0 += block) {
            int i_end = std::min(i0 + block, n);
            int j_end = std::min(j0 + block, n);
            for (int i = i0; i < i_end; ++i)
                for (int j = j0; j < j_end; ++j)
                    dst[j * n + i] = src[i * n + j];
        }
    }
}

验证与对比

// main.cpp —— 编译后配合valgrind/cachegrind统计缓存未命中
#include <cstdio>
#include <cstdlib>
#include <vector>

int main(int argc, char** argv) {
    int n = 1024;
    int mode = 0;  // 0=naive, 1=blocked
    if (argc > 1) n = atoi(argv[1]);
    if (argc > 2) mode = atoi(argv[2]);

    std::vector<float> src(n * n), dst(n * n);
    for (int i = 0; i < n * n; ++i) src[i] = static_cast<float>(i);

    if (mode == 0)
        transpose_naive(src, dst, n);
    else
        transpose_blocked(src, dst, n);

    // 正确性校验：转置后 dst[i*n+j] == src[j*n+i]
    bool ok = true;
    for (int i = 0; i < n && ok; ++i)
        for (int j = 0; j < n && ok; ++j)
            if (dst[i * n + j] != src[j * n + i]) ok = false;
    printf("n=%d mode=%d %s\n", n, mode, ok ? "PASS" : "FAIL");
    return ok ? 0 : 1;
}

编译与运行

g++ -O2 -std=c++11 main.cpp -o transpose
# 分别统计两种实现的缓存未命中
valgrind --tool=cachegrind ./transpose 1024 0   # 朴素
valgrind --tool=cachegrind ./transpose 1024 1   # 分块

判定标准

• 程序输出 PASS，说明转置结果正确。
• Cachegrind报告末尾的 D1 miss rate（一级数据缓存未命中率）中，分块版本应明显低于朴素版本（例如n=1024时通常可降低30%~60%）。
• 对比两个版本的 D1 miss rate 数值即可验证缓存优化效果。

关键说明

分块大小block取16~32通常效果较好，实际最优值取决于目标CPU的缓存行大小与L1容量。本案例仅演示优化方法与验证路径，不声称特定硬件上的实测数值。若需调整矩阵规模，直接修改命令行参数即可。