cachelab是csapp的配套实验之一，该实验分为A、B两个部分，A部分要求实现一个cache模拟器，B部分是实现一个针对cache优化的矩阵转置函数。

Part A

Part A部分我们需要完成csim.c源文件，参考csim-ref程序接收相同的命令行参数并产生相同的输出。csim-ref是一个参考可执行程序，它能够模拟cache并处理valgrind生成的trace文件，它遵循LRU(最近使用)替换策略。我们的main函数要依次做如下几件事情：

  • 使用getopt库处理参数，保存cache的几个基本参数如s、E、b，并根据基本参数计算其它参数如S、B、t等。
  • 根据这些参数初始化cache，这步需要使用malloc动态申请内存。
  • 读取trace文件并逐行处理每一个operation，其中I操作可以忽略，L和S操作访问cache一次，M操作访问cache两次，这是最关键的一步。
  • 关闭文件流并释放cache的内存。
  • 使用printSummary函数输出结果。
...

Part B

Part B部分我们需要完成trans.c源文件，实现矩阵的转置同时要尽可能的减少cache miss。
首先如下指令安装valgrind

sudo apt install valgrind

注意在进行后续步骤前，要将当前实验目录移动到linux其它目录而非docker的共享文件夹中，否则会出现Program timed out，并且运行driver.py脚本需要python2.7环境。所谓cache friendly如何做到呢，现在脑子里有几个概念：

  • 程序要有良好的空间局部性和时间局部性。时间局部性是多次访问同一个地址尽可能在同一小时间段内(后面访问时该地址大概率在cache里)；空间局部性是在一小段时间内访问的地址尽可能靠近(这样两个地址更可能在同一个block内)。大部分业务层的代码做到这两点基本就够了
  • 对于性能要求苛刻的场景(大循环和重计算)，核心开销代码不得不考虑进行更深层次的cache优化。每个函数都可以视为自身 独占 完整的cache资源(就算刚执行时cache中都是其它数据，在函数执行一定时间后cache的大量block也会被替换为该函数访问的地址)，此时考虑cache的平均hit率，一个有效的策略是对于循环访问的数组进行分块。

32x32

首先计算cache的大小，在test-trans.c中使用的cache是(s=5,E=1,b=5)规格，每个block 2^5=32个字节，能存储8个int值；每一组只有一个块，一共有2^5=32组，所以cache能同时保存32*8=256个int值，也就是可以同时缓存256*4=1024字节=1M连续地址空间的内容。
分析给出的示例代码，单次循环要分别访问A[i][j]和B[j][i]一次，cache在执行该函数时被A和B数组共用。函数对A数组的是沿行遍历访问，效率尚可，对A的访问一共会产生32*4=128次左右miss。但是由于需要对数组转置，对B数组的遍历访问是沿列遍历访问，空间局部性很差，几乎每次访问都是miss，一共会产生1024次左右miss。我们的目标就清晰了，改进遍历方式，优化B数组访问的空间局部性，同时不对A的空间局部性产生影响。根据ppt的提示，我们可以使用分块的方式，也就是将A、B数组分成数个大小一致的正方块，只要保证访问每个块的空间局部性是较优的，那么让数组按块遍历的空间局部性也是较优的。由于cache至多可以存放32x32数组中连续8行的地址空间，所以我们选用8x8作为遍历的基本单位，A、B数组分别被分为16个块，平均每个块产生8次miss，理论上一共产生16*8*2=256次miss。

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    if(M == 32){
        int i, j, tmp;
        int k1, k2;
        for(k1 = 0; k1<32; k1+=8){
            for(k2=0; k2<32; k2+=8){
                for(i=0; i<8; i++){
                    for(j=0; j<8; j++){
                        tmp = A[k1+i][k2+j];
                        B[k2+j][k1+i] = tmp;
                    }
                }
            }
        }
    }
}

使用如上代码测试转置32x32的矩阵一共产生了343次miss，原因是A、B数组共用一个cache，所以某些块会出现A某行(对应B某列)使用cache的同一个block的情况，此时A、B不再能视为各自独立访问。简化计算可以假设A[0][0]和B[0][0]都使用cache的第0组，位于左对角线上的元素会额外产生一次miss，位于对角线上的块会多产生8次miss，每个数组的访问会多产生32次miss，这样理论上一共产生(16*8+32)*2=320次miss。此时就要考虑 时间局部性 的优化，由于题目限制不能在栈上定义超过12个局部变量，我们可以定义8个中间值tmp0～tmp7，将A数组块中一行的数据一次性取出分别赋给8个局部变量，然后在逐个赋给B数组块中一列的数据，这样对角线上的元素仅在访问B时才会产生一次额外miss，理论上一共产生16*8*2+32=288次。

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    if(M == 32){
        int i, tmp0,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7;
        int k1, k2;
        for(k1 = 0; k1<M; k1+=8){
            for(k2=0; k2<M; k2+=8){
                for(i=0; i<8; i++){
                    tmp0 = A[k1+i][k2];
                    tmp1 = A[k1+i][k2+1];
                    tmp2 = A[k1+i][k2+2];
                    tmp3 = A[k1+i][k2+3];
                    tmp4 = A[k1+i][k2+4];
                    tmp5 = A[k1+i][k2+5];
                    tmp6 = A[k1+i][k2+6];
                    tmp7 = A[k1+i][k2+7];
                    B[k2][k1+i] = tmp0;
                    B[k2+1][k1+i] = tmp1;
                    B[k2+2][k1+i] = tmp2;
                    B[k2+3][k1+i] = tmp3;
                    B[k2+4][k1+i] = tmp4;
                    B[k2+5][k1+i] = tmp5;
                    B[k2+6][k1+i] = tmp6;
                    B[k2+7][k1+i] = tmp7;
                }
            }
        }
    }
}

使用如上代码测试转置32x32的矩阵一共产生了287次miss符合预期，低于300次即可拿到满分。

64x64

对于64x64的矩阵，明显不能单纯使用8x8的分块策略，因为每行从32个值增加为64个值，此时cache至多可以存放64x64数组中连续4行的地址空间。按照之前的思路我们选用 4x4的分块策略，数组将被分为256个块，那么理论上共会产生256*4*256*2+64=1600次miss,实际测试时发现产生了1699次miss，没达到满分1300次以内的要求，只得到了3.4分，原因是在4x4分块时cache的利用率较低。看了下网上的解决方案都比较复杂，这种针对特定场景的高级别的优化基本可以看作是纯粹的脑力训练，这里我就不求甚解了，代码如下

void transpose_submit(int M, int N, int A[N][M], int B[M][N]){
    if(M == 64){
        int i, tmp0,tmp1,tmp2,tmp3;
        int k1, k2;
        for(k1 = 0; k1<M; k1+=4){
            for(k2=0; k2<N; k2+=4){
                for(i=0;i<4;i++){
                    tmp0 = A[k1+i][k2];
                    tmp1 = A[k1+i][k2+1];
                    tmp2 = A[k1+i][k2+2];
                    tmp3 = A[k1+i][k2+3];
                    B[k2][k1+i] = tmp0;
                    B[k2+1][k1+i] = tmp1;
                    B[k2+2][k1+i] = tmp2;
                    B[k2+3][k1+i] = tmp3;
                }
            }
        }
    }
}

61x67

对于不规则61x67的矩阵，可以先对60x60的矩阵使用4x4的分块策略，剩下的部分直接用最原始的赋值即可。代码如下：

void transpose_submit(int M, int N, int A[N][M], int B[M][N]){
    if(M == 61){
        int i, tmp0,tmp1,tmp2,tmp3;
        int k1, k2;
        int k1_max = M/4*4;
        int k2_max = N/4*4;
        for(k1 = 0; k1<k1_max; k1+=4){
            for(k2=0; k2<k2_max; k2+=4){
                for(i=0;i<4;i++){
                    tmp0 = A[k1+i][k2];
                    tmp1 = A[k1+i][k2+1];
                    tmp2 = A[k1+i][k2+2];
                    tmp3 = A[k1+i][k2+3];
                    B[k2][k1+i] = tmp0;
                    B[k2+1][k1+i] = tmp1;
                    B[k2+2][k1+i] = tmp2;
                    B[k2+3][k1+i] = tmp3;
                }
            }
        }
        for(k1=k1_max; k1<M; k1++){
            for(k2=0; k2<k2_max; k2++){
                tmp0 = A[k1][k2];
                B[k2][k1] = tmp0;
            }
        }
        for(k1=0; k1<k1_max; k1++){
            for(k2=k2_max; k2<N; k2++){
                tmp0 = A[k1][k2];
                B[k2][k1] = tmp0;
            }
        }
        for(k1=k1_max; k1<M; k1++){
            for(k2=k2_max; k2<N; k2++){
                tmp0 = A[k1][k2];
                B[k2][k1] = tmp0;
            }
        }
    }
}