ardxwe

CSer

0%

CS15-213labs-cache-lab

发表于 更新于

关于课程

这门课程围绕 CSAPP 展开。

书本相关的所有信息，你可以在 这里 找到。

你可以在 Bilibili 或者 YouTube 查看所有的课程视频，Bilibili附带中文字幕。

建议看完相应的章节然后去做相应的实验。大名鼎鼎的 CSAPP 的作者即是这门课程的讲师。你可以在 这里 找到实验相关的所有内容。

这门课程的实验代码可以在我的 Github 找到我的所有解答及相关资料。本次实验相关代码在 ./cachelab-handout 文件夹下。

cache lab

文档

点击 这里， 然后点击圆圈处 Self-Study Handout 即可下载此次实验对应的文档。

解压之后文件夹对应目录:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
➜  下载 tree cachelab-handout
cachelab-handout
├── cachelab.c
├── cachelab.h
├── csim.c
├── csim-ref
├── driver.py
├── Makefile
├── README
├── test-csim
├── test-trans.c
├── tracegen.c
├── traces
│   ├── dave.trace
│   ├── long.trace
│   ├── trans.trace
│   ├── yi2.trace
│   └── yi.trace
└── trans.c

1 directory, 16 files
  • cachelab.c: 一些需要的辅助函数
  • cachelab.h: cachelab.c 对应头文件
  • csim.c: 需要编写的 A 部分: cache 模拟器
  • csim-ref: 可执行文件, 可以用来做参考的 cache 模拟器, 可以验证我们编写的模拟器的正确性
  • driver.py: 运行 test-csim 和 test-trans
  • Makefile: 编译代码
  • README: CMU 给出的相关说明， 我编写的文件介绍基本是翻译此文件中的内容 -> 说明文件
  • test-csim: 可执行文件， 测试我们编写的 cache 模拟器
  • test-trans.c: 测试我们实验B的正确性
  • tracegen.c: test-trans.c 的一些辅助函数
  • traces/ : 文件夹, 被 test-csim.c 使用的踪迹文件
  • trans.c: 需要编写的 B 部分: 转置函数

内容

A： 编写简单的缓存模拟器
B： 优化矩阵转置以最大限度减少缓存未命中次数

环境

LINUX

过程

分析

实验官方说明文件 cachelab

PART A

这是我编写的 csim.c:

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
229
230
231
232
233
234
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <unistd.h>

// #define NDEBUG
#define print(x) if (infoflag) printf(x)

#include "cachelab.h"
#include "assert.h"

void getaddrfromline(char* buff, char* result);
long getlownnumber(long addr, long n);

int main(int argc, char* argv[])
{
    // 记录次数
    long hit_count = 0;
    long eviction_count = 0;
    long miss_count = 0;

    // 缓存相关数据
    long tagbits = 0;
    long setsbits = 0;
    long linesperset = 0;
    long blockbits = 0;

    // 文件名
    char* filename = NULL;

    // 是否输出具体信息
    bool infoflag = false;

    // 文件
    FILE* fp = NULL;

    // 实现 LRU 变量
    long max = 1;

    // 解析命令行参数
    for (long i=1; i<argc; i++){
        size_t length = strlen(argv[i]);
        assert(length == 2);
        switch (argv[i][1])
        {
        case 'v':
            infoflag = true;
            break;
        
        case 's':
            setsbits = atoi(argv[++i]);
            break;
        
        case 'E':
            linesperset = atoi(argv[++i]);
            break;
        
        case 'b':
            blockbits = atoi(argv[++i]);
            break;
        
        case 't':
            filename = argv[++i];
            break;

        default:
            fprintf(stderr, "Parameter error, you should use -v -s number -E number -b number -t filename");
            return -1;
        }

    }

    // 地址剩余位数应该为 tag 的位数
    tagbits = sizeof(void*) * 8 - setsbits - blockbits;

    assert(tagbits > 0);

    // cache块数
    long count = (1 << setsbits) * linesperset;

    // tag 和 used 用来模拟 cache
    // calloc: malloc and memset 0
    long* tagptr = calloc(count, sizeof(long));
    long* usedptr = calloc(count, sizeof(long));

    if (usedptr == NULL || tagptr == NULL){
        fprintf(stderr, "calloc error.");
        return -1;
    }

    fp = fopen(filename, "r");

    char buff[1024];
    char number[1024];
    long addr;

    long set;
    long tag;

    while (fgets(buff, 1024, fp) != NULL) {
        memset(number, 0, 1024);

        // 忽略 I 开头的行
        if(*(buff) == 'I')continue;

        // 去掉行尾回车
        if(buff[strlen(buff)-1] == '\n')buff[strlen(buff)-1] = '\0';

        // 去掉行头空格
        if(infoflag && buff[0] == ' ') {
            printf("%s ", buff + 1);
        }
        else if (infoflag) {
            printf("%s ", buff);
        }

        // 得到地址 存于 number
        getaddrfromline(buff, number);
        sscanf(number, "%lx", &addr);

        // 得到地址对应的 tag set
        tag = getlownnumber(addr >> (blockbits + setsbits), tagbits);
        set = getlownnumber(addr >> blockbits, setsbits);

        // cache 行
        long* nowptr = usedptr + set * linesperset;

        long* this = nowptr;

        bool allone = true;
        
        // 试图找到 tag
        for (int i=0; i < linesperset; i++) {
            if (*this != 0) {
                if (*(tagptr + set * linesperset + i) == tag) {
                    if (*(buff+1) == 'M') {
                        print("hit hit \n");
                        hit_count++;
                    }
                    else {
                        print("hit \n");
                    }
                    (*this) = max++;
                    hit_count++;
                    goto ff;
                }
            }
            else allone = false;
            this++;
        }

        long index = 0;

        // 有空余块
        if (allone == false) {
            this = nowptr;
            for (int i=0; i < linesperset; i++) {
                if (*this == 0) {
                    *(tagptr + set * linesperset+i) = tag;
                    break;
                }
                this++;
            }
            *this = max++;
            if (*(buff+1) == 'M') {
                print("miss hit \n");
                hit_count++;
                *this = max++;
            }
            else {
                print("miss \n");
            }
            miss_count++;
        }

        // 驱逐
        else {
            long min = 0x7FFFFFFFFFFFFFFF;
            this = nowptr;
            for (int i=0; i < linesperset; i++) {
                if (*this != 0 && ((*this) < min)) {
                    min = *this;
                    index = i;
                }
                this++;
            }
            *(tagptr + set *linesperset + index) = tag;
            *(nowptr + index) = max++;
            if (*(buff+1) == 'M') {
                print("miss eviction hit \n");
                hit_count++;
            }
            else {
                print("miss eviction \n");
            }
            miss_count++;
            eviction_count++;
        }
        ff:;
    }

    printf("hits:%ld ", hit_count);
    printf("misses:%ld ", miss_count);
    printf("evictions:%ld\n", eviction_count);
    // printSummary(hit_count, miss_count, eviction_count);
    free(tagptr);
    free(usedptr);
    fclose(fp);
    return 0;
}

void getaddrfromline(char* buff, char* result) {
    long start = 0;
    long end = 0;

    for (long i=0; ; i++) {
        if ((buff[i] == ' ') && (i != 0) &&(buff[i+1] != ' ')) {
            start = i + 1;
        }
        else if (buff[i] == ',') {
            end = i;
            break;
        }
    }
    strncpy(result, buff + start, end - start);
}

long getlownnumber(long addr, long n) {
    long x = 1;
    for (long i=1; i<n; i++) x = x | (x << 1);
    return x & addr;
}

代码非常清晰： 首先解析命令行参数， 获取缓存参数以及是否打印详细信息的标志， 然后 malloc 对应大小的 tag 和 used(因为需要使用最近最久未使用算法驱逐对应的块)， 之后读取参数的 trace 文件， 打印每一次缓存命中情况。这里获取命令行参数没有使用 说明文件 推荐的 getopt 函数， 因为我觉得直接通过 argc 和 argv 挺方便。

结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
➜  cachelab-handout git:(master) make      
gcc -g -Wall -Werror -std=c99 -m64 -o csim csim.c cachelab.c -lm 
gcc -g -Wall -Werror -std=c99 -m64 -O0 -c trans.c
gcc -g -Wall -Werror -std=c99 -m64 -o test-trans test-trans.c cachelab.c trans.o 
gcc -g -Wall -Werror -std=c99 -m64 -O0 -o tracegen tracegen.c trans.o cachelab.c
# Generate a handin tar file each time you compile
tar -cvf ardxwe-handin.tar  csim.c trans.c 
csim.c
trans.c
➜  cachelab-handout git:(master) ✗ ./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

TEST_CSIM_RESULTS=27

都正确。 加入 -v 查看输出是否一致:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
➜  cachelab-handout git:(master) ✗ gcc -o csim csim.c                                     
➜  cachelab-handout git:(master) ✗ ./csim -v -s 4 -E 1 -b 4 -t traces/yi.trace > 1.txt    
➜  cachelab-handout git:(master) ✗ ./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace > 2.txt
➜  cachelab-handout git:(master) ✗ diff 1.txt 2.txt                                       
➜  cachelab-handout git:(master) ✗ cat 1.txt                                              
L 10,1 miss 
M 20,1 miss hit 
L 22,1 hit 
S 18,1 hit 
L 110,1 miss eviction 
L 210,1 miss eviction 
M 12,1 miss eviction hit 
hits:4 misses:5 evictions:3
➜  cachelab-handout git:(master) ✗ cat 2.txt 
L 10,1 miss 
M 20,1 miss hit 
L 22,1 hit 
S 18,1 hit 
L 110,1 miss eviction 
L 210,1 miss eviction 
M 12,1 miss eviction hit 
hits:4 misses:5 evictions:3

一切都一样。

PART B

我不会。