Cache的基本原理
目前Cache被集成在CPU内部，且用SRAM实现，速度快，成本高
当cache要运行时，会将主存的存储空间进行“分块”，cache与主存之间的数据交换以cache块为单位。
例：设每1KB为一块，主存共4MB，cache为8KB，主存与cache间以“块”为单位进行数据交换。
4MB=$2^{22}bit$，1K=$2^{10}$，因此主存可以被分为$2^{12}=4096$块，cache分为8块。
然后因主存的地址共22位，所以可以将12位用来表示块号，剩下10位表示块内地址。
局部性原理
- 空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的
- 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息（指一段代码可能在邻近时间很快再被调用）。
Cache就是用局部性原理，把程序中正在使用的部分数据存在cache中，使CPU的访存操作大多数针对cache进行，从而提高程序的执行速度。
例：
//程序A：按行访问
int sumarrayrows(int a[M][N])
{
int i, j, sum = 0;
for( i = 0; i < M; i++){
for( j=0; j<N; j++){
sum += a[i][j];
}
}
}//程序B：按列访问
int sumarrayrows(int a[M][N])
{
int i, j, sum = 0;
for( j = 0; j < N; j++){
for( i=0; i<M; i++){
sum += a[i][j];
}
}
}由于数组是按行进行存放在内存中，因此按行访问会有空间连接性，程序A的空间局部性会比程序B的空间局部性更好。cache执行程序A会更快。
性能分析
在之前要先了解一些概念，
命中率H：CPU欲访问的信息已在Cache中的比率。
缺失（未命中）率： M = 1 - H。
设一个程序执行期间，cache的总命中次数位$N_c$，访问主存的总次数为$N_m$，则命中H：
$$
H=N_c/(N_c+N_m)
$$
设$t_c$为访问一次cache所需时间，$t_m$为访问一次主存所需时间。则cache主存系统的平均访问时间t（以先访问cache，若cache未命中再访问主存）为：
$$
t=Ht_c+(1-H)(t_c+t_m)
$$
若同时访问cache和主存，若cache命中则立即停止访问主存，平均访问时间t：
$$
t=Ht_c+(1-H)t_m
$$
cache和主存的映射方式
cache行中的信息是主存中某个块的副本，地址映射就是指把主存地址空间映射到cache地址空间。并且cache中每块要加一个标记，指明它是主存中的哪一块副本。为了说明cache行中的信息是否有效，每个cache行需要一个有效位。
地址映射的方法有三种：
全相连映射
主存的每一块可以装入cache中的任何位置，每行的标记用于指出该行取自主存的哪一块，所以CPU访存时需要与所有cache行的标记进行比较。
优点是比较灵活，cache块的冲突概率低，空间利用率搞，命中率也高；
缺点是标记的比较速度较慢，实现成本较高，通常需要采用昂贵的按内容寻址的相联存储器进行地址映射。
例：
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据cache有8个cache行（即cache块，与主存块的大小相等），行长为64B。
主存256MB=$2^{28}$bit，主存的地址共28位，由于块大小为64B=$2^6$， 所以主存块内地址为6位，主存块号22位。
使用全相联映射，先初始所有有效位为0，主存的块可以放到cache中的任意位置。假设将主存块号0放到cache3中，此时会将有效位置为1，并标记上当前主存的主存块号。
同样若将$2^{22}-3$的主存块放入到cache1中，标记会变为$2^{22}-3$的主存块号。如下图所示。
当使用“全相联映射”进行访问主存地址$1…1101 \quad 001110$时，会根据主存地址的前22位对比cache 中所有块的标记；
若标记匹配且有效位=1，则cache 命中，访问cache块内地址为001110的单元。
若未命中或有效位=0，则正常访问主存。
直接映射（只能放固定位置）
主存中的每一块只能装入cache中的唯一位置。若这个位置已有内容，则产生块冲突，原来的块将无条件被替换出去（无需使用替换算法）。直接映射实现简单，但不够灵活，即使cache的其他许多地址空着也不能占用，空间利用率低。
直接映射的关系可定义为：
$$
cache行号=主存块号 % cache总行数
$$
例：
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据cache有8个cache行（即cache块，与主存块的大小相等），行长为64B。
主存256MB=$2^{28}$bit，主存的地址共28位，由于块大小为64B=$2^6$， 所以主存块内地址为6位，主存块号22位。
若将0块号主存放入到cache中，此时0%8=0，所以会放到cache0中。
若想再将8块号主存放到cache中，由于8%8=0，所以会直接覆盖原先cache存放的信息。
使用直接直接映射由于是对cache总行数取模，因此可以只取$\log_2总行数$来得到应映射到cache哪一行，该例题中$log_28=3$，因此只需19位标记即可，3位作于cache的行号，就可以直接根据主存块地址的后三位来确定应该放在cache的哪一行。
组相联映射（可放到特定分组）
将cache分成Q个大小相等的组，每个主存块可以装入固定组中的任意一行，即组间采用直接映射、组内采用全相联映射的方式。
组相联映射的关系可以定义为：
$$
cache组号=主存块号 % cache组数（Q）
$$
例：
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据cache有8个cache行（即cache块，与主存块的大小相等），行长为64B，采用二路组相联映射（2块为一组，分四组）。
主存256MB=$2^{28}$bit，主存的地址共28位，由于块大小为64B=$2^6$， 所以主存块内地址为6位，主存块号22位。
若想将块号1主存放入cache中，此时分组数=4，1%4=1，所以会放入到第1组中任意位置。
同样的，和直接映射类似，可以通过$\log_2分组数$来直接判断应该留几位作为判断放入cache的哪一个分组。在这例子中$\log_24=2$，2位作为cache行号，剩下20位作为标记位。
Cache中主存块的替换算法
在采用全相联映射或组相联映射方式时，从主存向cache传送一个新块，当cache或cache组中的空间已被占满时，就需要使用替换算法置换cache行。
随机算法（RAND）
若cache已满，则随机选择一块替换。
例：
设总共有4个cache块，初始整个cache为空。采用全相联映射，依次访问主存块 {1，2，3，4，1，2，5，1，2，3，4，5}
由题第一次调用1，2，3，4会依次将主存块放入cache中，此时cache都未命中（因为原先cache中没有内容）。
再进行访问 1，2，此时cache中有1，2，就算命中，当访问5时，由于cache中没有5，根据随机算法cache会随机替换一个，假设这里随机替换了cache2中的3。
而后面的步骤就与前面几乎相同，若cache中有则命中，没有则进行替换。
随机算法实现简单，但没考虑局部性原理，实际效果很不稳定。
先进先出算法（FIFO）
选择最早调入的行进行替换。
例：
设总共有4个cache块，初始整个cache为空。采用全相联映射，依次访问主存块 {1，2，3，4，1，2，5，1，2，3，4，5}
前面与上个随机算法图相似，依次访问到5的时候，根据先进先出的原则，会将cache0块中的1替换为5.
后面都是同样的步骤。
先进先出算法实现简单，也没考虑局部性原理，最先被调入cache的块也有可能是被频繁访问的，同时也会出现抖动现象（频繁的换入换出）。
近期最少使用算法（LRU）
依据程序访问的局部性原理，选择近期内长久未访问过cache行进行替换，是堆栈类算法。
LRU会为每一个cache块设置一个“计数器”，用于记录每个cache块有多久没被访问，当cache满后替换“计数器”最大的。
计数器的变化规则为：
- 命中时，所命中的行的计数器清零，比其低的计数器加1，其余不变。
- 未命中且还有空闲行时，新装入的行的计数器置0，其余全加1；
- 未命中且无空闲行时，计数器最大的行的信息块被淘汰，新装行的块的计数器置0，其余全加1。
例：
设总共有4个cache块，初始整个cache为空。采用全相联映射，依次访问主存块 {1，2，3，4，1，2，5，1，2，3，4，5}
前面与先前的算法都一样，依次访问到5的时候，由于此时cache已满，根据访问时间来看，3是最久没被访问的，所以会用5来替换3的位置，后面的处理方法类似。
cache块的总数=$2^n$，则计数器只需n位。且cache装满后所有计数器的值一定不重复。
最不经常使用算法（LFU）
为每一个cache块设置一个“计数器”，用于记录每个cache块被访问过几次。当cache满后替换“计数器”最小的。
例：
设总共有4个cache块，初始整个cache为空。采用全相联映射，依次访问主存块 {1，2，3，4，1，2，5，1，2，3，4，5}
前面与先前的算法都一样，新调入的块计数器置0，之后每个被访问过后计数器都会加1，依次访问到5的时候，需要替换，会选择计数器最小的行（若有多个最小的行，可按行号递增或FIFO策略进行选择），此时5就会替换3的位置，后面的步骤就与前面一致。
LFU算法，曾经被经常访问的主存块在未来不一定会用到，并没有很好的遵循局部性原理，实际运行效果不如LRU。
Cache写策略
因为cache中的内容是主存块副本，当对cache中的内容进行更新时，就需选用写操作策略使cache内容和主存内容保持一致。
写命中
对应cache写命中（write hit），有两种处理方法。
全写法（写直通法， write-through）
当CPU对cache写命中时，必须把数据同时写入cache和主存。这种方法实现简单，保证主存数据的正确性。缺点使增加访存次数，降低了cache 的效率。
使用全写法需要借助一个写缓冲（SRAM实现的FIFO队列）：为减少全写法直接写入主存的时间损耗。
每当对cache块进行写入时，同样也会对写缓冲进行写入，然后会在专门的控制电路下逐一写回。
当出现频繁写时，会使写缓冲饱和溢出。
回写法（write-back）
当CPU对cache写命中时，只把数据写入cache，而不立即写入内存，只有当此块被换出时才写回主存。
并且会给每个cache行设置一个修改位（脏位）。若修改位为1，则说明对应cache行中的块被修改过，替换时需写回主存；若=0，则说明未被修改。
如下图所示，cache3被修改过，仅当cache3被换出时候写回主存0块号。
写不命中
对于cache写不命中，也有两种处理方法。
写分配法（write-allocate）
加载主存中的块到cahe中，然后更新这个cache块。
通常搭配写回法使用。
非写分配法（not-write-allocate）
只写入主存，不进行调块。 非写分配法通常搭配全写法使用。
现代计算机一般都会采用多级cache。
