综述
实验下载：https://csapp.cs.cmu.edu/3e/labs.html
这个实验将帮助你理解 cache 缓存对 C 程序性能的影响。
这个实验分为两部分，第一部分你将完成一个 C 程序（大约 200~300 行）来模拟 cache 缓存的行为。第二部分，你需要优化一个矩阵转置的函数，已达到 cache miss 最小的目的。
在实验压缩包里，你需要修改两个文件：csim.c 和 trans.c。通过以下命令进行编译：
make clean
make描述
Reference Trace Files
我们使用 reference trace files 来评估你 Part A cache 模拟器的正确性。这些文件是由 Linux 程序 valgrind 生成的。例如：
valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l这条指令将运行程序 "ls -l"，并捕获其内存访问，并将结果打印到 stdout。
operation address,size
I 0400d7d4,8
M 0421c7f0,4
L 04f6b868,8
S 7ff0005c8,8每行表示一个或者两个内存访问。
operation
"I" 表示 an instruction load。
"L" 表示 a data load。
"S" 表示 a data store。
"M" 表示 a data modify。相当于 L 和 S 操作。
address
表示 64 位的 16 进制地址，表示内存地址。
size
表示本次内存操作的字节数大小。
Part A: Cache 模拟器
你将在 csim.c 完成一个 cache 模拟器，接收 a valgrind memory trace 作为输入，模拟 cache 缓存命中/非命中的行为，然后输出 hits, misses, and evictions 的总数。
我们已经为你提供了一个可供参考的 cache 模拟器的二进制可执行文件，称为 csim-ref，模拟 cache 在 a valgrind trace file 上的行为。其使用 LRU 的替换策略来进行 cache line 替换。
命令行参数如下：
./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>-S <s>：set index bits 的数目 S=2^s；
-E <E>：每个 set 的行数；
-b <b>：block bits 的数目 B=2^b 是 block 大小；
-t <tracefile>
示例：
./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:3详细模式下的相同示例：
./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示例分析：
s = 4，即 S = 16；E = 1；b = 4, 即 B = 16，因此
L 10, 1
地址 000...00010000，t = 0, set = 1, b = 0，miss
M 20, 1
地址 000...00100000，t = 0, set = 2, b = 0，miss, hit
L 22, 1
地址 000...00100010，t = 0, set = 2, b = 2，hit
S 18, 1
地址 000...00011000，t = 0, set = 1, b = 8，hit
L 110, 1
地址 000..100010000，t = 1, set = 1, b = 0，miss eviction
L 210, 1
地址 000.1000010000，t = 2, set = 1, b = 0，miss eviction
M 12, 1
地址 000...00010010，t = 0, set = 1, b = 2, miss eviction hit
Part A 编码规则
对于这个实验，我们的重点在于 data cache 的性能，所以你的模拟器应该忽略所有 instruction cache 访问（即以 "I" 开头的行）。回想一下，valgrind 总是把 "I" 放在第一位，即开头无空格，"M"、"L"、"S" 前有空格。
在 main 函数的结尾需要调用
printSummary，这个函数会输出 hits, misses, 和 evictions 的总数。
printSummary(hit_count, miss_count, eviction_count);对于本实验，应该假设内存访问是正确对齐的，例如单个内存访问永远不会跨越块边界。通过做这个假设，你可以忽略 trace files 中的请求大小。
Part B 优化矩阵转置
Part B 部分，你将在 trans.c 中实现一个转置函数，要求尽可能少的造成 cache misses。
用 A 表示矩阵，Aij 表示第 i 行，第 j 列的元素。A 的转置表示为 AT，即 Aij = ATji。
为了帮助你开始，实验在 trans.c 中提供了一个示例转置程序，该程序计算 N * M 的矩阵 A 的转置，并将结果存到 M * N 的矩阵 B 中。
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N]);这个示例是正确的，但不是高效的，因为存在大量的 cache misses。
在 Part B 中，你需要写一个相似的函数，transpose_submit，将不同大小的矩阵转置的 cache misses 最小化。
char transpose_submit_desc[] = "Transpose submission";
void transpose_submit(int M, int N, int A[N][M], int B[M][N]);不要修改字符串 "Transpose submission"，自动评分程序会通过搜索字符串的方式去决定哪一个转置函数需要评价。
Part B 编码规则
在 trans.c 中的代码必须在没有警告的情况下编译才能获得积分；
每个转置函数允许定义最多 12 个 int 类型的局部变量；
不允许通过使用任何 long 类型的变量或使用任何位技巧将多个值存储到单个变量来回避前面的规则；
转置函数不可以使用递归；
如果使用帮助函数，则所有函数一起不能超过 12 个局部变量；
你的转置函数不可以修改数组 A。然而，你可以对数组 B 的内容做任何你想做的事情；
不允许在代码中定义任何数组或使用 malloc 的任何变体。
Part B 的评分标准
对于 Part B，我们将在三个不同大小的输出矩阵上评估 transpose_submit 函数的正确性和性能：
32 * 32（M=32，N=32）
64 * 64（M=64，N=64）
61 * 67（M=61，N=67）
指定 cache 参数 s=5，E=1，b=5。
32 * 32，cache misses 在 300 以内；
64 * 64，cache misses 在 1300 以内；
61 * 67，cache misses 在 2000 以内。
帮助
Part A
实验提供一个自动评分程序，test-csim，其使用 reference traces 测试你的 cache 模拟器的正确性。在运行 test 前确保你的模拟器被成功编译：
使用一个小的 traces 来 debugging，例如 traces/dave.trace；
csim 不需要使用 -v 特性，但是强烈建议你去实现，因为这样可以帮助你 debug；
建议使用 getopt 函数来解析命令行参数，你需要包含以下头文件：
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>Part B
实验提供一个自动评分程序，test-trans.c，该程序将测试你注册给自动评分程序的每个转置函数的正确性和性能。
你可以在你的 trans.c 文件中注册 100 个版本的转置函数。每个转置函数的版本如下格式：
/* Header comment */
char trans_simple_desc[] = "A simple transpose";
void trans_simple(int M, int N, int A[N][M], int B[M][N])
{
/* your transpose code here */
}注册的方式如下所示：
registerTransFunction(trans_simple, trans_simple_desc);trans.c 中的 registerFunctions，会自动计算每个注册的转置函数并打印结果。当然，其中一个注册的函数必须是您要提交的 transpose_submit 函数：
registerTransFunction(transpose_submit, transpose_submit_desc);自动评测程序将矩阵尺寸作为输入，例如，32 * 32 矩阵，
make
./test-trans -M 32 -N 32Step 1: Evaluating registered transpose funcs for correctness:
func 0 (Transpose submission): correctness: 1
func 1 (Simple row-wise scan transpose): correctness: 1
func 2 (column-wise scan transpose): correctness: 1
func 3 (using a zig-zag access pattern): correctness: 1
Step 2: Generating memory traces for registered transpose funcs.
Step 3: Evaluating performance of registered transpose funcs (s=5, E=1, b=5)
func 0 (Transpose submission): hits:1766, misses:287, evictions:255
func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151
func 2 (column-wise scan transpose): hits:870, misses:1183, evictions:1151
func 3 (using a zig-zag access pattern): hits:1076, misses:977, evictions:945
Summary for official submission (func 0): correctness=1 misses=287在这个例子中，我们在 trans.c 中注册了四个不同的转置函数。test-trans 程序测试每个注册的函数，显示每个函数的结果。
这里有一些关于做 B 部分的提示和建议。
Test-trans 程序将函数 i 的 trace 保存在文件 trace.fi 中。这些 trace 文件是非常宝贵的调试工具，可以帮助你准确地了解每个转置函数的 hits 和 misses 来自何处：
./csim-ref-v-s 5-E 1-b 5-t trace.f0
S 68312c,1 miss
L 683140,8 miss
L 683124,4 hit
L 683120,4 hit
L 603124,4 miss eviction
S 6431a0,4 miss
...由于转置函数是在直接映射的缓存上求值的，因此冲突不命中是一个潜在的问题。思考一下代码中潜在的冲突不命中，特别是沿着对角线。尝试能够减少这些冲突不命中次数的访问模式。
Bocking 是一种减少 cache misses 的有用技术：
https://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf
Part A
数据结构
typedef struct {
bool is_valid;
unsigned long long tag;
int timestamp;
} CacheLine;
typedef struct {
CacheLine* cache_line;
} CacheSet;
typedef struct {
CacheSet* cache_set;
} Cache;
typedef struct {
int s;
int e;
int b;
char path[256];
bool v;
} Metadata;
typedef struct {
int hits;
int misses;
int evictions;
} Result;定义类似 cache 的结构，Cache，CacheSet 和 CacheLine。定义 Metadata 来存储输入的 options 信息，定义 Result 来存储结果。
本实验的 cache line 替换策略使用 LRU，LRU 的实现具体可以参考：https://www.chongchenshi.top/archives/1723509320860 ， 由于 c 语言中没有 hashset 和 list（懒得实现了），所以暂时不采用 O(1) 的方法来实现。
整体实现
int main(int argc, char* argv[])
{
Metadata metadata;
memset(&metadata, 0, sizeof(Metadata));
if(ParseOptions(argc, argv, &metadata)) {
Result result;
memset(&result, 0, sizeof(Result));
HandleCache(&metadata, &result);
printSummary(result.hits, result.misses, result.evictions);
}
return 0;
}ParseOptions 负责参数解析
bool ParseOptions(int argc, char* argv[], Metadata* metadata) {
const char* optstring = "hvs:E:b:t:";
int ret;
while((ret = getopt(argc, argv, optstring)) != -1) {
switch (ret) {
case 'h': {
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");
printf("\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");
return false;
}
case 's': {
metadata->s = atoi(optarg);
break;;
}
case 'E': {
metadata->e = atoi(optarg);
break;
}
case 'b': {
metadata->b = atoi(optarg);
break;
}
case 't': {
memcpy(metadata->path, optarg, strlen(optarg));
break;
}
case 'v': {
metadata->v = true;
break;
}
default:
printf("unknown option: %s\n", optarg);
exit(-1);
}
}
return true;
}HandleCache 用于模拟 Cache 逻辑
void HandleCache(Metadata* metadata, Result* result) {
int S = (1 << metadata->s), E = metadata->e;
Cache cache;
CallocCache(&cache, S, E);
FILE* fp = fopen(metadata->path, "r");
if(fp == NULL) {
printf("%s is not exits!!!\n", metadata->path);
exit(-1);
}
char line[1024];
while(fgets(line, 1024, fp) != NULL) {
if(line[0] == 'I') continue;
char op;
unsigned long long address;
int data;
if(sscanf(line, " %c %llx,%d", &op, &address, &data) == -1) {
printf("%s format is error!!!\n", line);
exit(-1);
}
if(metadata->v) printf("%c %llx,%d ", op, address, data);
AddressSplit(op, address, &cache, metadata, result);
}
fclose(fp);
DeleteCache(&cache, S);
}其中 CallocCache 和 DeleteCache 用于动态分配内存
void CallocCache(Cache* cache, int S, int E) {
cache->cache_set = (CacheSet*)calloc(S, sizeof(CacheSet));
for(int i = 0; i < S; ++i)
cache->cache_set[i].cache_line = (CacheLine*)calloc(E, sizeof(CacheLine));
}
void DeleteCache(Cache* cache, int S) {
for(int i = 0; i < S; ++i)
free(cache->cache_set[i].cache_line);
free(cache->cache_set);
}AddressSplit 用于处理地址的拆分
void AddressSplit(char op, unsigned long long address, Cache* cache, Metadata* metadata, Result* result) {
unsigned long long address_tag = (address >> (metadata->s + metadata->b));
int address_set = (address >> metadata->b) & (~(-1 << metadata->s));
switch (op)
{
case 'L':
case 'S':
LRUCacheLine(address_set, address_tag, 1, cache, metadata, result);
break;
case 'M':
LRUCacheLine(address_set, address_tag, 2, cache, metadata, result);
break;
default:
break;
}
}LRUCacheLine 用于实现缓存替换策略
void LRUCacheLine(int set, unsigned long long address_tag, int num, Cache* cache, Metadata* metadata, Result* result) {
int index = -1, max_timestamp = 0, invalid_index = -1, min_index = 0, min_timestamp = INT_MAX;
for(int i = 0; i < metadata->e; ++i) {
if(cache->cache_set[set].cache_line[i].is_valid) {
if(cache->cache_set[set].cache_line[i].tag == address_tag) {
index = i;
}
if(cache->cache_set[set].cache_line[i].timestamp > max_timestamp) {
max_timestamp = cache->cache_set[set].cache_line[i].timestamp;
}
if(cache->cache_set[set].cache_line[i].timestamp < min_timestamp) {
min_timestamp = cache->cache_set[set].cache_line[i].timestamp;
min_index = i;
}
} else {
invalid_index = i;
}
}
if(index == -1) {
if(metadata->v) printf("miss");
result->misses++;
if(invalid_index != -1) {
cache->cache_set[set].cache_line[invalid_index].is_valid = true;
cache->cache_set[set].cache_line[invalid_index].tag = address_tag;
cache->cache_set[set].cache_line[invalid_index].timestamp = max_timestamp + 1;
if(num == 2) {
result->hits++;
if(metadata->v) printf(" hit\n");
} else {
if(metadata->v) printf("\n");
}
} else {
cache->cache_set[set].cache_line[min_index].is_valid = true;
cache->cache_set[set].cache_line[min_index].tag = address_tag;
cache->cache_set[set].cache_line[min_index].timestamp = max_timestamp + 1;
if(num == 1) {
result->evictions++;
if(metadata->v) printf(" eviction\n");
} else {
result->evictions++;
result->hits++;
if(metadata->v) printf(" eviction hit\n");
}
}
} else {
cache->cache_set[set].cache_line[index].timestamp = max_timestamp + 1;
if(metadata->v) printf("hit");
result->hits++;
if(num == 2) {
result->hits++;
if(metadata->v) printf(" hit\n");
} else
if(metadata->v) printf("\n");
}
}结果
Part B
分析
以 4x4 矩阵为例，来进行分析。
根据实验说明，cache 的组成如下所示：
s = 5, E = 1, b = 5
S = 32; E = 1; B = 32
即 cache 块的大小为 32 个字节，即 8 个 int 型数据，故数组中前 8 个元素在同一个块中，后 8 个元素在另一个块中。
A 数组按行访问，B 数组按列访问。
矩阵是先行后列，每个元素是 4 字节。
使用如下命令：
./csim -v -s 5 -E 1 -b 5 -t trace.f0数组 A 的 cache 情况如下所示：
L 10c100,4 miss eviction
10000110000 01000 00000
不命中，8 号 cache 被置换，填充。
L 10c104,4 miss eviction
10000110000 01000 00100
不命中，8 号 cache 被 B 数组占用。
L 10c108,4 miss eviction
10000110000 01000 01000
不命中，8 号 cache 被 B 数组占用。
L 10c10c,4 hit
10000110000 01000 01100
命中 8 号 cache。
L 10c110,4 hit
10000110000 01000 10000
命中 8 号 cache。
L 10c114,4 miss eviction
10000110000 01000 10100
不命中，8 号 cache 被 B 数组占用。
L 10c118,4 miss eviction
10000110000 01000 11000
不命中，8 号 cache 被 B 数组占用。
L 10c11c,4 hit
10000110000 01000 11100
命中 8 号 cache。
L 10c120,4 miss eviction
10000110000 01001 00000
不命中，9 号 cache 被 B 数组占用。
L 10c124,4 hit
10000110000 01001 00100
命中 9 号 cache。
L 10c128,4 hit
10000110000 01001 01000
命中 9 号 cache。
L 10c12c,4 miss eviction
10000110000 01001 01100
不命中，9 号 cache 被数组 B 占用。
L 10c130,4 miss eviction
10000110000 01001 10000
不命中，9 号 cache 被数组 B 占用。
L 10c134,4 hit
10000110000 01001 10100
命中 9 号 cache。
L 10c138,4 hit
10000110000 01001 11000
命中 9 号 cache。
L 10c13c,4 miss eviction
10000110000 01001 11100
不命中，9 号 cache 被数组 B 占用。
数组 B 的 cache 情况如下所示：
S 14c100,4 miss eviction
10100110000 01000 00000
不命中，8 号 cache 被 A 数组占用。
S 14c110,4 miss eviction
10100110000 01000 10000
不命中，8 号 cache 被 A 数组占用。
S 14c120,4 miss eviction
10100110000 01001 00000
不命中，9 号 cache 被填置换，填充。
S 14c130,4 hit
10100110000 01001 10000
命中 9 号 cache。
S 14c104,4 miss eviction
10100110000 01000 00100
不命中，8 号 cache 被 A 数组占用。
S 14c114,4 miss eviction
10100110000 01000 10100
不命中，8 号 cache 被 A 数组占用。
S 14c124,4 hit
10100110000 01001 00100
命中 9 号 cache。
S 14c134,4 hit
10100110000 01001 10100
命中 9 号 cache。
S 14c108,4 miss eviction
10100110000 01000 01000
不命中，8 号 cache 被 A 数组占用。
S 14c118,4 hit
10100110000 01000 11000
命中 8 号 cache。
S 14c128,4 miss eviction
10100110000 01001 01000
不命中，9 号 cache 被 A 数组占用。
S 14c138,4 miss eviction
10100110000 01001 11000
不命中，9 号 cache 被 A 数组占用。
S 14c10c,4 hit
10100110000 01000 01100
命中 8 号 cache。
S 14c11c,4 hit
10100110000 01000 11100
命中 8 号 cache。
S 14c12c,4 miss eviction
10100110000 01001 01100
不命中，9 号 cache 被 A 数组占用。
S 14c13c,4 miss eviction
10100110000 01001 11100
不命中，9 号 cache 被 A 数组占用。
如图所示：
其中含有颜色的方块表示访问冲突。
解决策略：
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
// int i, j, tmp;
// for(i = 0; i < N; i++) {
// for(j = 0; j < M; j++) {
// tmp = A[i][j];
// B[j][i] = tmp;
// }
// }
int x1, x2, x3, x4, x5, x6, x7, x8;
x1 = A[0][0], x2 = A[0][1], x3 = A[0][2], x4 = A[0][3];
x5 = A[1][0], x6 = A[1][1], x7 = A[1][2], x8 = A[1][3];
B[0][0] = x1, B[1][0] = x2, B[2][0] = x3, B[3][0] = x4;
B[0][1] = x5, B[1][1] = x6, B[2][1] = x7, B[3][1] = x8;
x1 = A[2][0], x2 = A[2][1], x3 = A[2][2], x4 = A[2][3];
x5 = A[3][0], x6 = A[3][1], x7 = A[3][2], x8 = A[3][3];
B[0][2] = x1, B[1][2] = x2, B[2][2] = x3, B[3][2] = x4;
B[0][3] = x5, B[1][3] = x6, B[2][3] = x7, B[3][3] = x8;
}将前 8 块数据提前缓存到临时变量中，结果如下图所示：
可以看到 misses 从 22 降到 8。