PC_替换算法/cache回写策略

常见替换算法

• 替换算法应用在
  • cache块-主存块替换
  • 主存-外存的页面替换

随机算法RAND

• 随机地确定要被替换的cache块
• 实现简单,但是由于不符合程序局部性原理,可能使得命中率较低

先进先出算法FIFO

• 选择最早调入的cache块进行替换(根据停留在cache中的时间来判断)
• 也比较容易实现,同样不符合程序局部性原理
  • 较早进入cache的主存块,及时它非常频繁地被使用,也会由于存在于cache中较长时间而导致被替换
  • 可见,仅仅依赖于存留时间是不太理想的替换标准
  • 如果能够知道某个块距离上一次访问时间间隔来综合考虑,那么会避免上述的弊端
    • 这样,如果某个常用的块在主存中停留了较长时间,但是由于它被频繁访问,因此它的上一次被访问时间点$T_{last}$和当下要执行替换操作的时间点$T_{now}$的间隔不会大,而且应该是比较小的

最近最少使用LRU

• LRU:Least Recently Used
• 这个算法比较符合程序局部性原理
• 算法选择近期一段时间内较长世界未被访问的Cache行替换掉
• 平均命中率比FIFO高,且实现开销不是太大

实现思路

• 采用数值记录主存块的使用情况
• LRU要求对每个cache行设置一个计数器
  • 计数器充当一个淘汰权重,的角色,数值越大,被淘汰的优先级越高
    • $W_i$:不妨把数值记为$W_i$,表示第$i$个cache块的淘汰权重
    • $V_i$:同时,$W_i$还反映该行最近的被访问情况,不妨用$V_i=\frac{1}{W_i}$来描述访问的频繁程度
      • $V_i$越大,表示访问第$i$个cache块也经常被使用
  • 根据计数值选择淘汰某个块,计数值的位数和cache组大小有关
  • 2路组相联采用1位LRU位
  • 4路组相联采用2位LRU位

LRU计数器变化(维护)规则:

• cpu每次访存,都会影响计数器

• 即,需要对每一行cache行的计数器执行检查/更新操作

• 就算是没有被访问的cache,或者没有命中的访存操作也可能发生计数值的变化

命中时(caseA)

• 🎈SIK操作约定(命中时执行)

  • 被命中的行的计数器清零$W_i=0$(Set)

    • 表示刚刚这些cache行被访问过了

  • 比$W_j<W_i$小的计数器+1(Increment)

  • 其余($W_j⩾W_i$的)的计数器值保持不变Keep

    • 这么约定可以计数器的最大值控制在一定的范围内,同时也不影响算法的有效性
    • 理论上这种情况计数器应该是也要+1的(也没有错),但是数值太大不利于表示
      • 假设说,cache(分组)的空间足够大,程序很小而且十分符合局部性原理.以至于大量的访问总是可以在分组内完成(命中)
        • 再极端一点考虑,cpu执行某个简单循环,总是访问同一条指令,cache组内的其他R-1条已知没有再次被访问,如果不使用keep策略,那么会导致这R-1条的计数器爆增
        • 而如果采用keep策略,就可以避免这种爆增情况
        • 认真分析可以发现,+1操作能够使得所有计数器的上限值增大的情况,总是发生在未命中的时候🎄)

cache未被命中(caseB)

• 🎈FSI约定操作(未命中时执行):
  • 填充置位更新操作(Fill+Set+Increment),简称为FSI操作
• CB1:如果cache中还有空闲空间(空闲cache行)
  • 那么将本次访问主存单元所在块(新数据块)调入cache的空闲行
  • FSI操作

• CB2:如果cache已满
  • 执行LRU淘汰操作,空出某(些)行
  • 将新的数据块从主存调入这些新的空行
  • FSI操作

• cache未被命中(另一种描述):

  • CB1:如果cache中还有空闲空间(空闲cache行)
    • 那么将本次访问主存单元所在块(新数据块)调入cache的空闲行
  • CB2:如果cache已满
    • 执行LRU淘汰操作,空出某(些)行
    • 将新的数据块从主存调入这些新的空行
  • 🎈CB1,CB2两类情况均要以FSI操作收尾

• 特点:

  • 当(映射到同一个cache分组的)集中访问的(主存)存储区域(或者说区域容量)超过了cache组的大小

  • 命中率可能会变得很低

  • 这种现象称为抖动

例🎈

• 假定采用4路组相联,用5个不同的主存块{$B_1,B_2,B_3,B_4,B_5$}映射到cache的同一个组

  • 上述的5个块在主存中可能使任意的顺序,且未必是相邻的

  • 将5个块简写为{1,2,3,4,5}

  • 假设主存访问序列是1,2,3,4,1,2,5,1,2,…

  • cache分组的4个cache行\访问的主存块序列	1		2		3		4		1		2		5		1		2
    0	0	1	1	1	2	1	3	1	0	1	1	1	2	1	0	1	1	1
    1			0	2	1	2	2	2	3	2	0	2	1	2	2	2	0	2
    2					0	3	1	3	2	3	3	3	0	5	1	5	2	5
    3							0	4	1	4	2	4	3	4	3	4	3	4

  • 每一大列

    • 左分列表示该cache行的计数器值($W_i$)
    • 右分列表示该cache行调入(持有)的主存块(块号$B_x$)
    • 本例中,$x=1,2,3,4,5;i=0,1,2,3$

最不经常使用算法LFU

• LFU:Least Frequently Used
• 和LRU类似
• 将一段时间内被访问次数最少的存储行换出
• 每一行cache行设置一个被访问次数计数器
• 新行建立后从0开始计数
• 每被访问一次,被访问的行计数器+1
• 在需要替换时比较各特定行的计数值,将计数值最小的

Cache写策略

• 因为Cache中的内容是主存块副本，当对Cache中的内容进行更新时，就需选用写操作策略使Cache内容和主存内容保持一致.
• 此时分两种情况(双向)
  • cache写入主存
  • 主存调入(写入)cache

Cache 写命中( write hit)

全写法

• 全写法（也叫写直通法,write-through).
• 当CPU对Cache 写命中时，必须把数据同时写入Cache 和主存.
  • 当某一块需要替换时(不命中)，不必把这一块写回主存，用新调入的块直接覆盖即可.
• 优点:
  • 这种方法实现简单，能随时保持主存数据的正确性.
• 缺点
  • 是增加了访存次数，降低了Cache的效率.

写缓冲

• 为减少全写法直接写入主存的时间损耗，在Cache和主存之间加一个写缓冲(Write Buffer )，
• CPU同时写数据到Cache 和写缓冲中，写缓冲再将内容写入主存.
• 写缓冲是一个FIFO 队列，写缓冲可以解决速度不匹配的问题.
  • 但若出现频繁写时，会使写缓冲饱和溢出.

回写法

• 回写法( write-back).
• 当CPU对 Cache 写命中时，只把数据写入Cache，而不立即写入主存，只有当此块被换出时才写回主存.这种方法减少了访存次数，但存在不一致的隐患.
• 为了减少写回主存的开销，每个Cache 行设置一个修改位（脏位).
  • 若修改位为1，则说明对应Cache行中的块被修改过，替换时需要写回主存;
  • 若修改位为0，则说明对应 Cache行中的块未被修改过，替换时无须写回主存.

小结

• 全写法和回写法都对应于Cache写命中（要被修改的单元在Cache中）时的情况.

Cache 写不命中

写分配法

• 写分配法 ( write-allocate).
  • 加载主存中的块到Cache 中，然后更新这个Cache块.
  • 它试图利用程序的空间局部性，但缺点是每次不命中都需要从主存中读取一块.

非写分配法

• 非写分配法( not-write-allocate)
  • 只写入主存，不进行调块.

小结

• 非写分配法通常与全写法合用，写分配法通常和回写法合用.

分离的Cache结构

• 随着新技术的发展（如指令预取)，需要将指令Cache和数据Cache分开设计，这就有了分离的Cache结构.
  • 统一Cache 的优点是设计和实现相对简单，但由于执行部件存取数据时，指令预取部件要从同–Cache读指令，会引发冲突.
  • 采用分离Cache 结构可以解决这个问题
    • 而且分离的指令和数据Cache还可以充分利用指令和数据的不同局部性来优化性能.
  • 现代计算机的Cache 通常设立多级Cache，假定设3级Cache，按离CPU的远近可各自命名为Ll Cache、L2 Cache、L3 Cache，离CPU越远，访问速度越慢，容量越大.
    • 指令Cache与数据Cache分离一般在L1级，此时通常为写分配法与回写法合用.
      • 例如
      • L1 Cache对 L2 Cache使用全写法，
      • L2 Cache对主存使用回写法，
    • 由于L2 Cache的存在，其访问速度大于主存，因此避免了因频繁写时造成的写缓冲饱和溢出.