4. 循环交换（Loop Interchange）

任务目标

本案例通过一个矩阵乘法核心片段，演示循环交换（Loop Interchange）如何将内层循环的访存模式从“按列跳跃”改为“按行连续”，从而提升Cache命中率。你将看到同一逻辑的两种循环顺序，并验证它们在访存连续性上的差异。

核心原理与实现

矩阵按行存储时，A[i][k]的地址随k递增而连续。若内层循环遍历k，则每次迭代访问相邻内存地址，Cache行利用率高；反之若内层循环遍历i，则每次跳过一个完整行，造成Cache行浪费。以下代码提供两种版本：bad_access（内层循环跳行）与good_access（内层循环连续），两者计算完全相同的矩阵乘法结果，仅循环顺序不同。

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 512

// 内层循环遍历 i（跳行访问，Cache不友好）
void bad_access(double A[N][N], double B[N][N], double C[N][N]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            double sum = 0.0;
            for (int k = 0; k < N; k++)
                sum += A[i][k] * B[k][j];  // B按列访问，跳行
            C[i][j] = sum;
        }
}

// 内层循环遍历 k（连续访问，Cache友好）
void good_access(double A[N][N], double B[N][N], double C[N][N]) {
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++) {
            double r = A[i][k];
            for (int j = 0; j < N; j++)
                C[i][j] += r * B[k][j];  // B按行连续访问
        }
}

// 初始化矩阵（确定性填充，便于验证）
void init(double A[N][N], double B[N][N], double C[N][N]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            A[i][j] = (i + j) % 100;
            B[i][j] = (i * j) % 100;
            C[i][j] = 0.0;
        }
}

// 验证两个版本结果一致
int verify(double C1[N][N], double C2[N][N]) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (C1[i][j] != C2[i][j]) return 0;
    return 1;
}

int main() {
    static double A[N][N], B[N][N], C_bad[N][N], C_good[N][N];
    init(A, B, C_bad);
    init(A, B, C_good);

    clock_t t1 = clock();
    bad_access(A, B, C_bad);
    clock_t t2 = clock();
    good_access(A, B, C_good);
    clock_t t3 = clock();

    printf("bad_access 耗时: %.3f 秒\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
    printf("good_access 耗时: %.3f 秒\n", (double)(t3 - t2) / CLOCKS_PER_SEC);
    printf("结果一致: %s\n", verify(C_bad, C_good) ? "是" : "否");
    return 0;
}

运行与验证

1. 编译：gcc -O2 -o loop_interchange loop_interchange.c（-O2为必要优化，否则差异不明显）
2. 运行：./loop_interchange
3. 通过条件：输出中“结果一致: 是”，且good_access耗时明显低于bad_access（通常差距在2倍以上，具体数值取决于CPU与Cache大小）。

预期输出示例

bad_access 耗时: 0.312 秒
good_access 耗时: 0.098 秒
结果一致: 是

以上耗时仅为逻辑一致的示例，实际数值随硬件不同而变化；关键在于good_access显著更快且结果一致。

关键说明

• 本案例使用static数组避免栈溢出，N=512时两个版本各需约2MB数据，适合L2/L3 Cache演示。
• 若你的环境未显示明显差异，可增大N至1024（内存约8MB）或改用-O3编译。
• 循环交换的核心价值在于将内层循环映射到内存连续方向，本案例中good_access对B矩阵的访问从“列跳跃”变为“行连续”，这正是Cache友好的关键。