缓存是现代计算机的重要部件，了解缓存的工作机制可以编写出缓存友好的程序，提高程序的速度。
partA
实现一个缓存模拟器，需要了解缓存的工作细节，完成后可以对缓存有更深入的理解。这个实现没有唯一的答案，不同的人实现方式都有差别。相对难点是实现LRU替换，如果换错了行会导致后边缓存行为的一系列错误。具体原理书里已经讲的非常详细了，相信只要理解了实现起来比较容易。我的代码见附1，需要的可以参考。
对于我代码的几点说明：
1、 我把行中的有效位和标记位放到了一个64位的变量中，有效位在最低位，标记位是高63位；
2、 组中的每一行用一个数字表示其访问情况，数字最大（E-1）的表示刚刚访问过，数字最小（0）表示距上次访问最久远，每次命中、miss、替换都要调整。
3、 模拟实际不需要为block分配空间，只需要有效位和标记即可，我刚开始不知道就分配了，后续懒得改了。
partB
这个稍微有点难度，同样考察对缓存的理解，不过是从应用的角度。即便在partA中实现了缓存模拟器，到应用阶段还是会遇到很多问题，可见一个概念想要真正熟悉需要从不同的角度不断练习。
这部分的核心思想是数据加载到行中，应用尽用，尽可能让这行数据只加载这一次，以后就不需要再换回来。
缓存大小是1k，块大小是32字节，矩阵元素是int型，4字节，所以一个块可以放8个数，根据前面的原则，在处理时要尽可能一次处理8个数。另外还有个技术是blocking（分块），利用分块可以减少miss数，具体原理可以看这篇官方手册推荐的文章http://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf。
缓存只有1k，所以对于32x32的矩阵可以缓存8行而没有冲突，64x64的矩阵可以缓存4行而没有冲突。由于有这个区别，很多人的处理方法是分开处理，32x32专门写一个程序，64x64专门写一个，61x67专门写一个。当然这样可以拿满分，不过我觉得不够优雅，所以我想用一个程序实现对三种矩阵的处理，最后虽然没有拿到满分（差0.1），但是却收获满满。
具体的方法真的不太容易想到，我也是网上看到再优化的，下面具体来说说。
我们的目的是从矩阵A变到矩阵B，先来分析哪些情况可能会出现问题。
如果一次一行处理8个数，32x32没什么问题，但是64x64不行，存前4个数B加载前4行，但是存后4个数的时候，由于64x64一次只能缓存4行，所以矩阵B的后四行会与前4行发生替换，下一次还会重复这个过程，这样一直换入换出很明显命中率不高。
如果一次处理4个数，而缓存一行可以加载8个数，很明显缓存利用率只有1/2，剩下的4个数在处理前很可能会被换出去，下次处理再加载回来，命中率还是不高。
还有一种情况是A和B的某些地址位于相同的行，这样存B的时候会把A换出去，下次读A的数据又要加载进来，这样的命中率也会下降。
针对以上问题，我们提出以下方案，
1、 首先分块是8x8，一次大循环处理8行8列，8x8的块进一步分成4x4的块；
2、 用8个中间变量存需要处理的数据，这样即便有冲突被换出去也没关系；
3、 用B的空间暂存A后四个数据，这样A即便被换出去也没关系；
具体过程如下：
1、 先处理前4行8个数，前4列正常处理，A的后4列转置后暂存在B的后4列中。
这里我们可以发现，B右上角黄色块的数据就是最终B紫色块的数据，接下来我们想办法复制过去就行。
2、 下面的一系列处理很巧妙，充分利用了缓存的特点。
先把B的第一行后4列暂存到临时变量中，把A的后4行的第一列存到临时变量中，如果是64x64，此时A的前4行被换了出去，缓存中是A的后4行；
将暂存的A数据存到B的第一行后4列，此时B的第一行已经是最终的数据；
取出A的后四行的第5列存入临时变量中，此时A的后四行位于缓存中，可以命中。
将临时变量的值存到B的第5行。如果是64x64，此时B的第5行会把第一行从缓存中换掉，而第一行已经是最终的数据，换出去也没关系。
以此类推，将上述过程再重复三次，处理剩下的数据。此过程充分利用了缓存中的数据，换出去的行以后不会再访问，大大提高了缓存命中率。
对于61x67，由于行列不是8的整数倍，所以经过上面的处理后会有遗漏，需要单独处理。对于列，一次取出一列8个数据，实测这样的命中率对于没对齐的矩阵命中率很高，对于剩余的行，同样按列读取，按行存命中率要高。
使用上面的方法，测试结果如下：
32x32和64x64的表现都很好，61x67多了10个miss，这10个miss实在不知道怎么优化了。
具体实现的代码如下
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
int i,j, k,l,t0,t1,t2,t3,t4,t5,t6,t7;
for(l=0;l<N/8;l++){
for(k=0;k<M/8;k++)
{
for (i = 0; i < 4; i++) {
t0= A[l*8+i][k*8];
t1= A[l*8+i][k*8+1];
t2= A[l*8+i][k*8+2];
t3= A[l*8+i][k*8+3];
t4= A[l*8+i][k*8+4];
t5= A[l*8+i][k*8+5];
t6= A[l*8+i][k*8+6];
t7= A[l*8+i][k*8+7];
B[k*8][l*8+i] = t0;
B[k*8+1][l*8+i]=t1;
B[k*8+2][l*8+i]=t2;
B[k*8+3][l*8+i]=t3;
B[k*8][l*8+i+4] = t4;
B[k*8+1][l*8+i+4]=t5;
B[k*8+2][l*8+i+4]=t6;
B[k*8+3][l*8+i+4]=t7;
}
for (i = 0; i < 4; i++) {
t0= B[k*8+i][l*8+4];
t1= B[k*8+i][l*8+5];
t2= B[k*8+i][l*8+6];
t3= B[k*8+i][l*8+7];
t4= A[l*8+4][k*8+i];
t5= A[l*8+5][k*8+i];
t6= A[l*8+6][k*8+i];
t7= A[l*8+7][k*8+i];
B[k*8+i][l*8+4] = t4;
B[k*8+i][l*8+5]=t5;
B[k*8+i][l*8+6]=t6;
B[k*8+i][l*8+7]=t7;
t4= A[l*8+4][k*8+i+4];
t5= A[l*8+5][k*8+i+4];
t6= A[l*8+6][k*8+i+4];
t7= A[l*8+7][k*8+i+4];
B[k*8+i+4][l*8] =t0;
B[k*8+i+4][l*8+1]=t1;
B[k*8+i+4][l*8+2]=t2;
B[k*8+i+4][l*8+3]=t3;
B[k*8+i+4][l*8+4]=t4;
B[k*8+i+4][l*8+5]=t5;
B[k*8+i+4][l*8+6]=t6;
B[k*8+i+4][l*8+7]=t7;
}
}
for(j=k*8;j<M;j++)
{
t0 = A[l*8][j];
t1 = A[l*8+1][j];
t2 = A[l*8+2][j];
t3 = A[l*8+3][j];
t4 = A[l*8+4][j];
t5 = A[l*8+5][j];
t6 = A[l*8+6][j];
t7 = A[l*8+7][j];
B[j][l*8] = t0;
B[j][l*8+1] = t1;
B[j][l*8+2] = t2;
B[j][l*8+3] = t3;
B[j][l*8+4] = t4;
B[j][l*8+5] = t5;
B[j][l*8+6] = t6;
B[j][l*8+7] = t7;
}
}
if(l*8<N)
{
for(j=0;j<M;j++)
{
for(i=l*8;i<N;i++)
{
t0 = A[i][j];
B[j][i] = t0;
}
}
}
}这个lab个人觉得还是有点难度的，尤其是之前完全不了解缓存机制的情况下，更是让人迷惑。不过，正是有这些疑惑，才逼自己一行行的分析trace，看看程序的实际行为如何，进而发现问题，找到解决的办法，这个过程中也不断的加深了对缓存的理解和认识。
附1：
/*
缓存行结构
|--63位标记--|-1位有效位|--n字节块--|
*/
#include "cachelab.h"
#include<unistd.h>
#include<stdio.h>
#include<stdlib.h>
#include<getopt.h>
#include<stdint.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<string.h>
extern char *optarg;
/*
命令行参数
*/
int verbose_flag=0,sets = 0,lines = 1,block_offset_bits = 0;
char * input_filep=NULL;
//缓存性能统计
int hits=0,misses=0,evictions=0;
void show_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");
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");
}
void parse_arg(int argc ,char *argv[])
{
int opt;
if(argc<2)
{
printf("./csim: Missing required command line argument\n");
show_usage();
exit(0);
}
while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
switch(opt){
case 'h':
show_usage();
exit(0);
case 'v':
verbose_flag=1;
break;
case 's':
sets = atoi(optarg);
break;
case 'E':
lines = atoi(optarg);
break;
case 'b':
block_offset_bits = atoi(optarg);
break;
case 't':
input_filep = optarg;
break;
default:
show_usage();
exit(0);
}
}
if(!input_filep)
{
printf("./csim: Missing required command line argument\n");
show_usage();
exit(0);
}
}
char * init_cache(int size)
{
return (char *)malloc(size);
}
void free_cache(void * cachep)
{
free(cachep);
}
void replay_trace(char * cache)
{
char buf[20]; //存储指令字符串
int blk_size = 1<<block_offset_bits; //块大小
int set_size = ((1<<block_offset_bits)+8)*lines; //组大小
int set_index = 0; //组索引
int64_t tag = 0; //标记
int64_t addr = 0; //地址
int bytes = 0;
char * setp;//*str; //组指针
int i=0,invalid_cnt=0,lru_index;
int hit_flag=0,miss_flag=0,evict_flag=0;
FILE *fp = fopen(input_filep,"r");
char *lru_cnt = (char *)calloc(lines*(1<<sets),1); //lru变量，替换最小值
while(fgets(buf,20,fp)!=NULL) //读取指令
{
hit_flag=0;
miss_flag=0;
evict_flag=0;
invalid_cnt = 0;
buf[strlen(buf)-1]=0;
if(buf[0]=='I')
continue;
sscanf(buf+3,"%lx,%d",&addr,&bytes); //获取地址和字节
set_index = (addr>>block_offset_bits)&((1<<sets)-1); //获得组索引
tag = addr>>(block_offset_bits+sets); //获得标记
setp = &cache[set_index*set_size]; //根据组索引得到组的缓存地址
for(i=0;i<lines;i++)
{
char cvalid = setp[i*(blk_size+8)]&0x1;
int64_t ctag =*(int64_t * )(setp+i*(blk_size+8))>>1;
if(cvalid)
{ if(ctag==tag)
{
if(bytes<=blk_size)
{
hits++;
hit_flag=1;
for(int j=0;j<lines;j++)
{
if(lru_cnt[i+lines*set_index]<lru_cnt[j+lines*set_index])
lru_cnt[j+lines*set_index]--;
}
lru_cnt[i+lines*set_index]=lines-1;
break;
}
}
}
else
{
invalid_cnt++;
}
}
if(i==lines)
{
misses++;
miss_flag=1;
if(!invalid_cnt)
{
evictions++;
evict_flag=1;
{
lru_index=0;
for(i=1;i<lines;i++)
{
if(lru_cnt[lru_index+lines*set_index]>=lru_cnt[i+lines*set_index])
{
lru_cnt[lru_index+lines*set_index]--;
lru_index = i;
}
else
{
lru_cnt[i+lines*set_index]--;
}
}
lru_cnt[lru_index+lines*set_index]=lines-1;
*(int64_t *)(setp+lru_index*(blk_size+8))=(tag<<1)|1;
}
}
else
{
for(i=0;i<lines;i++)
{
char cvalid = setp[i*(blk_size+8)]&0x1;
if(!cvalid)
{
*(int64_t *)(setp+i*(blk_size+8))=(tag<<1)|1;
for(int j=0;j<lines;j++)
{
if(lru_cnt[i+lines*set_index]<lru_cnt[j+lines*set_index])
lru_cnt[j+lines*set_index]--;
}
lru_cnt[i+lines*set_index]=lines-1;
break;
}
}
}
}
if(buf[1]=='M')
{
hits++;
}
if(verbose_flag)
{
printf("%c %lx,%d ",buf[1],addr,bytes);
if(miss_flag)
printf("miss ");
if(evict_flag)
printf("eviction ");
if(hit_flag)
printf("hit ");
if(buf[1]=='M')
printf("hit ");
printf("\n");
}
}
free(lru_cnt);
fclose(fp);
}
int main(int argc ,char *argv[])
{
parse_arg(argc ,argv);
int size =((1<<block_offset_bits)+8)*lines*(1<<sets);
char * cp = init_cache(size);
replay_trace(cp);
free_cache(cp);
printSummary(hits, misses, evictions);
return 0;
}
