PART A
要求设计一个cache模拟器，输入s,E,b等参数和读入文件位置，按照文件提供的load/save/modify(load + save)操作来进行模拟，输出命中/不命中/排除的次数和具体情况。
cache存储类型定义如下：
struct myblock{
LL tg;
int v,pre;
};
typedef struct myblock cacheblock;
struct myset{
cacheblock* b;
};
typedef struct myset cacheset;
cacheset* cache;
读入参数后直接malloc.
note1:写操作和读操作一致，即在cache中寻找地址，找不到则将新地址加入cache.
note2:数据已经保证不会出现读取数据超过一个块的情况，故不用真正存2^b的数据，只用记一下tag和确定是否存在地址的value即可。
注意eviction操作遵循LRU规则（丢掉最早被调用过的地址），记个时间戳记录一下即可。
一个坑是当在cache中找到地址时还要更新一下时间戳。
代码见附录PART A.
PART B
你要优化一个给定N*M矩阵的转置，使得cache miss次数尽可能少，给定cache大小参数s=5,E=1,b=5.
三个子任务：
1.N=32，M=32 ，miss次数<300
2.N=64，M=64，miss次数<1300
3.N=61, M=67, miss次数<2000
所有subtask代码见附录。
SUBTASK 1
由b=5知一个块只能存8个int，一行32个int存4个块，8行存下一整个cache.
另外由于A和B的tag域不同，矩阵里位置相同的块访问A会取代B的缓存。
画出每个块对应存矩阵地址的位置如下，数字表示对应第几个集合的块，对于传统直接循环处理的方式，A数组按行遍历是连续的，而B数组由于是按列遍历，会造成多次不命中，如A循环第一行时，B的cache更新完1-8行后，新的行把原来cache存的地址抵掉，等到A循环第二行时，B又要在cache重新更新1-8行的地址。
容易想到对矩阵进行8*8分块处理，让B把前8行所有块做完。
这样的结果为：
Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:1710, misses:343, evictions:311
优化效果不够好，原因可能在于转置A和B所用缓存有一定重合，循环时会出现A->B->A存入cache的情况，降低了命中。
于是我们加入8个变量tmp0...tmp7，一次直接把A的7个元素全部取出，再依次赋值给B。
优化后结果达到了要求：
func 0 (Transpose submission): hits:1766, misses:287, evictions:255
SUBTASK 2
一行64个int存8个块，4行存完一个cache。
若采用8*8分块结果为：
func 0 (Transpose submission): hits:3586, misses:4611, evictions:4579
func 1 (Simple row-wise scan transpose): hits:3474, misses:4723, evictions:4691
与暴力遍历相比没有什么优化。
由subpoint 1我们采用4*4分块，让B的cache充分命中：
func 0 (Transpose submission): hits:6498, misses:1699, evictions:1667
由于一个块实际能存8个int，这样还是会有一些不命中，如下图：
右上块为A，左下为B，每个块4*4，A顺序做完b1,b2，再做b3时，cache重新填入b1T所在行的地址，做b4时，cache重新填入b2T所在行的地址，这样就造成了两轮不命中。
一种优化方法使得每个8*8块的转置只有一轮不命中：
(1)A按行访问b1,b2，将其转置拷贝到b1T,b3T的位置，此时cache存b1T的行地址。
(2)A按列访问b3，对每一列，先用临时变量记录b2T对应行4个元素，再用b3T取代b2T，此时cache存的还是b1T的行地址；最后用临时变量给b2T对应行赋值，此时cache更新为b2T的行地址，产生一次不命中。
（3)最后A按行访问b4，拷贝到b4T，在(2)结束后cache全部替换为b2T地址，故不会产生不命中。
注意对于(1)和(3)也要使用临时变量进行优化。
结果如下：
func 0 (Transpose submission): hits:9018, misses:1227, evictions:1195
SUBTASK 3
N=61，M=67很不规律，故这里尝试了4*4,8*8等分块方法，最后会遗留几个小块。
尝试8*8分块得到了<2000的结果：
func 0 (Transpose submission): hits:6182, misses:1997, evictions:1965
总结
PART A不是很难，只用模拟即可；
PART B想拿满分很难，subtask 2减少命中的方法非常巧妙。
一般的常数优化仅考虑了数组下标按行/按列连续访问的情况，但PART B指出当按列访问足够小到可以用cache存下每个地址时，按列访问也可以保持连续性而达到较高的速度，提供了常数优化的新途径。
参考&感谢
《深入理解计算机系统-cachelab》（博客），AC-NEWBIE，https://blog.csdn.net/xbb224007/article/details/81103995.
附录
PART A code:
/*student ID: 2017201975 name: YangYueQian*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cachelab.h"
#define SETS 1
#define SETE 2
#define SETB 4
#define SETT 8
#define MAXLENGTH 100
#define LL long long
struct myblock{
LL tg;
int v,pre;
};
typedef struct myblock cacheblock;
struct myset{
cacheblock* b;
};
typedef struct myset cacheset;
cacheset* cache;
int s,e,b,tg,len,view;
int totnum[3];
char ch[3][10]={"hit","miss","eviction"};
char addr[MAXLENGTH],str[MAXLENGTH];
void premalloc()
{
cacheblock* b0;
cache=malloc((1<<s)*sizeof(cacheset));
for(int i=0;i<(1<<s);++i)
{
cache[i].b=malloc(e*sizeof(cacheblock));
b0=cache[i].b;
for(int j=0;j<e;++j) b0[j].v=b0[j].pre=b0[j].tg=0;
}
}
void delmalloc()
{
for(int i=0;i<(1<<s);++i) free(cache[i].b);
free(cache);
}
void call(int o)
{
totnum[o]++;
if(view) printf("%s ",ch[o]);
}
void work()
{
premalloc();
FILE* f=fopen(addr,"r");
int l,opt,s1,anc,clo=0;
LL tg1,x,num;
cacheblock* blo;
while(f!=NULL&&fgets(str, MAXLENGTH, f)!=NULL)
{
if(str[0]!=' ') continue;
clo++;
if(view) printf("%s ",str+1);
l=strlen(str);
if(str[1]=='M') opt=1;else opt=0;
num=0;
for(int i=3;i<l;++i)
{
if(str[i]>='0'&&str[i]<='9') num=num*16+str[i]-'0';
else if(str[i]>='a'&&str[i]<='f') num=num*16+str[i]-'a'+10;
if(str[i]==',') {x=num; break; }
}
s1=(x>>b)&((1LL<<s)-1LL);
tg1=(x>>(b+s))&((1LL<<(64-(b+s)))-1LL);
blo=cache[s1].b;
anc=0;
for(int i=0;i<e;++i)
{
if(blo[i].v&&blo[i].tg==tg1) {blo[i].pre=clo; anc=1; break; }
}
if(anc) call(0);
else
{
call(1);
int tmp=clo,aim=0;
for(int i=0;i<e;++i)
{
if(!blo[i].v) {blo[i].v=1; blo[i].pre=clo; blo[i].tg=tg1; aim=-1; break; }
else if(tmp>blo[i].pre) tmp=blo[i].pre, aim=i;
}
if(aim>=0) call(2),blo[aim].pre=clo,blo[aim].tg=tg1;
}
if(opt) call(0);
if(view) printf("\n");
}
delmalloc();
fclose(f);
}
int main(int argc, char** argv)
{
char* p;
int opt=0,state=0;
char ch;
for(int i=1;i<argc;++i)
{
p=argv[i];
opt=0;
while((ch=(*(p++)))!='\0')
{
if(opt)
{
state=0;
if(ch=='v') view=1;
if(ch=='s') state|=SETS;
if(ch=='E') state|=SETE;
if(ch=='b') state|=SETB;
if(ch=='t') state|=SETT;
opt=0;
continue;
}
if(ch=='-') opt=1;
else if(state&SETT) addr[len++]=ch;
else if(ch>='0'&&ch<='9')
{
if(state&SETS) s=s*10+ch-'0';
if(state&SETE) e=e*10+ch-'0';
if(state&SETB) b=b*10+ch-'0';
}
}
}
addr[len]='\0';
work();
printSummary(totnum[0], totnum[1], totnum[2]);
return 0;
}
SUBTASK 1:
int tmp0,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7;
for(int i=0;i<4;++i)
for(int j=0;j<4;++j)
{
for(int ik=i*8;ik<(i+1)*8;++ik)
{
tmp0=A[ik][j*8];
tmp1=A[ik][j*8+1];
tmp2=A[ik][j*8+2];
tmp3=A[ik][j*8+3];
tmp4=A[ik][j*8+4];
tmp5=A[ik][j*8+5];
tmp6=A[ik][j*8+6];
tmp7=A[ik][j*8+7];
B[j*8][ik]=tmp0;
B[j*8+1][ik]=tmp1;
B[j*8+2][ik]=tmp2;
B[j*8+3][ik]=tmp3;
B[j*8+4][ik]=tmp4;
B[j*8+5][ik]=tmp5;
B[j*8+6][ik]=tmp6;
B[j*8+7][ik]=tmp7;
}
}
SUBTASK 2:
int tmp0,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7;
for(int i=0;i<64;i+=8)
for(int j=0;j<64;j+=8)
{
for(int ik=i;ik<i+4;++ik)
{
tmp0=A[ik][j];
tmp1=A[ik][j+1];
tmp2=A[ik][j+2];
tmp3=A[ik][j+3];
tmp4=A[ik][j+4];
tmp5=A[ik][j+5];
tmp6=A[ik][j+6];
tmp7=A[ik][j+7];
B[j][ik]=tmp0;
B[j+1][ik]=tmp1;
B[j+2][ik]=tmp2;
B[j+3][ik]=tmp3;
B[j][ik+4]=tmp4;
B[j+1][ik+4]=tmp5;
B[j+2][ik+4]=tmp6;
B[j+3][ik+4]=tmp7;
}
for(int jk=j;jk<j+4;++jk)
{
tmp0=B[jk][i+4];
tmp1=B[jk][i+5];
tmp2=B[jk][i+6];
tmp3=B[jk][i+7];
B[jk][i+4]=A[i+4][jk];
B[jk][i+5]=A[i+5][jk];
B[jk][i+6]=A[i+6][jk];
B[jk][i+7]=A[i+7][jk];
B[jk+4][i]=tmp0;
B[jk+4][i+1]=tmp1;
B[jk+4][i+2]=tmp2;
B[jk+4][i+3]=tmp3;
}
for(int ik=i+4;ik<i+8;++ik)
{
tmp0=A[ik][j+4];
tmp1=A[ik][j+5];
tmp2=A[ik][j+6];
tmp3=A[ik][j+7];
B[j+4][ik]=tmp0;
B[j+5][ik]=tmp1;
B[j+6][ik]=tmp2;
B[j+7][ik]=tmp3;
}
}
SUBTASK 3:
int tmp0,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7;
for(int i=0;i<N;i+=8)
for(int j=0;j<M;j+=8)
{
for(int ik=i;ik<i+8&&ik<N;++ik)
{
if(j<M) tmp0=A[ik][j];
if(j+1<M) tmp1=A[ik][j+1];
if(j+2<M) tmp2=A[ik][j+2];
if(j+3<M) tmp3=A[ik][j+3];
if(j+4<M) tmp4=A[ik][j+4];
if(j+5<M) tmp5=A[ik][j+5];
if(j+6<M) tmp6=A[ik][j+6];
if(j+7<M) tmp7=A[ik][j+7];
if(j<M) B[j][ik]=tmp0;
if(j+1<M) B[j+1][ik]=tmp1;
if(j+2<M) B[j+2][ik]=tmp2;
if(j+3<M) B[j+3][ik]=tmp3;
if(j+4<M) B[j+4][ik]=tmp4;
if(j+5<M) B[j+5][ik]=tmp5;
if(j+6<M) B[j+6][ik]=tmp6;
if(j+7<M) B[j+7][ik]=tmp7;
}
}
Comments | NOTHING