CSAPP

2024-07-02 18:54| 来源: 网络整理| 查看: 265

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>b) & (unsigned long)((1 (b+s); switch(operation) { case 'L': case 'S': if(verbose) printf("%c %lx,%d ", operation, addr, bytes); cache_simulate(cache, set, tag); if(verbose) printf("\n"); break; case 'M': if(verbose) printf("%c %lx,%d ", operation, addr, bytes); cache_simulate(cache, set, tag); cache_simulate(cache, set, tag); if(verbose) printf("\n"); break; default: break; } } } 模拟高速缓存

根据从内存操作中由地址映射的组索引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

【本文地址】

CSAPP

CSAPP

今日新闻

推荐新闻