Cache是什么
CPU和内存之间速度的差距越来越大，cache的出现能够弥补这个gap，从计算机组成原理的角度看，cache位于CPU/GPU等处理器和main memory之间的组件，为啥添加一个cache就能提高性能呢？根据之前的存储结构层次，这取决于计算机程序运行的一个特点——程序局部性原理。但是这个概念可以很宽泛。
cache, the term is also used to refer to any storage managed to take advantage of locality of access.
即，只要利用了局部性原理的存储策略，均可以认为是cache，因此在各种网站、数据库中为了负载均衡使用的各种Redis、memcached均为cache。
Cache作为bridge
软件工程师意识不到cache的存在，只是认为在访问内存中的一个地址对应的存储单元。
关于cache的疑问
对于cache的使用和访问，以下问题是核心内容：
- 如何知道是否有数据在cache中？
- 如果在cache中，如何找到该数据？
为了回答上述的问题，需要了解direct-mapped cache structure。
direct-mapped cache structure
这种cache结构，为了将cache中的数据与内存中的数据关联，直接基于这些数据在main memory中的地址，来分配它们在cache中的位置。
- 每个内存地址唯一对应cache中的一个位置；
- 但是cache中的一个位置，可以对应多个内存地址中的位置；
那么如何建立地址之间的映射关系呢？最简单的方式，是取模。
$$
\text{Block address} \text{ mod } \text{Number of blocks in the cache}
$$
如下图：
- cache中有8个blocks(lines);
- 因为8个blocks，对应 $2^3$ ，因此所有main memory中的地址低3位相同的数字都会映射到相同的cache地址上；
回答问题2：如何找到cache中的数据
解决方案：在cache line中添加一个tag字段。
这个字段含有请求数据的main memory地址信息。但是，有意思的是，这个tag段，只需要包含前半部分的地址信息，而不是所有，则是因为低部分的地址是cache line的索引序号。
以上图为例：
- 对于00001，其对应的cache位置是001，这是它的低3位，因此在001cache line上的tag字段只需要记录00，即剩下的高两位即可，两者组成在一起就是main memory的地址；
- 例如，对于访问内存地址11101上的数据时，发现101对应cache line中序号为101的位置，其tag字段还是11，那么该访问就hit the cache了；
回答问题1：如何确定cache中有数据？
为啥先回答问题2，再回答问题1，因为问题1可以由上述的答案解决，逐次对比每个cache line，肯定能知道访问的数据在cache中是否存在。
但是，有几种情形：
- 开机时，cache中为空，tag中的地址信息无意义，进行比较纯属浪费时间；
- 即便执行了很多指令，cache中仍然没有存入数据，这时tag字段也无意义；
因此，啥时候可以不看tag呢？最常用的办法是在cache line中添加一个valid bit。
- 这个bit表明是否该line包含有效的main memory地址；
- 这个bit如果没有设置，说明数据访问时无法与该line进行匹配；
加了这个bit，现在访问cache中的数据分为两步：
- 确定valid bit有效；
- 识别tag字段和cache line的index字段，生成main memory的地址；
这种策略在很多的场景都有用到，通过添加一个标志位，就可以省略了很多的无意义的操作，以空间换时间的典型做法。
参考资料
Computer Organization and Design : the hardware/software interface
