CSAPP 实验IV CacheLab

发表于 2024-03-09 更新于 2024-04-13 分类于 csapp 阅读次数：

自己实现一个模拟cache缓存，优化转置矩阵函数减少不命中次数

更新历史

24.03.09：初稿

系列

任务目标

CacheLab实验，第一部分需要模拟Cache计算命中，未命中次数，第二部分实现代码优化，减少未命中次数。

题目及解法

Part A Writing a Cache Simulator

完成csim.c文件，使用valgrind生成测试数据，输出命中，未命中和替换次数，输出格式为hits:4 misses:5 evictions:3。

答案

#define MaxSetbits 5
#define MaxLine 4
#define MaxBytebits 5

typedef struct Myline{
  int valid; //有效位
  unsigned long int tag;   //tag标记  十进制
  int lru_num;   // 最近使用标记 0 - (E - 1)
}Myline;
typedef struct Mycache{
  int S;            // set 大小
  int E;            // line 大小
  int B;            //偏移大小
  int size_Tag;     // tag bits = 64 - s- b
  Myline **set;    //set数组
}Mycache;



//get command line arguments
//p_s s的指针   p_E E的指针   p_b b的指针    fn 文件名
void Mygetopt(int argc, char *argv[], int *p_s, int *p_E, int *p_b, char *fn, int *flag_v);   
//16进制转换十进制
unsigned long int Hex2dec(char *hex);
//返回tag
unsigned long int GetDecTag(unsigned long int dec, int s, int b);
//返回组号
int GetDecSetNum(unsigned long int dec, int s, int b);
//返回这个dec地址下当前偏移量开始剩余的字节数
int GetDecRestByte(unsigned long int dec, int s, int b, int B);
//初始化set
void Initset(Mycache *mc);
//处理最近未使用
int GetminLRU(Myline *set, int E);
//是否set满了
int IsFullSet(Myline *set, int E);
//命中处理  
void HitDeal(Myline *set, int E, int Eindex);
//未命中 加载cache
// 有空余line加载
void MissLoadDeal(Myline *set, int E, int Eindex, unsigned long int dec_tag);
//line替换
void MissEvictionDeal(Myline *set, int E, int delindex, unsigned long int dec_tag);
//访问处理   返回1 hit   2  miss  3 miss eviction
int LoadDeal(Myline *set, int E, unsigned long int now_tag, int flag_v);
void StoreDeal(Myline *set, int E, unsigned long int now_tag, int flag_v);
void ModifyDeal(Myline *set, int E, unsigned long int now_tag, int flag_v);

int main(int argc, char *argv[]) {
  FILE *fp;
  int hit_count, miss_count, eviction_count;
  int s, E, b;
  int flag_v = 0;     //opt v 的标记
  char *file_name;
  char optcache = ' ';
  char ignorechar = ' ';
  char hex[65] = "";
  int size = 0;        //个数
  unsigned long int dec;

  hit_count = 0;
  miss_count = 0;
  eviction_count = 0;
  Mycache cache;
  file_name = (char *)malloc(sizeof(char) * 30);
  Mygetopt(argc, argv, &s, &E, &b, file_name, &flag_v);
  cache.S = pow(2, s);
  cache.E = E;
  cache.B = pow(2, b);
  cache.size_Tag = 64 - s - b;
  Initset(&cache);

  fp = fopen(file_name, "r");
  while(fscanf(fp, " %c %[^,]%c%d", &optcache, hex, &ignorechar, &size) != -1){
    if(optcache == 'I'){
      fscanf(fp, "%c", &ignorechar);
      continue;
    }
    if(flag_v == 1){
      printf("%c %s,%d", optcache, hex, size);
    }
    dec = Hex2dec(hex);
    //========处理内存访问
    int setnum = 0;  //组号
    int flag_kind = 0;   //cache 类型   hit miss  
    unsigned long int dectag = 0;
    //int restbyte = 0;  // 当前偏移量下剩余的字节数
    //int loadbyte = 0;  //已加载的字节数
    unsigned long int loaddec = dec;   //当前加载的地址
    setnum = GetDecSetNum(loaddec, s, b);
    dectag = GetDecTag(loaddec, s, b);
    //restbyte = GetDecRestByte(loaddec, s, b, cache.B);   //剩余加载的字节数
    flag_kind = LoadDeal(cache.set[setnum], E, dectag, flag_v);
    /*loadbyte += restbyte;
    loaddec += restbyte;   //当前地址加上剩余字节数  如果加载字节数不够  这就是下一个加载地址
    while(loadbyte < size){
      setnum = GetDecSetNum(loaddec, s, b);
      dectag = GetDecTag(loaddec, s, b);
      LoadDeal(cache.set[setnum], E, dectag, flag_v);
      loadbyte += cache.B;
      loaddec += cache.B;
    }*/
    if(flag_kind == 1){
      hit_count++;
      if(flag_v == 1){
        printf(" hit");
      }
    }
    else{
      if(flag_kind == 2){
        miss_count++;
        if(flag_v == 1){
          printf(" miss");
        }
      }
      else{
        miss_count++;
        eviction_count++;
        if(flag_v == 1){
          printf(" miss eviction");
        }
      }
    }
    if(optcache == 'M'){
      hit_count++;   //修改  store一定hit
      if(flag_v == 1){
        printf(" hit\n");
      }
    }
    else{
      if(flag_v == 1){
        printf("\n");
      }
    }


    //=====================
    fscanf(fp, "%c", &ignorechar);
  }


  printSummary(hit_count, miss_count, eviction_count);
  return 0;
}

void Mygetopt(int argc, char *argv[], int *p_s, int *p_E, int *p_b, char *fn, int *flag_v){
  int opt;
  while ((opt = getopt(argc, argv, "vh:s:E:b:t:")) != -1) {
    switch (opt) {
      case 's':
        *p_s = atoi(optarg);
        break;
      case 'E':
        *p_E = atoi(optarg);
        break;
      case 'b':
        *p_b = atoi(optarg);
        break;
      case 't':
        strcpy(fn, optarg);
        break;
      case 'v':
        *flag_v = 1;
        break;
    }
  }
}

unsigned long int Hex2dec(char *hex){
  int len = strlen(hex);
  unsigned long int dec = 0;
  int pow16 = 1;
  for(int i = len - 1; i >= 0; i--){
    if(isdigit(hex[i])){
      dec += (hex[i] - '0') * pow16;
    }
    else{
      dec += (hex[i] - 87) * pow16;
    }
    pow16 *= 16;
  }
  return dec;
}
unsigned long int GetDecTag(unsigned long int dec, int s, int b){
  return dec >> (s + b);
}
int GetDecSetNum(unsigned long int dec, int s, int b){
  int setbits = (1 << s);
  setbits = ~(~setbits + 1);
  dec = dec >> (b);
  return dec & setbits;   //返回set组号
}
int GetDecRestByte(unsigned long int dec, int s, int b, int B){
  int Bytebits = 1 << b;
  Bytebits = ~(~Bytebits + 1);
  dec = dec & Bytebits;   //剩余偏移量
  return B - dec;  //返回剩余的字节数
}
void Initset(Mycache *mc){
  int S = (*mc).S;
  int E = (*mc).E;
  (*mc).set = (Myline **)malloc(sizeof(Myline *) * S);

  for(int i = 0; i < S; i++){
    (*mc).set[i] = (Myline *)malloc(sizeof(Myline) * E);
  }
  for(int i = 0; i < (*mc).S; i++){
    for(int j = 0; j < (*mc).E; j++){
      (*mc).set[i][j].valid = 0;  //有效位为0
      (*mc).set[i][j].lru_num = 0;
    }
  }
}
int GetminLRU(Myline *set, int E){
  int min = 1000;
  int k = 0;
  for(int i = 0; i < E; i++){
    if(set[i].valid == 0){   // 如果存在一个无效位置 直接返回
      k = i;
      break;  
    }
    if(set[i].lru_num < min){  
      min = set[i].lru_num;
      k = i;
    }
  }
  return k;
}


int IsFullSet(Myline *set, int E){
  for(int i = 0; i < E; i++){
    if(set[i].valid == 0){
      return 0;
    }
  }
  return 1;
}
void HitDeal(Myline *set, int E, int Eindex){
  int nowLRU = set[Eindex].lru_num;
  //把比现在要访问的cache set中lrunum大的全部减一  
  for(int i = 0; i < E; i++){
    if(set[i].lru_num > nowLRU){
      set[i].lru_num--;
    }
  }
  set[Eindex].lru_num = E - 1;  //最新访问的cache LRU设置为最大
}
void MissLoadDeal(Myline *set, int E, int Eindex, unsigned long int dec_tag){

  //把比现在要访问的cache set中lrunum大的全部减一  
  for(int i = 0; i < E; i++){
    if(set[i].lru_num > 0){
      set[i].lru_num--;
    }
  }
  set[Eindex].tag = dec_tag;
  set[Eindex].valid = 1;  
  set[Eindex].lru_num = E - 1;  //最新访问的cache LRU设置为最大
}

void MissEvictionDeal(Myline *set, int E, int delindex, unsigned long int dec_tag){
  //将要替换的line命中  改为最近访问过,然后再替换掉tag值
  HitDeal(set, E, delindex);
  set[delindex].tag = dec_tag;
}
int LoadDeal(Myline *set, int E, unsigned long int now_tag, int flag_v){
  int i = 0;
  for(i = 0; i < E; i++){
    if(set[i].tag == now_tag && set[i].valid == 1){
      HitDeal(set, E, i);
      break;
    } 
  }
  if(i == E){
    int Lindex = GetminLRU(set, E);
    if(IsFullSet(set, E) == 1){
      //满的  替换
      MissEvictionDeal(set, E, Lindex, now_tag);
      return 3;
    }
    else{
      MissLoadDeal(set, E, Lindex, now_tag);
      return 2;
    }
  }
  else{
    return 1;
  }
}
void StoreDeal(Myline *set, int E, unsigned long int now_tag, int flag_v){
  //Store 相当于 Load

}
void ModifyDeal(Myline *set, int E, unsigned long int now_tag, int flag_v){
  //int kind = LoadDeal(set, E, now_tag,flag_v);
}

Part B Optimizing Matrix Transpose

完成trans.c文件，实现一个转置矩阵代码transpose_submit，尽可能少的产生cache未命中。

思路

数据是对齐的，所以一个cache行包含32个字节，存储8个int数据，cache能存储256个int数据，根据~~3B^2 << C，块长为B=8~~。根据2B^2 << C，块长<=11，由于cache行可以存8个数据，所以选择块长8。

以32*32的矩阵为例，除了处于对角线上的块会产生冲突不命中，其他块都可以优化不命中情况

以上这种情况对32*32是成立的，64*64和61*67不成立，所以重新思考了这道题的解法，根据data lab中数据的操作都是在内存中进行的。

数组的首地址给出后，行优先数据为一维连续存储形式

这道题可以转换为数组A[N][M]在内存中连续存放，每一个位置x的数根据相同的转换方式保存到数组B[M][N]的位置y，转换公式为i_a = x / M，j_a = x % M，y = j_a * N + i_a * M。于是存储公式为B(y) = A(x)。

示意图如上，cache行存2个数据，3*3的数组中，无法直观看出内存区别，而cache的分块目的是为了在内存中读取到cache时减少miss次数，所以我们根据内存进行重排数组，改为5*2的数组。

所以这道题可以把数组转换为32列的任意数组，由于一行只有32列，远远小于cache的容量256个数据，所以相邻行的上下两个数据不会映射的同一个cache行。

需要把文件放入linux的文件夹中，如果在共享文件夹中会出现运行超时。

32 x 32

基本步骤：

重排数组
处理AB数组中x，y映射相同的位置，先用局部变量保存，然后处理这一行的其他数据，最后保存在B数组的中，cache行自动换出。

分析原因

当A[i][j]与B[j][i]的cache映射相同set内时，取出A[i][j]中的值，写入B数组时会换出A的cache行，导致下次访问A的同一行cache数据时需要继续换出一次。

解决办法

用局部变量保存访问冲突的值，等循环结束后，在写入B中。

计算所在行，x表示数组一维连续内存的位置(0开始)，cache 组号s=（x%256 ) / 8;

结果

void main(int M, int N, int A[N][M], int B[M][N]) {
  //int t_1, t_2, t_3;
  int t_4, t_5;
  int i, j, ii, jj;
  for (i = 0; i < N; i += 8) {
    for (j = 0; j < M; j += 8) {
      for (ii = i; ii < ((i + 8) < N ? i + 8 : N); ii++) {
        //标记没有访问冲突
        t_4 = -1;
        for (jj = j; jj < ((j + 8) < M ? j + 8 : M); jj++) {
          if (ii * M + jj == jj * N + ii) {
            if (t_4 == -1) {
              t_4 = ii;
              t_5 = jj;
            }
            continue;
          }
          // printf("**  2-- %d  3--  %d\n", t_2, t_3);
          B[jj][ii] = A[ii][jj];
        }
        if (t_4 != -1) {
          B[t_5][t_4] = A[t_4][t_5];
        }
      }
    }
  }
}

miss数量287，满分

64 x 64

出现一个cache行中两次相同映射的问题

分析原因

在32 x 32的数组中，一个cache行为8，块为8x8，一个cache行最多只有对角线的的一个元素冲突miss，但是64x64的数组中，8x8的块中，前四行与后四行冲突miss，所以一个cache行的8个数据中，最多有两个元素冲突miss

解决办法

继续添加一个局部变量记录冲突位置，一行遍历完后再处理。

继续出现了只遍历到了32，在64 X 64的数组转换为32列时，行数为128。

miss数量为4611，还需要继续调低。

分析原因

~~错误答案~~

64X64中，改了内存排列后，第二行与第一行的转置不在同一cache行内。

按照左上右上，左下，右下顺序。

结果

分析原因

没有拿到满分，按照上下划分为两个4X8的数组

下边的4X8数组，一行中的后四列在B数组中会cache冲突行，如图

注意：

上四行转置之后，B数组的下四行正在cache中，为了不换出，先转置A数组的右下，再左下。

结果

减少到1547，但是还没有满分。

继续修改

题目要求减少miss数量，可以利用cache中空闲的地方保存数据最后在替换出去

如图，A的上半部分的后四列存到B的后四列中

下半部分的第一列，先把B数组的第一行后四列保存到下部分的第一行，这样第一个cache就替换完成，依次完成其他行，最后把右下角转置过去。

结果

miss数1339，差39次满分，没有找到优化位置。

61 X 67

结果

最终得分

拿到了51.5分，之后有时间再来查代码优化的地方。

CSAPP 实验IV CacheLab

系列

任务目标

相关内容

题目及解法

Part A Writing a Cache Simulator

相关内容

答案

Part B Optimizing Matrix Transpose

相关内容