CSAPP: Cache Lab

这个实验分为PART A和PART B。PART A要求我们写一个cache模拟器，PART B要求我们利用cache来优化一个矩阵的转置以达到cache miss最少。

目前只完成了A部分，B部分等把CSAPP的其它实验全部做完了有空的话再回来做，剩下的几个lab也都很有意思。

这个simulator完全要自己写，没有给函数接口和数据结构，这些要自己设计。最终的binary接受4个参数：

1
2
3
4

-b  // b bits来表示block大小
-E  // 一个set里有E项，即E-way associativity
-s  // s bits来表示set大小
-t  / /测试文件

在测试文件里有4种类型的命令：

1
2
3
4

I 0400d7d4,8    // Instruction load
M 0421c7f0,4    // Modify, i.e, a data load followed by a data store
L 04f6b868,8    // a data load 
S 7ff0005c8,8   // a data store

然后根据命令行指定参数的cache来模拟运行这些指令，给出最终的hit数，miss数和eviction数。替换策略为LRU。

data structure

总的来说，无非就是一个2s行，E列的数组，数组的元素是一个struct，由is_valide，tag和access_time。下面是我定义的数据结构：

1
2
3
4
5
6
7
8
9

struct oneSet
{
    int *v;
    clock_t *last_access_time;
    long *tag;    
};

// the global pointer to the cache, setptr[n] stands for the nth set entry
struct oneSet *setptr;

其中oneSet这个struct中的指针都需要根据参数动态分配，所有数组的大小为E。

Load operation

如果当前指令是load，那么处理的伪代码伪：

1
2
3
4
5
6
7
8

if cache hit:
    hit++
else:   //cache miss:
    if cache is not full:
        miss++
    else:   // cache is full
        miss++
        evict++

Store operation

如果当前指令是store，那么处理的伪代码伪：

1
2
3
4

if cache hit:
    hit++
else:   //cache miss
    do a load operation

Modify operation

如果当前指令是Modify，那么处理的伪代码伪：

1
2

do a load operation
do a store operation

如果把上面的逻辑想通了，那么就可以编码了。

函数设计

以下是我所有函数的原型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// to get the opt from the command line
void get_opt();

// do init work, i.e, malloc space
void do_init();

// do deinit work, i.e, free space
void do_deinit();

// do a load operation
void do_L(void *addr, int size);

// do a modify operation
void do_M(void *addr, int size);

// do a store operation
void do_S(void *addr, int size);

// get set number according to the address of data
int  getset(void *addr);

// get tag number according to the address of data
long gettag(void *addr);

遇到的些问题

  1. 替换策略为LRU，所以要记录每个block的最后访问时间，我本来是调用clock()来获取当前cpu时间作为当前时间的，运行后程序出问题，调试发现这个值一直为0。后来查到了原因，是程序运行时间太短cpu时间太小导致精度不够…表示i7四代太强了。后来用一个long来表示时间解决这个问题。

  2. 虚拟机不能用mmap。本来一个更方便读测试文件的方法是用mmap把它映射到内存然后直接内存操作，但我的host是mac，在parallel desktop上跑ubuntu，导致了mmap不能正常使用，详细见这里

源码

代码放在了github上。