实验材料
开始依然是一脸懵逼，看了两遍Writeup大概明白要干啥了。整个实验分为两大部分，第一部分是实现一个缓存模拟器，第二个部分是优化矩阵运算。
Part A:Writing a Cache Simulator
给出一系列对于内存的读写，需要实现一个缓存模拟器计算缓存命中，未命中和替换的总次数，还给了一个标准的程序来对答案。
- 每次操作的类型为
L，S和M中的一种，分别为读取，存储和改变，其中M相当于先L再S。仔细分析，在我们的模拟器中L和S没有本质的区别，所以这些操作最后都化为同一种操作，只不过M要做两次这样的操作。 - 要求的替换算法是
LRU，也就是最近最少使用策略，主要有两种实现方式，一种是维护一个时间戳，每次访存暴力找到距离最长的块进行替换，然后暴力更新其他时间戳。另外一个是维护一个队列，每个块保存一个指针指向，同时还要保存前驱的后继，每次访存维护这个队列。显然前一种复杂度高，但是好写。 - 缓存可以看作是一个二维数组
cache[S][E]，在动态分配内存时，可以分配一个一维数组也可以分配一个二维数组，本质是一样的。
在PPT上还给了一些其他帮助，比如如何读取命令行参数等等。除此以外就没什么需要注意的点了，完全可以当一道模拟题去写。
我这里偷了个懒，按照固定的格式去读取参数，使用时间戳的暴力算法进行模拟，最后是写了行不到完成了这个实验。
下面是代码：
#include "cachelab.h"
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
unsigned int tag, time, valid;
} line;
int s, E, b;
int hits, misses, evictions;
line *cache;
void Simulate(unsigned int address)
{
unsigned int tag = address >> s;
unsigned int id = address - (tag << s);
int i, hitPos = -1, validPos = -1, lruPos = -1;
unsigned int lruValue = 0;
for (i = id * E; i < id * E + E; i++)
{
if (cache[i].valid && cache[i].tag == tag)
hitPos = i;
else if (!cache[i].valid)
validPos = i;
if (cache[i].time >= lruValue)
{
lruValue = cache[i].time;
lruPos = i;
}
}
if (hitPos != -1) // hit stage
{
hits++;
for (i = id * E; i < id * E + E; i++)
cache[i].time = (i == hitPos ? 0 : cache[i].time + 1);
return;
}
misses++; // miss stage
if (validPos != -1)
{
cache[validPos].tag = tag;
cache[validPos].valid = 1;
for (i = id * E; i < id * E + E; i++)
cache[i].time = (i == validPos ? 0 : cache[i].time + 1);
return;
}
evictions++; // eviction stage
cache[lruPos].tag = tag;
for (i = id * E; i < id * E + E; i++)
cache[i].time = (i == lruPos ? 0 : cache[i].time + 1);
}
int main(int argc, char *argv[])
{
s = atoi(argv[2]); // get parameters
E = atoi(argv[4]);
b = atoi(argv[6]);
cache = (line *)calloc(sizeof(line), (1 << s) * E);
FILE *inputFile = fopen(argv[8], "r");
char buffer[256];
while (fgets(buffer, 256, inputFile))
{
if (buffer[0] == 'I')
continue;
unsigned int address = 0;
int id = 3;
while (buffer[id] != ',')
{
address *= 16;
address += isalpha(buffer[id]) ? buffer[id] - 'a' + 10 : buffer[id] - '0';
id++;
}
address >>= b;
Simulate(address);
if (buffer[1] == 'M')
Simulate(address);
}
printSummary(hits, misses, evictions);
fclose(inputFile);
free(cache);
return 0;
}
运行结果：
dyume@LAPTOP-LLU88NPC:/mnt/c/Users/dy199/Desktop/cpp/CsappHomework/cachelab$ ./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
顺利通过。
