CSAPP-cachelab 解题思路记录

模拟缓存

阅读官方指导文档

文档中写清楚了 lab 要求和限制，比较容易忽略的几点是：

代码文件编译时不能有警告和错误；
不用考虑指令的缓存读写，就是 .trace 文件中 “I” 开头的记录；
.trace 文件中记录的缓存读写是不会越过主存块边界的，不用考虑这个问题，所以记录中最后读写大小的数据可以忽略；

确定缓存映射方式

缓存映射方式有三种，文档中未说明 lab 中使用的何种方式：

直接映射：每个主存块映射到 Cache 的固定行；
全相联：每个主存块映射到 Cache 的任意一行；
组相联：每个主存块映射到 Cache 固定组中任意一行；

lab 提供了一个可执行文件 csim-ref，我们最后实现的功能要和这个可执行文件一模一样，这个文件就是模板；修改它的输入件观察它的输出，就可以得出 lab 要求的是什么缓存映射方式：

输入文件中有以下缓存读取记录：
1 2 3 4

L 10,1 L 110,1 L 210,1 M 12,1
0x10、0x110、0x210 按照一个主存块16字节的话，分别位于第1、17、33号主存块；

第一次使用 ./csim-ref -v -s 3 -E 2 -b 4 -t traces/example.trace, 输出：

1
2
3
4
5


L 10,1 miss
L 110,1 miss
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:1 misses:4 evictions:2

第二次使用 ./csim-ref -v -s 2 -E 4 -b 4 -t traces/example.trace, 输出：

1
2
3
4
5


L 10,1 miss
L 110,1 miss
L 210,1 miss
M 12,1 hit hit
hits:2 misses:3 evictions:0

第一次命令使用的缓存具有8组，每组2行；对于例子中的输入，如果是直接映射，地址 0x10 所在的主存块将缓存在缓存区第一行中，地址 0x110 所在的第17主存块也将缓存在同样的地方，但是对应行输出中并没有 miss eviction 的信息，所以这不是直接映射；
而当 0x210 所在的33号主存块载入时，发生了 miss eviction，这时缓存中还有足够的空间，所以这不是全相联映射；
只有在映射方式为半相联方式时，主存块号 % 组数获得主存在缓存中的组号，然后映射到该组中任一行（至于组中所有行都被占用，则应用算法来弹出旧的，存入新的），1、 17、33 和组数 8 取模结果都是1；都映射在第一组，第一个输出结果也证实了这一点；
第二次的命令进行验证，这次有4组，每组4行，前三次缓存读取没有发生 miss eviction，lab 中使用的缓存映射方式确实是 组相联 。

代码

功能上可以分成三个部分：

处理命令行输入，初始化各参数，使用 C 库中的 getopt() 函数来完成；
读入命令行参数中指定的 trace 文件，对文件内容进行解析，使用 C 库中的 fscanf() 函数；

模拟缓存对 trace 文件中缓存读写条目的反应，并记录，定义一个结构体来模拟缓存中的行；

1
2
3
4
5
6


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

lab 要求的功能核心在第三步。

具体代码思路见注释：

  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


#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,总比一个嵌套 for 循环好吧 */
      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;
  /* 一个 trick,反正是模拟,有空位就放入并结束程序 */
  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];
  /* 如果被 datalab 虐过,那下面的 << >> 应该不会陌生 */
  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🅱️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;
}

矩阵转置

阅读官方指导文档

在转置函数中最多可以定义 12 个本地变量；
不要使用一个变量存储多个值来规避第一条限制；
不准使用递归；
如果使用帮助函数，运行过程中栈上不能有超过 12 个本地变量；
不准修改代码中的 array A 变量；
不准在代码中定义其它数组，或者使用 malloc 的任何变种；

矩阵转置提高命中率

按文档中要求的，transpose_submit 的命中率表现通过使用 valgrind 来解析函数地址读取记录，然后使用模拟缓存中的模拟器来模拟函数的缓存读取，缓存大小是 s = 5, E = 1, b = 5，也就是说，这个缓存有32组，每组1行，每行32个字节-每个主存块32个字节，这样一个缓存可以存储最多256个 int 型数据；
需要针对三个大小的 int 类型的矩阵进行转置并测试：67 * 61，32 * 32，64 * 64；

核心逻辑就是分块（正方形矩阵）；

对于 67 * 61 大小的 int 矩阵：

lab 的要求是 miss 小于 2000，是三个矩阵中要求最宽松的；
因为不规则，所以无法分成均匀的正方形矩阵；
这个大小的矩阵可以尝试分成不同大小的分块试试看哪个效率最高（其中有一个行列是不足的）；
试着从 8 * 8 矩阵开始分块，看哪一个可以达到要求；
16和23都是符合要求的 miss 小于 2000；

代码：

 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


void transpose_61_67(int M, int N, int A[N][M], int B[M][N])
{
  int i, j, k, l, temp, index, block_size = 23;
  for(i=0;i<N;i+=block_size)
    {
      for(j=0;j<M;j+=block_size)
    {
      for(k=i;k<i+block_size && k<N;k++)
        {
          for(l=j;l<j+block_size && l<M;l++)
        {
          if(k != l)
            {
              B[l][k] = A[k][l];
            }
          else
            {
              temp = A[k][l];
              index = k;
            }
        }
          if(i == j)
        {
          B[index][index] = temp;
        }
        }
    }
    }
}

对于 32 * 32 大小的 int 矩阵：

要求 miss 小于 300；
正方形矩阵，且它的前8行正好占满1KB，也就是 lab 指定的 cache，它一行中的前8个元素占一个缓存组；
所以按8分块，分成16个分块，同一个矩阵分块内的每行在主存中的组号是不冲突的，可以有效利用 cache；
针对矩阵对角线上的情况，一定要特殊处理，否则理论上会造成两个矩阵间同在一个缓存组（其实就是行号相同列号相同）的两行增加进出 cache 的次数，这也会增加 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


void transpose_32_32(int M, int N, int A[N][M], int B[M][N])
{
  int i, j, k, l, temp, index;
  int block_size = 8;
  int h_v_blocks = M / block_size;
  for(i=0;i<h_v_blocks;i++)
    {
      for(j=0;j<h_v_blocks;j++)
    {
      for(k=block_size*i;k<block_size+block_size*i;k++)
        {
          for(l=block_size*j;l<block_size+block_size*j;l++)
        {
          if(k != l)
            {
              B[l][k] = A[k][l];
            }
          else
            {
              temp = A[k][l];
              index = k;
            }
        }
          if(i == j)
        {
          B[index][index] = temp;
        }
        }
    }
    }
}

对于 64 * 64 大小的 int 矩阵：

要求 miss 小于1300；
如果还是按照 32 * 32 矩阵中的解法，miss 超过2000，这是因为它的前4行占满了一个缓存，第五行和第一行在缓存中的组号是相同的，如果还是分成 8 * 8 的矩阵，在处理这样情况的例子中就会抖动；
如果分成 4 * 4 的分块，又不能有效利用缓存，毕竟同一行中8个元素占一个缓存组，最后的结果还是降不到 1300 以下；
还是考虑 8 * 8 分块的情况，不过这一次是在分块内再次分块成 4 个 4 * 4 分块，分别处理这 4 个分块；
具体的思路，我想到分块再分块以后一直拿不出一个成功分别处理的逻辑、代码，这里摘抄一下别人的想法：
1.先考虑把A的上半部分存入到B，但是为了考虑Cache不冲突，所以把右上角的 4×4的区域也存在B的右上角。对于在对角线上的块，A的miss率是1/8，B的左上角部分miss率是1/2。对于不在对角线上的块，A的miss率还是1/8，B左上角部分的 miss率为1/4.
1. 接下来这步是减少miss率的关键，把A左下角的一列4个数据读出，B右上角的一行4个数据读出，都用int变量暂存，然后把前四个填入B右上角行中，后四个填入B的左下角行中。因为从B右上角读取的时候，把块放入了Cache，然后从A往B中填的时候，就不会出现miss操作。来计算一下miss率，对于在对角线上的块，从A左下角读取miss率为1，B的右上角的操作miss率为1/4，B的左下角miss率为1/4。对于不在对角线的快，A的 miss率为1/4，B右上角miss率为0，左下角miss率为1/4。
2. 最后一步就是把A的右下角填入B的右下角，对于在对角线上的块，A的miss率为1/4，B的miss率为1/2.不在对角线上的块，A，B的miss率都为0.

代码：

 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


void transpose_64_64(int M, int N, int A[N][M], int B[M][N])
{
  int i, j, k;
  int a1, a2, a3, a4, a5, a6, a7, a8;
  for(i=0;i<64;i+=8){
    for(j=0;j<64;j+=8){
      for(k=j;k<j+4;++k){
    a1=A[k][i];
    a2=A[k][i+1];
    a3=A[k][i+2];
    a4=A[k][i+3];
    a5=A[k][i+4];
    a6=A[k][i+5];
    a7=A[k][i+6];
    a8=A[k][i+7];

    B[i][k]=a1;
    B[i][k+4]=a5;
    B[i+1][k]=a2;
    B[i+1][k+4]=a6;
    B[i+2][k]=a3;
    B[i+2][k+4]=a7;
    B[i+3][k]=a4;
    B[i+3][k+4]=a8;
      }
      for(k=i;k<i+4;++k){
    a1=B[k][j+4];
    a2=B[k][j+5];
    a3=B[k][j+6];
    a4=B[k][j+7];
    a5=A[j+4][k];
    a6=A[j+5][k];
    a7=A[j+6][k];
    a8=A[j+7][k];

    B[k][j+4]=a5;
    B[k][j+5]=a6;
    B[k][j+6]=a7;
    B[k][j+7]=a8;
    B[k+4][j]=a1;
    B[k+4][j+1]=a2;
    B[k+4][j+2]=a3;
    B[k+4][j+3]=a4;
      }
      for(k=i+4;k<i+8;++k){
    a1=A[j+4][k];
    a2=A[j+5][k];
    a3=A[j+6][k];
    a4=A[j+7][k];

    B[k][j+4]=a1;
    B[k][j+5]=a2;
    B[k][j+6]=a3;
    B[k][j+7]=a4;
      }
    }
  }
}

文章目录

模拟缓存

阅读官方指导文档

确定缓存映射方式

代码

矩阵转置

阅读官方指导文档

矩阵转置提高命中率