「cache」计算机体系结构之cache

cache

cache电路
cache模型
cache算法
与cache相关的系统调用

0 cache简介

高速缓存（cache）是cpu内部用来加快数据访问的缓存技术。高速缓存属于SRAM，主存储器属于DRAM，一般而言主存储器一般称内存，后续我们使用内存称呼主存储器。

对于计算机程序而言，cache的存在是透明的，采用通俗的语言描述就是在程序中可能找不到与cache相关的代码，几乎在访问内存的数据时都用到了cache，当然前提条件是CPU硬件上有cache，其中与cache相关的流程已经硬件设计完成了，因此在软件上是透明的。

1 cache外部模型

1.1 计算机存储模型

在对cache模型进行描述前，不得不首先介绍一下计算机的存储层次模型，在计算机存储层次结构中，一般将内存分成好几个层次，计算机多处用到缓存的思想，不仅仅cache是内存的缓存，此外可以将内存视为磁盘的缓存，磁盘可以视为远程网络资源的缓存，计算机存储层次模型如下：

寄存器
L1 icache和L1 dcache（数据cache和指令cache）
L2 cache
L3 cache
主存储器
磁盘
远程网络资源

其中CPU访问其中的数据速率从寄存器到远程资源逐渐下降，可以从下图看出CPU对cache和内存的访问时钟周期，对于CPU内部的寄存器，一般用于存储程序中局部变量，其访问时间大概为一个时钟周期，可想而知对于一个时钟为4GHz的CPU其一个时钟周期有多快。下图可能有些不足，没有说明磁盘的访问时间，这里补充说明一下：一般而言，CPU访问磁盘的时间大约在秒级左右。

此图来源于/d/file/news/20190605/latency.png

有些关于存储的参考书，直接将“网络”的思想引入到计算机的存储层次模型中，他们将各存储看成是网络中的节点，他们之间的物理关系变形成了网络拓扑。大到计算机与计算机之间形成网络拓扑，小到计算机内部各设备连接形成网络拓扑，再小到CPU内部存储之间形成网络拓扑等等，从这个角度看待计算机cache可能会得到新的体会。

目前，大多数处理器包括三级cache（L1-3），例如Intel core-i7有四个核，其中四个核共享一个L3 cache，L1 cache和L2 cache是每个核私有的，下面对Intel core-i7包含的cache进行了整理，如下：

一个L3 cache
四个L2cache
四个L1 icache
四个L1 dcache

为了验证以上结论，使用cpu-z对一台Intel core i7进行测试，其结果如下：

在这里插入图片描述

从图中可以看出，core i7第七代有6MBytes的L3 cache一个、256KBytes的L2 cache四个等等。将其画成框图如下，其中只画出了其中一个核的关系图，紫色部分为一个核。

本文在对cache相关技术进行研究时，采用一级cache进行说明，上图只是更好的说明cache完备的模型。

1.2 cache内部结构

上一节关于cache与其他元件的连接关系，以及cache访问速率等。接下来，进入到cache本身内部相关的技术，例如cache内部访问时路、组和标记相关的概念，cache本质是一个缓冲存储器，也会存在读写操作，那么cache的读写操作有什么玄机吗？先展示一张cache内部图，一个cache结构分成路、组和数据，根据路和组的映射关系，可以将其分为直接映射、全相联映射、组相联映射三种。　

1.2.1 地址映射

所谓映射是指如何确定cache中的内容是主存中的哪一部分的拷贝，即必须应用某种函数把主存地址映射到cache中定位，也称地址映射。当信息按这种方式装入cache中后，执行程序时，应将主存地址变换为cache地址，这个变换过程叫作地址变换。下面对三种映射进行简介，可结合上图进行理解。

直接映射
一个路只有一组，有多路，每个主存地址映射到cache中的一个指定地址的方式，称为直接映象方式。在直接映象方式下，主存中存储单元的数据只可调入cache中的一个位置，如果主存中另一个存储单元的数据也要调入该位置则将发生冲突。地址映像的方法一般是将主存空间按cache的尺寸分区，每区内相同的块号映像到cache中相同的块位置。一般地，cache被分为2N块，主存被分为同样大小的2M块，主存与cache中块的对应关系可用如下映像函数表示：j = i mod 2N。式中，j是cache中的块号，i是主存中的块号。
直接映射是一种最简单的地址映像方式，它的地址变换速度快，而且不涉及其他两种映像方式中的替换策略问题。但是这种方式的块冲突概率较高，当称序往返访问两个相互冲突的块中的数据时，cache的命中率将急剧下降，因为这时即使cache中有其他空闲块，也因为固定的地址映像关系而无法应用。
组相联映射
一路对应多个组，有多路。组相联映射方式是直接映射和全相联映射的一种折衷方案。这种方法将存储空间分为若干组，各组之间是直接映射，而组内各块之间则是全相联映射。它是上述两种映像方式的一般形式，如果组的大小为1，即cache空间分为2N组，就变为直接映射；如果组的大小为cache整个的尺寸，就变为了全相联映射。组相联方式在判断块命中及替换算法上都要比全相联方式简单，块冲突的概率比直接映像的低，其命中率也介于直接映射和全相联映射方式之间。
全相联映射
所有的组都在一路下，只有一路，主存中的每一个字块可映射到cache任何一个字块位置上，这种方式称为全相联映射。这种方式只有当cache中的块全部装满后才会出现块冲突，所以块冲突的概率低，可达到很高的cache命中率；但实现很复杂。当访问一个块中的数据时，块地址要与cache块表中的所有地址标记进行比较已确定是否命中。在数据块调入时存在着一个比较复杂的替换问题，即决定将数据块调入cache中什么位置，将cache中那一块数据调出主存。为了达到较高的速度，全部比较和替换都要用硬件实现。

1.2.2 替换策略和一致性问题的处理方法

cache和存储器一样具有两种基本操作，即读操作和写操作。当CPU发出读操作命令时，根据它产生的主存地址分为两种情形：

一种是需要的数据已在cache中，那么只需直接访问cache，从对应单元中读取信息到数据总线；
另一种是需要的数据尚未装入cache，CPU需从主存中读取信息的同时，cache替换部件把该地址所在的那块存储内容从主存拷贝到cache中；若cache中相应位置已被字块占满，就必须去掉旧的字块。

常见的替换策略有两种：

先进先出策略（FIFO）
FIFO（First In First Out）策略总是把最先调入的cache字块替换出去，它不需要随时记录各个字块的使用情况，较容易实现；缺点是经常使用的块，如一个包含循环程序的块也可能由于它是最早的块而被替换掉。
最近最少使用策略（LRU）
LRU（least recently Used）策略是把当前近期cache中使用次数最少的那块信息块替换出去，这种替换算法需要随时记录Cache中字块的使用情况。LRU的平均命中率比 FIFO高，在组相联映像方式中，当分组容量加大时，LRU的命中率也会提高。

当CPU发出写操作命令时，也要根据它产生的主存地址分为两种情形：一种是不命中时，只向主存写入信息，不必同时把这个地址单元所在的整块内容调入cache中；另一种是命中时，这时会遇到如何保持cache与主存的一致性问题，通常有三种处理方式：

直写式（write through）
即CPU在向cache写入数据的同时，也把数据写入主存以保证cache和主存中相应单元数据的一致性，其特点是简单可靠，但由于CPU每次更新时都要对主存写入，速度必然受影响。
缓写式（post write）
即CPU在更新cache时不直接更新主存中的数据，而是把更新的数据送入一个缓存器暂存，在适当的时候再把缓存器中的内容写入主存。在这种方式下，CPU不必等待主存写入而造成的时延，在一定程度上提高了速度，但由于缓存器只有有限的容量，只能锁存一次写入的数据，如果是连续写入，CPU仍需要等待。
回写式（write back）
即CPU只向cache写入，并用标记加以注明，直到cache中被写过的块要被进入的信息块取代时，才一次写入主存。这种方式考虑到写入的往往是中间结果，每次写入主存速度慢而且不必要。其特点是速度快，避免了不必要的冗余写操作，但结构上较复杂。

此外，还有一种设置不可cache区（Non－cacheable Block）的方式，即在主存中开辟一块区域，该区域中的数据不受cache控制器的管理，不能调入cache，CPU只能直接读写该区域的内容。由于该区域不与cache发生关系，也就不存在数据不一致性问题。目前微机系统的BiOS设置程序大多允许用户设置不可cache区的首地址和大小。

1.3 情景分析

上一节重点介绍cache在电路上与CPU、主存以及总线、I/O设备之间的物理关系，本小节将重点放在从代码级上思考cache对程序的影响。

首先考虑一个程序存在时间和空间上的局部特性，具有良好局部特性的程序能大大提高执行效率，例如体现在执行完成的时间上。其局部特性与cache有重要的关系。在探讨普通应用程序与cache的关联之前，我们必须了解什么是程序的"局部性原理"

程序运行有以下3个特点：

时间局部性：如果一个数据/指令正在被访问，那么在近期它很可能还会被再次访问
空间局部性：在最近的将来将用到的信息很可能与正在使用的信息在空间地址上是临近的
顺序局部性：在典型程序中，除转移类指令外，大部分指令是顺序进行的

考虑这么一段程序：

#include <stdio.h>

int main(int argc,char *argv[])
{
	/* 对array[][]二维数组进行按“行”赋值操作 */
	int array[10][10]={0};
	int i=0,j=0;
	for(i=0;i<10;i++){
		for(j=0;j<10;j++){
			array[i][j] = 1;
		}
	}
	retuen 0;
}

对于C语言来说，从内存角度，对一个数组存储的时，一般按照“行”对array中的数据进行存储，简而言之，属于同一行的元素之间在内存中的地址是相邻的，上一行的最后一个元素与下一行的第一个元素是邻接的，因此，在对array进行访问时，按照“行”对于上面这段程序具有良好的空间局部特性。

在CPU要对内存进行数据访问时，需要查看访问的数据是否在cache中：

如果在，称为命中，
如果不在，称为缺失

以下图作为研究对象。

当CPU需要读或写一个主存储器上的数据时，CPU需要发出一个地址，从硬件的角度看，硬件会先使用该地址检查是否在cache中有缓存，命中或者缺失。那么这个地址有两种可能：一是虚拟地址，没有经过MMU转换成物理地址；二是物理地址，已经由MMU转换完。对于这两种硬件上不同的设计，存在两种高速缓存：虚拟高速缓存和物理高速缓存，下面就对两种缓存展开。

计算机体系结构之cache

cache

0 cache简介

1 cache外部模型

1.1 计算机存储模型

1.2 cache内部结构

1.2.1 地址映射

1.2.2 替换策略和一致性问题的处理方法

1.3 情景分析

相关阅读

栏目导航

推荐阅读

热门阅读