Cache简介

Cache一词来源于1967年的一篇电子工程期刊论文。其作者将法语词“cache”赋予“safe keeping storage”的涵义,

当CPU处理数据时,它会先到Cache中去寻找,如果数据因之前的操作已经读取而被暂存其中,就不需要再从随机存取存储器(Main memory)中读取数据——由于CPU的运行速度一般比主内存的读取速度快,主存储器周期(访问主存储器所需要的时间)为数个时钟周期。因此若要访问主内存的话,就必须等待数个CPU周期从而造成浪费

提供“缓存”的目的是为了让数据访问的速度适应CPU的处理速度,其基于的原理是内存中“程序执行与数据访问的局域性行为”,即一定程序执行时间和空间内,被访问的代码集中于一部分。为了充分发挥缓存的作用,不仅依靠“暂存刚刚访问过的数据”,还要使用硬件实现的指令预测与数据预取技术——尽可能把将要使用的数据预先从内存中取到缓存里。

Cache基本结构

Cache和主存的信息交互按块来组织,块大小常为2的次幂方字节。

Cache对程序员而言是透明的(看不到,所以无需管),CPU访存指令中给出主存地址,改地址被分割为两部分

  • 块地址 -- 用于定位Cache块地址
  • 块内偏移

映像规则

  1. 直接映像

主存块地址第i块映射到大小为M的Cache的第j块

$$ j = i \bmod M $$

  1. 全相连映像

主存块可以放在任意一个Cache块

  1. 组相连映像

主存块地址第i块可以放到分组为G的Cache中第K组的任意一个位置

$$ k = i \bmod G \\ 若\quad G = 2^g \\ n = M/G $$

当G为2的g次幂,则k刚好为i的低g位
如果组相连中每组有n个块,则称之为n路组相连
n即为相连度

查找方法

为了区分当前某Cache保存的是哪一个主存块,有专门的硬件用来记录对应信息,称之为目录表

1 . 对于直接映像
主存块地址结构

    • tag 对应保存的除索引以外的高位部分
    • 块索引

    2 .组相连映像

    主存块地址结构

    • tag 对应保存的除索引以外的高位部分
    • 组索引

    3 .全相连映像

    主存块地址结构

    • tag 只有tag

    全相连映像/组相连中组内如何确定?

    • 使用相连存储器 -- 查找时间为O(1)
    • 使用单体多字存储器+比较器

    替换算法

    当新调入一块,而该块能够占用的Cache位置已被占满时,替换哪一块?

    1. 随机法
    2. FIFO (First In First Out)先进先出法

    实现:使用队列实现

    缺点:不能反映程序的局部性原理

    1. LRU (Least Recently Used)最近最少使用

    原理:依据局部性原理,最近用过的块很有可能马上用到,最不常用的块就是最佳的替换者

    简单实现:计数器

    高效实现:链表+哈希(最近使用块放在链表头,最不常用要删除的块放在链表尾。若Cache中有一块命中,则将之提到链表头,查找位置则由哈希优化)

    1. LFU

    原理:选择一个过去时间内用到最少的块替换

    简单实现:计数器(消耗空间大)

    高效实现:双哈希

    写策略

    对于读访问的优化我们可以在读出标识进行比较的同事,把cache块也读出,若有效,则直接送CPU,若无效,则丢弃。

    一个高效的写策略会大大提高Cache的性能,对于在进行写操作时,该主存块是否以及在Cache中有备份分为两种情况来探讨。

    • 该主存块未在Cache中存在(写失效)

    此时有两种策略

    • 按写分配法(Write allocate)

    写时将所在单元块调入Cache,再进行更新,又称写时取(Fetch on Write)

    • 不按写分配法(Not Write allocate)

    写时直接写入下一级存储器(主存),而不写入Cache,又称绕写(Write Around)

    • 该主存块已在Cache中(写命中或写失效时按写分配)

    此时有两种策略

    • 写直达法(Write Through)

      不仅将信息写入Cache中所在的块,更将其更新至下一级存储器(可先写入写缓冲器中)

    • 写回法(Write Back)

      将信息写入Cache中所在快,只有在该块被替换的时候,才被写回至下一级存储器(需增加一位脏位来判断数据块是否经过修改

    Cache性能分析

    平均访存时间

    平均访存时间 = 命中时间 + 失效率*失效时间

    • 命中时间(Hit Time)指访问Cache命中所用的时间
    • 失效开销,需具体问题具体分析,看Cache是否为分离式Cache,是否为写直达策略

    CPU时间

    $$ CPU时间=IC \times\left(\mathrm{CPI}_{\text {execution }}+\frac{\text { 访存次数 }}{\text { 指令数 }} \times \text { 失效率 } \times \text { 失效开销 }\right) \times 时钟周期时间 $$

    IC:指令数

    例:
    假设一台计算机在 Cache全命中的情况下CPI为1.0,只有Load和 Store指令能进行访存,这两种指令占总指令的50%,如果失效开销为200个时钟周期,失效率为2%,比较全命中情况,此计算机由于失效带来的性能损失有多少?
    解:

    全命中时机器的性能为
    CPU执行时间全命中=(CPU执行周期数+访存停顿周期数)x 时钟周期时间=(IC + CPI + 0) × 时> > 钟周期时间 = IC × 1.0 × 时钟周期时间
    具有真实 Cache的机器性能为
    CPU执行时间(有cache)=IC X (CPI+(访存次数/指令数) X 失效率 X 失效开销)X 时钟周期时间
    =(IC×1.0+IC×(1+0.5)×0.02×200)×时钟周期时间
    =IC×7.0×时钟周期时间
    = 7.0

    改进Cache

    降低Cache失效率

    首先介绍下Cache失效三种情况

    • 强制失效 这种通常发生在第一次访问一个主存块时,该块不在Cache中,需调入
    • 容量失效 由于Cache容量有限,在Cache满,金星替换时,若被替换出去的又被访问,则发生容量失效
    • 冲突失效 在组相联或直接映像中,若多个块映射到同一Cache块,且发生冲突替换,被替换出去的又被访问,则发生冲突失效
    • 调节Cache块大小

    思路:增加块大小利用空间局部性,减少强制失效
    注意:当Cache块大小增大时,也会增加失效开销,因此块大小应调节到使失效率较低且平均访存时间最小的状态

    • 提高相联度
      思路:提高相联度使得冲突失效减少,但同时也会增加Cache的命中时间
    • 使用Victim Cache
      Victim Cache是一个较小的全相联Cache,位于Cache与下一级存储器之间。在访问下一级存储器前,先判断Victim Cache是否存在该块,若有则调入。
    • 硬件预取

    指令和数据在处理器提出访问请求之前进行预取

    • 编译器控制的预取
    • 编译器优化

      • 数组合并
      • 内外循环交换
      • 循环融合
      • 分块

    减少Cache失效开销

    • 写缓冲与写合并

    在写直达Cache中,经常使用一个写缓冲来降低失效开销

    • 让读失效优先于写

    在读失效时检查写缓冲器的内容,如果没有冲突,则继续处理读失效

    • 请求字处理

    请求字:在存储器向CPU调入一块时,往往只有一个字时真正需要的,称为请求字

    当请求字一旦到达就立即送往CPU,同时从存储器中调入其他部分也称为回绕读写

    • 多级Cache
    • 非阻塞Cache

    在允许指令乱序执行的机器中,若数据Cache失效,CPU在等待的同时可以从指令Cache中取指令等工作

    减少命中时间

    • 容量小、结构简单的Cache
    • 虚拟Cache

    使用虚地址映射并访问的Cache

    • 访问流水化

    提高Cache带宽,从整体上降低平均命中时间

    • 多体Cache

    减小Cache平均命中时间,增大Cache的吞吐率

    • 路预测
    Last modification:May 15th, 2020 at 07:37 pm
    如果觉得我的文章对你有用,请随意赞赏