处理器基础知识——cache

本文节选自书籍《大话处理器：处理器基础知识读本》
PDF版本可以访问我的网盘通过网盘分享的文件：大话处理器：处理器基础知识读本.pdf 提取码: 1234

0 什么是 Cache

1. 随处可见的Cache–技术来源于生活
   使用电脑的人对 Cachc 并不会陌生，只要在 Windows 下搜索“Cache”，就会找到一大堆命名包括“Cache”的文件和文件夹，系统目录下有，浏览器目录下有，QQ目录下有，PPStream目录下有，迅雷看看目录下有……
   维基百科对 Cache的定义是:它是一个部件，透明地存储了一些数据，当下次需要这些数据时，就能更快的访问到。以迅雷看看为例，在网络上看完一个节目后，节目就存储在本地硬盘上，当下次再看这个节目时，就真接访问硬盘上缓存的内容，而不是从网络上去取,这样获取节目的速度就加快了。“透明”的意思是,用户不需要关心这段数据存在哪。Cache 的思想，并不是计算机专有的，它来源于生活。我们在大学读书时，书都放在宿舍里，今天要上《高数》课，就把《高数》的课本放进书包，明天要上《C语言》，就把书包中的《高数》课本取出来，把《C语言》课本放进书包，这个包就是一个 Cache(缓存)。垃圾篓、旅行包等都可以叫Cache。

1 处理器的 Cache 结构

1.1 Cache 的层次–层次化管理

我们通常会有这样的生活习惯，将最常用的东西放在桌上，这样可以最方便地拿到，将次常用的东西放在抽屉里，也能较快地拿到，将不常用的东西放在箱子里，去箱子里拿东西需要耗一点时间。
这种思想也被用在了Cache中，现在的处理器，都采用多级的Cache 组织形式，来达到性能和功耗的最优。

• 单核处理器大都采用如下的 Cache 结构:
  
  单核处理器通常包含两级Cache:L1Cache和L2 Cache，L表示 Level(级)。在 L1中，程序(Program)和数据(Data)使用各自的缓存(LIP和LID)，而在L2中，程序和数据共用一套缓存。通常 L1空间为几十K，L2空间为几百K。
  当内核需要访问程序或数据时，会先从L1中去取，如果L1中没有，则L1从L2中将数据导入，如果 L2中也没有，则L2从内存中将数据导入。
  L1 通常和内核同频率，以保证速度，L2通常会降频使用，工作频率比内核低，这样能降低功耗。
• 多核处理器大都采用如下的 Cache 结构：
  
  在多核处理器中，一般每个内核独享自己的L1和L2，所有的内核会共用一个大容量的 L3。

1.2 Cache的工作方式——命中与未命中

整个 Cache 空间被分成了N个line，每个line(Cache line)通常是32 byte、64 byte等，Cache line 是 Cache 和内存交换数据的最小单位，每个Cache line 最少会包含如下3部分：

• block中存储的是内存在Cache中缓存的数据
• tag中存储的是该Cacheline 对应的内存块的地址。
• valid 表示该Cache line中的数据是否有效。

下面描述了一个基本的Cache 工作方式，假设处理器只有一级Cache，当内核访问一个数据时，内核首先会在Cache中找，一开始自然找不到，于是就发生了Cachemiss(未命中)，这时内存中的数据被导入到一个Cache line的block中，将地址写到相应的 tag 位置处，并将valid 标志置1。当下一次内核继续访问这个数据时，处理器根据地址在Cache中找到对应的 Cache line，发现 valid 标志为1并且tag 标志也匹配，就知道找到了数据,直接从 Cache 中取这个数据，这个过程叫 Cache hit。

• 当Cache 命中时，内核直接从Cache中取数据，时间通常为几个cycle
• 当 Cache 未命中时，数据需要从内存中导入，时间通常是几十、几百个cycle，极大地拖垮了处理器的性能。

1.3 Cache的映射方式–多对一的策略

由于内存的空间要远远大于Cache的空间，因此内存中的数据搬到Cache 中时，会存在一个多对一的映射。

1. Full-associative Cache(全关联 Cache)
   内存以字节为存储单位，不过由于内存和Cache交换数据的最小单位是一个Cacheline，因此姑且将内存也看成按照 line的方式存储。
   在Full-associativeCache中,内存中的每个1ine能够被映射到Cache中的任意一个Cacheline，如下图:
   

在 32位处理器中，地址线为32bit，如果每个1ine为64byte(6 bit表示)，那么每个Cache line 的tag需要 26bit(32-6=26)。
全关联 Cache 有个缺点，那就是当判断一个数据是不是在 Cache 中时，它需要将地址和所有 Cache line 的tag 进行匹配，成本太高。在实际的处理器中，这种方式很少见。

2. Direct-mapped Cache(直接映射 Cache)
   与Full-associative Cache 不同的是，Direct-mapped Cache 将内存按照 Cache 的大小分成了N个Page，每个Page 和 Cache 大小相同。Page 中的line0只能映射到 Cache 中的 line0，依次类推。
   内存的 Cache Page 示例如下：
   
   假设Cache有4个Cache line，那么 Direct-mapped 的映射方式如下：Direct-mapped 映射方式最直接的一个好处是:随便给一个地址，通过地址就能知道它位于哪个 Cache line 中，这是因为每一个内存地址，都只会映射到唯一一个 Cache line 中。为了 Cache line知道自己存储的是哪个地址处的数据,tag需要记录Page的索引。以C64 DSP的L1P Cache 为例，地址总线为32bit，L1P大小为16Kbyte(14bit 表示 2 的14次方等于 16384 就是16Kyte大小)，每个 Cache line32 byte(5bit 表示)，于是tag需要18bit(32-14)。
   每个 32bit 的地址被分成了3部分:tag用于标识该Cacheline属于哪个Page，line指示该数据应该存储在哪一行Cache中,Ofset表示数据应该存储在Cache line中的哪个位置。下图为C64 DSPL1P Cache中32 bit地址的结构。
   
   使用 Direct-mapped Cache，Cache 控制器要判断一-个数据是否在 Cache 中时，首先根据这个数据的地址提取出TAG(头18bit)和LINE(中间 9bit)，根据 LINE 找到对应的Cache line，如果 Cache line 中的 tag和 TAG 一致，并且 valid 标志为1，那么 Cache 就命中，反之，则未命中。

3. Set-associative Cache(组关联 Cache)
   Direct-mapped Cache要比Full-associative Cache 简单，也是处理器上比较常用的方式不过 Direct-mapped Cache 在很多情况下会有很大的缺陷。
   以下面这段程序为例子：

for (i=0;i<10;i++ )
{c += a[i] + b[i];

假设 Cachc 只有4个Cache line,数组a存储在内存的line0,数组b存储在内存的 line4，则 Cache 访问过程如下：
(1)CPU 访问 a[0]，Cache miss,数组a从内存中被搬移到Cache line0中。(2)CPU访问 b[0]，Cache miss,数组b从内存中被搬移到 Cache line0中。
(3)CPU访问 af1]，Cache miss,数组a从内存中被搬移到 Cache line0中。
(4)CPU 访问 b1]，Cache miss,数组 b从内存中被搬移到 Cache linc0中。
(5)…
由于a和b都映射到Cache line0，每次访问数据都发生Cache miss，严重影响效率。

在上面的这个例子中，Cache line1、Cache line 2、Cache line3 都浪费了，而 Cache line0却冲突严重。其实 Full-associative Cache 可以解决这个问题，因为内存中的每个 1ine 都可以映射到任意 Cache line 中，从这个角度来看，Full-associative Cache 效率最高，但是由于查找复杂，所以很少使用。而商用的处理器都使用 Set-associative Cache 来解决这个问题。

Set-associative Cache将Cache 分成了多个way(份)，如下图所示:

Cache way1和 Cache way0是完全相同的结构，访问a时,a被 Cache 到 way0 的 line0中，访问b时，发现way0的line0已经被使用了，就将b缓存到way1的 line0中，这样就解决了上面的冲突问题。数组a和b的访问只在第一次访问 a[0]和 b[0]时需要从内存导入，其他的时候都能直接从 Cache 中取数。

Direct-mapped Cache等同于1-way Set associative Cache。
在相同 Cache 容量下，Cache way越多，则每个 Cache way 的容量就越少。Cache way的增多会减少 Cache miss，但是 Cache way 容量的减小，又会增加 Cache miss。Cache way越多，Cache 的硬件结构也越复杂，功耗也越高。不同的处理器都会根据自己的应用来设定最佳的 Cache way 数目、每个 Cache way 的容量。

在TI的c64+ DSP 内核中，L1P使用1wayCache，LID使用2way Cache，L2 不区分程序和数据，使用4wayCache。x86CPU使用更多的Cache way。

• 置换策略
  Cache 的容量毕竟有限，Cachc way也有用完的时候，当Cache way用完时，再来数据就要替换其中的一个了，那么替换哪个呢?
  常用的替换策略有:
  (1)随机(Random)，随便找个替换。
  (2)先进先出(FirstInFirstOut，FIFO)，最早被使用的那个 way 被替换。(3)最近最少被使用(LeastRecentlyUsed,LRU)，替换最近最少被使用的那个 way。在这几种策略中，LRU性能最好，LRU基于Cache的时间相关性，刚刚被访问的数据很有可能继续被访问，很久都没有被访问的数据则很可能就不会被访问了。

1.4 Cache的写方式

前面只提到了Cache 的读方式，当CPU修改了Cache 中的数据，内存中的数据需不需要跟着改变呢?
Cache 提供了两种写策略。

1. Write through(写通)
   Write through 策略是指每次 CPU修改了Cache 中的内容,Cache 立即更新内存的内容
   
   在上面的这个例子中，内核读入了变量x，它的值为3，不久后内核将x改成5，内核修改的是 Cache 中的数据，当 Cache 采用 Write through 略时，Cache 控制器将x的值更新到内存中。

2. Write back(写回)
   Write back 策略是指内核修改 Cache 的内容后，Cache 并不会立即更新内存中的内容,而是等到这个Cache line因为某种原因需要从Cache中移除时,Cache才更新内存中的数据例如，Cache的1ine0已经存储了内存line0的数据，内核想修改地址在内存line0中的变量，它实际上修改的是Cache line0中的数据，当内核访问内存1ine4时，这块数据也需要使用 Cache line0，这时 Cache 控制器会先将Cacheline0的内容更新到内存的line 0，然后再将 Cache line0作为内存1ine4的缓存。内存1ine0在很长时间内存储的都不是最新的数据，不过这并不影响程序的正确性。
   

在上面的这个例子中，内核修改了x，但是x并没有被更新到内存中Write through(写通)由于有大量的访问内存的操作，效率较低，大多数处理器都使用 Write back(写回)策略。
Cache 怎么知道这行的数据有没有被修改呢?这就需要新增一个标志—dirty 标志。dirty 标志为 1，表示 Cache 的内容被修改，和内存的内容不一致，当该Cacbe line 被移除时，数据需要被更新到内存，dinty标志位为0(称为clean)，表示Cache 的内容和内存的内容一致。
下图为增加了 dinty 标志的 Cache 结构:

程序 Cache 不会被修改，不需要 dirty 标志，数据 Cache 需要 dirty 标志。

2 Cache 一致性

2.1一致性问题的产生——信息不对称导致的问题

现实生活中常常会出现因为沟通不畅而导致的扯皮，一方改变了某些东西，又没有及时通知到另一方，导致两方掌握的信息不一致，这就是一致性问题。多核处理器也有这样的问题，在下面这个简单的多核处理器示例中，内存中有一个数据x，它的值为3，它被缓存到Core0和Core1中，不过Core0将x改为5，如果 Core 1不知道x已经被修改了，还在使用旧的值，就会导致程序出错，这就是Cachc 的不一致。

2.2 Cache 一致性的底层操作

为了保证 Cache的一致性，处理器提供了两个保证Cache致性的底层操作:Writeinvalidate 和 Write update 。

• Write invalidate(置无效):当一个内核修改了一份数据，其他内核上如果有这份数据的复制，就置成无效(invalid)。
  在下面的这个例子中，3个Core都使用了内存中的变量x，Core0将它修改为5，其他Core 就将自己对应的Cache line置成无效(invalid)。
  

• Write update(写更新):当一个内核修改了一份数据，其他地方如果有这份数据的复制，就都更新到最新值。Write update
  示例如下:
  

Write invalidate 和 Write update 比较:Write invalidate 是–种很简单的方式，不需要更新数据，如果Core1和Core2以后不再使用变量x，这时候采用 Write invalidate 就非常有效。不过由于一个 valid 标志对应一个 Cache line,将 valid 标志置成invalid 后，这个 Cacheline 中其他的本来有效的数据也不能被使用了。Write update 策略会产生大量的数据更新操作，不过只用更新修改的数据，如果Core1和Core2会使用变量x，那么 Write update 就比较有效。由于 Write invalidate 简单，大多数处理器都使用== Write invalidate 策略==。

2.3 Cache一致性协议

Write invalidate 提供了实现 Cache 一致性的简单思想，处理器上会有一套完整的协议，来保证 Cache 一致性。比较经典的Cache一致性协议当属MESI协议，奔腾处理器有使用它，很多其他的处理器都是使用它的变种。
前面介绍的 Cache 中每个 Cache line 有两个标志:dinty和 valid 标志，它们很好的描述了Cache和 Memory(内存)之间的数据关系(数据是否有效、数据是否被修改)，而在多核处理器中，多个核会共享一些数据，MESI协议就包含了描述共享的状态。
在MESI协议中，每个Cacheline有4个状态，可用两个bit 表示，它们分别是:

状态	描述
M(Modified)	这行数据有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中
E(Exclusive)	这行数据有效，数据和内存中的数据一致，数据只存在于本Cache中
S(Shared)	这行数据有效，数据和内存中的数据一致，数据存在于很多Cache中
I(Invalid)	这行数据无效

M(Modified)和E(Excusive)状态的Cacheline，数据是独有的，不同点在于M状态的数据是 dirty的(和内存的不一致)，E状态的数据是 clean 的(和内存的一致)。
S(Shared)状态的 Cache line，数据和其他的 Cache 共享。只有 clean 的数据才能被多个 Cache 共享。
I(Invalid)表示这个Cache line 无效。
E状态示例如下:
只有Core0访问变量x，它的Cache line状态为E(Exclusive)。

S 状态示例如下:
3个Core都访问变量x，它们对应的Cacheline为S(Shared)状态。
M 状态和1状态示例如下:

Core0修改了x的值之后，这个Cache line变成了M(Modified)状态，其他 Core 对应的Cache line 变成了I(Invalid))状态。在 MESI协议中，每个Cache 的 Cache 控制器不仅知道自己的读写操作，而且也监听(snoop)其他Cache的读写操作。每个Cache line所处的状态根据本核和其他核的读写操作在4个状态间进行迁移。MESI协议状态迁移图如下：

在上图中,LocalRead表示本内核读本Cache中的值,Local Write表示本内核写本Cache中的值，Remote Read 表示其他内核读其他Cache 中的值，Remote Write 表示其他内核写其他 Cache 中的值，箭头表示本 Cache line 状态的迁移，环形箭头表示状态不变当内核需要访问的数据不在本Cache中,而其他 Cache有这份数据的备份时,本 Cache既可以从内存中导入数据，也可以从其他Cache中导入数据，不同的处理器会有不同的选择。MESI协议为了使自己更加通用，没有定义这些细节，只定义了状态之间的迁移。

3 片内可寻址存储器——软件管理的Cache

在 x86 处理器中，处理器内部的存储器全部作为Cache 使用，不纳入存储空间的编址Cache 对程序员是透明的，Cache完全由处理器硬件来管理，程序员不需要关心Cache，编程也简单。
而在 DSP等性能要求很高的嵌入式处理器中,处理器内部的存储器一部分作为Cache;另一部分作为可寻址存储器，程序员可直接访问这部分空间。

为什么在处理器内部需要可寻址存储器呢?因为Cache miss 是不可避免的，当发生 Cache miss 时，处理器要花大量的时间等待数据，而可寻址存储器可以由程序员自己管理，也就可以有效地控制数据 miss。

有3个原因会导致Cachemiss:
Compulsory(必须的)miss，第一次访问程序或数据时，这些数据没有在Cache中于是就导致了 Cache miss。这种 Cache miss是不可避免的，因此叫做Compulsory miss。
Capacity(容量)miss，Cache容量毕竞有限，当Cache已满，新数据又要进来，就必须重新搬移，这就叫做 Capacity miss。
Conflict(冲突)miss,有时候 Cache虽然还有空闲空间,但是这个地址对应的 Cache line已经被使用了，也会导致Cachemiss，这就叫做Conflict miss。

Cache 要等到CPU 访问数据时，才从内存中将数据取进来，而此时CPU能等待。如果处理器内部有了可寻址存储器，就可以通过软件控制 DMA(DirectMemory Access)将以后需要的数据提前搬到处理器内部,这就省去了不少CPU的等待时间。DMA 是处理器中专业负责数据搬移的模块。

在上面的这个例子中，程序知道 CPU什么时候要访问数组x,于是通过控制 DMA 提前搬移数据,而 Cache 不知道它没法提前搬。因此使用 DMA的方式，程序总的执行时间要比使用Cache的方式少。DMA 的任务就是快速的搬移数据，而数据的组织形式千差万别。例如，在多媒体领域，语音数据通常采用一维数组的形式存储，图像数据采用二维数组来存储，彩色图像包含多个分量(如RGB、YCbCr等)，各个分量又独立存储。DSP的DMA 也相应提供了 1D、2D、3D 的数据搬移方式，如下图所示:

1D方式搬运一块连续地址的空间，2D方式可看作由多个规则的1D方式组合而成，完成一个 1D操作后，地址加上一个固定偏移，继续下一个 1D操作，3D 搬移也就是多个规则的 2D 搬移。
使用 DMA 程序的效率较高，不过程序员不仅要关注代码和数据的逻辑关系，还要关心代码和数据的存储位置，这对程序员来说，是一个不小的挑战。通用处理器为了简化编程难度，通常只提供 Cache 这一种方式，DSP 对程序性能要求很高，通常提供了Cache 和DMA 的组合方式。
现在的处理器认识到传统Cache的缺陷,于是也产生了很多 Cache预取机制,如当CPU在访问本行数据时，自动取下一行的Cache 数据。处理器也提供了指令让程序员更灵活地控制 Cache，以提高程序的效率。