CSAPP cachelab

Part A

由于不关心具体的块内偏移，所以 cache 可以这样设计：作为一个二维数组，第一维代表组号，第二维代表组内的行号，存放标记位和上一次访问的时间。每次操作时，读取和存放是等价的，直接在对应组号内遍历所有标记位，看是否有对应上的。否则看有无空缺，或是替换掉某一行。修改和上面类似，只需要添加一次命中记数就可以了。

读入命令行参数是一个比较陌生的话题：

while((opt=getopt(argc,argv,"s:E:b:t:"))!=-1)
{
    switch(opt)
    {
        case 's':
            s=atoi(optarg);
            S=1<<s;
            break;
        case 'E':
            E=atoi(optarg);
            break;
        case 'b':
            b=atoi(optarg);
            break;
        case 't':
            input_file=optarg;
            break;
        case '?':
            fprintf(stderr,"Unknown option: %c\n",optopt);
            return 1;
    }
}

"s:E:b:t:" 代表可接受的选项，: 代表该选项需要一个参数。

case '?': 如果选项不在其中，会自动识别为 ?。

整体还是比较容易实现的，写了一百来行就写完了。

Part B

32 $\times$ 32

$8$ 行会填满 cache，所以将数组切成 $8\times 8$ 的小块。但是直接这样做还达不到满分的标准，一个技巧是：将 A 的 8 个元素记录下来，再赋值给 B，这样实现了对 A 的连续访问。

64 $\times$ 64

（参考了网上的做法）

还是考虑 8 × 8 分块，由于存在着每 4 行就会占满一个缓存的问题，在分块内部处理时就需要技巧了，我们把分块内部分成 4 个 4 × 4 的小分块分别处理：

• 第一步，将A的左上和右上一次性复制给B
• 第二步，用本地变量把B的右上角存储下来
• 第三步，将A的左下复制给B的右上
• 第四步，利用上述存储B的右上角的本地变量，把A的右上复制给B的左下
• 第五步，把A的右下复制给B的右下

61 $\times$ 67

如此不规整的数字显然不适合分析了。直接暴力分块，发现块大小取 17 的时候取得最优结果。

---

撒花！