理论基础

1. 时间局部性
2. 空间局部性

存储结构

• 存储器
  • ROM
  • RAM
    • SRAM->CACHE
    • DRAM->MEM

CACHE与主存映射

直接映射

假定主存储器32位地址，cache行64B，cache容量512B，则cache有8行

全相联映射

假定主存储器32位地址，cache行64B，cache容量512B

组相联映射

假定主存储器32位地址，cache行64B，cache容量512B，采用两路组相联，则共有4组

三种映射方式总结

映射方式	优点	缺点
直接映射	硬件简单，效率高	空间利用率低，命中率低
全相联映射	空间利用充分，命中率高	或者映射慢或者比较器等硬件资源耗费多
组相联映射	硬件实现、空间利用及效率折衷，综合效果好

1. 组相联映射为直接映射及全相联映射的折衷，平衡两者优缺点，组间直接映射，组内全相联映射，使收益最大；
2. 直接映射相当于一路组相联映射；
3. 全相联映射相当于只有一组的组相联映射。

替换算法

针对全相联映射及直接映射，当内存地址对应的cache组内或全相联区间满了时替换策略

随机算法(RAND)

实现简单，但完全没考虑局部性原理，命中率低，实际效果很不稳定。

先进先出算法(FIFO)

替换最先被调入的Cache 行
实现简单，同样未考虑局部性原理

近期最少使用算法(LRU)

为每行cache设置计数器，每次cache访问各种情况如下处理:

1. 命中时，命中行计数清零，其他非空闲行计数+1；
2. 未命中但有空闲行时，当前块装入空闲行并使其计数置0，其他非空闲行计数+1；
3. 未命中且无空闲行时，找出计数最大行替换当前块，其他行计数+1。

最不经常使用(LFU)

为每行cache设置计数器，每次cache访问各种情况如下处理:

1. 命中时，命中行计数+1；
2. 未命中但有空闲行时，当前块装入空闲行并使其计数置0；
3. 未命中且无空闲行时，找出计数最小行替换当前块，并使计数置0。

写策略

多级缓存

各级缓存间采用写不分配+写通法，最后级cache与主存间采用写分配+写回法。