cache lab 和分块（blocking)
做完 cache lab 后做的总结，先简单说一下cache和块
cache
是什么：
高速缓存存储器(Cache Memory)是 CPU 缓存系统甚至是金字塔式存储体系中最有代表性的缓存机制，它也与虚拟存储器有着很深的关联。
三个关键组成部分（注意区分大小写）：
- S 表示集合(set)数量
- E 表示数据行(line)的数量
- B 表示每个缓存块(block)保存的字节数目
存放数据的空间大小为：C=S×E×B
一些相关的介绍可以参考之前写的 编写高速缓冲友好的代码
分块
是什么
- 在内循环中提高局部性
- 将数据结构组织成很多块，载入L1 cache
- 用完一个后再载入下一个块
分块好的原因
- 因为cache块大小有限，只能载入一部分到其中，当访问的数据不在其中时就会miss，进行替换代价巨大
- 如果没有合理分块的话，可能会经常出现未命中情况，就会进行替换，之后访问前面被替换的数据又miss了，于是再次替换进来，来来回回就会很惨
- 分块的关键就是减少这种来来回回替换发生的次数，每个小块间发生的替换次数会大大减少，这样可以使所有小块的替换次数加起来也没有一个大块的替换次数多，就会比较爽
- 详情可以看PPT的 Cache Miss Analysis 部分，贴在下文中了
但是代价呢
会使代码很难读！
实验
实现一个cache
主要学习了 getopt() 函数的使用，用于获取命令行中的参数。
ch = getopt(argc, argv, "ab:c")- 单个字符，字符后面没有冒号则不需要参数（-a, -c这样使用），接一个冒号说明后面跟随一个选项参数，字符后面接两个冒号说明后面跟随一个可有可无的选项参数
- 当参数列已经到结尾时getopt()函数返回-1，当遇到一个未知的选项时，getopt 返回’?’
用库函数 **atoi()**，即把一个字符串转化为一个整数；
还有一个，从文件读取用到了库函数 **fscanf()**，该函数与普通的scanf的区别就是该函数多一个参数，就是指向目标文件的文件指针，也就是从指向的文件读取数据。
int fscanf(FILE *stream, char *format, [argument...]);从一个流中执行格式化输入, fscanf遇到空格和换行时结束
其中的format就是相当于正则表达式中的格式，即用什么样的格式来分隔文件中的信息
cache采用LRU策略进行替换，这里用时间戳的方式记录
整个流程：
- 输入数据指定需要访问的地址寄存器
- 分析输入的地址获取其中的组号，块号，并判断是否命中
- 如果命中，则hits++，并更新LRU值。这里我们是在cache块中设置一个时间戳的位来进行更新
- 如果不命中，则misses++，然后判断是否需要eviction，并更新LRU值
实现分块计算
主要是尝试各种不同的块大小，看哪个产生的miss最少，也就是说进行cache块的替换次数最少
这个博文讲的超级细致，详细介绍了每次读取写入数据时cache中的块的查询顺序及所替换的块
从A矩阵转置为B矩阵，A和B都映射在同一个cache上，映射的方式也是相同的，所以不分块时，频繁发生A读取数据时对其中一个块进行替换后，B写入时又对其进行替换，紧接着A读取时再次对其进行替换，，，
而分块就是缩小了A和B访问的数据的范围，因此A替换某个cache块后，很长一段时间内B写入时可能都不会访问这个块，因此减少了miss数。下图例子进行了详细的解释
不分块时：
分块：
