CSAPP-LAB-Cache Lab

预备知识

开始这个实验前,需要学习《CSAPP 第六章-存储器层次结构》的相关内容,与缓存相关的内容,我也做了相关的CPU Cache 高速缓存学习记录可以参考。

实验相关的文件可以从CS:APP3e, Bryant and O’Hallaron下载。

其中,

  • README:介绍实验目的和实验要求,以及实验的相关文件。需要注意的是,必须在 64-bit x86-64 system 上运行实验。需要安装 Valgrind 工具。
  • Writeup:实验指导。
  • Release Notes:版本发布信息。
  • Self-Study Handout:需要下载的压缩包,里面包含了待修改的源码文件等。

下载 Self-Study Handout 并解压,得到如下文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
├── cachelab.c    # 一些辅助函数,如打印输出等,不需要修改
├── cachelab.h # 同上
├── csim.c # 需要完善的主文件,需要在这里模拟Cache
├── csim-ref # 已经编译好的程序,我们模拟的Cache需要与这个程序运行的结果保持一致
├── driver.py # 驱动程序,运行 test-csim 和 test-trans
├── Makefile # 用来编译csim程序
├── README #
├── test-csim # 测试缓存模拟器
├── test-trans.c # 测试转置功能
├── tracegen.c # test-trans 辅助程序
├── traces # test-csim.c 使用的跟踪文件
│ ├── dave.trace
│ ├── long.trace
│ ├── trans.trace
│ ├── yi2.trace
│ └── yi.trace
└── trans.c

Part A —— Writing A Cache Simulator

在 Part A,我们将在 csim.c 中编写一个缓存模拟器,它将 valgrind 内存跟踪作为输入,在此跟踪上模拟高速缓存的命中/未命中行为,并输出命中、未命中和驱逐的总数。

这里的输入由valgrind通过以下命令生成的:

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

--log-fd=1表示将输出输出到标准输出;
--tool=lackey:Lackey 是一个简单的 Valgrind 工具,可进行各种基本程序测量;
--trace-mem=yes:Lackey 的一个参数,启用后,Lackey 会打印程序几乎所有内存访问的大小和地址;
ls -l:是一个简单的程序,可以查看当前目录下的文件列表。
也就是检测ls -l程序在运行时访问内存的情况。

执行结果像下面的形式:

1
2
3
4
5
6
7
8
9
10
11
# [space]operation address,size
I 0400639c,4
L 1ffeffec00,8
I 040063a0,2
S 1ffeffea50,8
I 040063a2,4
L 1ffeffebf0,8
I 040063a6,3
I 040063a9,3
L 1ffeffebf8,4
I 040063ac,7

操作字段表示内存访问的类型:I表示指令加载,L表示数据加载,S表示数据存储,M表示数据修改(即,数据加载后跟数据存储) )。每个I之前都没有空格。每个MLS之前总是有一个空格。地址字段指定一个 64 位的十六进制内存地址。 size 字段指定操作访问的字节数。

了解这些基础后,我们最主要的是要明确,我们需要实现一个什么样的程序,这个程序具体有哪些参数,怎么执行的csim-ref是已经完成的可执行文件,它的用法是

1
./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>
  • -h:打印帮助信息;
  • -v:显示详细信息,如是 I,L 还是 M;
  • -s <s>:组索引位数($S=2^{s}$组个数);
  • -E <E>:关联性(每组的行数);
  • -b <b>:块位数($B=2^{b}$ 是块大小);
  • -t <tracefile>:valgrind 生成的文件;

如:

1
2
./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:3

如果显示详细信息可以执行:

1
2
3
4
5
6
7
8
9
./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace
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

我们的目的就是要完善csim.c,使其能够使用上面相同的参数,得到与csim-ref相同的结果。
Cache Lab Implementa/on and Blocking这份 PPT 里有一些实验指导,可以参考。
首先需要解决的就是如何处理输入的参数,我们可以使用 PPT 里提到的getopt库来解决。

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

static int S; // 组个数
static int s; // 组占的位数
static int E;
static int B;
static int hits = 0;
static int misses = 0;
static int evictions = 0;

typedef struct _CacheLine {
unsigned tag;
struct _CacheLine *next;
struct _CacheLine *prev;
} CacheLine;

typedef struct _Cache {
CacheLine *head;
CacheLine *tail;
int *size;
} Cache;

static Cache *cache;

void parse_option(int argc, char **argv, char **fileName)
{
int option;
while ((option = getopt(argc, argv, "s:E:b:t:")) != -1) {
switch (option) {
case 's':
s = atoi(optarg);
// 传入的参数为占用的bit,需要转换为10进制
S = 1 << s;
case 'E':
E = atoi(optarg);
case 'b':
B = atoi(optarg);
case 't':
strcpy(*fileName, optarg);
}
}
}

void initialize_cache()
{
cache = malloc(S * sizeof(*cache));
for (int i = 0; i < S; i++) {
cache[i].head = malloc(sizeof(CacheLine));
cache[i].tail = malloc(sizeof(CacheLine));

cache[i].head->next = cache[i].tail;
cache[i].tail->prev = cache[i].head;
(cache[i].size) = (int *)malloc(sizeof(int));
*(cache[i].size) = 0;
}
}

/*!
* @breif Add a new CacheLine to the Cache first line
* @param nodeToDel CacheLine to be deleted
* @param curLru Current Cache
*/
void insert_first_line(CacheLine *node, Cache *curLru)
{
node->next = curLru->head->next;
node->prev = curLru->head;

curLru->head->next->prev = node;
curLru->head->next = node;

*(curLru->size) = *(curLru->size) + 1;
}

void evict(CacheLine *nodeToDel, Cache *curLru)
{
nodeToDel->next->prev = nodeToDel->prev;
nodeToDel->prev->next = nodeToDel->next;
*(curLru->size) = *(curLru->size) - 1;
}

void update(unsigned address)
{
unsigned int mask = 0xFFFFFFFF;
unsigned int maskSet = mask >> (32 - s);
// 取出组索引
unsigned int targetSet = ((maskSet) & (address >> B));
// 取出标记
unsigned int targetTag = address >> (s + B);

Cache curLru = cache[targetSet];

// 查找是否存与当前标记位相同的缓存行
CacheLine *cur = curLru.head->next;
bool found = 0;
while (cur != curLru.tail) {
if (cur->tag == targetTag) {
found = true;
break;
}
cur = cur->next;
}

if (found) {
hits++;
evict(cur, &curLru);
insert_first_line(cur, &curLru);
printf("> hit!, set: %d \n", targetSet);
} else {
CacheLine *newNode = malloc(sizeof(CacheLine));
newNode->tag = targetTag;
if (*(curLru.size) == E) { // 如果缓存已满,则删除最后一个缓存行
evict(curLru.tail->prev, &curLru);
insert_first_line(newNode, &curLru);
evictions++;
misses++;
printf("> evic && miss set:%d\n", targetSet);
} else {
misses++;
insert_first_line(newNode, &curLru);
printf("> miss %d\n", targetSet);
}
}
}

void cache_simulate(char *fileName)
{
// 分配并初始化S组缓存
initialize_cache();

FILE *file = fopen(fileName, "r");
char op;
unsigned int address;
int size;

while (fscanf(file, " %c %x,%d", &op, &address, &size) > 0) {
printf("%c, %x %d\n", op, address, size);
switch (op) {
case 'L':
update(address);
break;
case 'M':
update(address);
case 'S':
update(address);
break;
}
}
}

int main(int argc, char **argv)
{
char *fileName = malloc(100 * sizeof(char));

parse_option(argc, argv, &fileName);
cache_simulate(fileName);
printSummary(hits, misses, evictions);
return 0;
}
构建和测试 RISC-V 架构下启用 ACPI 的内核 CPU Cache 高速缓存
You need to set install_url to use ShareThis. Please set it in _config.yml.

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×