前面我们知道了,高速缓冲存储器在整个存储系统当中的视图及其功能,和构建高速缓冲存储器的理论(局部性原理)。

Cache的基本原理

存储系统中的Cache 视图

Y3FSQx.png

CPU中任何存在速度差异的地方都配有高速缓冲存储器,比如CPU的一级和二级Cache,以及磁盘当中的高速缓冲存储器。这一节主要侧重CPU和主存之间的高速缓冲存储器。

Cache的功能:缓解快速CPU与慢速的主存之间的速度差异

Cache的理论基础:局部性原理

Cache 的工作过程

读操作

Y3A9aD.png

CPU和Cache之间是字交换,而Cache和主存之间是块交换。

命中时:CPU需要访问主存时,根据访问的地址在Cache中找到了想要的内容。若数据存在就命中。

这个过程有几个问题:

  • 如何判断数据在Cache中?
  • 怎么知道主存里的地址访问Cache能得到正确的数据?
  • Cache中的数据是否有效?(除了CPU访问储存,其他的外设可能会用过DMA操作向主存中写数据,如果修改了,则Cache中的数据就是无效的错的)

不命中时:如果CPU根据主存地址找Cache, 遍历了也没找到信息,就会去向主存要数据。这时候,为了不影响速度,主存会直接把数据传给CPU,同时,为了方便后续访问,将数据所在的一片区域的数据整块挪到Cache里面。

以上就是Cache的读操作。由上可知,如果数据不在Cache中,则访问速度就会变的很慢。

写操作

写操作也分为两种,一种是写穿策略,一种是写回策略。

写穿策略是指,CPU根据主存地址写Cache的同时,也要把接口写到主存当中去。

tQyv60.png

如图,将数据写入到主存中后,才会得后一个写完成的响应。

而写回策略,是CPU先向Cache中写数据,写完后Cache给CPU一个写完成的响应。等到CPU不再往Cache里写数据的时候,将Cache里的数据一起写到主存中。

tQcib8.png

由于Cache没有及时向主存中写数据,所以主存的数据不是最新的,而且如果外围设备有DMA操作,访问了主存,得到的数据就不是最新的。

总结两种策略各有优缺点。第一个策略的缺点是,没有用上Cache的高速特性。每次都写主存还是慢。但是第二个就是,主存中的数据不是最新的。

Cache的地址映射机制

刚才说到,Cache和主存之间是块交换。但是由于原本主存地址是一维的,Cache中的地址是二维的,所以我们要把主存分块。一个数据地址就有了两个参数,说明是那一块,在这一块里这个字是第几个。

但是仅仅这样划分是不够的,还得细化分。刚才读操作命中时就有一个问题判断是不是再Cache中是如何判断的。现在通过细化分可以解决。将块地址再划分为一个tag和一个index。

  • Tag用来判断数据是否在Cache中。
  • Index用来判断在Cache的哪个位置读写数据。

tQWCWQ.png

Cache的结构

为了迎合刚才主存做的一些变化以及解决刚才提出的三个问题,我们需要对Cache也做相应的变化。

如图所示将Cache分为几行,几行里又分出不同区域。

tQW1yR.png

  • 将Cache分为若干行,每一行的大小应该与主存分的块的大小一致,因为主存中的数据是整块搬迁来的。
  • Cache每行包含四部分,是Cache要保存的信息。Tag从CPU访问主存的地址中剥离得到、Data是与主存交换的数据块、Valid表示Cache中的数据 是否有效、 Dirty表示主存中的数据是最新

这里有一个抽象的操作流程的图

tQ4llQ.png

CPU根据剥离出来的Tag位判断数据是否在相连存储图表中判断数据是否在Cache中,如果在就直接让Cache给数据,如果不在,就把地址为传给主存,由主存将数据给CPU,然后主存再将那一块搬到Cache中的特定行。

在搬迁过程中,如果Cache中的特定行被占用了,那还有一个替换策略。后面会讲到。

相联存储器

相联存储器的作用

前面说到Cache是解决快速的CPU和慢速的主存之间的速度差异。为了实现快速的查找,就需要用到相联存储器。

首先我们得知道相联存储器要解决哪些问题。

  • 判断CPU要访问的内容是否在Cache 中
  • 判断依据是什么

Y3FSQx.png

首先,根据上面的图,CPU是根据数据在主存的中的地址来访问主存的,这是冯诺依曼体系结构计算机的的工作原理里说明的。那为了实现快速的判断,如何实现按照主存地址查找Cache?是全部的地址信息吗?

如果用主存的全部地址来查找,那和直接访问主存查找没什么区别,没提高速度,所以只采用一部分地址(即主存地址的部分内容作为查找依据)。那具体是哪一部分参与查找,不同的查找方法有不同的规则。

判断的基本思路

那么有了规则,如何实现快速查找呢?传统的查找算法有顺序,二分查找等等,但是这种查找方法,满足不了高速缓冲存储器中快速查找的要求。所以我们采用另一种方法:使用相联存储器,通过硬件并发查找。

相联存储器的基本结构及工作原理

先看一下相联存储器的结构图

t1b9EQ.png

  • 从地址中剥离出Key关键字
  • 以Key 为关键字全局硬件并发比较
  • 存储体存放有效位、标记、数据等信息
  • 符合寄存器存放Cache 命中行信息
  • 根据符合寄存器的信息取出命中行的数据

下面来详细说一下作用

  • “检索寄存器”和“屏蔽寄存器”这两块结构是从地址中剥离出关键字。
  • 然后多路并发比较线路就是并发的查找的电路
  • 如果通过硬件比较电路判断出数据在Cache当中的时候,就在符合寄存器中记录要查找的数据是在哪个位置,然后相关部件就会利用这个位置信息,在存储体中快速找到数据。

相连存储器的一种技术实现

先从主存地址数据中剥离出标记部分,标记部分送到相关电路。

给出有效位和标记位的存储体,这些内容都会送到多路并发比较线路中进行比较。将从地址中玻璃出阿里的标记,与原来存放在相连存储体中的标记进行多路的并发比较。

t1LSYj.png

比较命中的时候,就是要访问的数据是在Cache中时,比较就会给出命中的结论。命中信号会通过多路选择题,从Cache的数据存储体中,将CPU要访问的数据取出来送给CPU从而实现快速查找。

Cache地址映射与变换方法

上面解决了如何查找,那么我们应该怎么把主存中的数据映射到Cache中呢?如何搬迁才能实现快速查找?

最常见的映射方式有三种:全相联(fully-associated),直接相连(direct mapped),组相联(set-associated)。不用的映射方式,对应的搬迁时的规则和方法不同。下面来讲解三种映射的 特点和原理。

全相联映射的工作原理

全相联映射首先要给主存分块,Cache分行(Line),而且两个分的单位大小要相同。如图所示

tGXs2Q.png

那么每一个字的地址就变为二维的。假如,一个块内有四个字,主存大小为1024个字,那么主存就能被分为256块。256表示为二进制就是8位二进制位。那么第61个字的主存地址为:00001111 01(块号 块内地址)。由于四个一块,第61个字在第15块里面,且是15块里面的第一个。将15转换为八位的二进制。

由此可看出,地址变成了二维的。

这种映射的方法是:主存的数据块可映射到Cache任意行,只要这个位置是空闲的或者符合某种替换规则。同时将该数据块地址对应行的标记存储体中保存。