| CSAPP | 您所在的位置：网站首页 › 深入学习Cache › CSAPP |
CSAPP
|
CacheLab
文章目录
CacheLab实验概述一些前置准备Part A实验预览思路数据结构创建高速缓存从命令行中读取参数信息初始化高速缓存代码
读入内存操作指令解析地址映射代码
模拟高速缓存代码
释放内存代码
主函数代码
Part B实验预览32×32优化——分块8×8代码
优化——分块8×8+使用局部变量代码
64×64优化——分块8×8优化——分块4×4代码
优化——对8×8的块用4×4的方式处理1.0代码
优化——对8×8的块用4×4的方式处理2.0代码
61×67评分
“All problems in computer science can be solved by another level of indirection” 实验概述实验分为两部分：Part A要求编写一个高速缓存模拟器（csim.c），Part B要求优化矩阵转置函数，最小化高速缓存的不命中的次数（trans.c） 这个实验设计得很好，恰好涵盖了书上第6章的两个核心部分：理解高速缓存的工作方式，以及编写高速缓存友好的代码，同时还应用到了p450页介绍的分块技术。建议先阅读以下的资料，再进行实验 CMU课件，最后有对Cache Lab的一些提示：rec07.pdf (cmu.edu) 分块技术的介绍：waside-blocking.pdf (cmu.edu) 讲解分块技术的博客：[读书笔记]CSAPP：16[VB]高速缓存存储器 - 知乎 (zhihu.com) 一些前置准备按照实验说明，解压cachelab-handout.tar，创建出一个名为cachelab-handout的目录，这是我们Part A和Part B的工作目录，Part A对应的文件是csim.c，Part B对应的文件是trans.c 进到目录后先输入命令：make clean && make，这将会编译csim.c,trans.c,test-trans.c等文件 Part A 实验预览Part A要求在csim.c文件中编写一个高速缓存模拟器，traces目录下的5个.trace文件是模拟器要执行的内存操作
老师提供了一个可供参考的缓存模拟器：csim-ref，这个模拟器有6个参数： Usage: ./csim-ref [-hv] -s -E -b -t • -h: Optional help flag that prints usage info • -v: Optional verbose flag that displays trace info • -s : Number of set index bits (S = 2^s is the number of sets) • -E : Associativity (number of lines per set) • -b : Number of block bits (B = 2b is the block size) • -t : Name of the valgrind trace to replay和书上使用的参数一致：s是组索引位数，E是每个组包含的高速缓存行的个数，b是块偏移位数，除此之外，参数v表示要详细输出每次内存执行时，高速缓存的模拟情况（命中、不命中、替换）；参数t是用于模拟内存操作的.trace文件名，举个例子： ./csim-ref -v -s 2 -E 2 -b 3 -t traces/yi.trace这表示用csim-ref模拟一个高速缓存，执行traces/yi.trace的内存操作。我们设定这个高速缓存有4个组，每个组有2个高速缓存行，每个高速缓存块有8个字节
查看一下yi.trace中的内存操作： L 10,1 M 20,1 L 22,1 S 18,1 L 110,1 L 210,1 M 12,1内存操作的格式为：[space]operation address, size，operation 有 4 种： I表示加载指令，表示从内存中读取指令内容L 加载数据，表示程序从某个内存地址加载了数据。（缓存命中、不命中、执行替换策略）S存储数据，表示程序向某个内存地址存储了数据。（写回、写分配）M 修改数据，表示程序对某个内存地址的数据进行了修改。不需要考虑加载指令I,M指令相当于先进行L再进行S，模拟器要做出的反馈有 3 种： hit：命中，表示要操作的数据在对应组的其中一行miss：不命中，表示要操作的数据不在对应组的任何一行eviction：驱逐，表示要操作的数据的对应组已满，进行了替换操作，这个实验的驱逐策略是LRU，选择最后被访问的时间距现在最远的块（CSAPP p423页）Part A要做什么： 编写csim.c，这个程序的执行效果要与csim-ref相同，能够模拟一个高速缓存器（参数自定义），执行traces/xx.trace中的内存操作过程。这个模拟器不需要真的存储数据，只是计算traces/xx.trace的内存操作过程中，缓存的命中、不命中、LRU替换的数量，然后将这些参数作为答案，传给printSummary函数 如何检验模拟器的正确性： 首先编译csim.c文件，命令为：gcc -o csim csim.c cachelab.c -lm，这将创建可执行文件csim，也就是你的模拟器 有两种检验方法： 使用csim-ref作为参考。设定相同的参数，分别用csim-ref和csim作为模拟器，读取同一个.trace文件的内存操作过程，比对两个模拟器输出的hit、miss、eviction的值使用评分程序test-csim，命令为：./test-csim，这个程序将会使用不同的参数设定你的模拟器，并让模拟器执行目录traces中所有的.trace文件，满分是27 思路我将整个高速缓存模拟器的实现分为3个部分： 创建高速缓存：这包括从命令行中读取参数信息，初始化缓存读入内存操作：就是读取xx.trace文件中每行的内容根据读入的内存操作，模拟高速缓存的行为：核心代码，这包括在高速缓存中查找地址所指示的字，对不命中的处理（是加载到一个空的缓存行还是需要执行LRU替换策略）。每次执行一次缓存(caching)，就更新缓存(cache)信息（有效位、标志位、时间戳），同时统计hit、miss、eviction 数据结构根据CMU课件的提示，我使用二维结构体数组实现cache。结构体定义如下： typedef struct { bool valid; //有效位 unsigned long tag; //标志位 int timestamp; //时间戳 }cache_line; //一个高速缓存行定义二维结构体数组为cache_line** cache，这个数组的大小是S×E，cache[i]是高速缓存组i，cache[i][j]是高速缓存组i中的高速缓存行j，cache[i][j]中包含有效位（valid）、标志位（tag）、时间戳（timestamp，记录这个高速缓存行最后被访问的时间），由于不需要存储数据，就没有定义高速缓存块
由于s、E、 b是由命令行参数设定的，所以要先读取命令行中的参数，可以使用课件中提示的getopt函数，参考getopt(3) - Linux manual page (man7.org) 为了便于访问参数s、E、b，我使用全局变量定义这些参数，简化代码。同时，我使用变量verbose来标识是否需要详细输出缓存过程 这里说一个小坑，getopt函数中，没有参数的选项不带":"，如果你写成了v:s:E:b:t，即不带参数的-v有了":"，那么getopt就会等待参数的输入。当opt为s时，会将读到的参数optarg给v，而不是后出现的s，这就是说，-v将-s的参数作为自己的参数，-s就直接被跳过了，然后后面就正常读了，所以E、b、t都没问题，只有s为0（花费我1h用gdb来回调试才发现的bug😢，这样的细节很要命） 初始化高速缓存为结构体数组分配空间： 相应的，二维结构体数组的空间也是动态分配的。根据读入的参数s、E、b，使用malloc分配内存 初始化高速缓存： 将cache[i][j]的有效位（valid）设置为0，表示这是一个空的高速缓存行；时间戳（timestamp）设置为0 代码实现的代码如下： cache_line** create_cache(int argc, char** argv) { int opt; while(-1 != (opt = getopt(argc, argv, "vs:E:b:t:"))) { switch(opt) { case 'v': verbose = 1; //设置verbose为1，表示要详细输出缓存过程 break; case 's': s = atoi(optarg); break; case 'E': E = atoi(optarg); break; case 'b': b = atoi(optarg); break; case 't': strcpy(t, optarg); break; default: break; //程序健壮性检验，如果不是一个合法的参数，就会退出switch,继续while读取 } } //申请内存，创建高速缓存，组数为2^s,每一组高速缓存行总数为E个。即创建一个行为2^s,列为E的二维结构体数组 int row = pow(2, s); int col = E; cache_line** cache = (cache_line**)malloc(row*sizeof(cache_line*)); if(cache == NULL) { printf("Failed to allocate memory!\n"); exit(1); } for(int i=0; i printf("Failed to allocate memory!\n"); exit(1); } } //初始化高速缓存，设置有效位为0，时间戳为0 for(int i=0; i cache[i][j].valid = 0; //有效位 置0 cache[i][j].timestamp = 0; } } return cache; } 读入内存操作我们要模拟的内存操作过程放在了xx.trace文件中，这个文件的名称由命令行参数提供，存放到字符数组t中。读入内存操作 就等价于 读取文件t的每一行，对指令进行解析，然后获取地址映射的组索引、标记，用于后续在模拟高速缓存时，在高速缓存中查找这个地址的内容 使用课件中建议的fscanf函数，读取文件t的每一行指令。 指令解析指令的形式为：[space]operation address, size，根据实验预览部分的分析，我们只需要读取指令L、S、M，而M等同于先L，再S，所以指令M需要进行两次缓存 地址映射参照书上对地址的划分方法，将读到的地址addr进行掩码运算，获得该地址映射的组索引set和标记tag: set = (addr>>b) & (unsigned long)((1 (b+s);
根据从内存操作中由地址映射的组索引set、标记tag，模拟缓存过程 为了简化参数，我使用一个数组result[3]来存放hit、miss、eviction的次数。 为了记录缓存行cache[i][j]最后被执行的时间，即设置时间戳cache[i][j].timestamp，我使用一个全局变量T作为整体的时间。初始 T设置为0，每当进行一次缓存(caching)，就要对T加1，这样当需要进行LRU替换时，我们遍历查找这个组，驱逐时间戳最小的缓存行。恰好我们在每一次缓存(caching)后，使用update函数更新缓存(cache)的信息，所以当调用update函数时，就意味着进行了一次缓存(caching)，因此可以在update函数中对T加1，更新整体的时间 模拟高速缓存的整体逻辑是： 首先在高速缓存组cache[set]中进行行匹配：遍历检查缓存行cache[set][j]的有效位和标记位，以确定地址中的字是否在缓存中。如果找到了一个有效的行cache[set][pos]，它的标记与地址中的标记tag相匹配，则缓存命中；若遍历了所有的行都不匹配，则为缓存不命中若缓存命中，则直接调用update函数，更新时间戳：cache[set][pos].timestamp = T，并统计hit：result[HIT]++（这里我使用了枚举）若缓存不命中，则需要判断这个组cache[set]是否满了，一种方法是维护一个数组occupancy，它记录了各个组中有效位为1的有效行个数，初始置为0。比较occupancy[set]（有效行个数）与E（行总数），判断缓存组cache[set]中是否还有空行 若occupancy[set] < E，则有空行。只需要遍历cache[set]中各个行的有效位，找到空行（设空缓存行是cache[set][pos]），然后调用update函数，将cache[set][pos]的有效位置1：cache[set][pos] = 1；标记位更新为tag：cache[set][pos].tag = tag；更新时间戳：cache[set][pos].timestamp = T；统计miss：result[MISS]++若occupancy[set] == E，则没有空行，需要执行LRU替换策略。调用函数LRU_replace，遍历整个组cache[set]，找到时间戳最小的缓存行，返回这个缓存行的位置pos，然后调用update函数，更新cache[set][pos]（同上），并统计eviction：result[eviction]++ 代码 //核心代码 void cache_simulate(cache_line** cache, int set, unsigned long tag) { bool find = false; //标识是否命中 int col = E; int pos = 0; for(int j=0; j pos = j; //对高速缓存行j进行更新 update(cache[set], HIT, pos, tag); find = true; break; } } //如果没有命中，则先检验这个组是否满了,通过维护一个数组occupancy，可以获得组set中有效缓存行的数量 if(!find) { //如果还有空的缓存行，则直接将内存块存放到这个空白行中 if(occupancy[set] != E) { occupancy[set]++; //要加载内存块到一个空缓存行中，占用量+1 for(int j=0; j pos = j; update(cache[set], MISS, pos, tag); break; } } }else //如果整个组都满了，没有空白行，则此时需要用LRU策略替换掉一个缓存行 { pos = LRU_replace(cache[set]); //获取要被替换的行号 update(cache[set], MISS, pos, tag); update(cache[set], EVICTION, pos, tag); //更新 } } } //更新 void update(cache_line* cache_set, enum Category category, int pos, int tag) { void update(cache_line* cache_set, enum Category category, int pos, int tag) { result[category]++; //统计相应的缓存情况（命中、不命中、替换） printf("%s ", category_string[category]); cache_set[pos].tag = tag; //更新标志位 cache_set[pos].valid = 1; //更新有效位 cache_set[pos].timestamp = T; //更新时间戳 T++; //每次更新，都要增加时间T } } //LRU替换,暴力搜索时间戳最小的缓存行，返回行号pos int LRU_replace(cache_line* cache_set) { int min = cache_set[0].timestamp; int pos = 0; for(int j=1; j pos = j; min = cache_set[j].timestamp; } } return pos; } 释放内存良好的编程习惯，手动释放内存 代码 void destory(cache_line** cache) { int row = pow(2, s); for(int i=0; i cache_line** cache = create_cache(argc, argv); get_trace(cache); destory(cache); printSummary(result[0], result[1], result[2]); return 0; }完整代码见github仓库：y-tanx/csapp: csapp lab,including solutions and explanations (github.com) 运行结果：
评分：
Part B要优化一个矩阵转置函数，尽可能减少miss次数，要修改的文件是trans.c，高速缓存的参数：s=5,E=1,b=5，这个高速缓存共有32组，每组有一行（直接映射），每一行存32字节，即8个int Part B很有意思，虽然矩阵转置的时间复杂度始终为O(n^2)，但是可以利用高速缓存和程序局部性，对矩阵转置函数进行优化 要进行转置的矩阵有三种：
Part B要做什么： 在trans.c中，使用分块技术优化矩阵转置函数，处理三个不同的输入，你要将优化后的函数写到这一行的下面：
如何检验优化的效果： 首先在目录中使用：make clean && make，编译trans.c、test-trans.c 然后使用命令： make && ./test-trans -M 32 -N 32 make && ./test-trans -M 64 -N 64 make && ./test-trans -M 61 -N 67分别检验三种规模的矩阵转置时的优化情况 评分标准如下，以缓存不命中的次数misses作为优化的指标：
也可以使用命令： ./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 > hitf在文件hitf中，查看内存的实际访问情况 32×32trans.c文件中提供了一个原始的转置方法trans，我们可以将它复制到transpose_submit中，检验一下效果：
测试如下：
测试结果是1:1183，不命中的数量是很大的 分析不命中出现在哪里：
假设A[0][0]的地址为0x0，B[0][0]的地址为0x1000（这是合理的，hitf文件中显示A、B的地址相差64的倍数）。可以看到，每8个元素映射到同一个缓存组，每一行的元素（32个）能映射到相邻的4个缓存组，按行来看：A[0]~A[7]这8行依次映射到组0 ~ 组3、组4 ~ 组7， 组8 ~ 组11，组12 ~ 组15，组16 ~ 组19，组20 ~ 组23，组24 ~ 组27，组28 ~ 组31。在第9行，A[8]与A[0]映射的缓存组相同（可以通过地址来看，每256个元素的组索引相同，会映射到同一个组），所以每隔8行，映射的缓存组相同。按列来看：B[0]与B[1]中的同一列元素相差4个缓存组，如B[0][0]映射到组0，B[1][0]映射到组4。同样的，同一列的元素每隔8行，就会映射到同一个缓存组，比如B[0][0]与B[8][0]都映射到组0 数组A、B每部分映射的缓存组如下图所示：
由上述的分析可知，在按行遍历数组A时，访问每组的首个元素时，会发生冷不命中（发生在A[0]~A[7]中）或 冲突不命中（A[8]之后），组中的其余元素不会再产生miss（对角线元素特殊，后面会讲解），共有(32×32)/8=128次miss 在按列遍历数组B时，当我们访问到B[i][j]时，我们将B[i][j]存放到它映射的缓存组中，设这个缓存组为组a，此时产生了一次不命中。由于要按列遍历，同一列元素相差4个缓存组，所以缓存组a不会再存放其它的数据，此时缓存组a的块只存放了一个元素B[i][j]。当遍历到同一列的B[i+8][j]时，由于同一列的元素每隔8行，就会映射到同一个缓存组，所以B[i+8][j]与B[i][j]均映射到缓存组a，此时访问B[i+8][j]会发生冲突不命中。由于组a中只有一个缓存行（直接映射缓存组），所以会将B[i][j]驱逐。当再次循环，遍历到B的下一列元素B[i][j+1]时，由于B[i][j]被驱逐了，组a中存放其它的元素，所以访问B[i][j+1]仍然不命中。因此，访问B中的每个元素时都不命中，总共有32×32=1024次miss
对于对角线元素，对角线元素A[i][i]与B[i][i]会映射到同一个高速缓存组（可以分析地址，A[i][i]与B[i][i]地址的组索引相同），设这个缓存组为组b。当访问到B[i][i]时，高速缓存组b已经存放了A[i][i]，所以B[i][i]会驱逐A[i][i]（这没有增加B的miss，因为上述分析中，访问B中的每个元素都不命中，接下来访问的B[i][i+1]不会映射到组b，所以访问B[i][i]只有一次不命中，被记入到1024次miss中了），但是接下来要访问A[i][i+1]，此时组b中存放的是B[i][i]，所以会再将B[i][i]驱逐，造成了A额外的一次冲突不命中。对角线元素有32个，最后一个对角线元素A[31][31]在块C的末尾，当访问B[31][31]时，会驱逐块C中的A[31][31]。但是在访问B[31][31]后，程序结束了，所以这次不会发生A额外的冲突不命中，因此共有31次额外的miss 总计，有128+1024+31=1183次miss，正好符合我们实际检验的值，这验证了上述分析的正确性 注意，上面的分析可看可不看，不会影响接下来的优化。但是自己画图，真正做一次这样的分析，尤其是分析对角线元素的相互驱逐，会加深你对缓存的理解，也能更清楚为什么我们要分块——增加块的利用率，从而减少不命中率。所以建议你试着画图，分析一下缓存过程，如果有问题再看我上面的分析 好了，分析这么多该开始想想怎么优化了 性能瓶颈：通过上面的分析，我们发现矩阵B对缓存的利用率很低，每次缓存组只存放B中一个元素，而且在后续访问这一列时，这个元素就被驱逐了，造成了每个元素读取一次，就会发生一次不命中的情况。而分块的核心思想就是：将一个程序中的数据结构组织成大的片（Chunk），使得能够将一个片加载到高速缓存中，并在这个片中多次进行读写，提高对缓存的利用率，分块技术正好对症！ 优化策略：增加矩阵B对缓存的利用率，最好的情况就是每个缓存块中的8个位置都填入了B的元素，所以首先考虑8×8分块，一次循环对8×8的元素块进行转置 优化——分块8×8
图模仿知乎博主：大猫咋，链接：(99+ 封私信 / 40 条消息) 大猫咋 - 知乎 (zhihu.com)，感谢学长优秀的文章 一次取出8×8的元素，由4个高速缓存组存储。8×8分块在块的内部不会造成冲突，A与B的高速缓存组正好错开了（A、B两个红色块映射的高速缓存组没有交集），而且充分利用了块的内存空间。核心在于降低了B的不命中率：原来要存放32个元素，有32次不命中；现在存放64个元素，有8次不命中，降低不命中率至1/8（除对角线块外，但对角块经过优化，只有一个对角元素不命中，所以不命中率也近似于1/8），所以优化是有效的 代码 void transpose_submit(int M, int N, int A[N][M], int B[M][N]) { // 使用分块8×8的方法来进行转置 for(int i=0; i for(int s=0; s B[j+k][i+s] = A[i+s][j+k]; } } } } }对于A中每一个操作块，只有每一行的第一个元素会不命中，所以为8次不命中；对于B中每一个操作块，只有每一列的第一个元素会不命中，所以也为 8 次不命中。总共miss次数为：8 × 16 × 2 = 256 看一下结果：
miss的次数是343，比理论高了太多，这是什么原因？ 性能瓶颈： 和分析trans函数一样，我们还需要分析对角线上的块。首先使用命令./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 > hitf，查看一下hitf
我们会发现A和B的地址的差距是0x40000(64的整数倍)，所以当操作块Ap、Bq位于对角线上时，存放两个块所用的4个缓存组相同，因此加载块Ap 和存储块Bq会一直发生驱逐，原因就在于需要不断加载块Ap来读取下一个元素。如果要避免这种情况发生，可以利用局部变量存储块Ap的一行，这么做，即使当存储块Bq时，驱逐了块Ap的这一行，后续也不需要再加载Ap的这一行，而直接使用保存在局部变量中的数据赋给块Bq 优化策略：考虑使用 8 个本地变量一次性存下 A 的一行后，再复制给 B 优化——分块8×8+使用局部变量 代码 void transpose_submit(int M, int N, int A[N][M], int B[M][N]) { //由于对角线部分的冲突不命中增多，导致miss的数量较大，使用的方法是将A中的一组元素（8个）使用局部变量存储在程序寄存器中，避免了A和B的加载和写回的冲突不命中 int a0, a1, a2, a3, a4, a5, a6, a7; for(int i=0; i //将一组的8个Aij都存放到寄存器文件中，然后直接传递给Bji，对于对角线元素虽然仍有冲突，但是除此之外，对角线块不会出现冲突 //估计约287misses（256+31），这种方法只有处在对角线上的元素会出现冲突 for(int k=0; k int a0, a1, a2, a3; for(int i=0; i for(int k=0; k a0 = A[i+s][j+k+0]; a1 = A[i+s][j+k+1]; a2 = A[i+s][j+k+2]; a3 = A[i+s][j+k+3]; B[j+k+0][i+s] = a0; B[j+k+1][i+s] = a1; B[j+k+2][i+s] = a2; B[j+k+3][i+s] = a3; } } } } }结果：
miss：1651，相较于上一个4×4分块的方法，没有优化太多，这是什么原因？ 性能瓶颈： 分析一下这个程序，相较于最初的8×8分块，这个版本的优化使B的miss减少很多（填入B的8个元素，miss只有8个，即每组首个元素的不命中，这是无法避免的），但是对于A的miss没有减少，而且没有我们想象的“充分利用块的空间，取出来8个Aij”。由于转置受限，我们只能取出块Ap每一组中的前4个元素，依次赋给块Bq的前4行。当Bq的前4行都填满时，我们才能取出Ap每组中的后4个元素，对Bq的后4行进行填写，所以对Ap的8个组，每一组会有2次miss，加载A中一个8×8的块共有16次miss，平均每取出4个元素就会出现1次miss，根本没有达到我们的目标——充分利用块的空间，一次miss能取出8个元素 优化策略： 这对于8×8的情况已经提升不少——按照初始的8×8方法，加载块Ap和存储块Bq共需要8 + 64（Bq全不命中） = 72个miss。但是相对于4×4的方法，这种方法没有太大的提升。这种改进版本和4×4的方法都减少了B的miss，而且效果等同：改进版本填入8个Bij有8次miss，而4×4分块中填入4个Bij有4次miss。但是4×4的方法就到这里了，而改进的方法还能被优化，因为我们能充分利用上高速缓存块中A的8个元素——一次取出高速缓存块中A的8个元素，4×4显然做不到。所以我们接下来对改进版本再优化，使它能一次取出高速缓存块中A的8个元素 优化——对8×8的块用4×4的方式处理2.0这个部分我试了很长时间，但是大致方向始终没有错误：利用4×4方法对8×8的块进行处理，按照特殊的转置方法，避开B的块内部的冲突 首先我想到要用8个变量存放块Ap的一行。存放A1的局部变量传递给B1，实现B1的转置；但是存放A2的局部变量只有传递给B2才能实现转置，而存储B2就会驱逐B1、B3部分，没有解决块Bq内部的冲突，而局部变量只能有12个，所以此时只有一个地方有空——B3，我只好把存放A2的局部变量传递给B3，此时B3中存放的是B2的转置结果，即A2^T
但是要驱逐B1、B3，保存B2、B4的前提是我不需要再修改B1、B3，所以我要在保存B2、B4之前，要将B3的转置结果填到B3中，这个过程很有技巧： 首先，将B3的一行存放到局部变量中
然后，将A3的一列填补到B3取出的这一行中，B3的这一行填入了对应的转置结果
开始对B2进行处理。我们每次只对B2的一行进行处理，而这一行恰好将我们从B3中取出的一行驱逐掉，B3的这一行已经存放了对应的A3^T，并且B3这一行的数据被存放在局部变量中了，B2这一行对应的A2^T恰好存放在B3的这一行中，所以接下来，只需要将局部变量的值赋给B2这一行就好了，这样也将转置结果填入了B2这一行。循环操作，直至B1、B3都被驱逐，此时B2也填入了A2^T
PS：这里有种思维惯性，就是总是想用A的一行转置到B的一列，但是形式所逼，只能用按行填入B3的转置结果，填入完一个行，才能放心地驱逐这一行 最后，很简单了，就是将A4^T填入到B4中，由于A4为4×4大小，而我们有8个局部变量可用，所以直接使用循环展开
我看有的博客说17*17是miss最少的，不过16、17、18这几个分块方式都能满分，我也不过多研究了（做完64×64太累了） 结果：
擦线飘过 评分满分53，Part A 27，Part B 26，代码风格7分由老师给 一个博主使用python3重构了driver.py： wget https://gitee.com/lin-xi-269/csapplab/raw/master/lab5cachelab/cachelab-handout/driver.py感谢作者：林夕丶，链接：(99+ 封私信 / 38 条消息) 林夕丶 - 知乎 (zhihu.com) 在下载之前，需要先将当前的driver.py删除，然后再用上面的下载指令，并将下载好的driver.py增加可执行权限 rm -rf driver.py wget https://gitee.com/lin-xi-269/csapplab/raw/master/lab5cachelab/cachelab-handout/driver.py chmod +x driver.py然后就可以测试了
完整代码见github仓库：y-tanx/csapp: csapp lab,including solutions and explanations (github.com) 一些小感想： 优化的过程不是一蹴而就的，而是通过不断尝试，逐渐迭代优化，一点点靠近最优的方法，Part B中的64×64转置经历了4个版本的优化，通过不断尝试，分析性能瓶颈，找到了优化的方向，并在迭代优化中找到最优的方案Part A耗时有点长，我的代码能力需要多练了！Part B是个很有意思的实验，虽然转置的时间复杂度始终为O(n^2)，但是不同的转置方法对高速缓存的利用情况不同，最终导致性能有很大差别工具是用熟的，这次调试Part A的bug又用上了lab2时曾经用过的gdb工具，这次是彻底会用gdb来调试程序了；我学了一下git的使用，把我的代码上传到github中了，后面会陆续将前面实验的代码上传的github上这个实验涵盖了第6章的所有核心内容，做了这个lab，第六章又复习了一遍，对高速缓存的机制理解更透彻了，更加感觉高速缓存设计的巧妙，正如文章开头所言：“All problems in computer science can be solved by another level of indirection”，计算机领域中的所有问题都可以通过增加一个中间层来解决，存储器的层次结构正印证了这句话本实验用时16h，两天；文章用时1天半写完 |
【本文地址】