CSAPP实验3:CacheLab

发表于 | 分类于 |

实验简介

​ Cache LAB分为Part A和B两部分，这次实验的任务很明确，就是制作自己的缓存系统，具体来说是

  • 实现一个缓存模拟器，根据给定的 trace 文件来输出对应的操作
  • 利用缓存机制加速矩阵运算

我们需要修改的是 csim.c（Part A） 和 trans.c（Part B）。编译的时候只需要简单 make clean 和 make，然后就可以进行测试了。

文件说明

Github地址：Cache Lab

  • csim.c：实现缓存模拟器的文件
  • trans.c：实现矩阵转置的文件
  • csim-ref：标准的缓存模拟器
  • csim：由你实现的模拟器可执行程序
  • tracegen：测试你的矩阵转置是否正确，并给出错误信息
  • test-trans：测试你的矩阵转置优化的如何，并给出评分
  • driver.py：自动进行测试评分

在每一次更新之后，首先用make生成文件，之后用相应的test跑分即可。

Part A：Writing a Cache Simulator 实现一个缓存模拟器

讲义上首先给我们提供了一个程序示例

1
linux> valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l

执行，我们可以看到如下面这样的输出：（输入的trace文件的内容）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
......

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

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

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

操作类型有以下三种：

  • L：读取，从内存中读取
  • S：存储，向内存中存储
  • M：修改，这涉及一次读取，一次存储操作
  • 地址指的是一个 64 位的 16 进制内存地址；大小表示该操作内存访问的字节数
  • 其中I指令无空格，M/S/L指令前有1个空格（解析指令时注意）

然后实验给我们提供了一个程序csim-ref，我们要做的就是写出一个和它功能一样的程序。

1
2
3
4
5
6
7
8
9
10
11
12
Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>
Options:
  -h         Print this help message.
  -v         Optional verbose flag.
  -s <num>   Number of set index bits.
  -E <num>   Number of lines per set.
  -b <num>   Number of block offset bits.
  -t <file>  Trace file.

Examples:
  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace

样例输出：

mark

分析

getopt 获取命令行参数

fscanf 读入trace文件内容

malloc 分配空间给cache

数据访问带来的miss：

  • L：Load，数据载入，可能发生1次miss
  • S：Store，可能发生1次miss
  • M：store后再load，两次访存。1 miss & 1 hit + 可能eviction

所以L/S指令结果是miss或者hit或者miss+eviction；而M指令结果是hit+hit或者miss+hit 或者 miss+eviction+hit

mark

1 Cache结构

设计Cache基本单元为 block，cache由cacheblock组成

1
2
3
4
5
6
typedef struct 
{
	unsigned tag;
	unsigned usedtime;
} block;
block *cache;

其中usedtime是判断LRU cache行。初始值为0表示没有用过，相当于invalid。非零值越小代表越少使用，usedtime最大代表刚使用。

2 命令行参数解析

首先对命令行参数进行解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getOpt(int argc,char **argv,int *s,int *E,int *b,int *verbose,char *tracefile)
{
	int oc;
	while((oc=getopt(argc,argv,"hvs:E:b:t:"))!=-1){
		switch(oc){
			case 'h': printHelpMenu();break; // print usage
			case 'v': *verbose=1;break; 	
			case 's': *s = atoi(optarg);break;
			case 'E': *E = atoi(optarg);break;
			case 'b': *b = atoi(optarg);break;
			case 't': strcpy(tracefile,optarg);break;
			default : printf("input error\n");break;
		}
	}
	return 0;
}

3 初始化cache

然后初始化cache： E<<s 是cache行数也就是E*2^s

1
2
cache = (block *)malloc(sizeof(block)* E<<s);
memset(cache,0,sizeof(block)* E<<s);

4 读取文件参数

fscanf读取trace文件中的指令、地址

1
2
3
4
5
6
7
8
9
10
fp = fopen (tracefile,"r");
while(fscanf(fp,"%s%x,%d\n",op,&addr,&size) > 0){
  if(verbose)
    printf("%s %x,%d ",op,addr,size);
  switch(op[0]){
    case 'M': hit++;
    case 'L':
    case 'S': find(op[0],addr,size,++t);     
  }
}

5 数据访问

获取tag和 set index

mark

1
2
unsigned tag = addr >>b >>s ;
unsigned set_index = addr >> b &((1<<s) -1);

找到对应的set

1
2
block *cache_set = cache + E * set_index ;  // set address
block *eviction_block = cache_set;            // LRU cacheline

进行数据查找，其中eviction_block表示查询过程中LRU的cache行，也就是usedtime最小的（但是非0）在一个set里面遍历cache行

  • 如果usedtime！=0且tag匹配：hit
  • 如果usedtime=0，是个空block，使用这个block：miss
  • 如果usedtime！=0，tag不匹配，跟eviction_block.usedtime比较，如果时间更小，更新eviction_block=该cacheblock

如果循环结束，也就证明这个set的所有cache行都满了，就替换LRU cache行。

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 find(char op, unsigned addr,unsigned size,int time){
    int i;
    unsigned tag = addr >>b >>s ;
    unsigned set_index = addr >> b &((1<<s) -1);
    block *cache_set = cache + E * set_index ;  // set address
    block *eviction_block = cache_set;            // LRU cacheline
    for(i = 0;i<E;i++){
        if(cache_set[i].usedtime>0 && cache_set[i].tag ==tag){ //hit
            cache_set[i].usedtime = time;
            hit++;
            if(verbose) cacheStateOut(op,0);
            return;
            
        }
        else if(!cache_set[i].usedtime){ // empty block
            miss++;
            cache_set[i].tag = tag;
            cache_set[i].usedtime = time;
            if(verbose) cacheStateOut(op,1);
            return;
        }
        else if(cache_set[i].usedtime < eviction_block->usedtime) // !=tag , current block is older
            eviction_block = cache_set+i;                          
    }
    miss ++;
    eviction ++;
    eviction_block->tag = tag; // replace sacrifice cacheline
    eviction_block->usedtime = time;
    if(verbose) cacheStateOut(op,2);
    return ;
}

测试

mark

结果正确

Part B：Optimizing Matrix Transpose 优化矩阵转置

要求优化对不同规格的矩阵的转置操作。 这里有三个矩阵，他们的miss次数要求分别如下：

  • 32 * 32: 8 points if m < 300, 0 points if m > 600
  • 64 × 64: 8 points if m < 1300, 0 points if m > 2000
  • 61 × 67: 10 points if m < 2000, 0 points if m > 3000

要求

  • 在tranc.c里进行完成 transpose_submit函数
  • 最多使用12个int型变量，不能使用数组和malloc函数，不能使用位运算，不能改变矩阵A

Tips

题目的cache参数如下：s=5，E=1，b=5

  • 是一个直接映射高速缓存
  • 32字节的Block size
  • 有32个set

分析

首先要明确，尽管矩阵的转置本身导致对于A矩阵（原始矩阵）的读和B矩阵（转置矩阵）的写不可能同时为连续的（即不可能同时存在连续读和连续写——对A矩阵行的连续读必然导致对B矩阵列的非连续写）。 但只要矩阵的大小小于缓存的总大小，那么在理想的情况下，在最初的强制不命中（即缓存为空导致的不命中）后，整个矩阵都会被加载进入缓存。在这之后的所有对于B矩阵的不连续写的引用都会命中。

在该实验中，缓存采用的是直接映射高速缓存，s = 5，b = 5，E = 1。对于该缓存，总共存在32个组，每个组共32个字节，可以装入8个int型变量，是非常有限的缓存，矩阵大小>cache大小。主要需要解决以下两个问题：

  1. 直接映射缓存所带来的冲突不命中。观察程序中矩阵存储的位置即可以发现，矩阵A和矩阵B的同一行实际上被映射到了同一个缓存组。当进行对角线的引用时，一定会发生缓存的冲突不命中。需要仔细地处理对角线上的元素。
  2. 所需优化的矩阵的总大小超出了缓存的总大小。必然导致程序的访存效率低下。

为了解决第一个问题，我们需要仔细地考虑对于矩阵访问顺序；第二个问题，采用矩阵的分块（Blocking）方法降低miss

矩阵分块的目的在于将大的、不能完全加载进入缓存的大矩阵分块成小的、可以完全加载进入缓存的小矩阵块来处理。小矩阵块具有良好的局部性，性能显著增加。 但同时也要注意，分块使得程序的可阅读性大大降低，因此一般只在常用的库函数中采用分块优化。

32 * 32

对于32 * 32的矩阵，一次可以装下8行的值。于是我们用8 * 8的分块来处理，增加缓存命中。

在32*32的情况中，一行是32个int，也就是4个block，所以cache可以存8行，由此可以推出映射冲突的情况：只要两个int之间相差8行的整数倍，那么读取这两个元素所在的block就会发生替换

但是转置的过程中这样的情况会发生吗？不会。图中的BCD三点对于A来说仅仅是行差了8K，这在转置中是不可能发生的！因为转置是将A[i][j]送到B[j][i]，不会有B[i+8k][j]的情况出现（不会在行相差8整数倍的块中，除非对角线上的块）。所以B在写入时miss概率也是1/8（强制失效）。

mark

一个cache block只有32个Byte，可以装下8个int。这个cache可以容纳矩阵的前8行。所以分块采用8 * 8合适。先读取A的一行，然后放入B的一列。12个int变量，4个用来循环，其余8个用来存A中块的一行。

简单8 * 8分块：

1
2
3
4
5
6
7
8
9
10
11
12
13
if(M == 32){
   for (i = 0; i < N; i+=8) {
        for (j = 0; j < M; j+=8) {
            for(k = i ;k < i + 8 && k<N;k++){
                    for(l = j ; l < j + 8 && l < M;l++)
                    {                            
                        a0 = A[k][l];
                        B[l][k] = a0;
                    }
            }
        }
    }
}

测试结果如下：超过了300miss，原因是对角线访问问题

mark

对角线上的block访问miss问题：

矩阵A和矩阵B的同一行实际上被映射到了同一个cache block。当进行对角线的引用时，一定会发生缓存的冲突不命中。并且，由于A和B的元素时一个一个处理的，必定会造成反复多次的冲突不命中。（如下图A第一个元素读miss，B第一个元素存miss，A读第二个元素miss）

解决方法：通过变量一次性读出A的一整行，再存入B

cache miss分析

（经过对角线块优化后）对于32 × 32的矩阵，总共存在1024次读(32*32)和1024次写。

对于非对角线的分块（总共12个），其缓存不命中率是1/8（仅强制不命中）；

对于对角线的分块（总共4个），A读缓冲不命中率1/8（仅强制不命中），B写不命中率1/4（强制失效 1/8 + 冲突不命中 1/8（A刚读的那行B写的时候会miss））

mark

因此，理论上优化之后的总缓存不命中数为2048 × 0.75 × 0.125 + 1024 × 0.25 × 0.125 + 1024 × 0.25 × 0.25 = 288次。最后跑出来的答案是287，非常接近。

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
for (i = 0; i < N; i+=8) {
            for (j = 0; j < M; j+=8) {
                if(i == j){
                    for(k = i ;k < i + 8 && k<N;k++){ 
                        a0 = A[k][j];   
                        a1 = A[k][j+1];
                        a2 = A[k][j+2];
                        a3 = A[k][j+3];
                        a4 = A[k][j+4]; 
                        a5 = A[k][j+5];
                        a6 = A[k][j+6];
                        a7 = A[k][j+7];
                        B[j][k]   = a0;
                        B[j+1][k] = a1;
                        B[j+2][k] = a2;
                        B[j+3][k] = a3;
                        B[j+4][k] = a4;
                        B[j+5][k] = a5;
                        B[j+6][k] = a6;
                        B[j+7][k] = a7;
                    }
                }
                else{
                    for(k = i ;k < i + 8 && k<N;k++){
                        for(l = j ; l < j + 8 && l < M;l++)
                            B[l][k] = A[k][l];
                    }
                }
            }
        }

测试结果：287miss

mark

64 * 64

这题难度是最大的，miss必须1300以下

首先考虑Cache中只能放4行A中的行，如果再用8×8的块，前面4行可以填入，后面4行会在Cache中发生冲突，导致miss次数增加。

如果只用4×4的块呢？那么每次Cache中放入8个int，我们却只用4个，浪费严重，这个方法最少也只能做到1677次miss。

题目说不能对A进行操作，但是可以对B进行操作！将B作为缓存使用

改进方法：将8 * 8 块再分成4个4 * 4的块进一步处理，经过改进，达到1171miss

首先对左上角和右上角进行处理：

  1. B左上角 = A左上角转置。B右上角=A右上角转置。
  2. 我们最后只需要把这部分平移到B的左下角就好。

现在B左上角完成

  1. 首先用四个变量存储A的左下角的一列。
  2. 再用四个变量存储B的右上角的一行。
  3. 把四个变量存储的A的左下角的一列移动到B右上角的一行
  4. 把四个变量存储的B的右上角的一行平移到B左下角的一列
  5. B的右下角=A的右下角转置

mark

关键的操作在第二步

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
for (i = 0; i < N; i += 8) {
       for (j = 0; j < M; j += 8) {
           for (k = i; k < i + 4; k++) {
               a0 = A[k][j];
               a1 = A[k][j + 1];
               a2 = A[k][j + 2];
               a3 = A[k][j + 3];
               a4 = A[k][j + 4];
               a5 = A[k][j + 5];
               a6 = A[k][j + 6];
               a7 = A[k][j + 7];

               B[j][k] = a0;
               B[j + 1][k] = a1;
               B[j + 2][k] = a2;
               B[j + 3][k] = a3;

               B[j][k + 4] = a4;
               B[j + 1][k + 4] = a5;
               B[j + 2][k + 4] = a6;
               B[j + 3][k + 4] = a7;
           }
           for (l = j + 4; l < j + 8; l++) {

               a4 = A[i + 4][l - 4]; // A left-down col
               a5 = A[i + 5][l - 4];
               a6 = A[i + 6][l - 4];
               a7 = A[i + 7][l - 4];

               a0 = B[l - 4][i + 4]; // B right-above line
               a1 = B[l - 4][i + 5];
               a2 = B[l - 4][i + 6];
               a3 = B[l - 4][i + 7];

               B[l - 4][i + 4] = a4; // set B right-above line 
               B[l - 4][i + 5] = a5;
               B[l - 4][i + 6] = a6;
               B[l - 4][i + 7] = a7;

               B[l][i] = a0;         // set B left-down col
               B[l][i + 1] = a1;
               B[l][i + 2] = a2;
               B[l][i + 3] = a3;

               B[l][i + 4] = A[i + 4][l];
               B[l][i + 5] = A[i + 5][l];
               B[l][i + 6] = A[i + 6][l];
               B[l][i + 7] = A[i + 7][l];
           }
       }
   }

测试结果：1171miss 通过

mark

61 * 67

不规则的matrix，本质也是用分块来优化Cache的读写，但是不能找到比较显然的规律看出来间隔多少可以填满一个Cache。但是由于要求比较松，因此无需考虑处理对角线，直接进行转置操作，仅尝试换用不同的边长分块即可。16 × 16的分块已可以保证满分。

测试：1992miss <2000

mark

自动评分脚本输出：

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
zjw@ubuntu:~/Desktop/cachelab-handout$ ./driver.py 
Part A: Testing cache simulator
Running ./test-csim
                        Your simulator     Reference simulator
Points (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
     3 (1,1,1)       9       8       6       9       8       6  traces/yi2.trace
     3 (4,2,4)       4       5       2       4       5       2  traces/yi.trace
     3 (2,1,4)       2       3       1       2       3       1  traces/dave.trace
     3 (2,1,3)     167      71      67     167      71      67  traces/trans.trace
     3 (2,2,3)     201      37      29     201      37      29  traces/trans.trace
     3 (2,4,3)     212      26      10     212      26      10  traces/trans.trace
     3 (5,1,5)     231       7       0     231       7       0  traces/trans.trace
     6 (5,1,5)  265189   21775   21743  265189   21775   21743  traces/long.trace
    27


Part B: Testing transpose function
Running ./test-trans -M 32 -N 32
Running ./test-trans -M 64 -N 64
Running ./test-trans -M 61 -N 67

Cache Lab summary:
                        Points   Max pts      Misses
Csim correctness          27.0        27
Trans perf 32x32           8.0         8         287
Trans perf 64x64           8.0         8        1171
Trans perf 61x67          10.0        10        1992
          Total points    53.0        53

Referrence

http://zxcpyp.com/csapp/2017/11/20/Cache-Lab#part-awriting-a-cache-simulator-%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AA%E7%BC%93%E5%AD%98%E6%A8%A1%E6%8B%9F%E5%99%A8