CSAPP Cache Lab
本 Lab 主要考察对计算机高速缓存（Cache）机制的理解，以及如何针对 Cache 进行程序的优化，对应知识点为书中的 6.4 ~ 6.6 节内容。
Part A: Writing a Cache Simulator
思路
基本流程
Part A 需要实现一个 Cache 模拟器，能够根据 valgrind 工具所生成的访存跟踪数据，模拟在特定参数的 Cache 环境下的命中（hits）次数、不命中（misses）次数和置换（evictions）次数，目标是实现与 csim-ref 同等的功能。模拟器需要具备的几个功能模块如下：
对命令行参数进行参数解析。
读取 trace 文件并解析为地址访问流。
定义 Cache 模拟器数据结构，以及相关的函数操作，包括初始化和地址访问。
遍历解析出来的地址访问流，依次进行访问模拟，计算得到命中次数等信息。
接下来分别对它们进行介绍。
命令行参数解析
根据实验手册的提示，可以使用 getopt 函数进行命令行参数的解析。另外，如果需要支持长选项（形如 --opt arg），则可以使用 GNU C 库提供的扩展版本 getopt_long 函数，其使用方法如下：
- generated by GPT4o
函数原型
include <getopt.h> int getopt_long(int argc, char *const argv[], const char *optstring, const struct option *longopts, int *longindex);
参数说明
1.
argc和argv与标准
getopt相同，分别表示命令行参数的个数和数组。2.
optstring一个字符串，表示短选项的格式规则：
- 每个选项是一个字符。
- 如果选项需要参数，在字符后添加一个冒号（
:）。- 如果选项的参数是可选的，在字符后添加两个冒号（
::）。3.
longopts一个指向
struct option数组的指针，用于定义长选项。
struct option定义如下：struct option { const char *name; // 长选项的名称 int has_arg; // 选项是否需要参数（no_argument, required_argument, optional_argument） int *flag; // 如果为 NULL，则返回值为 val；否则将 *flag 设置为 val 并返回 0 int val; // 短选项的字符值或自定义值 };
name：长选项名称，例如"help"对应--help。has_arg：
no_argument（0）：无参数。required_argument（1）：需要参数。optional_argument（2）：参数可选。flag：
- 如果为
NULL，getopt_long会返回val的值。- 如果非
NULL，getopt_long会将*flag设置为val，并返回 0。val：指定与该长选项关联的返回值（通常与短选项的字符值一致）。4.
longindex指向一个整型变量的指针，用于存储被解析的长选项在
longopts数组中的索引位置。如果不需要，可以传NULL。
返回值
- 返回短选项的字符值，或者由
struct option中val指定的值。- 遇到未知选项时返回
?。- 当没有更多选项时，返回
-1。
根据 getopt_long 的返回值，以及全局变量 optarg，可以对不同的命令行参数进行分发处理。
// 参数定义
struct option long_options[] = {
{ "help", no_argument, NULL, 'h' },
{ "verbose", no_argument, NULL, 'v' },
{ "set", required_argument, NULL, 's' },
{ "lines", required_argument, NULL, 'E' },
{ "block", required_argument, NULL, 'b' },
{ "trace", required_argument, NULL, 't' },
{ 0, 0, 0, 0 }
};
// 参数解析
int opt;
while ((opt = getopt_long(argc, argv, "hvs:E:b:t:", long_options, NULL)) != -1) {
switch (opt) {
case 'h':
print_usage();
return 0;
case 'v':
vflag = 1;
break;
case 's':
s = atoi(optarg);
break;
case 'E':
E = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
break;
case 't':
trace_file = optarg;
break;
default:
print_usage();
return 1;
}
}trace 文件解析
对 trace 文件进行解析，首先读取文件中的每一行操作，对于 operation 为 I 的访存操作，直接跳过不做处理。由于剩余的 M, L, S 操作都满足格式 [space]operation address,size，因此可以直接使用 sscanf 进行解析，提取出各字段。
对不同操作的处理比较简单：L 和 S 操作需要一次访存，M 操作需要两次访存。
这里我没有考虑一次访存位于多个 Cache 行中的情况，始终视作一次/两次访存，也通过了全部测试样例。
char line[256];
while (fgets(line, sizeof(line), file)) {
if (line[0] == '\n' || line[0] != ' ') continue;
line[strlen(line) - 1] = '\0'; // 去除尾置换行符
char *pline = line + 1; // 去除前导空格
char operation;
int address, size;
if (sscanf(pline, " %c %x,%d", &operation, &address, &size) != 3) {
fprintf(stderr, "Invalid line format: %s\n", pline);
continue;
}
access_cache(&cache, address);
if (operation == 'M') {
access_cache(&cache, address);
}
}Cache 模拟器数据结构设计
整个 Cache 模拟器包含 Cache 数据部分、Cache 的参数和命中次数等模拟结果。
typedef struct {
int s;
int E;
int b;
int set_num;
CacheSet *sets;
int hit_count;
int miss_count;
int evict_count;
int access_count;
} Cache;s, E, b 参数即命令行输入的参数。Cache 数据部分可以划分为若干个 Cache 组，组的数量 set_num 等于 $2^s$。
每个 Cache 组可划分为 E 个 Cache 行。
typedef struct {
CacheLine *lines;
} CacheSet;而每个 Cache 行包含有效位、tag 和访问位。由于我们只需要统计命中次数等信息，因此在进行访存模拟时，无需实际存储任何数据内容，只需要将有效位置为 1，并更新 tag 和访问位（用于行替换策略）。
typedef struct {
int valid;
int tag;
int last_used;
} CacheLine;地址访问
根据地址进行模拟访存时，首先需要根据地址 address 获取 Cache 数据中对应的组号 index 和 tag。
组号即地址 address 的第 $b$ 到 $b + s$ 位，tag 即地址 address 的高位部分。
void get_cache_parts(Cache *cache, int address, int *tag, int *index)
{
*index = (address >> cache->b) & (cache->set_num - 1);
*tag = address >> (cache->s + cache->b);
}得到组号和 tag 后，遍历对应 Cache 组的所有行，进行 tag 的对比。若存在某一行的 tag 与 address 对应的 tag 相同，说明缓存命中，更新 hit_count 次数；否则，缓存不命中，更新 miss_count 次数，并将不命中的内存块写入 Cache 中。
int isHit = 0; // 是否命中
CacheSet *set = &cache->sets[index];
for (int i = 0; i < cache->E; ++i) {
if (set->lines[i].valid == 1 && set->lines[i].tag == tag) {
isHit = 1;
++cache->hit_count;
set->lines[i].last_used = cache->access_count++;
break;
}
}这里可能涉及到 Cache 组已满的情况，为此需要进行替换，替换策略采用 LRU 策略，即选取最近最久未被访问过的 Cache 行。为此需要维护访问位，这里为了实现的方便，访问“位” last_used 使用一个整数来存储，其值表示本 Cache 行最近一次访问是整个 Cache 的第 last_used 次访问。因此，last_used 值越小，表示本行最近最久未被访问。
if (!isHit) { // 未命中
++cache->miss_count;
int lru_index = 0;
for (int i = 1; i < cache->E; ++i) {
// LRU策略选择写入行
if (set->lines[i].last_used < set->lines[lru_index].last_used) {
lru_index = i;
}
}
if (set->lines[lru_index].valid == 1) {
++cache->evict_count; // 行置换
}
set->lines[lru_index].valid = 1;
set->lines[lru_index].tag = tag;
set->lines[lru_index].last_used = cache->access_count++;
}代码
#include "cachelab.h"
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
int vflag; // verbose flag
// 根据vflag选择是否打印信息
void trace_info(const char* info)
{
if (vflag) {
printf("%s", info);
}
}
// 缓存行
typedef struct {
int valid;
int tag;
int last_used;
} CacheLine;
// 缓存组
typedef struct {
CacheLine *lines;
} CacheSet;
// 缓存模拟器
typedef struct {
int s;
int E;
int b;
int set_num;
CacheSet *sets;
int hit_count;
int miss_count;
int evict_count;
int access_count;
} Cache;
// 初始化缓存模拟器
void init_cache(Cache *cache, int s, int E, int b)
{
cache->s = s;
cache->E = E;
cache->b = b;
cache->set_num = 1 << s;
cache->sets = (CacheSet *)malloc(cache->set_num * sizeof(CacheSet));
for (int i = 0; i < cache->set_num; ++i) {
cache->sets[i].lines = (CacheLine *)malloc(E * sizeof(CacheLine));
for (int j = 0; j < E; ++j) {
cache->sets[i].lines[j].valid = 0;
cache->sets[i].lines[j].last_used = 0;
}
}
cache->hit_count = 0;
cache->miss_count = 0;
cache->evict_count = 0;
cache->access_count = 0;
}
// 获取地址对应组号和tag
void get_cache_parts(Cache *cache, int address, int *tag, int *index)
{
*index = (address >> cache->b) & (cache->set_num - 1);
*tag = address >> (cache->s + cache->b);
}
// 访问指定地址对应的cache组号和tag
void access_cache(Cache *cache, int address)
{
int tag, index;
get_cache_parts(cache, address, &tag, &index);
int isHit = 0; // 是否命中
CacheSet *set = &cache->sets[index];
for (int i = 0; i < cache->E; ++i) {
if (set->lines[i].valid == 1 && set->lines[i].tag == tag) {
isHit = 1;
trace_info(" hit");
++cache->hit_count;
set->lines[i].last_used = cache->access_count++;
break;
}
}
if (!isHit) { // 未命中
trace_info(" miss");
++cache->miss_count;
int lru_index = 0;
for (int i = 1; i < cache->E; ++i) {
// LRU策略选择写入行
if (set->lines[i].last_used < set->lines[lru_index].last_used) {
lru_index = i;
}
}
if (set->lines[lru_index].valid == 1) {
trace_info(" eviction");
++cache->evict_count; // 行置换
}
set->lines[lru_index].valid = 1;
set->lines[lru_index].tag = tag;
set->lines[lru_index].last_used = cache->access_count++;
}
++cache->access_count;
}
void print_usage()
{
printf("Usage: ./csim-ref [-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\n");
printf("Examples:\n");
printf(" linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n");
printf(" linux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}
int main(int argc, char *argv[])
{
vflag = 0;
int s = -1, E = -1, b = -1;
char *trace_file = NULL;
// 参数定义
struct option long_options[] = {
{ "help", no_argument, NULL, 'h' },
{ "verbose", no_argument, NULL, 'v' },
{ "set", required_argument, NULL, 's' },
{ "lines", required_argument, NULL, 'E' },
{ "block", required_argument, NULL, 'b' },
{ "trace", required_argument, NULL, 't' },
{ 0, 0, 0, 0 }
};
// 参数解析
int opt;
while ((opt = getopt_long(argc, argv, "hvs:E:b:t:", long_options, NULL)) != -1) {
switch (opt) {
case 'h':
print_usage();
return 0;
case 'v':
vflag = 1;
break;
case 's':
s = atoi(optarg);
break;
case 'E':
E = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
break;
case 't':
trace_file = optarg;
break;
default:
print_usage();
return 1;
}
}
Cache cache;
init_cache(&cache, s, E, b);
FILE *file = fopen(trace_file, "r");
if (!file) {
fprintf(stderr, "Faild to open file %s\n", trace_file);
return -1;
}
char line[256];
while (fgets(line, sizeof(line), file)) {
if (line[0] == '\n' || line[0] != ' ') continue;
line[strlen(line) - 1] = '\0'; // 去除尾置换行符
char *pline = line + 1; // 去除前导空格
char operation;
int address, size;
if (sscanf(pline, " %c %x,%d", &operation, &address, &size) != 3) {
fprintf(stderr, "Invalid line format: %s\n", pline);
continue;
}
trace_info(pline);
access_cache(&cache, address);
if (operation == 'M') {
access_cache(&cache, address);
}
trace_info("\n");
}
printSummary(cache.hit_count, cache.miss_count, cache.evict_count);
return 0;
}Part B: Optimizing Matrix Transpose
分块优化
根据实验手册的说明，分块是降低 Cache misses 的有效方法，可以参考矩阵乘分块优化方法。
对于朴素二重循环的矩阵转置方法，矩阵 $A$ 的空间局部性较好，但是矩阵 $B$ 的时间局部性和空间局部性都比较差，访问效率很低。而采用分块方法时，矩阵 $A$ 的空间局部性没有太大下降，但是 $B$ 的时间局部性和空间局部性却有了很大的提升。
因此我先尝试了分块优化方法，问题在于，块大小应该如何选取？为了偷懒（🤭），我利用 C 语言宏编写了一个分块矩阵转置的函数模板，并测试三个测试样例在不同块大小下的 Cache misses 次数。
#define DEFINE_BLOCKED_TRANSPOSE(R, C) \
char blocked##R##_##C##_trans_desc[] = "(" #R ", " #C ") Blocked row-wise scan transpose"; \
void blocked##R##_##C##_trans(int M, int N, int A[N][M], int B[M][N]) \
{ \
int i, j, ii, jj, tmp; \
int brsize = R, bcsize = C; \
int enr = brsize * (N / brsize); \
int enc = bcsize * (M / bcsize); \
\
for (ii = 0; ii <= enr; ii += brsize) { \
for (jj = 0; jj <= enc; jj += bcsize) { \
for (i = ii; i < (N < ii + brsize ? N : ii + brsize); ++i) { \
for (j = jj; j < (M < jj + bcsize ? M : jj + bcsize); ++j) {\
tmp = A[i][j]; \
B[j][i] = tmp; \
} \
} \
} \
} \
}在使用时，只需要将模板“实例化”即可：
DEFINE_BLOCKED_TRANSPOSE(4, 4)
DEFINE_BLOCKED_TRANSPOSE(5, 5)
...
DEFINE_BLOCKED_TRANSPOSE(20, 20)然后将这些函数注册到 registerFunctions 中，使用 test-trans 即可对所有注册的矩阵转置函数进行测试。
void registerFunctions()
{
/* Register your solution function */
registerTransFunction(transpose_submit, transpose_submit_desc);
/* Register any additional transpose functions */
registerTransFunction(trans, trans_desc);
// Blocked
registerTransFunction(blocked4_4_trans, blocked4_4_trans_desc);
registerTransFunction(blocked5_5_trans, blocked5_5_trans_desc);
...
registerTransFunction(blocked20_20_trans, blocked20_20_trans_desc);
}经过暴力枚举，发现在 $32×32$、$64×64$、$61×67$ 下的最优矩阵分块大小分别为 8、4、17，在 transpose-submit 函数中根据 M、N 的值分别调用适合的转置函数，得分如下：
循环展开
在上面的分块转置模板中，矩阵 $A$ 和 $B$ 是交替进行访问的，这可能导致矩阵 $A$ 访问的块马上又在访问矩阵 $B$ 时被置换，因此可以将最内层循环进行展开，对于分块大小为 $bsize$ 的转置方法，先连续访问完 $A$ 的一个 $1×bsize$ 的切片，将其暂存入变量中，再连续访问 $B$ 的 $bsize×1$ 切片。
将 $32×32$ 和 $64×64$ （$61×67$ 的测试样例已得满分，没有选择进一步优化）的对应的分块转置方法的内层循环展开后，得分如下：
这样，$32×32$ 也得到了满分，但是 $64×64$ 分数仍然比较低，看来简单的分块方法还不够，可能需要针对 Cache 的参数将矩阵元素访问顺序进行重排，这部分我暂时没有完成，之后有时间可以再尝试一下。
微信
支付宝
