Cache 浅学（二）

梦里梦外; 2023-03-04 11:30 70阅读 0赞

# Cache 浅学（二） #

## 1 L1 memory system ##

### 1.1 L1 概述 ###

L1存储系统由单独的指令和数据高速缓存组成。 您可以在实现期间分别将指令和数据缓存配置为8KB，16KB，32KB或64KB。  
L1内存系统具有一个存储缓冲区，该缓冲区具有四个具有数据合并功能的64位插槽，可以处理对设备，强序存储，可缓存和不可缓存的写入。  
L1指令存储系统具有以下功能：

•指令侧高速缓存行长度为32字节。
    •虚拟索引和物理标记的指令缓存。
    •伪随机缓存替换策略。
    •2路组关联指令缓存。
    •支持四种大小的内存页面。
    •导出外部存储系统的存储属性。
    •支持安全扩展。
    •可以使用系统控制协处理器独立禁用。 
    •在高速缓存未命中时，执行高速缓存的关键词优先填充。

L1数据存储系统具有以下功能：

•数据侧缓存行长度为64字节。
    •物理索引和物理标记的数据缓存。
    •伪随机缓存替换策略。
    •4路组关联数据缓存。
    •两个32字节的换行缓冲区和一个64字节的逐出缓冲区。
    •4条目64位合并存储缓冲区。
    •可以使用系统控制协处理器独立禁用。 请参阅系统控制
    •在高速缓存未命中时，将执行高速缓存中的关键单词优先填充。

### 1.2 Cache behaviour ###

您可以独立禁用每个缓存。在高速缓存未命中时，将执行高速缓存的关键字优先填充。  
如果缓存报告内存标记为“不可缓存”，“设备”或“强排序”的内存位置命中，则称为意外缓存命中。 在这种架构上无法预测的情况下，缓存可能返回错误的数据。 由于缓存是物理寻址的，因此不正确的页表配置是创建此方案的唯一方法。

#### 1.2.1 Data cache disable behavior ####

SACTLR.C位在ACTLR.SMP为1时启用或禁用L1数据和统一缓存。如果在处理器加电和断电过程中ACTLR.SMP为0，则无论SCTLR.C位设置如何，都将禁用高速缓存。  
禁用L1数据和统一缓存后，可缓存的加载将照常进行，并将查找存储在缓存中。 在L1数据高速缓存命中时，将像启用L1数据高速缓存一样进行加载或存储。 在L1数据高速缓存未命中时，不会将高速缓存行分配到L1数据高速缓存中。 在L1数据和统一缓存中都丢失的可缓存负载在ACE主接口上发出ReadOnce或ReadNoSnoop事务。  
如果禁用了L1数据和统一缓存，则缓存维护操作仍可以正常执行。

#### 1.2.2 Instruction cache disabled behavior ####

SCTLR.I位启用或禁用L1指令缓存。 如果禁用了I位，则访存将无法访问任何指令高速缓存阵列。 CP15指令高速缓存操作是该规则的一个例外。 如果禁用了指令缓存，则指令缓存维护操作仍可以正常执行。

#### 1.2.3 Instruction cache speculative memory accesses ####

一条指令保留在访存和执行阶段之间的流水线中。 因为管道中可能有几个未解决的分支，所以指令提取是推测性的，这意味着无法保证它们会被执行。 代码流中的分支或特殊指令可能导致流水线刷新，从而丢弃当前获取的指令。  
由于积极的预取行为，因此不能将对读取敏感的设备与代码放在同一页中。 具有“设备”或“顺序排列”的内存类型属性的页面被视为“不可缓存的普通内存”。 您必须使用TLB XN（“从不执行”）属性位标记包含敏感设备的页面。  
为了避免在禁用地址转换时对读取敏感设备进行推测性获取，必须在物理内存映射中将这些获取的设备和代码分开。 有关更多信息，请参见《 ARM体系结构参考手册》。

### 1.3 L1 instruction memory system ###

L1指令侧存储系统负责向Cortex-A7 MPCore处理器提供指令流。 提高整体性能并降低功耗  
消费，它包含以下功能：

•动态分支预测
    •指令缓存。

指令端包括以下内容：  
**Prefetch Unit (PFU)**  
PFU实现了两级预测机制，包括以下内容：

•256个条目的分支模式历史记录表。
    •4项BTIC。
    •8项BTAC。
    •8入口返回堆栈。

预测方案在ARM状态，Thumb状态和ThumbEE状态下可用。 它还能够预测从ARM到Thumb以及从Thumb到ARM的状态变化。 它不会预测任何其他状态更改或任何更改处理器模式的指令。 请参阅程序流预测。

**Instruction Cache Controller**  
指令高速缓存控制器根据PFU预测的程序流从内存中获取指令。  
指令高速缓存是2路集关联的。 它包含以下功能：

•可配置的大小为8KB，16KB，32KB或64KB。
    •虚拟索引的物理标记（VIPT）。
    •64位本机访问，每个周期最多可向PFU提供4条指令。
    •安全扩展支持。
    •不支持锁定。

#### 1.3.1 Enabling program flow prediction ####

通过将SCTLR.M位设置为1来启用MMU时，始终会启用程序流预测。

#### 1.3.2 Program flow prediction ####

Predicted and non-predicted instructions  
本节显示处理器预测的指令。 除非另有说明，否则该列表适用于ARM和Thumb指令。 通常，流预测硬件会预测所有分支指令，而与寻址模式无关，包括：

•条件分支。
    •无条件分支。
    •与函数调用和返回指令关联的间接分支。
    •在ARM和Thumb状态之间切换的分支。

但是，无法预测某些分支指令：

•PC目标数据处理操作。
    •带有S后缀的指令是无法预测的，因为它们通常用于从异常返回，并且具有可以更改特权模式和安全状态的副作用。
    •所有模式更改说明。

**Thumb state conditional branches**  
在Thumb状态下，可以通过包含在If-Then（IT）块中来使通常被编码为无条件的分支成为有条件的。 然后将其视为正常的条件分支。

**Return stack predictions**  
返回堆栈在函数调用类型分支指令之后存储指令的地址和ARM或Thumb状态。 该地址等于r14中存储的链接寄存器值。 如果预测到以下指令，则会导致返回堆栈压入：

• BL immediate.
    • BLX immediate.
    • BLX register.

如果预测到以下说明，则会导致返回堆栈弹出：

• BX r14 .
    • POP { …,pc} .
    • LDR pc, [r13]

LDR指令可以使用任何寻址模式，只要r13是基址寄存器即可。  
由于异常返回指令可以更改处理器特权模式和安全状态，因此无法预测它们。 这包括LDM R, \{… ,pc\}^ instruction, RFE , and the MOVS pc, r14 instruction。

### 1.4 L1 data memory system ###

L1数据缓存被组织为物理索引和物理标记的缓存。 Micro TLB在执行高速缓存访问之前从虚拟地址生成物理地址。

#### 1.4.1 Internal exclusive monitor ####

Cortex-A7 MPCore L1内存系统具有一个内部专用监视器。 这是一个两个状态的，开放且互斥的状态机，用于管理加载/存储互斥（LDREXB，LDREXH，LDREX，LDREXD，STREXB，STREXH，STREX和STREXD）访问并清除互斥（CLREX）指令。 您可以使用这些指令来构造信号量，以确保处理器上运行的不同进程之间以及信号量使用相同一致内存位置的不同处理器之间的同步。 Load-Exclusive指令标记一小块内存以进行独占访问。 被标记的块的大小由CTR.ERG定义为16个字，一条缓存行。  
导致将ARLOCK \[0\]设置为1的事务的Load-Exclusive指令预期会收到EXOKAY响应。 对ARLOCK \[0\]设置为1的事务的OKAY响应表示，在该事务的地址处不支持互斥访问，并导致进行精确中止。 如果内存属性为：加载专用指令使ARLOCK \[0\]设置为1：

•内部不可缓存，外部不可缓存。
    •设备或有序订购。
    •内部写回和外部共享以及BROADCASTOUTER设置为1。
    •内部直写和外部共享以及BROADCASTOUTER设置为1。
    •外部写回和外部共享以及BROADCASTOUTER设置为1。
    •外部可写和外部可共享以及BROADCASTOUTER设置为1。
    •内部写回和内部共享以及BROADCASTINNER设置为1。
    •内部直写和内部共享以及BROADCASTINNER设置为1。
    •外部写回和内部共享以及BROADCASTINNER设置为1。
    •外部可写通过和内部可共享以及BROADCASTINNER设置为1。

如果ACTLR.SMP位清零，则“负载独占”指令也可能会精确终止。  
有关这些指令的更多信息，请参见《 ARM体系结构参考手册》。  
Treatment of intervening STR operations  
如果LDREX / STREX代码序列中有中间STR操作，则中间STR不会对内部专用监视器产生任何直接影响。 本地监视器在LDREX之后处于独占访问状态，在STR之后仍处于独占访问状态，并且仅在STREX之后才返回到Open Access状态。  
但是，如果地址LDREX / STREX代码序列在可缓存内存中，则包含该地址的缓存行的任何驱逐都会清除监视器。 因此，建议不要在LDREX和STREX之间放置任何加载或存储指令，因为这些附加指令会导致缓存被逐出。 任何数据高速缓存维护指令也可以清除独占监视器。

#### 1.4.2 ACE transactions ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70]

### 1.5 Data prefetching ###

#### 1.5.1 PLD and PLDW instructions ####

PLD和PLDW指令在高速缓存中查找，如果未命中并到达可高速缓存的地址，则开始换行。 但是，PLD或PLDW指令在其换行开始后立即退休，而不是等待数据返回，这使其他指令可以在换行继续在后台运行的同时执行。 如果内存类型是可共享的，则任何由PLDW指令启动的换行都会使数据在其他处理器中无效，以便准备写入该行。

#### 1.5.2 Data prefetching and monitoring ####

Cortex-A7 MPCore数据高速缓存实现了一个自动预取器，可以监视处理器中的高速缓存未命中。 当检测到图案时，自动预取器将在后台开始换行。 预取器以固定的步幅模式识别三个数据高速缓存未命中的序列，该步幅位于四个高速缓存行中（正负）。 有时，在将数据分配到缓存之前，可能会删除这些换行符。 数据高速缓存中命中的任何中间存储或装入都不会干扰高速缓存未命中模式的识别。 可以使用CP15辅助控制寄存器位在软件中将其禁用。  
使用PLD指令进行数据预取时，需要短序列或不规则的模式获取。

### 1.6 Direct access to internal memory ###

Cortex-A7 MPCore处理器提供了一种通过系统协处理器接口的实现定义的区域来读取Cache和TLB结构使用的内部存储器的机制。 当调查缓存中的数据与系统内存中的数据之间的一致性中断的问题时，此功能很有用。 使用许多只写CP15寄存器选择合适的存储块和位置，并从只读CP15寄存器中读取数据，如表6-2所示。 这些操作仅在安全特权模式下可用。 在所有其他模式下，执行CP15指令都会导致未定义指令异常。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 1]

#### 1.6.1 Data cache tag and data encoding ####

Cortex-A7 MPCore处理器数据高速缓存由4路集关联结构组成。 每种方式下的集合数取决于缓存的配置大小。 表6-3中显示了在适当的MCR指令中Rd中设置的编码，该编码用于查找所需的标记和数据存储器缓存数据条目。 标签访问和数据RAM访问都非常相似。 数据RAM访问包括一个附加字段，用于在高速缓存行中定位适当的双字。  
设定索引范围参数（S）由以下方式确定：  
![在这里插入图片描述][20200803172230511.png]

数据高速缓存读取数据寄存器0和数据寄存器1中返回的64位数据。使用数据寄存器0和数据寄存器1，使用所示格式返回所选缓存行的标签信息，MOESI一致性状态，外部属性和有效信息。 在表6-4中。Cortex-A7 MPCore处理器跨Data Register 0和Data Register 1的两个字段对4位MOESI相干状态进行编码。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 2]

#### 1.6.2 Instruction cache tag and data encoding ####

Cortex-A7 MPCore处理器指令高速缓存与数据高速缓存明显不同，这在用于访问标签和数据存储器的CP15操作中使用的编码和数据格式中得到了证明。 表6-5显示了选择给定高速缓存行所需的编码。设定索引范围参数（S）由以下方式确定：

S = log 2 (Instruction cache size (Byte) / 2*32)) for the 2-way set-associative cache.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 3]

表6-6显示了仅使用Data register 0的所选高速缓存行的标记和有效位格式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 4]

CP15指令高速缓存数据读取操作从Data register 0和Data register 1中的高速缓存返回两个条目，它们对应于高速缓存行中的16位对齐偏移量：

Data Register 0  Bits[17:0] data from cache offset+  0b00 .
    Data Register 1  Bits[17:0] data from cache offset+  0b10.

在ARM模式下，这两个字段组合始终代表一条指令。 在Thumb中，它们可以表示16位指令和部分或完整32位指令的任意组合。  
CP15数据高速缓存数据读取操作从Data register0和Data register1中的高速缓存返回两个条目，对应于高速缓存行中的16位对齐偏移量：

Data Register 0  Bits[31:0] data from cache offset+  0b000 .
    Data Register 1  Bits[31:0] data from cache offset+  0b100.

#### 1.6.3 TLB RAM accesses ####

Cortex-A7 MPCore处理器统一的TLB是基于2路集相关RAM的结构构建的。 要将单个条目读入数据寄存器，软件必须写入TLB数据读操作寄存器。 表6-7显示了写TLB数据读操作寄存器位置编码。  
![在这里插入图片描述][20200803172343143.png]

TLB RAM包含主TLB，漫游缓存和中间物理地址（IPA）缓存RAM的数据。 表6-8显示了用于确定TLB RAM访问格式的TLB索引。  
![在这里插入图片描述][20200803172355520.png]

Table 6-9 shows the data fields in the TLB descriptor.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 7]

**Walk cache RAM**  
The walk cache RAM uses a 86-bit encoding. Table 6-10 shows the data fields in the Walk cache descriptor.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][20200803172455426.png]

**IPA cache RAM**  
The Intermediate Physical Address (IPA) cache RAM uses a 86-bit encoding. Table 6-10 on page 6-14 shows the data fields in the IPA cache descriptor

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 9]

## 2 cache memory架构 ##

### 2.1 cortex A7 cache架构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 10]

在Cortex-A7架构上，L1 cache分为单独的instruction cache（ICache）和data cache（DCache）。L1 cache是CPU私有的，每个CPU都有一个L1 cache。一个cluster 内的所有CPU共享一个L2 cache，L2 cache不区分指令和数据，都可以缓存。L2 cache通过总线和主存相连。

### 2.2 Cortex A53 cache架构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 11]

在Cortex-A53架构上，L1 cache分为单独的instruction cache（ICache）和data cache（DCache）。L1 cache是CPU私有的，每个CPU都有一个L1 cache。一个cluster 内的所有CPU共享一个L2 cache，L2 cache不区分指令和数据，都可以缓存。所有cluster之间共享L3 cache。L3 cache通过总线和主存相连。

### 2.3 多级cache之间的配合工作 ###

首先引入两个名词概念，命中和缺失。 CPU要访问的数据在cache中有缓存，称为“命中” (hit)，反之则称为“缺失” (miss)。多级cache之间是如何配合工作的呢？我们假设现在考虑的系统只有两级cache。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 12]

当CPU试图从某地址load数据时，首先从L1 cache中查询是否命中，如果命中则把数据返回给CPU。如果L1 cache缺失，则继续从L2 cache中查找。当L2 cache命中时，数据会返回给L1 cache以及CPU。如果L2 cache也缺失，很不幸，我们需要从主存中load数据，将数据返回给L2 cache、L1 cache及CPU。这种多级cache的工作方式称之为inclusive cache。某一地址的数据可能存在多级缓存中。与inclusive cache对应的是exclusive cache，这种cache保证某一地址的数据缓存只会存在于多级cache其中一级。也就是说，任意地址的数据不可能同时在L1和L2 cache中缓存。

### 2.4 Cache的查找方式 ###

cache控制器在查找cache的时候，通常我们有3种方法，分别是：直接映射缓存、两路组相连缓存、全相连缓存。  
我们继续引入一些cache相关的名词。cache的大小称之为cahe size，代表cache可以缓存最大数据的大小。我们将cache平均分成相等的很多块，每一个块大小称之为cache line，其大小是cache line size。例如一个64 Bytes大小的cache，如果将64 Bytes平均分成64块，那么cache line就是1字节，总共64行cache line。如果我们将64 Bytes平均分成8块，那么cache line就是8字节，总共8行cache line。现在的硬件设计中，一般cache line的大小是4-128 Byts。  
这里有一点需要注意，cache line是cache和主存之间数据传输的最小单位。什么意思呢？当CPU试图load一个字节数据的时候，如果cache缺失，那么cache控制器会从主存中一次性的load cache line大小的数据到cache中。例如，cache line大小是8字节。CPU即使读取一个byte，在cache缺失后，cache会从主存中load 8字节填充整个cache line。

#### 2.4.1 直接映射缓存（Direct mapped cache） ####

我们假设下面的讲解都是针对64 Bytes大小的cache，并且cache line大小是8字节。我们可以类似把这块cache想想成一个数组，数组总共8个元素，每个元素大小是8字节。就像下图这样。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 13]

现在我们考虑一个问题，CPU从0x0654地址读取一个字节，cache控制器是如何判断数据是否在cache中命中呢？cache大小相对于主存来说，可谓是小巫见大巫。所以cache肯定是只能缓存主存中极小一部分数据。我们如何根据地址在有限大小的cache中查找数据呢？现在硬件采取的做法是对地址进行散列（可以理解成地址取模操作）。我们接下来看看是如何做到的？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 14]

我们一共有8行cache line，cache line大小是8 Bytes。所以我们可以利用地址低3 bits（如上图地址蓝色部分）用来寻址8 bytes中某一字节，我们称这部分bit组合为offset。同理，8行cache line，为了覆盖所有行。我们需要3 bits（如上图地址黄色部分）查找某一行，这部分地址部分称之为index。现在我们知道，如果两个不同的地址，其地址的bit3-bit5如果完全一样的话，那么这两个地址经过硬件散列之后都会找到同一个cache line。所以，当我们找到cache line之后，只代表我们访问的地址对应的数据可能存在这个cache line中，但是也有可能是其他地址对应的数据。所以，我们又引入tag array区域，tag array和data array一一对应。每一个cache line都对应唯一一个tag，tag中保存的是整个地址位宽去除index和offset使用的bit剩余部分（如上图地址绿色部分）。tag、index和offset三者组合就可以唯一确定一个地址了。因此，当我们根据地址中index位找到cache line后，取出当前cache line对应的tag，然后和地址中的tag进行比较，如果相等，这说明cache命中。如果不相等，说明当前cache line存储的是其他地址的数据，这就是cache缺失。在上述图中，我们看到tag的值是0x19，和地址中的tag部分相等，因此在本次访问会命中。  
**由于tag的引入，因此解答了我们的一个疑问“为什么硬件cache line不做成一个字节？”。这样会导致硬件成本的上升，因为原本8个字节对应一个tag，现在需要8个tag，占用了很多内存。**  
我们可以从图中看到tag旁边还有一个valid bit，这个bit用来表示cache line中数据是否有效（例如：1代表有效；0代表无效）。当系统刚启动时，cache中的数据都应该是无效的，因为还没有缓存任何数据。cache控制器可以根据valid bit确认当前cache line数据是否有效。所以，上述比较tag确认cache line是否命中之前还会检查valid bit是否有效。只有在有效的情况下，比较tag才有意义。如果无效，直接判定cache缺失。  
上面的例子中，cache size是64 Bytes并且cache line size是8 bytes。offset、index和tag分别使用3 bits、3 bits和42 bits（假设地址宽度是48 bits）。我们现在再看一个例子：512 Bytes cache size，64 Bytes cache line size。根据之前的地址划分方法，offset、index和tag分别使用6 bits、3 bits和39 bits。如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 15]

**直接映射缓存的优缺点**  
直接映射缓存在硬件设计上会更加简单，因此成本上也会较低。根据直接映射缓存的工作方式，我们可以画出主存地址0x00-0x88地址对应的cache分布图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 16]

我们可以看到，地址0x00-0x3f地址处对应的数据可以覆盖整个cache。0x40-0x7f地址的数据也同样是覆盖整个cache。我们现在思考一个问题，如果一个程序试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？首先我们应该明白0x00、0x40、0x80地址中index部分是一样的。因此，这3个地址对应的cache line是同一个。所以，当我们访问0x00地址时，cache会缺失，然后数据会从主存中加载到cache中第0行cache line。当我们访问0x40地址时，依然索引到cache中第0行cache line，由于此时cache line中存储的是地址0x00地址对应的数据，所以此时依然会cache缺失。然后从主存中加载0x40地址数据到第一行cache line中。同理，继续访问0x80地址，依然会cache缺失。这就相当于每次访问数据都要从主存中读取，所以cache的存在并没有对性能有什么提升。访问0x40地址时，就会把0x00地址缓存的数据替换。这种现象叫做**cache颠簸（cache thrashing）**。针对这个问题，我们引入多路组相连缓存。我们首先研究下最简单的两路组相连缓存的工作原理。

#### 2.4.2 两路组相连缓存（Two-way set associative cache） ####

我们依然假设64 Bytes cache size，cache line size是8 Bytes。什么是路（way）的概念。我们将cache平均分成多份，每一份就是一路。因此，两路组相连缓存就是将cache平均分成2份，每份32 Bytes。如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 17]

cache被分成2路，每路包含4行cache line。我们将所有索引一样的cache line组合在一起称之为组。例如，上图中一个组有两个cache line，总共4个组。我们依然假设从地址0x0654地址读取一个字节数据。由于cache line size是8 Bytes，因此offset需要3 bits，这和之前直接映射缓存一样。不一样的地方是index，在两路组相连缓存中，index只需要2 bits，因为一路只有4行cache line。上面的例子根据index找到第2行cache line（从0开始计算），第2行对应2个cache line，分别对应way 0和way 1。因此index也可以称作set index（组索引）。先根据index找到set，然后将组内的所有cache line对应的tag取出来和地址中的tag部分对比，如果其中一个相等就意味着命中。  
因此，两路组相连缓存较直接映射缓存最大的差异就是：第一个地址对应的数据可以对应2个cache line，而直接映射缓存一个地址只对应一个cache line。那么这究竟有什么好处呢？

**两路组相连缓存优缺点**  
两路组相连缓存的硬件成本相对于直接映射缓存更高。因为其每次比较tag的时候需要比较多个cache line对应的tag（某些硬件可能还会做并行比较，增加比较速度，这就增加了硬件设计复杂度）。为什么我们还需要两路组相连缓存呢？因为其可以有助于降低cache颠簸可能性。那么是如何降低的呢？根据两路组相连缓存的工作方式，我们可以画出主存地址0x00-0x4f地址对应的cache分布图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 18]

我们依然考虑直接映射缓存一节的问题“如果一个程序试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？”。现在0x00地址的数据可以被加载到way 1，0x40可以被加载到way 0。这样是不是就在一定程度上避免了直接映射缓存的尴尬境地呢？在两路组相连缓存的情况下，0x00和0x40地址的数据都缓存在cache中。试想一下，如果我们是4路组相连缓存，后面继续访问0x80，也可能被被缓存。

因此，当cache size一定的情况下，组相连缓存对性能的提升最差情况下也和直接映射缓存一样，在大部分情况下组相连缓存效果比直接映射缓存好。同时，其降低了cache颠簸的频率。从某种程度上来说，直接映射缓存是组相连缓存的一种特殊情况，每个组只有一个cache line而已。因此，直接映射缓存也可以称作单路组相连缓存。

#### 2.4.3 全相连缓存（Full associative cache） ####

既然组相连缓存那么好，如果所有的cache line都在一个组内。岂不是性能更好。是的，这种缓存就是全相连缓存。我们依然以64 Byts大小cache为例说明。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 19]

由于所有的cache line都在一个组内，因此地址中不需要set index部分。因为，只有一个组让你选择，间接来说就是你没得选。我们根据地址中的tag部分和所有的cache line对应的tag进行比较（硬件上可能并行比较也可能串行比较）。哪个tag比较相等，就意味着命中某个cache line。因此，在全相连缓存中，任意地址的数据可以缓存在任意的cache line中。所以，这可以最大程度的降低cache颠簸的频率。但是硬件成本上也是更高。

**一个四路组相连缓存实例问题**  
考虑这么一个问题，32 KB大小4路组相连cache，cache line大小是32 Bytes。请思考一下问题：  
1). 多少个组？ 2). 假设地址宽度是48 bits，index、offset以及tag分别占用几个bit？

总共4路，因此每路大小是8 KB。cache line size是32 Bytes，因此一共有256组（8 KB / 32 Bytes）。由于cache line size是32 Bytes，所以offset需要5位。一共256组，所以index需要8位，剩下的就是tag部分，占用35位。这个cache可以绘制下图表示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 20]

#### 2.4.4 Cache的地址查找方式 ####

既然我们是以地址来进行查找cache的，那么我们到底是用虚拟地址还是物理地址？通常我们有三种方式。

##### 2.4.4.1 虚拟地址查找cache #####

以虚拟地址来查找cache，那么这么做有一个优点即单进程中每次读cache的时候，不需要经过MMU的TLB进行地址转换，因此速度快，反应快。但是缺点明显，那就是如果在多task的操作系统当中，每当进行进程切换（虚拟地址映射表发生改变），cache中的虚拟地址就不能再用了（因为虚拟地址对应的物理地址发生了变动），此后就要重新读内存，造成了许多不必要的性能浪费（这种早期的ARM720T和ARM926EJ-S中能看到，现在基本已经淘汰）。

##### 2.4.4.2 物理地址查找cache #####

以物理地址来查找cache（我们叫它PIPT），那么这么做很明显解决了第一种的缺点（因为是以物理地址进行cache的，不管映射表怎么变，物理地址不会变）。但是由引入了一个缺点：每次进行查表的时候，都需要到MMU去进行地址转换，这样增加了查找cache需要的时间，效率明显没有采用虚拟地址的高。注：这种方法，依赖MMU，即MMU关闭，cache就必须关闭。

##### 2.4.4.3 VIPT查找cache #####

第三种则是第一种和第二种的择中处理，即我们将这个查找过程分为两步，tag用物理地址的，index用虚拟地址的，我们叫它VIPT（Virtually Indexed, Physically Tagged）。那么怎么实现呢？首先，由于cache控制器和MMU是两个独立模块，因此通过MMU去查找TAG和通过index去cache查找way是相互独立的即可以同时运行。即当用index去cache查找set（上面有解释，即index相同，但处于不同way的一组集合）的同时也在用虚拟地址去MMU找物理地址的tag，当从cache找到一组set（line\[way\]）的时候（因为只提供了index，因此cache control不知道到底是哪个way，所以返回每个包含index的way），此时MMU中也查到了物理tag，然后再用该物理tag去匹配返回的set，最后获取到对应的cache line。常用CPU情况如下：  
![在这里插入图片描述][20200803172906155.png]

可能到这里有人会问了，混合使用物理地址和虚拟地址不会有问题吗？毕竟虚拟地址在进程发生变动的时候是会不断变化的。不不不，理论上是不会有问题的，为什么呢？我们知道我们的虚拟映射表了，我们的映射表一般是以4K为一个page，即4k对齐，不管虚拟地址怎么发生变化，一个page内的偏移是不变的。要寻址一个4k大小我们需要\[11:0\]共12个bit来提供支持，即在MMU当中，虚拟地址的低12位和物理地址的低12位是相同的。假如我们用的是一个16kb大小，含有4个way，每个line 32bytes的cache，那么通过计算\[4:0\]用于cache的offset定位，\[11:5\]则用于cache的index定位。如上所说，虚拟地址和物理地址的\[11:0\]是相同的，因此index用虚拟地址就不会有影响。但是话又说回来，如果我们的cache大小超过了16k，加入为32kb呢？那么我们以32KB，含有4个way，每个line 32bytes的cache来说，\[4:0\]用于offset定位，\[12:0\]用于index定位，那么问题来了，由于虚拟地址和物理地址仅仅是\[11:0\]相同，那么第13位在发生切换后，就可能会出现0/1两个值，意味着一个物理地址可能会同时占用2个cache line，即两个副本， 这样就会容易引发cache一致性的问题。针对于这种cache alias问题，目前的方案是由操作系统来保证，对于同一物理地址在不同进程空间的虚拟地址，他们的虚拟地址的差一定是cache way大小的整数倍，也就是说他们的第13位一定是相同的。同时已经有些cpu厂商在开发监视模块，试图在硬件层面解决类似的同步问题。同理对于64kb的cache也采用同样的方法。

### 2.5 Cache分配策略（Cache allocation policy） ###

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

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

### 2.6 Cache更新策略（Cache update policy） ###

**1. 写直通（write through）：**  
当CPU执行store指令并在cache命中时，我们更新cache中的数据并且更新主存中的数据。cache和主存的数据始终保持一致，也就是cache和主存都要写一份。  
![在这里插入图片描述][20200803172945418.png]

**2. 写回（write back）：**  
当CPU执行store指令并在cache命中时，我们只更新cache中的数据。并且每个cache line中会有一个bit位记录数据是否被修改过，称之为dirty bit（翻翻前面的图片，cache line旁边有一个D就是dirty bit）。我们会将dirty bit置位。主存中的数据只会在cache line被替换或者显示clean操作时更新。因此，主存中的数据可能是未修改的数据，而修改的数据躺在cache line中。  
同时，为什么cache line大小是cache控制器和主存之间数据传输的最小单位呢？这也是因为每个cache line只有一个dirty bit。这一个dirty bit代表着整个cache line时候被修改的状态。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 21]

为了在写入的时候，不需要等待上一条写入到主存的指令执行完成，因此，增加了写缓存即write-buffer。这是一个硬件模块，程序员不可见，但可配置。它的作用很简单，就是当写入数据到主存的时候，不需要核心去等待写入完成这个动作，这个动作由write-buffer来实现，核心只需要将要执行的动作送入到write-buffer即可返回，然后去执行下条指令，这样可以增加系统的写入性能和效率。下图为在不同写入模式下，write-buffer的位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 22]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 23]

注：在cache里面clean的意思是将cache或者cache address上的脏数据写入到主存。Invalidation的意思是将cache或者cache address上的数据标记成无效，不会回写到主存(复位后，所有cache line都是无效状态)。

### 2.7 Cache的替换策略 ###

第一种，轮转替换，这个这里就不解释了。

第二种，随机替换，方法如名字，当cache存满了后，如果来了一条新的，则随机找一个cache line被替换

第三种，LRU替换，方法如名字，当cache存满了后，如果来了一条新的，则选择最少使用的被替换。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70]: /images/20230208/f594c254a80948f593afe822a9ea446f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 1]: /images/20230208/84bc5e8783cf4b60a092dcd12d67198b.png
[20200803172230511.png]: /images/20230208/263531dbf42b4dceb14159d8aca48835.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 2]: /images/20230208/8c413ce46b0c4bfaa70a322644e6dc0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 3]: /images/20230208/a608f3d17952492cb8a816cfddbf12ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 4]: /images/20230208/ca849f6ca4324da7bd61353280be36e2.png
[20200803172343143.png]: /images/20230208/90d88bc59d684c279b8520505106235d.png
[20200803172355520.png]: /images/20230208/e27613a655d04756ab0249045dcc411b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 5]: /images/20230208/f45be22e10fe4dab99bb4e102c200a8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 6]: /images/20230208/1a2dc058d9664df491f2469acdfba49c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 7]: /images/20230208/c5aeadb8403d4a9c9e9549df6b376887.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 8]: /images/20230208/d25841e9c8544aedbacaf492f72c6f40.png
[20200803172455426.png]: /images/20230208/75ef24f1745944588d37f0910ccc88a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 9]: /images/20230208/c873ab4d3189409c8b520cfb985a3479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 10]: /images/20230208/cef1a3b6acf94a6da980a280d4bb1ef3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 11]: /images/20230208/61e71d3ee11345fb8872e1bb9795135f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 12]: /images/20230208/2268797f4434453e90eeb293b0e24d50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 13]: /images/20230208/8f0ef466c1c64f548a0fd12445f9f478.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 14]: /images/20230208/0b7fc3822e334b43a90d9f22acbd63c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 15]: /images/20230208/c35840d325be4ec2b8a1f2aa9ff04902.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 16]: /images/20230208/56b1a4264a534273988a216fb1697a5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 17]: /images/20230208/eb3450bee18a43c182ae37f9ff373b8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 18]: /images/20230208/02f42ab19f8d451ea6b769407273affd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 19]: /images/20230208/c3157cba06f649eb88de2706d15e52cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 20]: /images/20230208/4bbbb3d9930744c195f1f1ff7069fa27.png
[20200803172906155.png]: /images/20230208/f8a90fb715944bdebf6aef023a1fd9fb.png
[20200803172945418.png]: /images/20230208/6293b1a50fb944a1a18ffdd20e8afa9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 21]: /images/20230208/40b423c736c94226abba4b2685205965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 22]: /images/20230208/b9d82b7e03644f7abcc314d7c1ab31ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM4MzY5MDk_size_16_color_FFFFFF_t_70 23]: /images/20230208/41fe8cc22c9a49b28019c895de5a649a.png