CSAPP Cache Lab解题报告

任务A

实现代码:

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
#include <stdio.h>
#include <stdbool.h>
#include "cachelab.h"
#include <stdlib.h>
#include <getopt.h>

#define ADDR_SIZE 64;
typedef struct{
char* filePath;
int setNum;
int lineNum;
int blockNum;
bool verbose;
}GlobalArgs;
GlobalArgs globalArgs;
typedef struct
{
unsigned long long tag;
int timestamp;
}CacheLine;

static const char* optString="hvs:E:b:t:";

void PrintHelp()
{
printf("%s\n","Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>");
printf("%s\n","Options:");
printf("%s\n"," -h Print this help message");
printf("%s\n"," -v Optional verbose flag");
printf("%s\n"," -s <num> Number of set index bits.");
printf("%s\n"," -E <num> Number of lines per set.");
printf("%s\n"," -b <num> Number of block offset bits");
printf("%s\n"," -t <file> Trace file.");
printf("\n\n");
printf("%s\n","Examples:");
printf("%s\n"," linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace");
printf("%s\n"," linux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace");
}
void SetArgus(int argc, char* argv[])
{
int opt=getopt(argc,argv,optString);
while (opt!=-1)
{
switch (opt){
case 'h':
PrintHelp();
break;
case 'v':
globalArgs.verbose=true;
break;
case 's':
globalArgs.setNum=atoi(optarg);
break;
case 'E':
globalArgs.lineNum=atoi(optarg);
break;
case 'b':
globalArgs.blockNum=atoi(optarg);
break;
case 't':
globalArgs.filePath=optarg;
break;
default:
printf("wrong argument\n");
break;
}
opt=getopt(argc,argv,optString);
}
}

void TryToHitCache(unsigned long address,int* hit,int* miss,int* eviction,CacheLine* cache)
{
static int timestamp=0;
int tagLen=64-(globalArgs.setNum+globalArgs.blockNum);
unsigned long set=(unsigned long)((address<<tagLen)>>(tagLen+globalArgs.blockNum));
unsigned long tag=(unsigned long)(address>>(64-tagLen));
int min=globalArgs.lineNum*set;
for(int i=0;i<globalArgs.lineNum;i++)
{

int idx=set*globalArgs.lineNum+i;
if(cache[idx].tag==tag&&cache[idx].timestamp!=0)
{
cache[idx].timestamp=++timestamp;
(*hit)++;
if(globalArgs.verbose)
printf("hit ");
return;
}
else if(cache[idx].timestamp==0)
{
cache[idx].timestamp=++timestamp;
(*miss)++;
cache[idx].tag=tag;
if(globalArgs.verbose)
printf("miss ");
return;
}
if(cache[idx].timestamp<cache[min].timestamp)
min=idx;
}
cache[min].timestamp=++timestamp;
cache[min].tag=tag;
(*miss)++;
(*eviction)++;
if(globalArgs.verbose)
printf("miss eviction ");
return;
}


int main(int argc,char* argv[])
{

SetArgus(argc,argv);
if(globalArgs.filePath==NULL)
{
exit(0);
}
FILE* fp=fopen(globalArgs.filePath,"r");
if(fp==NULL)
{
printf("File not found %s\n",globalArgs.filePath);
exit(0);
}
int hit=0,miss=0,eviction=0;
int S=(1<<globalArgs.setNum);
int E=globalArgs.lineNum;

CacheLine* cache=calloc(S*E, sizeof(CacheLine));

char opt;
unsigned long address;
int block;


while(fscanf(fp," %c %lx,%d", &opt,&address,&block)>0)
{
if(opt=='I')
continue;
if(globalArgs.verbose)
{
printf("%c %lx,%d ",opt,address,block);
}
TryToHitCache(address,&hit,&miss,&eviction,cache);
if(opt=='M')
TryToHitCache(address,&hit,&miss,&eviction,cache);
if(globalArgs.verbose)
printf("\n");
}

fclose(fp);
free(cache);

printSummary(hit,miss,eviction);

return 0;

}

实现思路:

任务A就是打开文件读入数据、处理数据、输出数据的过程,核心逻辑就是在于怎么模拟一个高速缓存来处理数据。我们将这部分逻辑封装在了void TryToHitCache(unsigned long address,int* hit,int* miss,int* eviction,CacheLine* cache)这个函数中。

首先我们定义一个静态变量static int timestamp,这个变量用来记录CPU向高速缓存器访问的时间戳(用来记录访问次数)。在该函数里我们需要接受几个参数,分别为请求的地址,hit次数,miss次数,eviction次数以及模拟的高速缓存器。然后我们将address的各部分结构进行解析,分别得到了set、tag等参数。

然后我们遍历模拟高速缓存器的组,比较address解析的set数是否与模拟缓存器的set数相同和是否可能为冷未命中的情况下。

如果能找到相同的tag且不是冷未命中的话,就将hit++,且更改timestamp的值。如果是冷未命中的话,就将miss++,并且更新timestamp的值并且设置该块的值。

如果则两种情况都不是的话,则需要更换块的内容。那么我们需要更新哪个块呢?根据局部性原则,我们应当更新距离我们这次访问时间戳距离最远的块,因此我们遍历一遍该组并找出该块并进行更换。然后进行更新数据。

任务B:

实现代码:

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
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
int a1,a2,a3,a4,a5,a6,a7,a8;
int i,j,k,h;
if(N==32){
for(i=0;i<4;i++){
for(j=0;j<4;j++){
for(k=i*8;k<(i+1)*8;k++){
h=j*8;
a1=A[k][h];a2=A[k][h+1];a3=A[k][h+2];a4=A[k][h+3];
a5=A[k][h+4];a6=A[k][h+5];a7=A[k][h+6];a8=A[k][h+7];

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

实现思路:

本题很明显要使用分块进行优化,但分块后如下后距离答案要求的数量还有不少距离。

我这里参考了网上大神们的做法。

32×32:

第一题要求miss次数在300以下,首先观察,Cache的一个块只有32B,也就是只能容纳8个int。这个Cache可以容纳这个matrix的前8行。分块的话,肯定是取8×8的比较合适。先读取A的一行,然后放入B的一列。12个int变量,4个用来循环,其余8个用来存A中块的一行。

对于在对角线上的块,A中每读一行,会有一次miss,也就是miss次数是读取操作的1/8,对于B数组的话,第一次读取这行会产生一次miss,之后对于第i行,只有A中读到第i行的时候,会被移除出Cache,然后存的时候会产生一次miss。可以粗略计算为miss次数是读取次数的1/4。

对于不在对角线上的块,做转置的时候,A还是1/8的miss率,B的每行在Cache中和A的行不冲突 ,所以也是1/8的miss率,我们计算下最后大概多少次miss呢?

大概是 [公式]

最后跑出来的答案是287,非常接近。

64×64:

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

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

有一种很巧妙的方法,就是还用8×8的块来做,题目说A数组不能变换,但是说B数组可以任意操作啊。我们必须要一步到位嘛?可否考虑先把数字移动到B中,然后在B中自己做变化。

考虑用同样的miss次数,把更多的数据移动到B中,但是不一定是正确的位置,然后再用同样的miss次数,把A中部分数据移动到B中时,完成把B中前面位置错误数据的纠正。

1.先考虑把A的上半部分存入到B,但是为了考虑Cache不冲突,所以把右上角的4×4的区域也存在B的右上角。对于在对角线上的块,A的miss率是1/8,B的左上角部分miss率是1/2。对于不在对角线上的块,A的miss率还是1/8,B左上角部分的miss率为1/4.

\2. 接下来这步是减少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。

\3. 最后一步就是把A的右下角填入B的右下角,对于在对角线上的块,A的miss率为1/4,B的miss率为1/2.不在对角线上的块,A,B的miss率都为0.

最后我们来计算下miss的次数吧,计算出来近似是1280次,实际我们代码跑出来是1219次 。

61×67:

不规则的matrix,本质也是用分块来优化Cache的读写,但是不能找到比较显然的规律看出来间隔多少可以填满一个Cache,但是由于要求比较松,我们可以尝试一些分块的大小,直接进行转置操作。尝试到16左右 ,可以小于2000次miss。