当前位置： 代码迷 >> 综合 >> CSAPP Lab4 实验记录 ---- Cache Lab
  详细解决方案

CSAPP Lab4 实验记录 ---- Cache Lab

热度：81   发布时间：2023-11-17 16:56:13.0

文章目录

    • Lab 总结博客链接
    • 前引
    • Lab4 Cache Lab
      • 1、获取相关Lab材料
      • 2、make 编译错误解决办法（gcc版本过高）
      • 3、Part A: Writing a Cache Simulator
        • 1、Overview
        • 2、Programming Rules for Part A
        • 3、编写 Part A 过程分析
          • 1、处理读入参数
          • 2、处理help -h
          • 3、处理缓冲区部分（仅记录modify_time 标识位）
          • 4、处理trace文件（最终部分）
        • 4、Part A 最终代码实现
        • 5、./csim 最终实现效果
        • 6、./test-csim 验证代码
      • 4、Part B: Optimizing Matrix Transpose
        • 1、无法启动driver.py
        • 2、Overview
        • 3、Solution（转载）
      • 结束语

Lab 总结博客链接

CSAPP Lab入门系统安装摸索 + Lab 博客链接

前引

之前的三个Lab有两个是大一做的 但因为中间觉得自己对于底层的寄存器啊 栈帧 还有一些其他理解确实不是很深入 而且中间看处理器的时候确实觉得太坐牢了 所以大一寒假看CSAPP的时候就没有继续看了 现在重新拾起来 觉得吧 CSAPP确确实实是一本大杂烩 什么都讲 后面还有对于OS 网络编程 虚拟地址 啥都讲

大一那个时候确实年轻气盛啊 hhh 那个时候看CSAPP确实还是挺早的 但是还是硬着头皮积累了很多 现在来看 在看了挺多的底层汇编 自己也动手了很多的底层编程之后 现在而言就没有那么困难了 想起来 当时作为我启蒙的Lab竟然第一个就是CSAPP啊 哈哈

那话还是不多说了 有些内容比如处理器部分 我确实有点点嚼不动啊 而且不是很感兴趣 所以也就选择性的阅读了 相比于看书 重要内容还是要看的 但是我更喜欢做这样的趣味Lab 做这样的Lab真的很好玩啊 哈哈

Lab4 Cache Lab

1、获取相关Lab材料

因为我有点时候也找不到在哪里下载Lab材料 所以这里为了方便大家 还是给一下链接吧
CSAPP 配套Lab下载 Self-Study Handout

然后我们直接解压了 然后再把文档中的pdf给下载下来 下面放一下pdf的截图 那实验前的材料我们就准备好了

在这里插入图片描述

2、make 编译错误解决办法（gcc版本过高）

这个问题卡了我好久 - - 在我发现大家都没有出现这个问题的时候 我这边make 就会报错 刚开始我认为是我需要修改那些文件 但是之后发现还是不行

之后无奈我又把文件在CentOS7 下载解压了一次 然后make 就发现可以正常编译 之后用gcc -v查看gcc版本 就发现那边的gcc版本为4.6 而我这边Ubuntu的版本为8.0 之前就因为编译器的问题出过问题 这次我认为还是编译器的问题

sudo update-alternatives --config gcc 更换gcc版本
然后手动选择版本 我们选择了gcc-4.6之后就可以正常编译了

在这里插入图片描述

我们输入make 看看是否能够成功编译了 成功
在这里插入图片描述

3、Part A: Writing a Cache Simulator

1、Overview

很多很懵比的hxd 刚开始拿着文档的时候不知所云 哈哈 这是正常的 因为没有多少人看一下文档就明白Lab需要做什么的 都需要仔细看个好几遍 才能大概知道需要编译的命令 和 我们需要做什么

那我就先这里说一下我们的PartA 要干嘛 要做什么 要用什么命令
我们可以先试一下 输入一下
./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace 就会看到下面出现这样的文字

hits:4 misses:5 evictions:3
hit 即命中缓存数 misses 即没有命中缓存数 evictions 即没有命中miss后 利用LRU机制替换掉了其他缓存字节 如果有空位的话 就不会计入

我们还可以试一下 下面的命令
./csim-ref -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

L 即Load 从内存读取数据
S 即Save 向内存写入数据
M 即Modify 修改数据 可以理解为 Load了一次 Save了一次

I.E M 12,1 miss eviction hit 即先Load 发现没有数据 则把数据放进缓冲区 而因为缓冲区组没有空余的缓冲块了 则把一个最久最少用的数据给丢弃 换成这个 而Save的时候 发现已经在内存中了 则直接Hit了

当然也可以出现 M 12,1 hit hit的情况 对于M的处理后面会说

上面对于上面的情况进行了部分的分析 相信大家有个大概模糊的概念 我们的Part A就是要模仿 csim-ref的功能 从零开始写 包括参数的读入 缓冲区的模拟 输入hit miss eviction数

哈哈 大家不要担心 我们不需要完全模拟缓冲区 因为我们不返回数据的 只需要存储一些数据就好了 也没有那么难的 大致和大家说了一下 然后lets continue

2、Programming Rules for Part A

这里再讲一下Part A的细节

? -h : Optional help flag that prints usage info（help 对于此实验没啥用 哈哈）
? -v : Optional verbose flag that displays trace info （这个也没有什么用）
? -s : Number of set index bits (S = 2^s （s 即 标识位的位数 2^s即组数）
is the number of sets)
? -E : Associativity (number of lines per set) （一组 几个缓冲块数）
? -b : Number of block bits (B = 2^b is the block size) (块偏移位数 2^b缓冲块字节数）
? -t : Name of the valgrind trace to replay （文件路径）

下面是机翻的注意事项

  1. 您的csim .c 文件必须编译而不发出警告才能获得信用。

  2. 您的模拟器必须正确工作任意 s， E和 b.这意味着您需要使用maloc功能为模拟器的数据结构分配存储空间。键入"人马洛克"，了解有关此功能的信息。

  3. 对于此实验室，我们只对数据缓存性能感兴趣，因此您的模拟器应忽略所有指令缓存访问（以"I"开始的行）。回想一下，Valgrind总是将"I"放在第一列（没有前面的空间），在第二列中将"M"、"L"和"S"放在第二列（前面的空间）中。这可能有助于您解析痕迹。

  4. 要获得 A 部分的信用，您必须在主函数结束时调用功能打印"Summary"，其中总点击次数、错过次数和驱逐次数：
    打印苏米（hit_count、miss_count、eviction_count）：

  5. 对于此实验室，您应该假设内存访问正确对齐，以便单个内存访问永远不会跨越阻止边界。通过做出此假设，您可以忽略 Valgrind痕迹中的请求大小。

我们Part A负责编写csim.c 基本上就是从零开始模仿csim-ref的程序输出 我们中间还需要导入参数 处理模拟valgrind的操作记录文件 最后利用给定的参数 模拟缓冲区 输出hit miss eviction数 我们最后也是根据这个来看程序是否成功编写

3、编写 Part A 过程分析

1、处理读入参数

这部分就直接给代码吧 一个部分一个部分给^^ 一些地方会给注释

int main(int argc,char* argv[]) //argc参数个数 argv[]参数指针
{
    int index_bits = 0,lines_per_set = 0,block_bits = 0;char* parse_path = NULL;bool read_file = false,v_flag = false,h_flag = false;int i;for(i = 1;i < argc;++i) // argv[0] == ./csim{
    if(argv[i][0] != '-')	continue; switch(argv[i][1]){
    case 'h':h_flag = true;break;case 'v':v_flag = true;break;case 's':index_bits = atoi(argv[i+1]); // sbreak;case 'E':lines_per_set = atoi(argv[i+1]); // Ebreak;case 'b':block_bits = atoi(argv[i+1]); // bbreak;case 't':parse_path = argv[i+1]; break;//路径 例如traces/yi.trace //处理文件采用 相对路径default:	break;}if(h_flag) break; //help flag}
2、处理help -h
if(h_flag){
    printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file> \n\ Options:\n\-h Print this help message.\n\-v Optional verbose flag.\n\-s <num> Number of set index bits.\n\-E <num> Number of lines per set.\n\-b <num> Number of block offset bits.\n\-t <file> Trace file.\n\n\ Examples:\n\linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n\linux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");return -1;}
3、处理缓冲区部分（仅记录modify_time 标识位）
struct set_cache
{
    bool* used_blocks;   //是否使用过unsigned long* identify_bits; //标识位int* modified_time;  //用于LRU剔除
};//malloc cache sizeint S = (int)pow(2,index_bits);struct set_cache cache[S];for(i = 0;i < S;++i){
    cache[i].used_blocks = (bool*)malloc(sizeof(bool) * lines_per_set);cache[i].identify_bits = (unsigned long*)malloc(sizeof(unsigned long*) * lines_per_set);cache[i].modified_time = (int*)malloc(sizeof(int) * lines_per_set);memset(cache[i].used_blocks,0,sizeof(char*) * lines_per_set);memset(cache[i].identify_bits,0,sizeof(long) * lines_per_set);memset(cache[i].modified_time,0,sizeof(int) * lines_per_set);}//deal with set_seq//如果b为16 s为16 则 set_seq = 0x00 00 00 00 ff ff 00 00//确认用于哪一组的unsigned long set_seq = ((unsigned long)1 << index_bits) - 1;set_seq <<= block_bits; //deal with identify seq//标识位 例如b为16 s为16 iden_seq = 0xff ff ff ff 00 00 00 00 unsigned long iden_seq = ((unsigned long)1 << (64 - (index_bits + block_bits))) - 1;iden_seq <<= (index_bits + block_bits);
4、处理trace文件（最终部分）
//deal with file if cant find breakFILE* fp;if((fp = fopen(parse_path,"r")) == NULL)	return -1;//deal with filechar num[20] = {
    0};char* endpos = NULL; //for strtolint time_stamp = 0; //LRU 需要记录操作顺序的 用来剔除最早的do{
    ++time_stamp;bool first_hit = false,second_hit = false,miss_flag = false,eviction_flag = false;memset(num,0,sizeof(char) * 20);memset(file_str,0,sizeof(char) * 30);//get per rowread_file = (fgets(file_str,MAX_BYTES_PER_ROW,fp) != NULL); if(!read_file) break;int pos = 3,save_pos = 0;char operation = '\0'; // 'L' 'M' 'S'unsigned long address = 0,op_bytes = 0; //deal with addresswhile((file_str[pos] >= '0' && file_str[pos] <= '9') || (file_str[pos] >= 'a' && file_str[pos] <= 'z'))num[save_pos++] = file_str[pos++];address = strtol(num,&endpos,16); //64位address++pos;//deal with op_bytesop_bytes = atoi(file_str+pos);//deal with operatoroperation = file_str[1];if(operation == ' ') continue; //忽略 I 开头的 cpu操作//get seq 确认组号unsigned long seq = (unsigned long)(address & set_seq) >> (block_bits);  //deal with operationbool flag = false; //记录是否hitfor(i = 0;i < lines_per_set;++i){
    if(cache[seq].used_blocks[i] && cache[seq].identify_bits[i]  == ((unsigned long)(address & iden_seq)) >> (index_bits + block_bits)){
    flag = true;++hit_count,first_hit = true;cache[seq].modified_time[i] = time_stamp;break;}}   if(!flag){
    ++miss_count,miss_flag = true; //miss了int min_time_stamp = INT_MAX,pos = 0;bool empty_flag = false;for(i = 0;i < lines_per_set;++i) //看看是否有空位可以插入{
    if(!cache[seq].used_blocks[i]){
    pos = i;empty_flag = true;break; }if(cache[seq].modified_time[i] < min_time_stamp){
    min_time_stamp = cache[seq].modified_time[i];pos = i;}}cache[seq].modified_time[pos] = time_stamp;cache[seq].used_blocks[pos] = true;cache[seq].identify_bits[pos] = ((unsigned long)(address & iden_seq)) >> (index_bits + block_bits);  if(!empty_flag)	++eviction_count,eviction_flag = true;}if(operation == 'M') ++hit_count,second_hit = true; //如果是M 直接++hitif(v_flag) //按照csim-ref -v要输出每个操作的hit miss{
    printf("%c %lx,%ld",operation,address,op_bytes);if(miss_flag) printf(" miss");if(eviction_flag) printf(" eviction");if(first_hit) printf(" hit");if(second_hit) printf(" hit");printf("\n");}} while(1);fclose(fp);//关闭文件指针printSummary(hit_count,miss_count,eviction_count);

4、Part A 最终代码实现

实现代码如下 ^^

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include "cachelab.h"#define true 1
#define false 0
#define MAX_BYTES_PER_ROW 30
typedef char bool;struct set_cache
{
    bool* used_blocks; // not needunsigned long* identify_bits;int* modified_time;
};int hit_count = 0,miss_count = 0,eviction_count = 0;int main(int argc,char* argv[])
{
    int index_bits = 0,lines_per_set = 0,block_bits = 0;char* parse_path = NULL,*file_str = (char*)malloc(sizeof(char) * 30);memset(file_str,0,sizeof(char)* 30);bool read_file = false,v_flag = false,h_flag = false;int i;for(i = 1;i < argc;++i) // argv[0] == ./csim{
    if(argv[i][0] != '-')	continue; switch(argv[i][1]){
    case 'h':h_flag = true;break;case 'v':v_flag = true;break;case 's':index_bits = atoi(argv[i+1]);break;case 'E':lines_per_set = atoi(argv[i+1]);break;case 'b':block_bits = atoi(argv[i+1]);break;case 't':parse_path = argv[i+1];break;default:	break;}if(h_flag) break;}if(h_flag){
    printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file> \n\ Options:\n\-h Print this help message.\n\-v Optional verbose flag.\n\-s <num> Number of set index bits.\n\-E <num> Number of lines per set.\n\-b <num> Number of block offset bits.\n\-t <file> Trace file.\n\n\ Examples:\n\linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n\linux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");return -1;}//deal with file if cant find breakFILE* fp;if((fp = fopen(parse_path,"r")) == NULL)	return -1;//malloc cache sizeint S = (int)pow(2,index_bits);struct set_cache cache[S];for(i = 0;i < S;++i){
    cache[i].used_blocks = (bool*)malloc(sizeof(bool) * lines_per_set);cache[i].identify_bits = (unsigned long*)malloc(sizeof(unsigned long*) * lines_per_set);cache[i].modified_time = (int*)malloc(sizeof(int) * lines_per_set);memset(cache[i].used_blocks,0,sizeof(char*) * lines_per_set);memset(cache[i].identify_bits,0,sizeof(long) * lines_per_set);memset(cache[i].modified_time,0,sizeof(int) * lines_per_set);}//deal with set_sequnsigned long set_seq = ((unsigned long)1 << index_bits) - 1;set_seq <<= block_bits; //deal with identify sequnsigned long iden_seq = ((unsigned long)1 << (64 - (index_bits + block_bits))) - 1;iden_seq <<= (index_bits + block_bits);//deal with filechar num[20] = {
    0};char* endpos = NULL;int time_stamp = 0;do{
    ++time_stamp;bool first_hit = false,second_hit = false,miss_flag = false,eviction_flag = false;memset(num,0,sizeof(char) * 20);memset(file_str,0,sizeof(char) * 30);//get per rowread_file = (fgets(file_str,MAX_BYTES_PER_ROW,fp) != NULL); if(!read_file) break;int pos = 3,save_pos = 0;char operation = '\0';unsigned long address = 0,op_bytes = 0;//deal with addresswhile((file_str[pos] >= '0' && file_str[pos] <= '9') || (file_str[pos] >= 'a' && file_str[pos] <= 'z'))num[save_pos++] = file_str[pos++];address = strtol(num,&endpos,16);++pos;//deal with op_bytesop_bytes = atoi(file_str+pos);//deal with operatoroperation = file_str[1];if(operation == ' ') continue;//get sequnsigned long seq = (unsigned long)(address & set_seq) >> (block_bits);  //deal with operationbool flag = false;for(i = 0;i < lines_per_set;++i){
    if(cache[seq].used_blocks[i] && cache[seq].identify_bits[i]  == ((unsigned long)(address & iden_seq)) >> (index_bits + block_bits)){
    flag = true;++hit_count,first_hit = true;cache[seq].modified_time[i] = time_stamp;break;}}   if(!flag){
    ++miss_count,miss_flag = true;int min_time_stamp = INT_MAX,pos = 0;bool empty_flag = false;for(i = 0;i < lines_per_set;++i){
    if(!cache[seq].used_blocks[i]){
    pos = i;empty_flag = true;break; }if(cache[seq].modified_time[i] < min_time_stamp){
    min_time_stamp = cache[seq].modified_time[i];pos = i;}}cache[seq].modified_time[pos] = time_stamp;cache[seq].used_blocks[pos] = true;cache[seq].identify_bits[pos] = ((unsigned long)(address & iden_seq)) >> (index_bits + block_bits);  if(!empty_flag)	++eviction_count,eviction_flag = true;}if(operation == 'M') ++hit_count,second_hit = true;if(v_flag){
    printf("%c %lx,%ld",operation,address,op_bytes);if(miss_flag) printf(" miss");if(eviction_flag) printf(" eviction");if(first_hit) printf(" hit");if(second_hit) printf(" hit");printf("\n");}} while(1);fclose(fp);printSummary(hit_count,miss_count,eviction_count);return 0;
}

5、./csim 最终实现效果

输入命令./csim -v -s 4 -E 1 -b 4 -t traces/yi.trace
实现效果与./csim-ref一样
在这里插入图片描述

输入命令./csim -h -v -s 4 -E 1 -b 4 -t traces/yi.trace 含有-h
实现效果与./csim-ref一样
在这里插入图片描述

输入命令 ./csim -v -s 4 -E 1 -b 4 -t traces/long.trace long trace
实现效果与./csim-ref一样

在这里插入图片描述

在这里插入图片描述

6、./test-csim 验证代码

输入命令./test-csim
成功 ^^
在这里插入图片描述

4、Part B: Optimizing Matrix Transpose

1、无法启动driver.py

该python脚本语言由python2的语法做的 所以我们还需要把解释器更改版本为2.X - - 我的系统默认版本为3.7
在这里插入图片描述

Linux安装Python2.7
然后进入driver.py修改运行解释器路径 #!/usr//bin/python2.7.9

最后测试一下 ./driver.py 成功运行

在这里插入图片描述

2、Overview

对于 Part B 确实很抱歉 Forgive Me我没有什么思路 而且也不是很感兴趣 - - 就没有继续做了 主要是没有什么思路 这部分的话 我就讲一下 任务大概是什么

我们就修改一个函数就行了 在trans.c中
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
在这里插入图片描述

我们的目标是 对于矩阵A[N][M] 我们转置一下 把每个 A[i][j]放入B[j][i] 最后就转置为了B[M][N] 在其期间 我们只能使用12个局部变量 尽量少的miss 我们的缓冲区参数为 s 5 E 1 b 5也就是 32组 2^5 32字节的缓冲区

3、Solution（转载）

这部分的话 大家去看一下这个博客吧 我确实没什么思路 也不是很感兴趣 - - 觉得太绕了 这篇博客写的很好 大家感兴趣就去做做 哈哈 那一Lab就到这里啦
CSAPP:CacheLab实验 博主：大白不白

结束语

尽管我自己一个人花了大概一个下午一个晚上做出来了Part A（在床上边躺着边做） 最后的Part B没有做出来 但是还是觉得这个Lab挺好玩的 对缓冲区又有了个概念和印象 虽然很可惜第二部分没有做出来 哈哈 也不在意这个了 CSAPP的Lab真的很不错 这两天在休息 所以就在床上躺着做Lab 待会小组赛RNG又要打比赛了 我等了好几天 一定得去看看 今晚打三把 希望能够拿下

那我们有缘下个Lab再见啦！

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.