用户投稿Cache Lab实验纪录
实验简介
This is the handout directory for the CS:APP Cache Lab.
欲修改档案
csim.c Your cache simulatortrans.c Your transpose function
测试工具
Makefile Builds the simulator and toolsREADME.md This filedriver.py* The driver program, runs test-csim and test-transcachelab.c Required helper functionscachelab.h Required header filecsim-ref* The executable reference cache simulatortest-csim* Tests your cache simulatortest-trans.c Tests your transpose functiontracegen.c Helper program used by test-transtraces/ Trace files used by test-csim.c
环境配置
我们需要读取trace文件中的命令来评估缓存的性能，而这些trace文件是由Valgrind这告软体生成的，因此建议先进行安装
输入
sudo apt install valgrind
完成安装后可以透过指令valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l，追蹤目录下所有可执行文件的缓存使用状况
输入完指令后可以在终端中看到以下图的格式输出，它代表程式执行过程中缓存的运作纪录
I → 读取指令(实验不需要实现该指令)M → 修改数据并存回缓存L → 读取数据S → 储存数据格式： [操作指令], [64 bits地址], [数据大小]
Part. A
该实验值主要编写一个LRU策略的虚拟缓存，透过读取trace文件指令模拟缓存的操作，并对hits, miss, eviction数量进行分析
实验须知
我们需要在csim.c中实现虚拟缓存由于测试时会使用不同的sets, line, block缓存使用的记忆体空间要使用malloc动态分配trace资料夹包括要所有要读取的.trace文件可以调用cachelab.c/.h中的helper function，例如printfSummary()如何进行验证
Lab文件说得很清楚:
测试自行编写的缓存，执行结果必须要跟
csim-ref相同
或是直接执行./test-csim查看输出结果与reference simulator是否相同，若是输出结果为27分那就代表通过测试用例
程式撰写
我们把整个程式粗略分成5个区块:
读取输入参数
该模块的目的是为了读取可执行档的后续参数，例如./csim -s 4 -E 1 -b 4 -t traces/yi.trace中的组数、行、偏移量、trace文件，先把这些数据暂存起来，待初始化缓存与读取trace文件时使用，其程式码区块如下
/** * func for getting operator */ static char get_operation(char* str){ if(strlen(str) <= 1){ return '\0'; } return str[1];}int main(int argc, char* argv[]){ // ... 省略 for(int i=1; i<argc; i++){ char op = get_operation(argv[i]); switch(op){ case 'h': print_help_message(); break; case 'v': print_msg = true; break; case 's': s = atoi(argv[++i]); input_check++; break; case 'E': E = atoi(argv[++i]); input_check++; break; case 'b': b = atoi(argv[++i]); input_check++; break; case 't': strcpy(filename, argv[++i]); input_check++; break; default: break; } } // ... 省略}初始化cache
利用得到的参数，为cache分配动态记忆体，其function为cache_init(s, E)，缓存中的行定义为结构体cacheLine
typedef struct{ uint32_t vaild; uint32_t tag; uint64_t timeStamp; // 供LRU使用的时间戳}cacheLine;/** * func for initializing cache memory */ static void cache_init(uint8_t s, uint8_t E){ uint32_t sets = 1 << s; virtual_cache = (cacheLine**)malloc(sizeof(cacheLine*) * sets); for(int i=0; i<sets; i++){ virtual_cache[i] = (cacheLine*)malloc(sizeof(cacheLine) * E); }}操作指令解读
该部份用来解读trace文件中的操作指令、地址、大小信息
函式cmd_parsing(filename)会逐条取trace文件的行直到EOF
函式load_operation(line)会解析该条指令并操作缓存
/** * func for loading data from cache */ static void load_operation(char* line){ uint64_t addr=0; uint32_t dataBytes=0; char op; /* 取trace文件的一行命令 */ sscanf(line, " %c %lx,%u", &op, &addr, &dataBytes); /* 操作指令只能有L, M, S */ if(op != 'L' && op != 'M' && op != 'S'){ return; } if(print_msg){ printf("%c %lx,%u ", op, addr, dataBytes); } /* 对地址进行解析 */ uint32_t set = (addr >> b) & (~(U64MAX << s)); uint32_t tag = addr >> (s+b); bool find = false; int empty_line = -1; /* 遍历cache查看是否存在该数据 */ for(int i=E-1; i>=0; i--){ /* 缓存命中，同时更新时间 */ if(virtual_cache[set][i].vaild && virtual_cache[set][i].tag == tag){ find = true; virtual_cache[set][i].timeStamp = ticks; break; }else if(virtual_cache[set][i].vaild == 0){ /* 找到空的行 */ empty_line = i; } } /* 若为修改指令，因为会写回所以hit数一定要加一 */ hits = op == 'M' ? hits+1 : hits; if(find){ hits++; if(print_msg){ printf("hit "); } }else{ miss++; if(print_msg){ printf("miss "); } /* 若不命中且没有空行，就会发生eviction */ if(empty_line == -1){ evictions++; /* 使用LRU找需要替换的行 */ empty_line = LRU(set); if(print_msg){ printf("eviction "); } } /* 不命中后重新加载，更新缓存 */ virtual_cache[set][empty_line].vaild = 1; virtual_cache[set][empty_line].tag = tag; virtual_cache[set][empty_line].timeStamp = ticks; } if(op == 'M' && print_msg){ printf("hit "); } if(print_msg){ printf("\n"); } }/** * func for parsing commands from trace file */ static void cmd_parsing(char* filename){ char line[MAX_LEN]; FILE* fp = fopen(filename, "r"); while(!feof(fp) && !ferror(fp)){ strcpy(line, "\n"); fgets(line, MAX_LEN, fp); load_operation(line); ticks++; } fclose(fp); }LRU
使用cacheLine的变数timeStamp判断哪个行距离现在使用最久远，因为每次操作时都会更新时间週期ticks(+1)，这代表timeStamp越小，距离现在越久
所以我们只需要扫描一遍某组中的所有行就可找出要替换的行
/** * func for applying LRU algo. */ static uint8_t LRU(uint8_t set){ int repalce = 0; for(int i=1; i<E; i++){ repalce = virtual_cache[set][i].timeStamp < virtual_cache[set][repalce].timeStamp ? i : repalce; } return repalce;}打印输出结果
可以调用cachelab.c/.h提供的printSummary(hits, miss, evictions)函式，简单打印缓存执行后的结果
释放cache记忆体
所有trace文件的操作指令执行完后，释放当初为缓存动态分配的记忆体
/** * func for releasing cache memory */ static void free_cache(){ uint32_t sets = 1 << s; for(int i=0; i<sets; i++){ free(virtual_cache[i]); virtual_cache[i] = NULL; } free(virtual_cache); virtual_cache = NULL;}Part. B
实验B要求实现一个矩阵的转移函式，并尽可能的降低缓存不命中的次数
实验总共要编写三种不同大小的转移函式
32 * 3264 * 6461 * 67Lab文件有提到miss的範围与得分佔比，例如64 * 64的矩阵测试结果miss要小于1300才能得到满分
实验须知
我们需要在trans.c中编写并测试转移函式转移函式中最多只能使用12个int类型的局部变数，若转移函式中调用其他函式，也要将该函式中的局部变数考虑进去不能使用位运算在一个整型变数存放多个值不允许使用long类型局部变数transpose_submit(int M, int N, int A[N][M], int B[M][N])中阵列参数只允许修改B转移函式中不允许宣告阵列变数或使用malloc如何进行验证
./test-trans -M 32 -N 32 for 32 * 32转移矩阵./test-trans -M 64 -N 64 for 64 * 64转移矩阵./test-trans -M 61 -N 67 for 61 * 67转移矩阵注册测试函式
注册多个不同的函式，可以在进行验证时同时执行，最多可以注册100个不同的转移函式
只需要在registerFunctions()中调用registerTransFunction()并填入该函式的注解字串以及函式名就可以了
注册函式细节请见
cachelab.c/.h
/* * trans - A simple baseline transpose function, not optimized for the cache. */char trans_desc[] = "Simple row-wise scan transpose";void trans(int M, int N, int A[N][M], int B[M][N]){ int i, j, tmp; for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { tmp = A[i][j]; B[j][i] = tmp; } } }void registerFunctions(){ registerTransFunction(transpose_submit, transpose_submit_desc); registerTransFunction(trans, trans_desc); registerTransFunction(trans32, trans_desc32); registerTransFunction(trans64, trans_desc64); registerTransFunction(trans6167, trans_desc6167);}Blocking
Blocking是一种记忆体区块化处理的技术，透过提高循环内的局部性降低不命中率
为了演示Blocking为何有效，我们编写一个简单的小函式，计算矩阵A的每列与矩阵B的每行相乘的加总
Non-Blocking
先遍历矩阵A的一列(row)，然后複製到矩阵B的一行上(column)假设N, M均为8假设缓存有4组，每组一行，一行存放8个整数int multi(int A[8][8], int B[8][8]){ int i, j, temp=0, sum=0; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { temp = A[i][j] * B[j][i]; sum += temp; } } return sum;}
矩阵miss数
由于缓存的一行刚好可以容纳矩阵A的一列，所以总共会发生8次miss，由于缓存只有4组，所以当遍历到第4列时就会覆盖掉第0列中缓存内容(发生eviction)，但由于是逐列扫描，所以差别不大
B矩阵是逐行(column)读取的，所以每次都会发生miss
b0, b8, b16, b24均发生miss，并分别将其加载进block0~block3b32, b40, b48, b56发生miss + eviction，将加载的数据覆盖block0~block3在每次循环中缓存内要不没有数据，不然就是存放其他列数据，产生miss和eviction因此每行均会发生8次miss，总长8行，miss数来到64次总miss数为8 + 64 = 72次miss
Blocking
将8 * 8矩阵分成4个4*4小块每次处理其中一个块将A矩阵块中的列与B矩阵块中的行相乘假设A矩阵块处理顺率为先左到右，再上到下假设B矩阵块处理顺率为先上到下，再左到右int multi(int A[8][8], int B[8][8]){ int i, j, temp=0, sum=0; /* 处理4个块 */ for (i = 0; i < 8; i+=4) { for (j = 0; j < 8; j+=4) { /* 处理每一个小块 */ for(int i1=i; i1<i+4; i1++){ for(int j1=j; j1<j+4; j1++){temp = A[i1][j1] * B[j1][i1]; sum += temp; } } } } return sum;}
矩阵miss数
由于缓存的一行刚好可以容纳矩阵A的一列，所以前4列的数据会全部加载进缓存中；同理左下的块加载时，右下的块需要的数据也已经在缓存中了。Blocking方法对矩阵A来说没变，依然是8次miss
对于B矩阵来说，每个块产生的miss:
读取矩阵B的b0, b8, b16, b24，并将前4列数据加载进缓存中下一次循环对b1, b9, b17, b25操作均不会发生miss，因为数据已经在缓存了因此每个块会发生4次miss，总共4块，所以miss数为4 * 4 = 16总miss数为8 + 16 = 24次miss
为何Blocking有效
从上述的小实验中可以看出，Blocking方法尽量避免缓存没有被充分利用(不管是缓存为空，或是加载后只读取一点数据)，让数据的读取有更好的空间局部性
使用Blocking方法需要特别注意缓存的大小以及读取数据的规模，因为这会涉及到缓存如何看待数据的加载目标
程式撰写
开始前先看看实验前提:
函式执行完后B矩阵必须是A矩阵的转移矩阵使用Blocking方法降低miss假设缓存大小为(s=5, E=1, b=5)，32组、1行、每行32bytes缓存大小为1024bytes，可以容纳256个int类型整数32 * 32
由于一列有32个整数，所以8列可以刚好填满缓存
使用大小为8 * 8的块(8代表8个整数大小)
/* * trans32*32 */char trans_desc32[] = "Simple transpose func32";void trans32(int M, int N, int A[N][M], int B[M][N]){ int i, j, i1; /* 循环遍历每个块 */ for (i = 0; i < M; i += 8) { for (j = 0; j < N; j += 8) { /* 对每个小块进行数据转移处理 */ for(i1=i; i1<i+8; i1++) { int temp_0 = A[i1][j]; int temp_1 = A[i1][j+1]; int temp_2 = A[i1][j+2]; int temp_3 = A[i1][j+3]; int temp_4 = A[i1][j+4]; int temp_5 = A[i1][j+5]; int temp_6 = A[i1][j+6]; int temp_7 = A[i1][j+7]; B[j][i1] = temp_0; B[j+1][i1] = temp_1; B[j+2][i1] = temp_2; B[j+3][i1] = temp_3; B[j+4][i1] = temp_4; B[j+5][i1] = temp_5; B[j+6][i1] = temp_6; B[j+7][i1] = temp_7; } } }}64 * 64
由于一列具有64个整数，所以缓存空间只能容纳4列(64 * 4 * 4 =1024 )，所以使用8*8块方法不适用另一个方法是将块大小缩减成4 * 4，但此方法会使miss数稍微超过1300，不是最佳解为了能最有效率使用块，同时又不发生多余eviction，需要特殊处理例如下图我们假设一个块大小为8 * 8，每个块可以细分成4个子块，每个子块大小为4 * 4
举例来说，若我们同时处理A1以及A3，就会发生
eviction，因为每过4列就会重头将缓存更新一遍，因此为了避免这种场景发生，我们都需要确保在缓存发生eviction替换前，被替换数据已尽量完成操作
块内的操作可以分成以下步骤:
步骤一将A1, A2数据複製给B1, B2A1, A2加载进缓存中B1, B2加载进缓存中步骤二将B2的内容先暂存再複製给B3；同时将A3複製给B2块A3, A4加载进缓存，覆盖掉原先的数据A1, A2该步骤是块B主要的miss以及eviction来源每次循环会先将B2数据读出，在加载A3的数据，这次使用的是缓存中存放的是B1, B2将A3複製给B2的操作由于当前缓存存放的事B1, B2因次会发生miss以及eviction(每列皆发生一次)下次循环中将B2数据读出，在加载A3的数据这个操作，每列又会发生一次miss以及eviction(因为缓存现在存放的数据变成B3, B4)步骤三将A4複製给B4
/* * trans64*64 */char trans_desc64[] = "Simple transpose func64";void trans64(int M, int N, int A[N][M], int B[M][N]){ int i, j, k; int temp_0, temp_1, temp_2, temp_3, temp_4, temp_5, temp_6, temp_7; /* 循环遍历每个块 */ for (i = 0; i < N; i += 8) { for (j = 0; j < M; j += 8) { /* A1, A2 --> B1, B2 */ for (k = 0; k < 4; k++) { temp_0 = A[i + k][j]; temp_1 = A[i + k][j + 1]; temp_2 = A[i + k][j + 2]; temp_3 = A[i + k][j + 3]; temp_4 = A[i + k][j + 4]; temp_5 = A[i + k][j + 5]; temp_6 = A[i + k][j + 6]; temp_7 = A[i + k][j + 7]; B[j][i + k] = temp_0; B[j + 1][i + k] = temp_1; B[j + 2][i + k] = temp_2; B[j + 3][i + k] = temp_3; B[j][i + k + 4] = temp_4; B[j + 1][i + k + 4] = temp_5; B[j + 2][i + k + 4] = temp_6; B[j + 3][i + k + 4] = temp_7; } /* B2 --> B3, A3 --> B2 */ for (k = 0; k < 4; k++) { temp_0 = A[i + 4][j + k]; temp_1 = A[i + 5][j + k]; temp_2 = A[i + 6][j + k]; temp_3 = A[i + 7][j + k]; temp_4 = B[j + k][i + 4]; temp_5 = B[j + k][i + 5]; temp_6 = B[j + k][i + 6]; temp_7 = B[j + k][i + 7]; B[j + k][i + 4] = temp_0; B[j + k][i + 5] = temp_1; B[j + k][i + 6] = temp_2; B[j + k][i + 7] = temp_3; B[j + k + 4][i] = temp_4; B[j + k + 4][i + 1] = temp_5; B[j + k + 4][i + 2] = temp_6; B[j + k + 4][i + 3] = temp_7; } /* A4 --> B4 */ for (k = 4; k < 8; k++) { temp_0 = A[i + k][j + 4]; temp_1 = A[i + k][j + 5]; temp_2 = A[i + k][j + 6]; temp_3 = A[i + k][j + 7]; B[j + 4][i + k] = temp_0; B[j + 5][i + k] = temp_1; B[j + 6][i + k] = temp_2; B[j + 7][i + k] = temp_3; } } }}61 * 67
方法一(推荐): 切分成两块
/* * trans61*67 */char trans_desc6167[] = "Simple transpose func6167";void trans6167(int M, int N, int A[N][M], int B[M][N]){ int i, j; int tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8; /* 61 * 64 */ for (i = 0; i < (M/8)*8; i += 8) { for (j = 0; j < N; i++) { tmp1 = A[j][i]; tmp2 = A[j][i + 1]; tmp3 = A[j][i + 2]; tmp4 = A[j][i + 3]; tmp5 = A[j][i + 4]; tmp6 = A[j][i + 5]; tmp7 = A[j][i + 6]; tmp8 = A[j][i + 7]; B[i][j] = tmp1; B[i + 1][j] = tmp2; B[i + 2][j] = tmp3; B[i + 3][j] = tmp4; B[i + 4][j] = tmp5; B[i + 5][j] = tmp6; B[i + 6][j] = tmp7; B[i + 7][j] = tmp8; } } /* 转移剩余的区块 */ for (i = 0; i < N; i++) { for (j = (M/8)*8; j < M; j++) { tmp1 = A[i][j]; B[j][i] = tmp1; } } }
/* * trans61*67 */char trans_desc6167[] = "Simple transpose func6167";void trans6167(int M, int N, int A[N][M], int B[M][N]){ int i, j, k; int temp_0, temp_1, temp_2, temp_3, temp_4, temp_5, temp_6, temp_7; /* 64 * 56 */ for (i = 0; i < 64; i += 8) { for (j = 0; j < 56; j += 8) { /* A1, A2 --> B1, B2 */ for (k = 0; k < 4; k++) { temp_0 = A[i + k][j]; temp_1 = A[i + k][j + 1]; temp_2 = A[i + k][j + 2]; temp_3 = A[i + k][j + 3]; temp_4 = A[i + k][j + 4]; temp_5 = A[i + k][j + 5]; temp_6 = A[i + k][j + 6]; temp_7 = A[i + k][j + 7]; B[j][i + k] = temp_0; B[j + 1][i + k] = temp_1; B[j + 2][i + k] = temp_2; B[j + 3][i + k] = temp_3; B[j][i + k + 4] = temp_4; B[j + 1][i + k + 4] = temp_5; B[j + 2][i + k + 4] = temp_6; B[j + 3][i + k + 4] = temp_7; } /* B2 --> B3, A3 --> B2 */ for (k = 0; k < 4; k++) { temp_0 = A[i + 4][j + k]; temp_1 = A[i + 5][j + k]; temp_2 = A[i + 6][j + k]; temp_3 = A[i + 7][j + k]; temp_4 = B[j + k][i + 4]; temp_5 = B[j + k][i + 5]; temp_6 = B[j + k][i + 6]; temp_7 = B[j + k][i + 7]; B[j + k][i + 4] = temp_0; B[j + k][i + 5] = temp_1; B[j + k][i + 6] = temp_2; B[j + k][i + 7] = temp_3; B[j + k + 4][i] = temp_4; B[j + k + 4][i + 1] = temp_5; B[j + k + 4][i + 2] = temp_6; B[j + k + 4][i + 3] = temp_7; } /* A4 --> B4 */ for (k = 4; k < 8; k++) { temp_0 = A[i + k][j + 4]; temp_1 = A[i + k][j + 5]; temp_2 = A[i + k][j + 6]; temp_3 = A[i + k][j + 7]; B[j + 4][i + k] = temp_0; B[j + 5][i + k] = temp_1; B[j + 6][i + k] = temp_2; B[j + 7][i + k] = temp_3; } } /* top right */ for(j = 56; j < M; j++){ temp_0 = A[i][j]; temp_1 = A[i+1][j]; temp_2 = A[i+2][j]; temp_3 = A[i+3][j]; temp_4 = A[i+4][j]; temp_5 = A[i+5][j]; temp_6 = A[i+6][j]; temp_7 = A[i+7][j]; B[j][i] = temp_0; B[j][i+1] = temp_1; B[j][i+2] = temp_2; B[j][i+3] = temp_3; B[j][i+4] = temp_4; B[j][i+5] = temp_5; B[j][i+6] = temp_6; B[j][i+7] = temp_7; } } /* buttom left */ for (i = 64; i < 67; i++) { for (j = 0; j < 56; j += 8) { temp_0 = A[i][j]; temp_1 = A[i][j + 1]; temp_2 = A[i][j + 2]; temp_3 = A[i][j + 3]; temp_4 = A[i][j + 4]; temp_5 = A[i][j + 5]; temp_6 = A[i][j + 6]; temp_7 = A[i][j + 7]; B[j][i] = temp_0; B[j + 1][i] = temp_1; B[j + 2][i] = temp_2; B[j + 3][i] = temp_3; B[j + 4][i] = temp_4; B[j + 5][i] = temp_5; B[j + 6][i] = temp_6; B[j + 7][i] = temp_7; } } /* buttom right */ for (i = 56; i < 61; i++) { temp_0 = A[64][i]; temp_1 = A[65][i]; temp_2 = A[66][i]; B[i][64] = temp_0; B[i][65] = temp_1; B[i][66] = temp_2; }}资源
https://github.com/WeiLin66/CMU-15-213/tree/main/Labs/cache-lab
微信扫一扫打赏
支付宝扫一扫打赏
