CSAPP:cachelab

来一波期末季（因为考试似乎没认真做）的最后一个lab!!（嘘
Cache这一章还算比较简单的
（没错今天复习的处理器才叫南…?
还有最后两门专业课考试和pj，奥利给!!

PART A

这是两周前写的了…晕
这里就是要自己写一个cache出来，要具备鉴别hit、miss、eviction和操作的能力，cache需要对任意的S/E/B都有效

#include "cachelab.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>static int miss=0,hit=0,eviction=0;
struct Block
{
    	int valid;int tag;int LRU;
};
struct Cache
{
    int linenum;int setnum;int blockbyte;struct Block **cache;
};int str2int(char *str)
{
    	int len=strlen(str);int res=0;for(int i=0;i<len;i++)res=res*10+str[i]-'0';return res;
}
long hex2dec(char *str)
{
    	int len=strlen(str);long res=0;for(int i=0;i<len;i++){
    	if(str[i]>='0'&&str[i]<='9') res=res*16+str[i]-'0';if(str[i]>='a'&&str[i]<='f') res=res*16+str[i]-'a'+10;if(str[i]>='A'&&str[i]<='F') res=res*16+str[i]-'A'+10;}
return res;
}void initiate_cache(int S,int E,int B,struct Cache *c)
{
    	c->linenum=E;c->setnum=S;c->blockbyte=B;c->cache=(struct Block**)malloc(sizeof(struct Block*)*S);for(int i=0;i<S;i++){
    	c->cache[i]=(struct Block*)malloc(sizeof(struct Block)*E);for(int j=0;j<E;j++)
{
    struct Block *p=(struct Block *)malloc(sizeof(struct Block));		   	c->cache[i][j]=*p;c->cache[i][j].valid=0;c->cache[i][j].tag=0;c->cache[i][j].LRU=0;}}
}void analysis(char* record,char* op,char *add,char *size)
{
    int i=0,j=0;while(record[i]==' ') i++;*op=record[i];i++;//optionfor(;record[i]!=',';i++,j++)add[j]=record[i];add[j]='\0';j=0;i++;for(;record[i]!='\n';i++,j++)size[j]=record[i];size[j]='\0';
}void operation(struct Cache* c,char *add,char *size,int rec)
{
    	long address=hex2dec(add);int sign=(address/c->blockbyte)%(c->setnum);long curtag=(address/c->blockbyte)/(c->setnum);int empty=-1;for(int i=0;i<c->linenum;i++){
    	if(c->cache[sign][i].valid==0)empty=i;if(c->cache[sign][i].valid==1&&c->cache[sign][i].tag==curtag){
    hit++;c->cache[sign][i].LRU=rec;return;}}miss++;if(empty>=0&&empty<c->linenum){
    c->cache[sign][empty].tag=curtag;c->cache[sign][empty].valid=1;c->cache[sign][empty].LRU=rec;return;}else{
    eviction++;int minrec=c->cache[sign][0].LRU;int del=0;for(int i=1;i<c->linenum;i++)if(c->cache[sign][i].LRU<minrec){
    minrec=c->cache[sign][i].LRU;del=i;}c->cache[sign][del].tag=curtag;c->cache[sign][del].LRU=rec;}return;
}int main(int argc,char *argv[])
{
    	struct Cache cache;int S,E,B;int s,b,count=0;char buf[50];FILE* fp=NULL;for(int i=0;i<argc;i++){
    	if(argv[i][0]=='-'){
    if(argv[i][1]=='s'){
    i++;s=str2int(argv[i]);S=1<<s;i++;}if(argv[i][1]=='E'){
    i++;E=str2int(argv[i]);i++;}if(argv[i][1]=='b'){
    i++;b=str2int(argv[i]);B=1<<b;i++;}if(argv[i][1]=='t'){
    i++;if((fp=fopen(argv[i],"r"))==NULL){
    printf("openfile %s error",argv[i]);exit(1);}}}}if(s<=0||E<=0||b<=0) return-1;initiate_cache(S,E,B,&cache);while(fgets(buf,sizeof(buf),fp)){
    count++;char op;char add[50];char size[50];analysis(buf,&op,add,size);if(op=='I') continue;operation(&cache,add,size,count);if(op=='M') operation(&cache,add,size,count);}printSummary(hit, miss, eviction);return 0;
}

思路：定义一个Block作为块单元，在Cache里搞一个Block二维数组模仿cache的结构，并且储存其他信息
str2int和 hex2dec都是用于转换，因为发现文件里读入的操作符为字符类型，我们需要的是它之后跟的数字，所以需要用函数判别并获得S/E/B参数
initiate_cache做cache的初始化，啊这里malloc搞了好久，动态数组真的挺麻烦的，此处先开出行，再每个初始化
参考：
https://blog.csdn.net/weixin_43480094/article/details/83932634
analysis是分析文件中读入的指令的，operation就是我们熟悉的cache操作了，判断是否hit和miss，如果miss同时记录该组里是否有空位，有空位就加入，没空位还要进行eviction（使用每个块里的LRU作为判别的时间标识
其实main函数有很多我也不知道在干什么…
主要参考：
https://blog.csdn.net/qq_35102066/article/details/89684271

验证正确性：

PART B

今天新鲜出炉的Part B （不是
在CSAPP的课件最后有提到一点点分块的技术，但是涉及不多
这里就是让你针对不同大小的二维数组做转置
对每种矩阵都要小于一定的miss数才能拿到满分

32*32

if(M==32&&N==32){
    int i,j,m,s1,s2,s3,s4,s5,s6,s7,s8;for(i=0;i<N;i+=8)for(j=0;j<M;j+=8)for(m=i;m<i+8;m++){
    s1=A[m][j];s2=A[m][j+1];s3=A[m][j+2];s4=A[m][j+3];s5=A[m][j+4];s6=A[m][j+5];s7=A[m][j+6];s8=A[m][j+7];B[j][m]=s1;B[j+1][m]=s2;B[j+2][m]=s3;B[j+3][m]=s4;B[j+4][m]=s5;B[j+5][m]=s6;B[j+6][m]=s7;B[j+7][m]=s8;}}

这里就是分了8* 8块啦
其实要注意AB两个数组对应的位置是映射冲突的，所以不可避免的要有一些miss
8*8的好处在于你可以在A矩阵一行读8个，它的Miss rate就下降到1/8

64*64

if(M==64&&N==64){
    int m,j,i,s1,s2,s3,s4,s5,s6,s7,s8;for(m=0;m<N;m+=8)for(j=0;j<M;j+=8){
    for(i=m;i<m+4;i++){
    s1=A[i][j];s2=A[i][j+1];s3=A[i][j+2];s4=A[i][j+3];s5=A[i][j+4];s6=A[i][j+5];s7=A[i][j+6];s8=A[i][j+7];B[j][i]=s1;B[j+1][i]=s2;B[j+2][i]=s3;B[j+3][i]=s4;B[j][i+4]=s8;B[j+1][i+4]=s7;B[j+2][i+4]=s6;B[j+3][i+4]=s5;}for(i=0;i<4;i++){
    s1=A[m+4][j+3-i];s2=A[m+5][j+3-i];s3=A[m+6][j+3-i];s4=A[m+7][j+3-i];s5=A[m+4][j+4+i];s6=A[m+5][j+4+i];s7=A[m+6][j+4+i];s8=A[m+7][j+4+i];B[j+4+i][m]=B[j+3-i][m+4];B[j+4+i][m+1]=B[j+3-i][m+5];B[j+4+i][m+2]=B[j+3-i][m+6];B[j+4+i][m+3]=B[j+3-i][m+7];B[j+3-i][m+4]=s1;B[j+3-i][m+5]=s2;B[j+3-i][m+6]=s3;B[j+3-i][m+7]=s4;B[j+4+i][m+4]=s5;B[j+4+i][m+5]=s6;B[j+4+i][m+6]=s7;B[j+4+i][m+7]=s8;}}}

越发有趣了
就还是8* 8块，但是由于这里是64* 64了，只能放入四行A矩阵的元素，第一行和第五行就已经映射冲突了
主要想法就是在第一次拿A数组的前四行时候，把5-8列的元素一起拿过来，先放在B数组的右上角，等之后再把它换下去，这样可以省去重复去A数组中拿的过程
下四行同理，需要有复制右上角的过程，下标的计算要注意
自己写只能写到这个程度：

参考：
https://zhuanlan.zhihu.com/p/79058089
十分感谢大佬555

61*67

if(M==61&&N==67){
    int m=M/8*8,n=N/8*8,j,i,s1,s2,s3,s4,s5,s6,s7,s8;for(j=0;j<m;j+=8)for(i=0;i<n;i++){
    s1=A[i][j];s2=A[i][j+1];s3=A[i][j+2];s4=A[i][j+3];s5=A[i][j+4];s6=A[i][j+5];s7=A[i][j+6];s8=A[i][j+7];B[j][i]=s1;B[j+1][i]=s2;B[j+2][i]=s3;B[j+3][i]=s4;B[j+4][i]=s5;B[j+5][i]=s6;B[j+6][i]=s7;B[j+7][i]=s8;}for(i=n;i<N;i++)for(j=m;j<M;j++){
    s1=A[i][j];B[j][i]=s1;}for(i=0;i<N;i++)for(j=m;j<M;j++){
    s1=A[i][j];B[j][i]=s1;}for(i=n;i<N;i++)for(j=0;j<M;j++){
    s1=A[i][j];B[j][i]=s1;}}
}/* * You can define additional transpose functions below. We've defined* a simple one below to help you get started. */ /* * trans - A simple baseline transpose function, not optimized for the cache.*/
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;for (i = 0; i < N; i++) {
    for (j = 0; j < M; j++) {
    tmp = A[i][j];B[j][i] = tmp;}}    

讲真这个比第二个简单点
就是不规则而已嘛，就先把一个56* 64的矩阵搞定，再把边边角角转置就OK～（说起来简单而已hh
这里的算法是在A数组中复制一长列的，我的算法是在A数组中复制一长行，然而永远在报错…

最后的grade：

这个lab就这样迷迷糊糊的做完了，其实CMU的同学都表示这个lab开始难了（开始hhh），确实是的，cachelab明显感觉需要更多自己构思和设计的能力，不再是按照框架解题得到正确答案，而是在考验学生对系统的理解并且自己搭建系统的能力
本学期的5个lab也就这样结束了，最后一节课老师说ICS最大的收获其实根本不在书本和PPT，而是在于做lab
还记得第一节课自己什么也不会，装个虚拟机也装了半天，一学期下来5个lab都算顺利完成，也挺开心的～
下学期依旧要和ICS相伴，寒假里打算再啃啃大厚书，现在的当务之急是好好复习备考，希望自己能得到想要的成绩叭～
期末季加油呀??

附一份在攻略里找到的CMU对分块技术的介绍：
http://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf