cache
cache的基本工作原理
cache作为主存的缓存，被划分为与主存相等的区域。主存中的区域称为块，也称为主存块，cache中用以存放主存块的区域称为行，或称为槽。
cache的有效位
每一个cache行需要一个有效位，用以标记该行的数据是否有效。在初始阶段，每个cache行都为空，此时有效位均为0.同时，可以通过将有效位置零表示将一个cache行驱逐，在置入一个新的主存块时，将有效位置1.
CPU访问cache的过程
CPU执行过程中需要从主存中读指令或者读写数据，这个过程中，CPU首先给出主存地址，先判断该地址的主存块是否在cache行中，如果在，则把cache行中的数据送CPU，否则，从相应的主存中取出主存块，按规则找到一个cache行，将主存块置入cache行中，并将相应地址的内容送CPU。
cache——主存的平均访问时间
graph LR A[是否命中?] B[cache访问时间] C[主存访问时间+cache访问时间] D[平均访问时间] A--是-->B A--否-->C B-->D C-->D\(T_c\)称为cache访问时间，如果一次cache命中，则需要的时间是\(T_c\)，否则，不命中，访问时间为\(T_c\)加上主存访问时间\(T_m\)，\(T_m\)也称为缺失损失。假设命中率为\(p\)，一次访问的平均时间就是：
\[T_a = p\cdot T_c + (1 - p) \cdot (T_c + T_m) = T_c + (1 - p) \cdot T_m \]cache行和主存块的映射
三种映射规则：
1. 直接映射
直接映射把每一个块映射到固定的cache行中，也称模映射，满足如下关系：
\[ {\DeclareMathOperator*{\mod}{mod} cache行号 = 主存块号 \mod cache行数 \]于是，一个主存地址就被分成了如下的几个部分：
| 标记 | cache行号 | 块内地址 |
|---|
其中，假设cache有\(2^c\)行，主存有\(2^m\)块，主存块共\(2^b\)字节，按字节编址，可得cache行号共c位，块内地址共b位，而主存块号共m位。主存地址中，标记位与cache行号共同组成了主存块号，因此标记的位数\(t=m - c\)。
这种映射方式将连续的\(2^c\)个主存块映射到不同的cache行中，只要低地址相同，就会被映射到同一个cache行。
在这种映射规则下，CPU访存首先根据cache行号直接找到对应的cache行，然后比较高\(t\)位的标记，如果标记位一致并且有效位为1,则命中，根据低b位的块内地址取出相应的数据送CPU，否则不命中，从主存中读出正确的块并淘汰原来的cache行中的内容，有效位置1。
直接映射容易实现，命中时间短，但是由于不够灵活，命中率较低，容易产生频繁的调入调出。
2. 全相连映射
全相连映射下，一个主存块可以放入任意一个cache行中，地址中不需要cache行号，只需要标记位以及块内地址。由于一个主存块可能被放在任何一个cache行中，因此最坏情况下，需要比较所有cache行号的标记，但是由于只要有空闲cache行，就不会发生冲突，命中率较高。
为了加快比较速度，通常每个行设置一个比较器，比较器的位数与标记位的位数一致。全相连映射的cache时间和元件开销大，不易实现，通常不适合较大的cache。
3. 组相连映射
组相连映射结合了前面两种映射规则的优点，将cache分成大小相等的若干个组，每个主存块映射到相应的组内的任意一个行中。满足如下映射关系
\[ {\DeclareMathOperator*{\mod}{mod} cache组号 = 主存块号 \mod cache组数 \]在这种映射规则下，一个主存地址被划分为三个部分：
| 标记 | cache组号 | 块内地址 |
|---|
其中，假设cache共\(2^c\)行，分成\(2^q\)组，则令\(s = 2^{c - q}\)，即组内的行数，称\(2^s\)路组相连。假设主存共\(2^m\)个块，标记位则有\(t = m - q\)位。s的选取关乎cache的性能，s越大，冲突概率越小，相连比较的复杂性越大，反之亦然。
在一次CPU访存中，首先根据cache组号找到相应的组，再比较所有的cache行的标记，如果有相同的标记且有效位为1,说明命中，否则不命中。不命中时，从主存中取出相应的数据，放入对应cache组中任意一行，有效位置1.
cache中主存块的替换算法
由于cache行比主存块数少得多，往往有多个主存块会被映射到同一个cache行，这就需要选择某一个cache行，将其淘汰，然后存放新的主存块，至于如何选择被淘汰的cache行，就设计替换算法。
1. 先进先出算法
该算法总是选择当前最早装入cache的行，将其替换掉。
这种算法容易实现，但是不能正确反映程序的局部性，早被装入cache的行有可能被多次访问，这种算法可能导致较高的缺失率。
2. 最近最少用算法
该算法选择近期最少使用的cache行被替换。
这种算法可以比较正确地反映程序的访问局部性。每个cache行都有一个计数器，称为LRU位，用以记录主存块的使用情况。LRU位的大小与cache组的大小有关，一个\(n\)路的组相连cache，每一个cache行需要\(log_2n\)位的LRU位。
为了简化LRU位计数的硬件实现，通常采用近似的LRU计数方法实现该算法。近似的LRU计数方法只区分哪些是新调入的主存块，哪些是较长时间未使用的主存块，在较长时间未使用的块中选择一个替换。
3. 最不经常使用算法
替换掉cache中引用次数最少的块。参考这个网站对LRU和LFU算法的对比，两者是有不同的。前者淘汰的是较长时间不使用的块，后者淘汰的是在一定时间内使用频率最低的块。
4. 随机替换算法
从候选行中随机选择一个淘汰。在模拟实验中，该算法的性能仅次于基于使用情况的算法，而且代价低。
cache一致性问题
cache中的内容是内存块的副本，这就涉及如何保持cache中内容与内存中内容保持一致的问题。当出现如下情况时，也可能出现一致性问题：
- 多个设备都可以访问主存时，其中一个设备修改了主存块或者CPU修改了cache中的内容时，就会出现一致性问题。
- 当多个CPU共享主存时，如果其中一个CPU修改了cache中的内容，而其他CPU的cache都变为无效。
解决一致性问题的关键在于处理好写操作，通常有两种方法：
全写法
写命中，则同时修改cache和主存，若写不命中，分为写分配法和非写分配法。
- 写分配法：先修改主存中的信息，然后主存块装入cache中。根据空间局部性，所修改的位置周围的内容会被频繁引用，这种方法可以充分利用这种特性。
- 非写分配法：修改完主存中的信息后，不装入cache中。这种方法不能很好地利用空间局部性，但是减少了读入主存块的开支。
为了减少写主存的开支，会在主存和cache中加一个写缓冲（write buffer），写缓冲是一个FIFO队列，一般只有几项，当写操作频率不高时，工作效果良好，但是当频率过高时，写缓冲会因为饱和而发生阻塞。
回写法
写命中时，仅修改cache中的内容，而不修改主存中的内容，等到该行被淘汰的时候再写回主存，这样减少了写主存的次数。这样就需要一个额外的修改位（dirty bit）来标记该行是否被修改。写不命中时，先将主存块装入cache，再修改cache。回写法在进行写操作的时候不会修改主存，而是在主存块被淘汰时一次性修改。
由于写回法不能及时更新主存中的信息，在某些情况下存在隐患（比如上文提到的两种情况），需要其他机制保证信息的一致性。
影响cache性能的因素
总体上看，影响cache性能的因素之一就是cache的命中率，而cache的命中率又和以下三个因素相关：
- 关联度。关联度是指一个内存块对应的cache行的行数。一个内存块的关联度越大，命中率就越高。
- cache容量。cache容量越大，命中率越高，这是比较容易理解的，在相同替换算法下，肯定是cache越大，关联度至少是不减的。
- 交换单位的大小。交换单位越大，根据局部性，命中率就越高。但是更大的交换单位意味着更大的缺失损失，因此主存块的大小需要适中。
另外影响cache性能的因素有：单级/多级cache的选择以及联合/分离cache的选择等。
多级cache是指CPU按顺序访问L1,L2...等多级cache，这种模式下，假设有两级cache，L1和L2的设计目标是不一样的。L1更多的需要考虑访问时间，因为如果不命中还可以访问L2，而L2则需要考虑命中率，否则将导致高额的访存开销。
主存-总线-cache的连接结构也是因素之一，主要有窄型结构，宽型结构以及交叉存储结构，其中，交叉存储结构的综合性能（性价比）最好。
cache与程序性能
程序的性能指程序运行的时间（以及占用的内存），这显然与程序访问数据/指令花费的时间相关，而对应的，这些时间又与cache的命中率，cache访问时间以及缺失损失相关，这就要求程序员编写能够提高命中率的程序（或者用编译器优化），下面是几种优化程序的方法：
- 循环交换。在某些程序中会有嵌套的循环，通过简单地交换循环次序，就可以使程序按存储顺序访问存储器中的数据。这使得程序在尽可能访问一个缓存块内得内容后才进入下一个缓存块。（提高了空间局部性）
- 分块。见《量化研究方法》