CSAPP Cache Lab解题报告

任务A

实现代码：

#include <stdio.h>
#include <stdbool.h>
#include "cachelab.h"
#include <stdlib.h>
#include <getopt.h>

#define ADDR_SIZE 64;
typedef struct{
    char* filePath;
    int setNum;
    int lineNum;
    int blockNum;
    bool verbose;
}GlobalArgs;
GlobalArgs globalArgs;
typedef struct
{
    unsigned long long tag;
    int timestamp;
}CacheLine;

static const char* optString="hvs:E:b:t:";

void PrintHelp()
{
    printf("%s\n","Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>");
    printf("%s\n","Options:");
    printf("%s\n","  -h         Print this help message");
    printf("%s\n","  -v         Optional verbose flag");
    printf("%s\n","  -s <num>   Number of set index bits.");
    printf("%s\n","  -E <num>   Number of lines per set.");
    printf("%s\n","  -b <num>   Number of block offset bits");
    printf("%s\n","  -t <file>  Trace file.");
    printf("\n\n");
    printf("%s\n","Examples:");
    printf("%s\n","  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace");
    printf("%s\n","  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace");
}
void SetArgus(int argc, char* argv[])
{
    int opt=getopt(argc,argv,optString);
    while (opt!=-1)
    {
        switch (opt){
            case 'h':
                PrintHelp();
                break;
            case 'v':
                globalArgs.verbose=true;
                break;
            case 's':
                globalArgs.setNum=atoi(optarg);
                break;
            case 'E':
                globalArgs.lineNum=atoi(optarg);
                break;
            case 'b':
                globalArgs.blockNum=atoi(optarg);
                break;
            case 't':
                globalArgs.filePath=optarg;
                break;
            default:
                printf("wrong argument\n");
                break;
        }
        opt=getopt(argc,argv,optString);
    }
}

void TryToHitCache(unsigned long address,int* hit,int* miss,int* eviction,CacheLine* cache)
{
    static int timestamp=0;
    int tagLen=64-(globalArgs.setNum+globalArgs.blockNum);
    unsigned long set=(unsigned long)((address<<tagLen)>>(tagLen+globalArgs.blockNum));
    unsigned long tag=(unsigned long)(address>>(64-tagLen));
    int min=globalArgs.lineNum*set;
    for(int i=0;i<globalArgs.lineNum;i++)
    {

        int idx=set*globalArgs.lineNum+i;
        if(cache[idx].tag==tag&&cache[idx].timestamp!=0)
        {
            cache[idx].timestamp=++timestamp;
            (*hit)++;
            if(globalArgs.verbose)
                printf("hit ");
            return;
        }
        else if(cache[idx].timestamp==0)
        {
            cache[idx].timestamp=++timestamp;
            (*miss)++;
            cache[idx].tag=tag;
            if(globalArgs.verbose)
                printf("miss ");
            return;
        }
        if(cache[idx].timestamp<cache[min].timestamp)
            min=idx;
    }
    cache[min].timestamp=++timestamp;
    cache[min].tag=tag;
    (*miss)++;
    (*eviction)++;
    if(globalArgs.verbose)
        printf("miss eviction ");
    return;
}


int main(int argc,char* argv[])
{

    SetArgus(argc,argv);
    if(globalArgs.filePath==NULL)
    {
        exit(0);
    }
    FILE* fp=fopen(globalArgs.filePath,"r");
    if(fp==NULL)
    {
        printf("File not found %s\n",globalArgs.filePath);
        exit(0);
    }
    int hit=0,miss=0,eviction=0;
    int S=(1<<globalArgs.setNum);
    int E=globalArgs.lineNum;

     CacheLine* cache=calloc(S*E, sizeof(CacheLine));

     char opt;
     unsigned long address;
     int block;


     while(fscanf(fp," %c %lx,%d", &opt,&address,&block)>0)
     {
        if(opt=='I')
            continue;
        if(globalArgs.verbose)
        {
            printf("%c %lx,%d ",opt,address,block);
        }
        TryToHitCache(address,&hit,&miss,&eviction,cache);
        if(opt=='M')
            TryToHitCache(address,&hit,&miss,&eviction,cache);
        if(globalArgs.verbose)
            printf("\n");
     }

     fclose(fp);
     free(cache);

     printSummary(hit,miss,eviction);

    return 0;

}

实现思路：

任务A就是打开文件读入数据、处理数据、输出数据的过程，核心逻辑就是在于怎么模拟一个高速缓存来处理数据。我们将这部分逻辑封装在了void TryToHitCache(unsigned long address,int* hit,int* miss,int* eviction,CacheLine* cache)这个函数中。

首先我们定义一个静态变量static int timestamp，这个变量用来记录CPU向高速缓存器访问的时间戳（用来记录访问次数）。在该函数里我们需要接受几个参数，分别为请求的地址，hit次数，miss次数，eviction次数以及模拟的高速缓存器。然后我们将address的各部分结构进行解析，分别得到了set、tag等参数。

然后我们遍历模拟高速缓存器的组，比较address解析的set数是否与模拟缓存器的set数相同和是否可能为冷未命中的情况下。

如果能找到相同的tag且不是冷未命中的话，就将hit++，且更改timestamp的值。如果是冷未命中的话，就将miss++，并且更新timestamp的值并且设置该块的值。

如果则两种情况都不是的话，则需要更换块的内容。那么我们需要更新哪个块呢？根据局部性原则，我们应当更新距离我们这次访问时间戳距离最远的块，因此我们遍历一遍该组并找出该块并进行更换。然后进行更新数据。

任务B:

实现代码：

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int a1,a2,a3,a4,a5,a6,a7,a8;
    int i,j,k,h;
    if(N==32){
        for(i=0;i<4;i++){
            for(j=0;j<4;j++){
                for(k=i*8;k<(i+1)*8;k++){
                    h=j*8;
                    a1=A[k][h];a2=A[k][h+1];a3=A[k][h+2];a4=A[k][h+3];
                    a5=A[k][h+4];a6=A[k][h+5];a7=A[k][h+6];a8=A[k][h+7];

                    B[h][k]=a1;B[h+1][k]=a2;B[h+2][k]=a3;B[h+3][k]=a4;
                    B[h+4][k]=a5;B[h+5][k]=a6;B[h+6][k]=a7;B[h+7][k]=a8;
                }
            }
        }
    }
    else if(N==64){
        for(i=0;i<64;i+=8){
            for(j=0;j<64;j+=8){
                for(k=j;k<j+4;++k){
                    a1=A[k][i];a2=A[k][i+1];a3=A[k][i+2];a4=A[k][i+3];
                    a5=A[k][i+4];a6=A[k][i+5];a7=A[k][i+6];a8=A[k][i+7];

                    B[i][k]=a1;B[i][k+4]=a5;B[i+1][k]=a2;B[i+1][k+4]=a6;
                    B[i+2][k]=a3;B[i+2][k+4]=a7;B[i+3][k]=a4;B[i+3][k+4]=a8;
                }
                for(k=i;k<i+4;++k){
                    a1=B[k][j+4];a2=B[k][j+5];a3=B[k][j+6];a4=B[k][j+7];
                    a5=A[j+4][k];a6=A[j+5][k];a7=A[j+6][k];a8=A[j+7][k];

                    B[k][j+4]=a5;B[k][j+5]=a6;B[k][j+6]=a7;B[k][j+7]=a8;
                    B[k+4][j]=a1;B[k+4][j+1]=a2;B[k+4][j+2]=a3;B[k+4][j+3]=a4;
                }
                for(k=i+4;k<i+8;++k){
                    a1=A[j+4][k];a2=A[j+5][k];a3=A[j+6][k];a4=A[j+7][k];

                    B[k][j+4]=a1;B[k][j+5]=a2;B[k][j+6]=a3;B[k][j+7]=a4;
                }
            }
        }
    }
    else{
        for(i=0;i<N;i+=16){
            for(j=0;j<M;j+=16){
                for(k=i;k<i+16&&k<N;k++){
                    for(h=j;h<j+16&&h<M;h++){
                        B[h][k]=A[k][h];
                    }
                }
            }
        }
    }
}

实现思路：

本题很明显要使用分块进行优化，但分块后如下后距离答案要求的数量还有不少距离。

我这里参考了网上大神们的做法。

32×32：

第一题要求miss次数在300以下，首先观察，Cache的一个块只有32B，也就是只能容纳8个int。这个Cache可以容纳这个matrix的前8行。分块的话，肯定是取8×8的比较合适。先读取A的一行，然后放入B的一列。12个int变量，4个用来循环，其余8个用来存A中块的一行。

对于在对角线上的块，A中每读一行，会有一次miss，也就是miss次数是读取操作的1/8，对于B数组的话，第一次读取这行会产生一次miss，之后对于第i行，只有A中读到第i行的时候，会被移除出Cache，然后存的时候会产生一次miss。可以粗略计算为miss次数是读取次数的1/4。

对于不在对角线上的块，做转置的时候，A还是1/8的miss率，B的每行在Cache中和A的行不冲突，所以也是1/8的miss率，我们计算下最后大概多少次miss呢？

大概是 $4\times 64\times(\frac{1}{8}+\frac{1}{4})+12\times 64\times2\times\frac{1}{8}=288$

最后跑出来的答案是287，非常接近。

64×64：

首先考虑Cache中只能放4行A中的行，如果再用8×8的块，前面4行可以填入，后面4行会在Cache中发生冲突，导致miss次数增加。

如果只用4×4的块呢？那么每次Cache中放入8个int，我们却只用4个，浪费严重，我用这个方法最少也只能做到1677次miss。

有一种很巧妙的方法，就是还用8×8的块来做，题目说A数组不能变换，但是说B数组可以任意操作啊。我们必须要一步到位嘛？可否考虑先把数字移动到B中，然后在B中自己做变化。

考虑用同样的miss次数，把更多的数据移动到B中，但是不一定是正确的位置，然后再用同样的miss次数，把A中部分数据移动到B中时，完成把B中前面位置错误数据的纠正。

1.先考虑把A的上半部分存入到B，但是为了考虑Cache不冲突，所以把右上角的4×4的区域也存在B的右上角。对于在对角线上的块，A的miss率是1/8，B的左上角部分miss率是1/2。对于不在对角线上的块，A的miss率还是1/8，B左上角部分的miss率为1/4.

\2. 接下来这步是减少miss率的关键，把A左下角的一列4个数据读出，B右上角的一行4个数据读出，都用int变量暂存，然后把前四个填入B右上角行中，后四个填入B的左下角行中。

因为从B右上角读取的时候，把块放入了Cache，然后从A往B中填的时候，就不会出现miss操作。

来计算一下miss率，对于在对角线上的块，从A左下角读取miss率为1，B的右上角的操作miss率为1/4，B的左下角miss率为1/4。对于不在对角线的快，A的miss率为1/4，B右上角miss率为0，左下角miss率为1/4。

\3. 最后一步就是把A的右下角填入B的右下角，对于在对角线上的块，A的miss率为1/4，B的miss率为1/2.不在对角线上的块，A，B的miss率都为0.

最后我们来计算下miss的次数吧，计算出来近似是1280次，实际我们代码跑出来是1219次。

61×67：

不规则的matrix，本质也是用分块来优化Cache的读写，但是不能找到比较显然的规律看出来间隔多少可以填满一个Cache，但是由于要求比较松，我们可以尝试一些分块的大小，直接进行转置操作。尝试到16左右，可以小于2000次miss。