Cache

高速Cache解决主存与CPU速度不匹配的问题。
CPU可以不访问主存，而与高速Cache交换信息。一般Cache采用高速的SRAM制作，价格比主存贵，容量远小于主存。

Cache-主存储存空间的基本结构

主存由2^n个可编址的字组成，每个字由一个的N位地址。为了与Cache映射，主存与缓存都分成若干块，每块内又包含若干个字，并且使他们的块大小相同。

把主存地址分为两段，高M位表示主存块地址，低B位表示块内地址。
缓存也分为两段，高C位表示缓存的块号，低B位表示块内地址。

任何时刻都有一些主存块在缓存中。CPU要读取主存某字时，1所需要的字已经在缓存，直接访问Cache。2不在Cache，将字所在的主存整个字块一次调入Cache，Cache和主存时字块传送的。

命中率来衡量Cache的效率，主要是指CPU要访问的信息已在Cache内的比率。

N称为访问Cache的总命中数，Nm为访问主存的总次数。命中率为，h=Nc/(Nc+Nm)

Tc是命中时的Cache访问时间，Tm是命中时主存访问时间。1-h是未命中率。Cache-主存系统平均访问时间为Ta=hTc+(1-h)Tm

较小的硬件代价使Cache-主存平均访问时间Ta越接近Tc好。
访问效率：e=Tc/Ta=Tc/(hTc+(1-h)Tm)

块长与命中率之间关系复杂，取决于各程序的局部特性。增大块长可能使命中率增加，也可能使命中率减少。

Cache基本结构


主要由Cache储存体，地址映射变换机构，Cache替换机构组成。
1，Cache储存体
Cache储存体以块为单位与主存交换信息，为加速Cache与主存之间的调用，主存大多采用多体结构，Cache访问主存的优先级最高。
2，地址映射变换机构
将CPU送来的主存地址转换为Cache地址。
3，替换机构
当Cache已满，无法接受来自主存的信息，就进行替换。
4，Cache的读写操作

读：读内存地址，若命中Cache，返回，未命中，访问内存，同时将主存块放入Cache，若装满，进行替换策略。

写：
1写直达法，写入操作时数据既写入Cache又写入主存。能保证主存和Cache数据一致，但增加了访问次数。

2，写回法，写操作时只把数据写入Cache，不写入主存，当Cache数据被替换出去时才写回主存。

为了识别Cache中数据是否一致，Cache中增加一个标志位。清；表示未修改过，主存一致。浊：修改过，与主存不一致。在Cache替换时，清的Cache不必写回主存。浊的需要写回主存。同时更新标志位。

对比：
写直达法：Cache与主存数据一致，读操作不设计对内存的写操作。
写回法：写操作只访问Cache，速度快，多次写只需要写入内存一次，但在读的时候Cache失效要发生数据替换，引起被替换的块回写主存。


Cache改进：
1，单一缓存和两级缓存
单一缓存，是指在CPU和主存之间只设置一个缓存。随着集成电路密度提高，也把缓存直接和CPU在一个芯片内，称为片内缓存。可以提高外部总线的利用率，提高了存取速度。
由于片内缓存在芯片内，容量小，通过系统总线访问内存，访问次数多，速度会下降。在主存与片内缓存之间再增加一个片外缓存，减轻系统总线的负担。
2，统一缓存和分立缓存
统一缓存是指指令和数据都存放在同一缓存Cache
分立缓存是指指令和数据分别存在两个缓存中，一个称为指令Cache，一个称为数据Cache。




Cache主存地址映射

1，直接映射

映射关系：i=j MOD C 或i=j MOD 2^C

i为缓存块号，j为主存块号，C为缓存块数。

每个主存对应一个缓存，每个缓存对应若干主存。

直接映射不够灵活，每个主存块只能固定地对应某个缓存块，即使缓存还有空着许多位置也不能占用，缓存空间利用不充分。如果程序要重复访问同一缓存位置的不同主存块，那么会不停的替换。


2全相联映射
主存每一字都映射到Cache中任何一个块上。


逻辑电路多，成本高

3，组相联映射
是直接映射和全相联映射的一个折中。



替换策略

1，先进先出FIFO，没有根据局部性原理，不能提高Cache命中率。
2，近期最少使用LRU，平均命中率比FIFO高，应用了局部性原理
3，随机法，没有应用局部性原理，不能提高Cache命中率。