CSAPP cache lab(一)

发表于 | 更新于 | 分类于 | 热度：
本文字数： 1.2k | 阅读时长 ≈ 1 分钟

1. Cache

Cache的内部组织结构如下图所示。Cache共有S组，每组E行，每行包括一个有效位(valid bit)，一个标签和B比特数据。当E=1时，称为直接映射，当E > 1时，称为E路组相连。

在这里插入图片描述

内存地址由标签（tag）、组索引（set index）、块偏移（block offset）三个部分组成。假设指令长度为m，则t=m-b-s，Cache存储的数据总量为S*B*E。

缓存未命中的原因有以下三种：

  • Cold (compulsory) miss 。首次访问cache必然导致未命中。

  • Conflict miss 。缓存还有大量的空余空间，但是多个数据对象被映射到相同的缓存块组，导致数据对象被交替换出。

  • Capacity miss。需要缓存的数据块超过了缓存的存储空间。

2. Cache 模拟程序

程序要求：

  • 不存储内存数据。
  • 不使用块偏移量-地址中的b位不会被置位。
  • 缓存模拟器需要在运行中指定的不同s，b，E工作。
  • 使用LRU算法，从缓存中逐出最近最少使用的块，以便为下一个块腾出空间。

2.1 测试数据

测试文件中的数据记载着每一次对内存的操作，前面的字母代表操作类型，统一的格式是:

[空格][操作类型][空格][内存地址][逗号][大小]

其中如果第一个不是空格而是I，则代表加载，没有实际意义。

操作类型有以下三种：

L：读取，从内存中读取
S：存储，向内存中存储
M：修改，这涉及一次读取，一次存储操作

地址指的是一个 64 位的 16 进制内存地址；大小表示该操作内存访问的字节数
其中I指令无空格，M/S/L指令前有1个空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

I  04ead900,3
I  04ead903,3
I  04ead906,5
I  04ead838,3
I  04ead83b,3
I  04ead83e,5
 L 1ffefff968,8
I  04ead843,3
I  04ead846,3
I  04ead849,5
 L 1ffefff960,8
I  04ead84e,3
I  04ead851,3
......

实验指导提供了一个样例可执行文件csim-ref，我们要做的就是写出一个和它功能一样的程序。

在这里插入图片描述

执行一个示例，结果如下。

在这里插入图片描述

除此之外，实验指导还提供三个函数帮助完成实验，分别是getopt、fscanf、malloc 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//getopt
int main(intargc, char** argv){ 
    int opt,x,y;     
    /* looping over arguments */ 
    while(-1 != (opt = getopt(argc, argv, "x:y:"))){

    /* determine which argument it’s processing */ 

        switch(opt) { 
         case 'x': x = atoi(optarg);
            break;             
         case 'y': y = atoi(optarg);
            break;             
         default: printf("wrong argument\n"); 
            break;         
         }     
    } 
}

getopt用于获取命令行参数，fscanf 读入测试文件内容，malloc 分配空间给cache。

3. 代码实现

3.1 Cache基本单元

定义Cache基本单元为struct cache_line,不要求存储内存数据，所以没有设置块偏移量。

1
2
3
4
5
6
typedef struct
{
  unsigned long tag;            /* 主存标记 */
  int valid;                    /* 有效位 */
  clock_t time_stamp;           /* 时间戳实现LRU算法 */
}cache_line;

3.2 解析命令行参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

 while((input=getopt(argc,argv,"s:E:b:t:vh")) != -1)
   {
     has_opt = 1;
     switch(input){
     case 's':
s = atoi(optarg);
break;
     case 'E':
E = atoi(optarg);
break;
     case 'b':
b = atoi(optarg);
break;
     case 't':
t = optarg;
break;
     case 'v':
v = 1;
break;
     case 'h':
print_usage();
exit(0);
     default:
print_usage();
exit(-1);
     }
   }
 if(!has_opt){
   printf("./csim: Missing required command line argument\n");
   print_usage();
   return 0;
 }

3.3 缓存处理

  • 使用位移解析内存地址中的组号和标签。
  • 使用hit_or_miss函数读取缓存的数据，返回命中或者没有命中。
  • 如果没有命中使用函数put_in_cache将该内存块放入缓存，并检查是否产生eviction。
  • 如果缓存中有空间，将内存块直接放入，如果没有，使用LRU算法进行置换，并且标识产生了eviction。
  • 统计所有的miss数量和eviction数量。

完整实验代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "unistd.h"
#include "getopt.h"
#include "time.h"
#include "cachelab.h"

typedef struct
{
  unsigned long tag;            /* 主存标记 */
  int valid;                    /* 有效位 */
  clock_t time_stamp;           /* 时间戳实现LRU算法 */
}cache_line;

cache_line** initiate(int set_index_bits, int associativity){
  /* 初始化 cache_line 二维数组 cache 并分配空间 */
  int i;
  int sets = 1 << set_index_bits;
  unsigned int size;
  cache_line** cache;
  cache = (cache_line** ) malloc(sizeof(cache_line) * sets);
  for(i=0;i<sets;i++)
    {
      size = sizeof(cache_line) * associativity;
      cache[i] = (cache_line* ) malloc(size);
      /*  memset 初始化内容全为0*/
      memset(cache[i], 0, size);
    }
  return cache;
}

int clean(cache_line** c, int set_index_bits){
  /* cache_line 二维数组的清理工作 */
  int i;
  int sets = 1 << set_index_bits;
  for(i=0;i<sets;i++)
    {
      free(c[i]);
    }
  free(c);
  return 0;
}

int hit_or_miss(cache_line* line, int line_length, unsigned long add_tag){
  /* hit: 1, miss: 0 */
  int i, result = 0;
  for(i=0;i<line_length;i++)
    {
      if((add_tag == line[i].tag) && (line[i].valid == 1))
	{
	  result = 1;
	  line[i].time_stamp = clock(); /* 如果 hit 的话,更新时间戳 */
	  break;
	}
    }
  return result;
}

int put_in_cache(cache_line* line, int line_length, unsigned long add_tag){
  /* no eviction: 0, eviction: 1 */
  int i, index = 0, result = 0;
  clock_t temp_stamp = line[0].time_stamp;
  /* 有空位就放入并结束程序 */
  for(i=0;i<line_length;i++)
    {
      if(line[i].valid == 0)
	{
	  line[i].tag = add_tag;
	  line[i].valid = 1;
	  line[i].time_stamp = clock();
	  return result;
	}
    }
  /* 没有空位,那就比较时间戳,使用LRU算法 */
  for(i=0;i<line_length;i++)
    {
      if(temp_stamp > line[i].time_stamp)
	{
	  temp_stamp = line[i].time_stamp;
	  index = i;
	}
    }
  result = 1;
  line[index].tag = add_tag;
  line[index].time_stamp = clock();
  return result;
}

void print_verbose(char* pre, char type, int hit_miss, int eviction){
  /* 命令行带 -v 的话的详细数据输出函数 */
  char* h = hit_miss?" hit":" miss";
  char* e = eviction?" eviction":"";
  char* format;
  if(type == 'M')
    {
      format = "%s%s%s\n";
      strcat(pre, format);
      printf(pre, h, e, " hit");
    }
  else
    {
      format = "%s%s\n";
      strcat(pre, format);
      printf(pre, h, e);
    }
}

int cache_access(cache_line** cache_sets, int s, int E, int b, int v, int bytes, int* hits, int* misses, int* evictions, unsigned long addr, char type){
  /* 缓存模拟核心逻辑 */
  int hit_miss = 0, evictions_or_not = 0;
  char pre[20];
  /* 索引地址位可以用位运算*/
  unsigned long tag = addr >> (b + s), sets = ((addr << (64 - b - s)) >> (64 -s));
  cache_line* set = cache_sets[sets];
  /* 尝试读取 */
  hit_miss = hit_or_miss(set, E, tag);
  /* 如果没命中的话就把这个主存块放入缓存,观察是否有 eviction */
  if(!hit_miss)
    {
      evictions_or_not = put_in_cache(set, E, tag);
    }
  /* 如果命令行带 -v 的话,打印详细信息 */
  if(v)
    {
      sprintf(pre, "%c %lx,%d", type, addr, bytes);
      print_verbose(pre, type, hit_miss, evictions_or_not);
    }
  /* 统计工作 */
  *hits += hit_miss;
  if(type=='M')
    {
      *hits += 1;
    }
  *misses += !hit_miss;
  *evictions += evictions_or_not;
  return 0;
}

/* 当使用 ./csim -h 或错误的参数或没有参数时打印这个帮助信息 */
void print_usage(){
  printf("Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>\n");
  printf("Options\n");
  printf("  -h        Print this help message.\n");
  printf("  -v        Optional verbose flag.\n");
  printf("  -s <num>: Number of set index bits.\n");
  printf("  -E <num>: Number of lines per set.\n");
  printf("  -b <num>: Number of block offset bits.\n");
  printf("  -t <file>: Trace file.\n");
  printf("\n");
  printf("Exampes:\n");
  printf("  linux> ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n");
  printf("  linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}

int main(int argc, char** argv)
{
  unsigned long address;
  int s, E, b, bytes, has_opt = 0, hits = 0, misses = 0, evictions = 0, v = 0;
  char* t;
  char input, type;
  FILE* fp;
  cache_line** cache;
  /* 解析命令行参数 */
  while((input=getopt(argc,argv,"s:E:b:t:vh")) != -1)
    {
      has_opt = 1;
      switch(input){
      case 's':
	s = atoi(optarg);
	break;
      case 'E':
	E = atoi(optarg);
	break;
      case 'b':
	b = atoi(optarg);
	break;
      case 't':
	t = optarg;
	break;
      case 'v':
	v = 1;
	break;
      case 'h':
	print_usage();
	exit(0);
      default:
	print_usage();
	exit(-1);
      }
    }
  if(!has_opt){
    printf("./csim: Missing required command line argument\n");
    print_usage();
    return 0;
  }
  /* 根据参数初始化二维数组 */
  cache = initiate(s, E);
  /* 读入文件并解析 */
  fp = fopen(t, "r");
  if(fp == NULL)
    {
      printf("%s: No such file or directory\n", t);
      exit(1);
    }
  else
    {
      while(fscanf(fp, " %c %lx,%d", &type, &address, &bytes) != EOF)
	{
	  /* 'I' 类型的指令读取我们不关心 */
	  if(type == 'I')
	    {
	      continue;
	    }
	  else
	    {
	      /* 得到详细参数,进入缓存模拟核心逻辑 */
	      cache_access(cache, s, E, b, v, bytes, &hits, &misses, &evictions, address, type);
	    }
	}
      fclose(fp);
    }
  printSummary(hits, misses, evictions);
  /* 记得 free 掉给二维数组分配的堆空间 */
  clean(cache, s);
  return 0;
}

测试程序运行效果。

在这里插入图片描述

PS：前往公众号“Linux工坊”，可以查看最新内容！关注即可免费领取面试&Linux技术书籍！

------ 本文结束------
  • 文章标题： CSAPP cache lab(一)
  • 本文作者： 你是我的阳光
  • 发布时间： 2021年04月05日 - 22:14:44
    • 最后更新： 2022年11月07日 - 16:45:00
  • 本文链接： https://szp2016.github.io/os/csapp-cache-lab/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
0%