1.Cache的原理
Cache被继承在CPU内部，用SRAM实现，速度快，集成度低（在芯片大小不能很大的情况下，Cache被允许的存储空间非常小），成本高
基于局部性原理，不难想到，可以把CPU目前访问的地址“周围”的部分数据复制到cache中，当CPU
想访问这些数据时，直接到Cache中寻找即可，提高了CPU的运行速度。
对于局部性原理的说明：
如下图所示，二维的数组会在内存中被顺序存放，若现在访问的是a[0][0]数组，那么与其相邻的数组可能很快会被访问，这就是空间局部性
空间局部性：在最近的未来要用到的信息(指令和数据)，很可能与现在正在使用的信息在存储空间上是邻近的
时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息，例如循环结构的指令代码。
若把程序A改为程序B，即按列访问，那么其访问二维数组的顺序为a[0][0],a[1][0],a[2][0]
可以发现，程序B空间局部性更差一些。
2.Cache的性能
CPU先访问Cache，若Cache未命中再访问主存，设 
为CPU访问一次Cache所需时间， 
为CPU访问一次主存所需时间。若CPU想要访问的信息已在Cache中，那么称为CPU命中，命中率为H，那么缺失(未命中)率M=1-H
那么系统的平均访问时间t为：
若CPU同时到Cache和主存中找需要的数据，若在Cache中命中，若Cache命中，则立即停止访问主存，那么访问的时间为 
,若Cache未命中，由于是同时查找，那么访问的时间为 
，那么总公式为：
例如：
假设Cache的速度是主存的5倍，且Cache的命中率为95%)，则采用cache后，存储器性能提高多少(设Cache和主存同时被访问，若cache命中则中断访问主存)?
若Cache和主存同时访问，命中时访问时间为t，未命中时访问时间为5t
平均访问时间为 0.95xt + 0.05x5t = 1.2t
故性能为原来的 5t/1.2t 4.17倍
若先访问Cache再访问主存，命中时访问时间为t，未命中时访问时间为t+5t
平均访问时间为T=0.95xt + 0.05x6t = 1.25t
故性能为原来的5t/1.25t = 4倍
基于局部性原理，不难想到，可以把CPU目前访问的地址“周围”的部分数据放到Cache中。如何界定“周围”？
可以将主存的存储空间“分块”，如：每 1KB为一块。主存与Cache之间以“块”为单位进行数据交换
在CPU访问某个内存数据时，可以通过其地址信息判断他属于哪一个块，并且把这一块复制到Cache中
如图所示，主存容量为4MB（2^22），每一块为1K(2^10)，那么整个主存被分为2^12=4096块
所以主存的地址共22位，结构如下：
同理，我们将Cache分为大小相同的块，那么主存与Cache就能进行以“块”为单位的数据交换
注：操作系统中，通常将主存中的“一个块”也称为”一个页/页面/页框”，Cache中的“块”也称为“行”
3.Cache和主存的映射方式
CPU如何区分Cache和主存的数据块的对应关系？
CPU先访问Cache，再访问内存，并将内存相应的块数据复制到Cache中（不是将其从内存中删除） ，即每次被访问的主存块一定会被立即调入Cache，那么如何记录主存块与Cache块的映射关系呢？
（1）全相联映射
主存块可以放在Cache的任意位置
（2）直接映射
每个主存块只能放到一个特定的位置：Cache块号=主存块号%Cache总块数
例如主存块号为1，9的内存块都会被放到Cache块号为1的位置。
（3）组相联映射
将Cache的各个块进行分组，每个分组的总块数相同，每个主存块可放到特定分组中的任意一个位置：组号=主存块号%分组数
例如下图中Cache被分为4个分组，那么对于内存块号为1的内存块就是1%4=1，那么1号内存块就会被放在Cache中第1组的任意空闲位置。
我们回到最初的问题：CPU如何区分Cache和主存的数据块的对应关系呢?
可以给每个cache块增加一个“标记”记录对应的主存块号,例如0号Cache块的标记为9,则表示0号Cache块的数据是9号内存块的副本
若2进制表示,初始都为0,没有数据的则记为0,但是0也可以表示为是主存号为0的内存块的副本,所以光有标记不行,还需要增加有效位
有效位的1表示有效,0表示无效,如下图所示,只有7号Cache块标记为0,有效位为1,表示7号Cache块存储的是0号内存块的副本,其余标记为0的Cache块,则表示没有数据
对于全相联映射:
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据Cache有8个Cache行(即Cache块,与主存快的大小相等)，行长为64B。
256M=2^28主存的地址,共28位,
按照如上结构,给定主存地址如下所示:
全相联映射的过程,全相联映射中,主存块可以放到Cache中的任意一个位置,如下图所示,主存块映射到3号Cache块,首先会将其有效位置1,接着标记其映射的是主存的哪一位置,即标记主存块号
(22位)
若CPU需要访问主存地址1.....1101001110:
①CPU会将主存地址的前22位，对比Cache中所有块的标记;
②若标记匹配且有效位=1，则Cache命中，在Cache中访问块内地址为001110的单元
③若未命中或有效位=0，则正常访问主存
优点:Cache存储空间利用充分命中率高;
缺点:查找“标记”最慢，有可能需要对比所有行的标记
对于直接映射:
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据Cache有8个Cache行，行长为64B。
直接映射，主存块在Cache中的位置=主存块号%Cache总块数
例如,对于0号内存块,只能放到0%8=0,即0号Cache块,将有效位改为1,同时标记为0...0000(22位)
若想将8号内存块调入Cache,8%8=0,则需要将之前存放的数据覆盖,同时要把标记改为8号主存块的块号0...01000
所以,如果采用直接映射的方式,虽然其他地方有空闲的Cache块,但是8号主存块不能使用
相比于全相联映射,直接映射灵活性低,空间利用率也不充分
是否能优化标记呢?
对于上图Cache块数为8,主存块号%2^3,相当于留下主存块号最后3位二进制数,表示主存块在Cache中的位置,也就是说某一主存块能够存放在0号 Cache,那么这个主存块的块号的末尾三位一定是000
我们已经知道主存块放在Cache中的位置,就没必要记录末尾3位了,将主存块号的其余位作为标记即可(标记保留19位即可,即块号的前19位)
总结:
若Cache总块数=2^n,则主存块号末尾n位直接反映它在Cache中的位置,将主存块号的其余位作为标记即可
基于这种方式,CPU如何访问主存地址:
若CPU访问主存地址0...01000 001110:
①根据主存块号的后3位确定Cache行
②若主存块号的前19位与Cache标记匹配且有效位=1，则Cache命中，在Cache块中访问块内地址为001110的单元。
③若未命中或有效位=0，则正常访问主存
优点:对于任意一个地址，只需对比一个“标记”，速度最快;
缺点:由于某个主存块只能放到Cache中的固定位置,Cache存储空间利用不充分，命中率低
对于组相联映射:
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据Cache有8个Cache行，行诊为64B。
组相联映射，所属分组=主存块号%分组数
假设Cache采用2路组相联映射---2块为1组,分四组
分为4组,所属分组=主存块号%分组数=主存块号%2^2,相当于只保留了主存块号的末尾2位来表示所属分组的组号,既然主存块出现在Cache中的同一组,那么说明主存块号末尾2位一定相同,所以标记就没有必要记录这两位了,所以对于这题的标记,只需要取主存块号前20位即可
总结:
CPU访问主存地址:1....1101001110
① 根据主存块号的后2位确定所属分组号
② 若主存块号的前20位与分组内的某个标记匹配且有效位=1，则Cache命中，在Cache中访问块内地址为 001110 的单元。
③若未命中或有效位=0，则正常访问主存
优点:另外两种方式的折中，综合效果较好
注:n路组相联映射----每n个Cache行为一组
计算机组成原理（4）-----Cache的原理及相关知识点(2)：https://developer.aliyun.com/article/1511479
