计组—缓存Cache

一时失言乱红尘 2022-04-16 07:16 567阅读 0赞

**缓存**

通过大量统计发现了一个访问规律：程序对存储空间90%的访问局限于存储空间的10%的区域中，另外10%的访问则分布在存储空间的90%区域中。（即：存储器10%的存储空间是高频访问区，90%的存储空间是低频访问区）

计算机程序对存储器的访问有两种局限性规律：

1.时间局限性：

如果一个存储单元被访问，则可能这个存储单元很快再次被访问。

2.空间局限性：

如果一个存储单元被访问，则它临近的存储单元可能很快被访问。

**cache的功能**

早期的计算机只有主存及外存，没有cache，因为cpu速度不断提高，**为了满足cpu和存储器之间的速度差异**，采用了cache技术。

cache是介于cpu和主存之间的小容量存储器，存取速度比主存快。能高速的向cpu提供指令和数据，加快程序的执行速度，它的内容为主存一部分内容的副本。当存储器接到有关读取指令时，现在cache中查找此信息是否存在，若有则不经主存直接从cache中取出，否则直接从主存取出，同时写入cache，以备再次使用。

cache目的是为了解决cpu和主存速度不匹配的技术。cache用来存放程序中当前最活跃的程序和数据。

总的原则：尽量使计算机的存取速度接近cache，容量为内存大小。

**cache的基本原理**

cpu与cache之间的数据交换是以字位单位。而cache与主存之间的数据交换是以块为单位，一个块由若干定长字组成。如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70][]

当cpu读取主存中一个字时，便发出此字的地址到cache和主存，此时cache控制逻辑依据地址判断此字当前是否在cache中，若是，此字立即传送给cpu；若非，则用主存读取周期把此字从主存读出送到cpu，与此同时，把含有这个字的整个数据库从主存读出送到cache中。

**cache的命中率**

增加cache的目的。就是在性能上使主存的平均读出时间尽可能接近cache的读出时间。因此，cache的命中率应尽量接近于1（100%）。由于程序访问的局限性，这是可能的。在一个程序执行期间，设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率，则有

![20181119115823320.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 1][]

**主存与cache的地址映射**

cache的容量很小，他保存的内容只是主存内容的一个子集，且cache与主存的数据交换是以块为单位。

cpu指令对对存储器进行读写时，指令中的地址是内存系统中**存储器的地址即大地址**

**cache的数据块称为行(L)，设cache共有2^r行，则行地址（行号）有r位**（例：cache有8行即2^3，即行地址有3位）；

主存的数据块称为块(B)，设**主存有2^s块**，则**块地址（块号）有s位**；

注：**行的容量=块的容量**

每个块（行）由若干连续的字(W)组成，字时cpu访问存储器的单位。

**若一个块（行）有2^m个字，即1块（行）=2^m字，则块（行）内字地址有m位。**

所以，**cache的地址位数 = r + m (位)**，即**行地址+字地址**

**内存地址= s + m（位），即块地址+字地址**

![20181119115842372.png][]

显然：由于内存容量大于cache容量，即**内存块地址大于cache行地址**，所以**内存地址要大于cache地址**

主存中的一个块的地址（块号）与块的内容一起存于cache的行中，其中块地址存于cache行的标记部分中

地址映射即是应用某种方法把主存地址定位到cache中；当cpu访问存储器时，它所给的一个字的内存地址会自动变成cache的地址，由于这个变换过程是用硬件实现的，因此地址变换过程速度非常快，软件人员丝毫感觉不到cache的存在。这种特性称为**cache的透明性**。

地址映射方式有**全相联方式**、**直接方式**和**组相联方式**三种 。

**1.全相联方式**

主存中的一个块的地址（块号）与块的内容一起存于cache的行中，其中块地址存于cache行的标记部分中。**全相联映射方式是指主存的一个块直接拷贝到cache中的任意一行上**，非常灵活。

优点：冲突概率小，cache的利用高。

缺点：比较器电路难于实现，适合小容量cache采用。（因为在定位cache行的时候需要将**块地址**与cache中的每一行的行号**即标记位**进行比较，找出命中的那一行，然后对命中的行进行**字地址**的查找，如果找到则直接取出，否则就直接去主存读取）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 2][]

**全相联映射主存地址的划分**：主存总容量64k=2^6\*2^10=2^16=65536，共有256=2^8个块，所以每个块大小为65536/256=256=2^8即每个块大小为2^8，即主存地址=块号地址8位和快内字地址8位组成，共16位；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 3][]

即全相联映射方式中主存地址中对应的**块号**对应于cache中的**标记位.**

**2.直接映射方式**

**一个主存的块只能拷贝到cache中一个特定行位置上去（通过函数映射）**

**cache的行号 i 与主存的块号 j 有如下的函数关系（取余数）：**

**i=j mod m （m为cache中的总行数）**

优点：硬件简单，成本低

缺点：每个主存块只有一个固定的行位置可存放，容易产生冲突。因此适合大容量cache采用

**直接映射主存地址的划分：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 4][]

说明：**主存容量为64K=2^16即内存总共16位地址**，低8位块内字地址，高8位块号（其中高8位块号中，低3位为cache行号，高5位位标记位）

查找过程：首先通过行号定位cache中的行位置，然后进行标记位的比较，最后通过字地址查找值

**3.组相联映射方式**

这种方式是前两种方式的折中方案。它将m行cache分成u组，每组v行，主存块存放到哪个组是固定的（直接映射方式），至于存到该组的哪一行是灵活的（全相联映射方式 ），即有如下函数关系：（m 为cache总行数，j 为内存块号，**q为cache组号**）

**m = u \* v    **

**q= j mod u**

**（每组几行就叫几路组相联，例如4组，每组两行则叫2路组相联）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 5][]

**组相联映射主存地址的划分：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 6][]

说明：内存总共16位，其中低8位为字地址，高8位为快号（其中高8位块号中，低2位cache组号，高6位为标记位）

查找过程：首先通过组号定位到cache所属组，然后比较对应的标记位，最后通过字地址查找值

**替换策略**

cache工作原理要求它尽量保存最新数据，必然存在将有用的信息从主存调进cache中，这样就产生替换。

对于直接映射cache来说，只要把此特定位置上的原主存块替换即可；对于全相联和组相联cache，就要从允许存放新主存块的若干特定行中选取一行换出。常用的替换算法有如下4中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 7][]

**cache的写操作策略**

1.写回法（write back，回写法）

当cpu写cache命中时，只修改cache的内容，而不立即写入主存，只有当此行（块）被替换时才写回主存。这种方法减少了访问主存的次数，但是存在不一致性的隐患。实现这种方法时，每个cache行必须配置一个修改位，以反映此行是否被cpu修改过。

2.全写法（write through，写直达法）

当写cache命中时，cache与主存同时发生写修改，因而较好的维护了cache与主存的内容一致性。

当写cache未命中时，直接向主存进行写入。cache中每行无需设置一个修改位以及相应的判断逻辑。此时是否修将改过的主存块调入cache，有两种方法：一种是调入cache，并分配一行；另一种是不调入cache。

缺点是降低了cache的功效。

3.写一次法

基于写回法并结合全写法的写策略，写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存，这便于维护系统全部cache的一致性。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70]: /images/20220416/f237ead064d74ff3bb585e85a5e53709.png
[20181119115823320.png]: /images/20220416/6c1bacd65a1b4c9dbe9368b3bef930ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 1]: /images/20220416/aedc9f74cf494fdfa8197a058bc791af.png
[20181119115842372.png]: /images/20220416/468d416bbb3a46edbc30bbc0a23df5b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 2]: /images/20220416/ff5e05f376dc48368f2e726d522f7d08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 3]: /images/20220416/fb1de80f53dc40dd8cb9fa079b0cdd46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 4]: /images/20220416/2f4bc941d9034392bfec056dc6083696.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 5]: /images/20220416/260447b475d4474dbc29e51ea2f5a24f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 6]: /images/20220416/d5802316b72c4445afcf6e18d4b7e1ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p3eDE5OTIxMjE1_size_16_color_FFFFFF_t_70 7]: /images/20220416/c06fb26f43a741d0ac82ea77032cfacb.png