高速缓冲存储器

高速缓存（英语：cache，/kæʃ/ KASH ）简称缓存

Cache工作原理

概念

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

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

CPU的缓存曾经是用在超级计算机上的一种高级技术，不过现今电脑上使用的的AMD或Intel微处理器都在芯片内部集成了大小不等的数据缓存和指令缓存，通称为L1缓存（L1 Cache即Level 1 On-die Cache，第一级片上高速缓冲存储器）；而比L1更大容量的L2缓存曾经被放在CPU外部（主板或者CPU接口卡上），但是现在已经成为CPU内部的标准组件；更昂贵的CPU会配备比L2缓存还要大的L3缓存（level 3 On-die Cache第三级高速缓冲存储器）。

当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。

缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。

在处理器看来，缓存是一个透明部件。因此，程序员通常无法直接干预对缓存的操作。但是，确实可以根据缓存的特点对程序代码实施特定优化，从而更好地利用缓存。

概念扩充

如今缓存的概念已被扩充，不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为Cache。

基本参数

cache命中率

在一个程序执行期间, 设Nc表示cache完成存取的总次数, Nm表示主存完成存取的总次数,h定义为命中率:

h=NcNc+Nm\mathrm{h}=\frac{N_c}{N_c+N_m}

cache/主存系统平均访问时间

若Tc表示命中时的cache访问时间, Tm表示未命中时的主存访问时间, 1-h 表示未命中率(缺失率),则平均访问时间:

ta=htc+(1−h)tmt_a=h t_c+(1-h) t_m

cache访问效率

cache/主存系统平均访问时间 Ta越接近Tc越好, 设 r=tm/tc (主存慢于cache的倍率), 访问效率e:

e=tcta=tchtc+(1−h)tm=1h+(1−h)r=1r+(1−h)he=\frac{t_c}{t_a}=\frac{t_c}{h t_c+(1-h) t_m}=\frac{1}{h+(1-h) r}=\frac{1}{r+(1-h) h}

CPU执行一段时间时，cache完成存取次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间:

h=NcNc+Nm=19001900+100=0.95r=tm/tc=250 ns/50 ns=5e=1r+(1−r)h=15+(1−5)×0.95=83.3%ta=tc/e=50 ns/0.833=60 ns\begin{aligned} & \mathrm{h}=\frac{\mathrm{Nc}}{\mathrm{Nc}+\mathrm{Nm}}=\frac{1900}{1900+100}=0.95 \\ & \mathrm{r}=\mathrm{tm} / \mathrm{tc}=250 \mathrm{~ns} / 50 \mathrm{~ns}=5 \\ & \mathrm{e}=\frac{1}{\mathrm{r}+(1-\mathrm{r}) \mathrm{h}}=\frac{1}{5+(1-5) \times 0.95}=83.3 \% \\ & \mathrm{ta}=\mathrm{tc} / \mathrm{e}=50 \mathrm{~ns} / 0.833=60 \mathrm{~ns} \end{aligned}

Cache置换策略

主存容量远大于CPU缓存，磁盘容量远大于主存，因此无论是哪一层次的缓存都面临一个同样的问题：当容量有限的缓存的空闲空间全部用完后，又有新的内容需要添加进缓存时，如何挑选并舍弃原有的部分内容，从而腾出空间放入这些新的内容。解决这个问题的算法有几种，如最久未使用算法（LFU）、先进先出算法（FIFO）、最近最少使用算法（LRU）、非最近使用算法（NMRU）等，这些算法在不同层次的缓存上执行时拥有不同的效率和代价，需根据具体场合选择最合适的一种。

  • 随机替换(RAND)

    • 硬件随机选择

  • 先进先出(FIFO: First-In First-Out)

    • 最先调入此cache组内的块被替换

  • 最少使用(LFU: Least Frequently Used)

    • 需要为每个cache行设置访问计数器

  • 最久未使用(LRU: Least Recently Used)

    • 需要为每个cache行设置计时器

Cache分配策略(Cache allocation policy)

cache的分配策略是指我们什么情况下应该为数据分配cache line。cache分配策略分为读和写两种情况。

读分配(read allocation)

当CPU读数据时，发生cache缺失，这种情况下都会分配一个cache line缓存从主存读取的数据。默认情况下，cache都支持读分配。

写分配(write allocation)

当CPU写数据发生cache缺失时，才会考虑写分配策略。当我们不支持写分配的情况下，写指令只会更新主存数据，然后就结束了。当支持写分配的时候，我们首先从主存中加载数据到cache line中（相当于先做个读分配动作，将cache line 与地址相关联），然后会更新cache line中的数据。

Cache更新策略(Cache update policy)

cache更新策略是指当发生cache命中时，写操作应该如何更新数据。cache更新策略分成两种：写直通和回写。

写直通(write through)

当CPU执行store指令并在cache命中时，我们更新cache中的数据并且更新主存中的数据。cache和主存的数据始终保持一致。

写回(write back)

当CPU执行store指令并在cache中命中时，我们只更新cache中的数据。并且每个cache line中会有一个bit位记录数据是否被修改过，称之为dirty bit（翻翻前面的图片，cache line旁边有一个D就是dirty bit）。我们会将dirty bit置位。主存中的数据只会在cache line被替换或者显式的clean操作时更新，这样可以一下子向主存中写入多个cache line。因此，主存中的数据可能是未修改的数据，而修改的数据躺在cache中。cache和主存的数据可能不一致。

主存与cache的地址映射

地址映射的基础: 内容可寻址存储器CAM

CAM(Content Addressable Memory)是一种利用内容寻址的存储器

普通存储器是输入地址输出数据，CAM则是输入数据输出地址（或另一数据）

全相联映射(Fully Associative Mapping)

把主存中的一小部分块拷贝在cache中。全相联映射中主存中的每个块都可以放在cache中的任意位置，主存地址与cache地址没有直接关系，需要链式查找

地址转换逻辑把CPU发送来的地址分成两部分，一个tag部分，一个偏移量部分。使用分离出的tag匹配cache中所有行的tag，如果命中则从偏移量处开始读取。如果未命中则取下一级cache中寻找或取主存中寻找

直接映射(Direct Mapping)

直接映射是多对一的映射关系，一个主存块只能映射到cache中的一个特定位置。因为主存中的块比cache中的多，必定有很多块使用同一个cache地址.

因为直接映射使用多对一映射，每个主存块只能存放到指定的cache行中。因为每个块有32个字，所以后5位仍为偏移量。因为cache容量为8行，所以偏移量前面的3位表示了行号，cache根据行号可以直接访问到指定cache行（而不需要链式查找），在当前行内判断剩下的32-3-5=24位是否匹配。如果匹配则cache命中. 实现简单，但易产生冲突缺失

组相连映射(v-way Set Associative Mapping)

在直接映射（多对一）的基础上采取多对多的形式，把cache分组，主存中的每个块只能对应到cache中的特定组（参考直接映射），因为主存容量大于cache容量，所以必定存在很多主存块对应同一个cache组。cache组可以存放多个块，cache在组中链式查找目标标签（参考全相联映射）

如果cache中的组内可以存放v个块，则称v路组相连映射

所以组相连映射的检索过程：

  1. 根据CPU地址传来的到cache中寻找对应的组（这个组一定存在）

  2. 在组中链式寻找标签匹配者

  3. 如果找到，使用偏移量访存

  4. 如果没找到，到下一级cache或者主存中去找

集成了全相联映射和直接映射的优点，被普遍采用

三种方式的比较

地址格式全称

一个组相联cache由64个行组成,每组4行。主存储器包含4K个块,每块128字。请表示内存地址的格式:

视频讲解

虚存与cache的比较

相同点：

  • 二者都利用了程序的局部性原理

  • 目标都是提升系统性价比而诞生的层次性存储体系

不同点：

虚存
cache

解决存储容量问题

解决存储速度问题，使存储器的访问速度尽量不影响CPU的运行速度

单位时间内交换次数少，每次交换数据量大

单位时间内交换次数多，每次交换数据量小

由操作系统（软件）和硬件协同完成，对系统程序不透明，对应用程序透明

完全由硬件实现

PreviousDRAM动态存储器Next指令系统

Last updated

Was this helpful?