缓存实验由两部分组成:模拟缓存程序的实现和局部性优化。

第一部分:缓存模拟程序

第一部分的任务就是写一个cache模拟器,程序读取一个读写指令,判断出这一条指令时hit还是miss,如果是miss并且原来的cache已经满了,就需要eviction。

模拟cache的结构:首先看看cache当中的一行需要什么东西:tag标记、valid标记是必须的,Block是用来存储数据的,但是我们的程序不用判断miss、hit、eviction,真实的数据读写是不需要的,因此数据块就不需要了。除了上面提到的东西,我们还需要一个链表项来实现LRU策略。所以,我定义了这么一个结构体:

struct line {
	bool valid;
	uint64_t tag;
	struct list_entry list;
};

LRU策略的实现:LRU就是牺牲掉least recently used的块,可以使用链表来模拟,按照行的最后访问时间维护一个有序链表,链表头部是最久没有访问的,链表尾部是最近访问的:

  • 在cache初始化的时候,将所有的行按照顺序排列成一个双向链表;
  • 当某行被访问后,将这一行从链表中删除,重新插入链表尾部;
  • 当需要选择一行换出cache的时候,选择链表头部的行换出即可。

代码实现可见csim.c

第二部分:局部性优化

B部分要求对矩阵转置函数进行内存读写的优化,按照CS:APP2e Web Aside MEM:BLOCKING:的提示,优化的基本思想就是先把一个大的矩阵分成若干个小的矩阵,然后对小矩阵进行转置,对于不同大小的矩阵,矩阵分割的小矩阵的大小对其表现有着巨大的影响,所以要把三种矩阵的处理方法分开来,我写了以下的操作:

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int i, ii, j, jj, blocksize;
    if (M == 32 && N == 32) {
        blocksize = 8;
    } else if (M == 64 && N == 64) {
        blocksize = 4; 
    } else {
        blocksize = 16;
    }
    for (ii = 0; ii < N; ii += blocksize)
        for (jj = 0; jj < M; jj += blocksize)
            for (i = ii; i < ii+blocksize && i < N; i++)
                for (j = jj; j < jj+blocksize && j < M; j++) 
                    B[j][i] = A[i][j];
}