文章目录：
  1. Part1 Cache模拟器实现
    1. 题目
        1. 题目描述
          1. 1、读入文件（memory trace）格式
          2. 2、Cache使用方法
          3. 3、输出格式
        2. 输入输出样例
    2. 思路
    3. 题解代码
  2. Part2 矩阵转置优化
    1. 题目
        1. 题目描述
          1. 题目一：16 x 16 矩阵转置优化（5分）
          2. 题目二：32 x 32 矩阵转置优化（5分）
        2. 输入输出样例
    2. 理解题意与预备工作
      1. 题目要干什么
      2. 安装使用WSL
    3. 解题
      1. 16*16矩阵
      2. 32*32矩阵
    4. 总结

image-20251207114642868

才发现是CSAPP的实验，网上很多教程
推荐：https://zhuanlan.zhihu.com/p/79058089

但是网上的教程和北航的实验有一点点差别，Cache大小从1KB变成了512B。

Part1 Cache模拟器实现

题目

在本节中，我们将完成一个Cache模拟器，它通过读取memory trace（内存访问记录文件），模拟访问内存的过程，并且给出每条访问记录在Cache中的命中/缺失情况。本实验只需要补全csim.c文件中的内容，提交评测也只需提交该文件。

题目描述

我们要求实现的Cache模拟器需要满足的功能详情描述如下。

1、读入文件（memory trace）格式

我们实现的Cache模拟器将从文本文件中逐行读取内存访问记录，每一条记录代表了一次内存相关操作。为了评测方便，内存访问记录的格式与valgrind（一个强大的程序内存检测工具，后文会有介绍）的输出格式相同，具体格式如下：

[space]<operation> <address>,<size>

memory trace示例：

I 0400d7d4,8
 M 0421c7f0,4
 L 04f6b868,8
 S 7ff0005c8,8
2、Cache使用方法
./csim [-hv] -s <s> -E <E> -b <b> -t <tracefile>

我们的Cache程序需要完成以下操作：

3、输出格式

  1. 基本输出格式

    hits:<hits> misses:<misses> evictions:<evictions>

    其中hits，misses，evictions分别表示Cache的命中数，缺失数和替换数。可参见cachelab.c中的printSummary函数，只需在主程序运行结束时调用该函数，即可完成基本的结果输出。

  2. 输出详细trace信息

    如果命令参数中有-v，那么需要在基本输出之前，输出对应的详细trace信息，具体输出格式如下（请注意空格与以下示例保持一致）。

    <operation> <address>,<size> [hit] [miss] [eviction]

    其中<operation>表示操作类型，<address>表示地址，<size>表示大小（具体含义参见对读入文件格式的描述），该部分输出与每行读入的信息保持一致即可（注意：*输出<address>和<size>时去掉前导0*）。

    对于描述信息，hit表示命中，miss表示缺失，eviction表示替换，当出现对应情况的时候就需要输出对应字符串。请注意，描述信息的输出需要按顺序判断，即应先判断是输出hit还是miss，再判断是否输出eviction（注意：I类型指令该部分分析可忽略，只需原样输出<operation>，<address>和<size>）。

    特别地，对于M类型指令，应当先输出Load对应的hit，miss，eviction情况，再输出Store对应的hit，miss，eviction情况，即对应以下的格式：

    <operation> <address>,<size> [hit] [miss] [eviction] [hit] [miss] [eviction]

    比如Load时未命中且发生替换，那么应当先输出miss，eviction，之后Store命中再输出hit。

在评测时，我们将对同学们实现的Cache读入内存访问记录，并将输出与标准输出进行比对，通过所有测试点即可通过本节实验（5分）。

输入输出样例

内存访问记录文件yi.trace

 L 10,1
 M 20,1
 L 22,1
 S 18,1
 L 110,1
 L 210,1
 M 12,1

输入命令

./csim -v -s 4 -E 1 -b 4 -t traces/yi.trace

输出结果

L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3

思路

首先去学习一下命令行参数的使用方法，使用getopt方法读取，第一步肯定是读取命令行参数，把几种参数有没有/值读进来，这里存到了一个Operation结构体里。

第二步，需要根据读到的命令行内容初始化Cache，题目需要自己定义数据结构去存储。Cache块是最基础单位，需要定义一个结构体（这里定义为CacheLine）存储tag、valid有效位、timestamp（LRU计数器）。用多维数组表述Cache结构，即一个组（定义为*CacheSet）有E块，总共有$2^S$个组（定义为总的**Cache）。这一部分即我代码里的initCache函数。

第三步，读取文件输入，根据每一条命令完成操作。首先如果命令行带-v需要输出指令详细信息，就原样输出文件输入就行。接着，首先读取每个命令的类型，其中取指的I指令不需要任何处理，直接跳过；因为这个题不涉及到真正的数据读取/修改，所以剩下几种指令本质上没有区别，都是在访问Cache，只是M指令多访问一次。

访问Cache步骤：解析文件输入的地址，解析出其中的组号（Set = (addr >> op->b) - (Tag << op->s);）和Tag。首先尝试匹配是否命中，对于这个组的每一个元素遍历一遍，判断Tag是否相等以及有效位即可。如果命中则输出Hit，不命中继续尝试加入到Cache。首先遍历一遍看看有没有有效位为0的，说明是空的块，直接加入即可。如果还没有，则尝试根据LRU规则替换，遍历出时间戳最大的一个即可。三种结果都需要根据LRU规则更新时间戳。

全部访问完成之后，调用给定的printSummary函数输出最终信息。

另外，makefile的使用：使用make指令生成所有可执行文件，使用make xxx可以生成xxx.c的可执行文件。Lab里故意强制不能忽略Warning，所以要处理所有警告，最常见是定义的变量未使用。

题解代码

#include <stdio.h>
#include <getopt.h>
#include <stdlib.h>
#include <string.h>
#include "cachelaba.h"

// 命令行结构
typedef struct {
    int h; // help
    int v; // 是否详细信息
    unsigned int s; // 2的s次方组数
    unsigned int E; // 每组块数
    unsigned int b; // 2的b次方块大小
    const char* t; // 跟踪文件名
}Operation;

// Cache块
typedef struct {
    unsigned long long tag;
    int valid;
    unsigned long long timestamp;
} CacheLine, *CacheSet, **Cache;

Cache cache = NULL;
int miss_cnt, hit_cnt, alter_cnt;

// 解析命令行参数
int parseArgs(int argc, char *argv[], Operation *op) {
    int opt;
    while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
        switch (opt) {
            case 'h':
                op->h = 1;
                return 0;
            case 'v':
                op->v = 1;
                break;
            case 's':
                op->s = atoi(optarg);
                break;
            case 'E':
                op->E = atoi(optarg);
                break;
            case 'b':
                op->b = atoi(optarg);
                break;
            case 't':
                op->t = optarg;
                break;
            default:
                return -1;
        }
    }
    return 1;
}

// 初始化cache
void initCache(Operation *op) {
    unsigned long long S = 1ULL << op->s;
    int E = op->E;
    cache = (Cache)malloc(S * sizeof(CacheSet));
    for (unsigned long long i = 0; i < S; i++) {
        cache[i] = (CacheSet)malloc(E * sizeof(CacheLine));
        for (int j = 0; j < E; j++) {
            cache[i][j].valid = 0;
            cache[i][j].tag = 0;
            cache[i][j].timestamp = 0;
        }
    }
    return ;
}

// 进行cache操作
void operate(unsigned long long addr, Operation *op){
    unsigned long long Tag = addr >> (op->s + op->b);
    unsigned long long Set = (addr >> op->b) - (Tag << op->s);

    for(int i = 0; i < op->E; i++){
        if(cache[Set][i].tag == Tag && cache[Set][i].valid == 1){\
            int tmp = cache[Set][i].timestamp;
            for(int j = 0; j < op->E; j++){
                if(cache[Set][j].timestamp < tmp) cache[Set][j].timestamp++;
            }
            cache[Set][i].timestamp = 0;
            hit_cnt++;
            if(op->v == 1) printf(" hit");
            return ;
        }
    }

    miss_cnt++;
    if(op->v == 1) printf(" miss");

    for(int i = 0; i < op->E; i++){
        if(cache[Set][i].valid == 0){
            cache[Set][i].valid = 1;
            for(int j = 0; j < op->E; j++){
                cache[Set][j].timestamp++;
            }
            cache[Set][i].timestamp = 0;
            cache[Set][i].tag = Tag;
            return ;
        }
    }

    alter_cnt++;
    if(op->v == 1) printf(" eviction");

    int maxid = 0;
    unsigned long long max = 0;
    for(int i = 0; i < op->E; i++){
        if(cache[Set][i].timestamp > max){
            max = cache[Set][i].timestamp;
            maxid = i;
        }
    }
    cache[Set][maxid].timestamp = 0;
    cache[Set][maxid].tag = Tag;
    for(int i = 0; i < op->E; i++){
        if(i==maxid) continue;
        cache[Set][i].timestamp++;
    }
    return;
}


// 处理文件输入
void processTrace(Operation *op){
    FILE *f = fopen(op->t, "r");
    char opt;
    unsigned long long addr;
    int size;

    while(fscanf(f, " %c %llx,%d", &opt, &addr, &size) != EOF){
        if(op->v == 1) printf("%c %llx,%d", opt, addr, size);
        switch (opt){
            case 'I':
                break;
            case 'L':
                operate(addr, op);
                break;
            case 'M':
                operate(addr, op);
            case 'S':
                operate(addr, op);
                break;
            default:
                break;
        }
        if(op->v == 1) printf("\n");
    }

    fclose(f);
}

int main(int argc, char *argv[])
{
    Operation op = {0, 0, 0, 0, 0, NULL};
    if(parseArgs(argc, argv, &op) == -1){
        fprintf(stderr, "Invalid arguments\n");
        return -1;
    }
    initCache(&op);
    processTrace(&op);
    printSummary(hit_cnt, miss_cnt, alter_cnt);
    return 0;
}

Part2 矩阵转置优化

题目

在本节中，我们将给出特定大小的矩阵，请同学们应用分块等优化思想，利用我们在实验一中实现的Cache模拟器，检验不同的分块策略对Cache命中/缺失情况的影响，并通过逐步优化使得miss（即缺失数）尽可能低。本实验只需要补全trans.c中的内容，提交评测也只需提交该文件。

题目描述

给定Cache结构为：s=4,E=1,b=5 。

考察trans.c中的矩阵转置函数transpose_submit，该函数要实现矩阵转置的功能，将N行M列矩阵A转置为M行N列的矩阵B。本节实验包含两个题目，我们分别给出矩阵的M和N，并要求根据Cache的结构和矩阵的结构，计算出一个比较好的矩阵转置方案，使得miss数量达到要求。

在完成转置功能以外，代码还需满足以下要求：

以上的代码要求会在评测后进行统一检查，如不满足以上要求则视为未通过本实验。

本节的评测逻辑较为复杂，我们将根据实现的矩阵转置函数transpose_submit，模拟生成该函数执行过程中对应的memory trace，并通过参考Cache程序csim-ref来模拟内存访问的情况，最终通过Cache得出miss数量，miss数量达到要求即可通过本节实验。

具体分值设置如下：

题目一：16 x 16 矩阵转置优化（5分）
等级miss情况得分预期判定结果
正确验证转置结果无误1Wrong Answer
基础要求miss < 2003Wrong Answer
通过要求miss < 1005Accepted
优秀挑战miss < 755Excellent
题目二：32 x 32 矩阵转置优化（5分）
等级miss情况得分预期判定结果
正确验证转置结果无误1Wrong Answer
基础要求miss < 6003Wrong Answer
通过要求miss < 4005Accepted
优秀挑战miss < 3005Excellent
输入输出样例

输入命令

./test-trans -M 16 -N 16

输出结果

Function 0 (1 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=4, E=1, b=5)
...

Summary for official submission (func 0): correctness=1 misses=67

TEST_TRANS_RESULTS=1:67

得到TEST_TRANS_RESULTS=1:67，即miss为67，达到通过要求。

理解题意与预备工作

题目要干什么

这个题开始我看了半天没明白是要干什么，具体怎么与Cache结合的，以及怎么访问Cache。

直接Ask GPT，以下为问答：

User：

所以这个题我需要考虑怎么模拟cache吗，到底是怎么访问Cache的。比如我这个代码，是直接统计代码底层怎么访问Cache的吗：

for(i = 0; i < N; i++){
    for(j = 0; j < M; j++){
        tmp0 = A[i][j];
        B[j][i] = tmp0;
    }
}

ChatGPT:

你只要写普通的 C 代码（像你贴的这个 for 循环），驱动程序会自动根据“你实际访问的内存地址”去统计 cache miss。

老师给了你一个 driver（driver.c + cachelab.c + trans.c），它会做大概这样的事情：

  1. 创建一个矩阵 A、一个空矩阵 B；
  2. 调用你写的 transpose_submit(M, N, A, B)；
  3. 在你这个函数运行的同时，记录你对内存的读写（访问 A、访问 B），生成一个 trace 文件；
  4. 把这个 trace 文件丢给你 Part A 的 cache 模拟器，让它算“在 512B、32B block、direct-mapped 的 cache 上，这些访问产生了多少 miss”；
  5. 打印结果、算成绩。

所以：你在 Part B 只负责写转置函数，不负责模拟 cache

这样就可以理解了，这道题不需要考虑具体怎么实现Cache、调用Cache，只需要正常地写一个C语言转置函数，完成转置的工作，并且不断地优化这个转置函数，减少Cache的miss率。

根据trans.c函数，这个模拟的Cache结构（s=4,E=1,b=5）：

我们不需要考虑怎么调用这个Cache，结构只是给我们用来参考，参考如何在这上面减少miss。

为了理解题目究竟是怎么得到输出的，可以直接把下面的代码复制进函数里，尝试运行：

for(i = 0; i < N; i++){
    for(j = 0; j < M; j++){
        tmp0 = A[i][j];
        B[j][i] = tmp0;
    }
}

然后，然后就发现可能直接报错了。⬇️

安装使用WSL

这个题目这里必须要安装WSL环境，要不然本地没法跑。在Windows下跑会报错：

PS C:\...\cache实验代码\cachelab>  make test-trans
gcc -g -Wall -Werror -std=c99 -m64 -O0 -c transreg.c
gcc -g -Wall -Werror -std=c99 -m64 -O0 -c trans.c
gcc -g -Wall -Werror -std=c99 -m64 -o test-trans test-trans.c cachelab.c transreg.o trans.o
test-trans.c:15:10: fatal error: sys/wait.h: No such file or directory
 #include <sys/wait.h> // fir WEXITSTATUS
          ^~~~~~~~~~~~
compilation terminated.
make: *** [test-trans] 错误 1

安装WSL完成之后，在WSL里面可以先切换到管理员权限：

sudo su

更新apt以及安装工具：

sudo apt update
sudo apt install build-essential make valgrind

访问cachelab所在目录，不能直接访问windows地址，需要变成mnt/c/User/...。

cd /mnt/c/Users/lixu/OneDrive/桌面/cache实验代码/cachelab
# 参考我的windows目录: C:\Users\lixu\OneDrive\桌面\cache实验代码\cachelab

然后直接make就可以了：

make

然后MMD我又报错了：

transreg.o:transreg.c:(.pdata+0x0): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x4): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x8): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0xc): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x10): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x14): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x18): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x1c): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
transreg.o:transreg.c:(.pdata+0x20): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
trans.o:trans.c:(.pdata+0x0): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
trans.o:trans.c:(.pdata+0x4): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
trans.o:trans.c:(.pdata+0x8): dangerous relocation: R_AMD64_IMAGEBASE with __ImageBase undefined
collect2: error: ld returned 1 exit status
make: *** [Makefile:14: test-trans]

查阅AI发现可能是因为我在windows编译过，产生了.o文件，Linux下链接了Windows下产生的文件，两种格式混在一起了，链接器直接懵了。

解决办法：

rm -f *.o test-trans
# or
make clean

然后，终于编译成功了（哭死）：

root@Legion-Y7000P:/mnt/c/Users/lixu/OneDrive/桌面/cache实验代码/cachelab# make test-trans
gcc -g -Wall -Werror -std=c99 -m64 -O0 -c transreg.c
gcc -g -Wall -Werror -std=c99 -m64 -O0 -c trans.c
gcc -g -Wall -Werror -std=c99 -m64 -o test-trans test-trans.c cachelab.c transreg.o trans.o

首先先试试我们刚才写的直接转置。

./test-trans -M 16 -N 16

发现：

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=4, E=1, b=5)
func 0 (Transpose submission): hits:211, misses:306, evictions:290

直接转置miss有300+。

解题

建议直接交到judge上跑，比本地快多了

自己画了一下图，感觉更加理解这道题整个逻辑了（尤其是冲突以及分块策略），见最下面。

之后就是处理如何优化了。建议直接看看别人的博客。

核心是分块，首先要明确每个分块的大小。

对转置来说：

  • 当前 A 的一个 b×b 小块；
  • 当前 B 的一个 b×b 小块；
  • 再加上一点别的东西（栈、代码等）。

大致要求是：

A 块 + B 块 的大小 远小于 cache 容量

对 int 来说，一个元素 4B，b×b 块就是 4 * b² 字节。加上A，两个块就是 8 * b² 字节。

如果 cache 是 512B，那：

8 * b² <= 512   →   b² <= 64   →   b <= 8

就可以选取b=8。

实在懒得写了。。。直接贴一下我的方法进化历程：

提醒：这个实验和网上的cachelab有亿点点区别，网上的cache为1KB，这个只有512B，尤其是32*32里面很多策略行不通。

16*16矩阵

第一版：直接正常的一个一个遍历地进行转置。

for(i = 0; i < N; i++){
 for(j = 0; j < M; j++){
     tmp0 = A[i][j];
     B[j][i] = tmp0;
 }
}

第二版：学会了分块的方法，按照块先进行遍历，再对块里面的一个一个遍历转置。

if(M == 16){ //16x16 matrix
    for(i = 0; i < N; i+=8){
        for(j = 0; j < M; j+=8){
            for(ii = i; ii < i+8; ii++){
                for(jj = j; jj < j+8; jj++){
                    tmp0 = A[jj][ii];B[ii][jj] = tmp0;
                }
            }
        }
    }
}

第三版：因为给了12个局部变量，所以在块里面，可以一次读一行（8个），一次性放到B里面。这一版的miss约80多。

if(M == 16){ //16x16 matrix
    for(i = 0; i < N; i+=8){
        for(j = 0; j < M; j+=8){
            for(ii = 0; ii < 8; ii++){
                e0 = A[i + ii][j];
                e1 = A[i + ii][j + 1];
                e2 = A[i + ii][j + 2];
                e3 = A[i + ii][j + 3];
                e4 = A[i + ii][j + 4];
                e5 = A[i + ii][j + 5];
                e6 = A[i + ii][j + 6];
                e7 = A[i + ii][j + 7];

                B[j][i + ii] = e0;
                B[j + 1][i + ii] = e1;
                B[j + 2][i + ii] = e2;
                B[j + 3][i + ii] = e3;
                B[j + 4][i + ii] = e4;
                B[j + 5][i + ii] = e5;
                B[j + 6][i + ii] = e6;
                B[j + 7][i + ii] = e7;
            }
        }
    }
}

第四版：考虑对角块，使用不同的策略。非对角块不变；对角块先读到B里面，再对B里面进行转置。这样做的原因是对角块容易把A、B映射在一起（见最下面总结）。

for(i = 0; i < N; i+=8){
    for(j = 0; j < M; j+=8){
        if(i != j){ // 对于非对角块
            for(ii = 0; ii < 8; ii++){
                e0 = A[i + ii][j];
                e1 = A[i + ii][j + 1];
                e2 = A[i + ii][j + 2];
                e3 = A[i + ii][j + 3];
                e4 = A[i + ii][j + 4];
                e5 = A[i + ii][j + 5];
                e6 = A[i + ii][j + 6];
                e7 = A[i + ii][j + 7];

                B[j][i + ii] = e0;
                B[j + 1][i + ii] = e1;
                B[j + 2][i + ii] = e2;
                B[j + 3][i + ii] = e3;
                B[j + 4][i + ii] = e4;
                B[j + 5][i + ii] = e5;
                B[j + 6][i + ii] = e6;
                B[j + 7][i + ii] = e7;
            }
        }else{ // 处理对角块
            for(ii = 0; ii < 8; ii++){
                e0 = A[i + ii][j];
                e1 = A[i + ii][j + 1];
                e2 = A[i + ii][j + 2];
                e3 = A[i + ii][j + 3];
                e4 = A[i + ii][j + 4];
                e5 = A[i + ii][j + 5];
                e6 = A[i + ii][j + 6];
                e7 = A[i + ii][j + 7];

                B[i + ii][j] = e0;
                B[i + ii][j + 1] = e1;
                B[i + ii][j + 2] = e2;
                B[i + ii][j + 3] = e3;
                B[i + ii][j + 4] = e4;
                B[i + ii][j + 5] = e5;
                B[i + ii][j + 6] = e6;
                B[i + ii][j + 7] = e7;
            }
            for (ii = i; ii < i+8; ii++) {
                for (jj = j; jj < j+8; jj++) {
                    if(ii >= jj) continue;
                    e0 = B[jj][ii];
                    e1 = B[ii][jj];
                    B[ii][jj] = e0;
                    B[jj][ii] = e1;
                }
            }
        }
    }
}

32*32矩阵

./test-trans -M 32 -N 32

第一版：直接使用原来的方案（8*8加对角块优化），misses会很大，居然有1000多，原因也可以看最下面总结。

第二版：借鉴了cache lab中64*64的实现方法，达到miss数335，想一晚上也没再优化下去（直到第二天早上才想到更优的办法）。这个方法是借助B来暂时存储一些数据。

else if(M == 32) {
        for(i = 0; i < 32; i += 8) {
            for(j = 0; j < 32; j += 8) {
                for(ii = i; ii < i + 4; ii++) {
                    e0 = A[ii][j];
                    e1 = A[ii][j + 1];
                    e2 = A[ii][j + 2];
                    e3 = A[ii][j + 3];
                    e4 = A[ii][j + 4];
                    e5 = A[ii][j + 5];
                    e6 = A[ii][j + 6];
                    e7 = A[ii][j + 7];

                    B[j][ii] = e0;
                    B[j + 1][ii] = e1;
                    B[j + 2][ii] = e2;
                    B[j + 3][ii] = e3;
                    B[j][ii + 4] = e4;
                    B[j + 1][ii + 4] = e5;
                    B[j + 2][ii + 4] = e6;
                    B[j + 3][ii + 4] = e7;
                }

                for(ii = j; ii < j + 4; ii++) {
                    e0 = A[i + 4][ii];
                    e1 = A[i + 5][ii];
                    e2 = A[i + 6][ii];
                    e3 = A[i + 7][ii];
                    e4 = B[ii][i + 4];
                    e5 = B[ii][i + 5];
                    e6 = B[ii][i + 6];
                    e7 = B[ii][i + 7];

                    B[ii][i + 4] = e0;
                    B[ii][i + 5] = e1;
                    B[ii][i + 6] = e2;
                    B[ii][i + 7] = e3;
                    B[ii + 4][i] = e4;
                    B[ii + 4][i + 1] = e5;
                    B[ii + 4][i + 2] = e6;
                    B[ii + 4][i + 3] = e7;
                }

                for(ii = i + 4; ii < i + 8; ii++) {
                    e0 = A[ii][j + 4];
                    e1 = A[ii][j + 5];
                    e2 = A[ii][j + 6];
                    e3 = A[ii][j + 7];

                    B[j + 4][ii] = e0;
                    B[j + 5][ii] = e1;
                    B[j + 6][ii] = e2;
                    B[j + 7][ii] = e3;
                }
            }
        }
    }

第三版：自己写的逆天版本，本来一位应该比上面强，结果还是335。后来自己仔细算了一下上面的算法，发现上面的算法在非对角块是没有冲突miss的，和我这个是一样的。所以我白写了...

未来块以及顺序：

B_RB_CA_RA_C辅助B_R辅助B_C
0000原来方法
0880016
016160024
024240816
8008816
8888原来方法
816168824
824248160
160016168
1688161624
16161616原来方法
16242416240
240024248
2488242416
24161624原来方法
24242424原来方法 
else if (M == 32) {

        for (j = 0; j < 32; j += 8) {
            for (i = 0; i < 32; i += 8) { 

                if ((i == 0  && j == 0)  ||
                    (i == 8  && j == 8)  ||
                    (i == 16 && j == 16) ||
                    (i == 16 && j == 24) ||
                    (i == 24 && j == 24)) {

                    for (ii = i; ii < i + 4; ii++) {
                        e0 = A[ii][j];
                        e1 = A[ii][j + 1];
                        e2 = A[ii][j + 2];
                        e3 = A[ii][j + 3];
                        e4 = A[ii][j + 4];
                        e5 = A[ii][j + 5];
                        e6 = A[ii][j + 6];
                        e7 = A[ii][j + 7];

                        B[j][ii]     = e0;
                        B[j + 1][ii] = e1;
                        B[j + 2][ii] = e2;
                        B[j + 3][ii] = e3;
                        B[j][ii + 4]     = e4;
                        B[j + 1][ii + 4] = e5;
                        B[j + 2][ii + 4] = e6;
                        B[j + 3][ii + 4] = e7;
                    }

                    for (ii = j; ii < j + 4; ii++) {
                        e0 = A[i + 4][ii];
                        e1 = A[i + 5][ii];
                        e2 = A[i + 6][ii];
                        e3 = A[i + 7][ii];
                        e4 = B[ii][i + 4];
                        e5 = B[ii][i + 5];
                        e6 = B[ii][i + 6];
                        e7 = B[ii][i + 7];

                        B[ii][i + 4] = e0;
                        B[ii][i + 5] = e1;
                        B[ii][i + 6] = e2;
                        B[ii][i + 7] = e3;
                        B[ii + 4][i]     = e4;
                        B[ii + 4][i + 1] = e5;
                        B[ii + 4][i + 2] = e6;
                        B[ii + 4][i + 3] = e7;
                    }

                    for (ii = i + 4; ii < i + 8; ii++) {
                        e0 = A[ii][j + 4];
                        e1 = A[ii][j + 5];
                        e2 = A[ii][j + 6];
                        e3 = A[ii][j + 7];

                        B[j + 4][ii] = e0;
                        B[j + 5][ii] = e1;
                        B[j + 6][ii] = e2;
                        B[j + 7][ii] = e3;
                    }
                }
                else {

                    if (i == 8  && j == 0)  { e2 = 0;  e3 = 16; } // A(8,0)   → B(0,8)，  辅助 B(0,16)
                    else if (i == 16 && j == 0)  { e2 = 0;  e3 = 24; } // A(16,0)  → B(0,16)， 辅助 B(0,24)
                    else if (i == 24 && j == 0)  { e2 = 8;  e3 = 16; } // A(24,0)  → B(0,24)， 辅助 B(8,16)
                    else if (i == 0  && j == 8)  { e2 = 8;  e3 = 16; } // A(0,8)   → B(8,0)，  辅助 B(8,16)
                    else if (i == 16 && j == 8)  { e2 = 8;  e3 = 24; } // A(16,8)  → B(8,16)， 辅助 B(8,24)
                    else if (i == 24 && j == 8)  { e2 = 16; e3 = 0;  } // A(24,8)  → B(8,24)， 辅助 B(16,0)
                    else if (i == 0  && j == 16) { e2 = 16; e3 = 8;  } // A(0,16)  → B(16,0)， 辅助 B(16,8)
                    else if (i == 8  && j == 16) { e2 = 16; e3 = 24; } // A(8,16)  → B(16,8)， 辅助 B(16,24)
                    else if (i == 24 && j == 16) { e2 = 24; e3 = 0;  } // A(24,16) → B(16,24)，辅助 B(24,0)
                    else if (i == 0  && j == 24) { e2 = 24; e3 = 8;  } // A(0,24)  → B(24,0)， 辅助 B(24,8)
                    else if (i == 8  && j == 24) { e2 = 24; e3 = 16; } // A(8,24)  → B(24,8)， 辅助 B(24,16)
                    
                    
                    /* 1) B00 = A00^T */
                    for (ii = 0; ii < 4; ++ii) {
                        for (jj = 0; jj < 4; ++jj) {
                            B[j + jj][i + ii] = A[i + ii][j + jj];
                        }
                    }

                    /* 2) C00 = A01^T  （辅助块上左 4x4） */
                    for (ii = 0; ii < 4; ++ii) {
                        for (jj = 0; jj < 4; ++jj) {
                            B[e2 + jj][e3 + ii] = A[i + ii][j + 4 + jj];
                        }
                    }

                    /* 3) B01 = A10^T  （B 块上右 4x4） */
                    for (ii = 0; ii < 4; ++ii) {
                        for (jj = 0; jj < 4; ++jj) {
                            B[j + jj][i + 4 + ii] = A[i + 4 + ii][j + jj];
                        }
                    }

                    /* 4) C01 = A11^T  （辅助块上右 4x4） */
                    for (ii = 0; ii < 4; ++ii) {
                        for (jj = 0; jj < 4; ++jj) {
                            B[e2 + jj][e3 + 4 + ii] = A[i + 4 + ii][j + 4 + jj];
                        }
                    }

                    /* 5) 把 C00 复制到 B10（B 块下左 4x4） */
                    for (ii = 0; ii < 4; ++ii) {
                        for (jj = 0; jj < 4; ++jj) {
                            B[j + 4 + jj][i + ii] = B[e2 + jj][e3 + ii];
                        }
                    }

                    /* 6) 把 C01 复制到 B11（B 块下右 4x4） */
                    for (ii = 0; ii < 4; ++ii) {
                        for (jj = 0; jj < 4; ++jj) {
                            B[j + 4 + jj][i + 4 + ii] = B[e2 + jj][e3 + 4 + ii];
                        }
                    }
                }
            }
        }
    }

第四版：直接Excellent，达到259的misses（理论最小值），也就是没有任何冲突。

刚才的版本发现，原本的二三版算法都是在对角块上存在冲突，非对角块没有任何冲突。那么就可以用类似第三版的“未来块”算法优化对角块（上一个版本没管对角块，是因为对角块需要两个“未来块”才可以优化，所以懒了一下）。

首先，整个的遍历顺序为按列读，即最外层循环从左到右，内层循环从上到下。这种遍历方法是为了让B接下来的几个块都划分到不同的Cache行里。

但是，为了保证本来的最后一个块（右下角的对角块）有“未来块”，所以我让每次读每列时，都先访问对角块，再从上到下遍历非对角块。

非对角块仍然使用上面第二版的代码。对角块处理逻辑如下：

对于4个对角块，分别给出每种两个“未来块”的映射（此时$j == i$），如下（其中$(j, e_0)$是未来块C的最左上角，$(j,e_1)$是未来块D的最左上角）：

if(j == 0) e0 = 8, e1 = 16;
else if(j == 8) e0 = 0, e1 = 16;
else e0 = 0, e1 = 8;

然后把A中块的上半4*8部分移动到C的上半4*8，A的下半4*8移动到D的上半4*8，之后再把C和D的其中两部分4*4移动到B的上半4*8部分，剩下移动到B的下半4*8部分。

我觉得我代码写的很清楚了，这部分直接看代码吧。

else if (M == 32) {
        for (j = 0; j < 32; j += 8) {
            // 先处理对角块
            if(j == 0) e0 = 8, e1 = 16;
            else if(j == 8) e0 = 0, e1 = 16;
            else e0 = 0, e1 = 8;
            // A00 -> C00
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + jj][e0 + ii] = A[j + ii][j + jj];
                }
            }
            // A01 -> C01
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + jj][e0 + 4 + ii] = A[j + ii][j + 4 + jj];
                }
            }
            // A10 -> D00
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + jj][e1 + ii] = A[j + 4 + ii][j + jj];
                }
            }
            // A11 -> D01
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + jj][e1 + 4 + ii] = A[j + 4 + ii][j + 4 + jj];
                }
            }
            // C00 -> B00
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + ii][j + jj] = B[j + ii][e0 + jj];
                }
            }
            // D00 -> B01
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + ii][j + jj + 4] = B[j + ii][e1 + jj];
                }
            }
            // C01 -> B10
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + ii + 4][j + jj] = B[j + ii][e0 + jj + 4];
                }
            }
            // D01 -> B11
            for (ii = 0; ii < 4; ++ii) {
                for (jj = 0; jj < 4; ++jj) {
                    B[j + ii + 4][j + jj + 4] = B[j + ii][e1 + jj + 4];
                }
            }


            // 处理非对角
            for (i = 0; i < 32; i += 8) { 
                if (i != j) {
                    for (ii = i; ii < i + 4; ii++) {
                        e0 = A[ii][j];
                        e1 = A[ii][j + 1];
                        e2 = A[ii][j + 2];
                        e3 = A[ii][j + 3];
                        e4 = A[ii][j + 4];
                        e5 = A[ii][j + 5];
                        e6 = A[ii][j + 6];
                        e7 = A[ii][j + 7];

                        B[j][ii]     = e0;
                        B[j + 1][ii] = e1;
                        B[j + 2][ii] = e2;
                        B[j + 3][ii] = e3;
                        B[j][ii + 4]     = e4;
                        B[j + 1][ii + 4] = e5;
                        B[j + 2][ii + 4] = e6;
                        B[j + 3][ii + 4] = e7;
                    }

                    for (ii = j; ii < j + 4; ii++) {
                        e0 = A[i + 4][ii];
                        e1 = A[i + 5][ii];
                        e2 = A[i + 6][ii];
                        e3 = A[i + 7][ii];
                        e4 = B[ii][i + 4];
                        e5 = B[ii][i + 5];
                        e6 = B[ii][i + 6];
                        e7 = B[ii][i + 7];

                        B[ii][i + 4] = e0;
                        B[ii][i + 5] = e1;
                        B[ii][i + 6] = e2;
                        B[ii][i + 7] = e3;
                        B[ii + 4][i]     = e4;
                        B[ii + 4][i + 1] = e5;
                        B[ii + 4][i + 2] = e6;
                        B[ii + 4][i + 3] = e7;
                    }

                    for (ii = i + 4; ii < i + 8; ii++) {
                        e0 = A[ii][j + 4];
                        e1 = A[ii][j + 5];
                        e2 = A[ii][j + 6];
                        e3 = A[ii][j + 7];

                        B[j + 4][ii] = e0;
                        B[j + 5][ii] = e1;
                        B[j + 6][ii] = e2;
                        B[j + 7][ii] = e3;
                    }
                }
                else {
                    continue;
                }
            }
        }
    }

总结

f89e3655c2dd4d712c862268dd80b364

295c24eaa82b747add0e18bc67df37de