计算机原理与嵌入式系统笔记：第六篇

最烦的一节，必考。

高速缓存

局部性原理

局部性原理是存储系统层级构成的基础。

• 时间局部性：当前被访问的数据有可能很快再次被访问。就比如刚拿了一本书到书桌上查阅，可能会很快地再次查阅它。
• 空间局部性：当前被访问数据地址相近的数据有可能很快被访问。就比如找到一本关于ARM的书籍时，也许紧挨着它的另一本书籍也是需要的，因为图书馆会将相同主题的书放在同一书架上。

程序为何会具有局部性？

• 程序中的循环结构，呈现出时间局部性
• 程序中的顺序执行指令，呈现出空间局部性

访问时间与缓存未命中

• 强制性未命中（compulsory miss）：
  • 也称为冷未命中（cold miss），
  • 发生在存储单元第一次被访问时。
• 容量未命中（capacity miss）：
  • 由于工作集过大造成的缓存未命中。
• 冲突未命中（conflict miss）：
  • 由于两个地址映射到高速缓存的同一个单元，缓存存入时互相挤占对方导致的未命中。

平均内存访问时间计算公式

一级缓存：

$$t_{av}=ht_{cache}+(1-h)t_{main}$$

其中h代表命中率。

多级缓存：

$$\begin{aligned} t_{av}&=h_1t_{L1}+(1-h_2-h_1)t_{main}\\ t_{av}&=h_1t_{L1}+(h_{12}-h_1)t_{L2}+(1-h_{12})t_{main} \end{aligned}$$

h₁表示在L1缓存的命中率，h₂表示在L2缓存的命中率，h₁₂表示在L1/L2两级缓存中的总命中率。

直接映射高速缓存

直接映射（Direct Mapped） 指低一级存储器中的每一个数据在高速缓存中的映射都有唯一确定的地址。

直接映射高速缓存由下面三部分组成：

• 有效标记(valid)：表示该缓存块内容是否有效
• 标签(tag)：指示这一块缓存代表哪个内存单元
• 数据域(data)：保存相应内存区域的内容

如何表示每一个数据的地址呢？我们使用“标签——索引——偏移量”这三部分来定位我们需要的数据。

• 标签(tag)：用来与被索引选中的缓存块的标签值进行比较，如果相同，则表明这个缓存块包含所需要的内存数据。内存中有2^t个块映射到同一个缓存块中。
• 索引(index)：选择要检查的缓存块，直接映射高速缓存有2^c个缓存块的索引。
• 偏移量(offset)：如果缓存块中数据域的长度大于最小可寻址单元，那么地址的最低几位被用作偏移量，从数据域中选择对应的内容。每个缓存块包含2^b个最小寻址单元（对于ARM来说，最小寻址单元是字节）。

说白了就是把高速缓存切成一行行的块，一共有2^c个这样的块。之后每个块有自己的一个标签tag，因为内存中也有许多块（2^t个）要映射到这一个块中，需要用tag把内存中的块进行区分。之后，高速缓存中这一行行的块，每一个可以存放很多数据，使用偏移量把存的这2^b个数据分开。

[{"url":"https://bp.esing.dev/https://raw.githubusercontent.com/Zxis233/images/main/img/image-20240612203515856_2024-6-12_2035_fn8chxoout.png","alt":"简单的练习"}]

加载更多

答案

1. B。

   因为4096=2¹²，也就是内存中的4096个块要对应到缓存中的一个块，则每个tag长度为12bit。因为缓存有64个块，一共就是64x12 bits。

缓存的写与读

写操作比读操作复杂，因为要更新高速缓存和主存（或下一级存储）的内容。一共有两种写操作方式：

• 通写（write through）：每次写操作都将同时更新高速缓存和主存单元。这种模式保证了高速缓存和主存的一致性，但会产生额外的主存通信。
• 回写（write back）：每次写操作仅仅将更新的数据写入高速缓存中，只有当修改过的缓存块（增加dirty bit来判断）从高速缓存中移出时，才将它写到主存中。这种模式可以减少缓存块被移出高速缓存之前，为了将它更新到主存而进行的多次写操作。

命中与未命中

• 读命中：
  • 高速缓存直接传送数据到处理器（所希望的情况）。
• 读未命中：
  • 暂停CPU的执行，从主存中获取数据块，传送到高速缓存，重新启动。
• 写命中：
  • 可以替换高速缓存和主存中的数据（通写）
  • 只将数据写入高速缓存，被替换时再写入主存（回写）
• 写未命中：
  • 将整个数据块先读入高速缓存，然后写其中某个数据。

直接映射的性能

如图所示，此时共有三个数据需要存储，这三个数据所对应的缓存块并不同，因此只有第一次访问时会发生强制未命中，后续都能找到。

如上图，显然0x04和0x24存在同一个缓存块内。这时候会发生什么？

两个人互相把对方挤下去。在开始时发生两次强制未命中，后续发生八次冲突未命中，合计100%的Miss。这体现了直接映射的缺点：冲突概率大。

总结：直接映射高速缓存速度快，耗费相对较低，但是策略过于简单，易发生冲突未命中。若频繁访问的单元正好被映射到同一个高速缓存块，我们将无法充分利用高速缓存的优势。

该如何缓解？我们提出了全相连高速缓存。

全相连高速缓存

全相联（fully-associative）高速缓存指任意一个内存数据块可以映射到高速缓存中的任意一个地址。

和直接映射高速缓存类似，全相连的高速缓存由下面三部分组成：

• 有效标记(valid)：表示该缓存块内容是否有效
• 标签(tag)：指示这一块缓存代表哪个内存单元
• 数据域(data)：保存相应内存区域的内容

对于地址，标签(tag)变为内存中有2^t个块映射到任意一个缓存块中。

偏移量(offset)和直接映射相同，但全相连高速缓存没有索引(index)，因为每次都要检查所有的缓存块。

也可以认为全相联高速缓存只有一个索引，因此c=0、2^c=1。

全相连的性能

不限制存放位置，因此0x04和0x24可以放在两个块中，避免之后的冲突未命中。

从上面例子可以看出，全相联高速缓存不限制主存数据在高速缓存中的存放位置，使映射具有最大的灵活性，命中率最高。但全相连相比直接映射也有缺点：

• 全相联映射方式造成硬件开销过大，有一定的局限性，因其在每次数据访问时要读出并比较所有的标记单元，速度慢，能耗也非常大。
• 全相联高速缓存一般只用于设计小容量缓存器。

那么，能否结合直接映射和全相连缓存的优点呢？

缓存的终极解决方案：组相联高速缓存

• 每个组由一个全相联高速缓存实现，即对组内的每路缓存块，只要是空的都可映射。
• 低一级存储器中的每一个数据直接映射到唯一确定的组。

高速缓存访问请求按照索引广播给组内所有缓存块，判断是否命中。

组相连高速缓存的地址也由三部分组成，但和直接映射高速缓存有一点区别：

• 标签(tag)的定义不变，依旧是内存中有2^t个块映射到同一个组中；
• 组相联高速缓存有2^c个组的索引(set index)。直接映射相当于每个缓存块就是一个组；全相联映射相当于所有缓存块构成一个组。
• 偏移量(offset)依旧是每个缓存块包含2^b个最小寻址单元。

说白了就是：主存每个数据块的大小决定offset，组的数量决定set，主存中映射到同一个组里的缓存块数量决定了tag。

区分 数据传输最小单元 和 最小寻址单元 ！

• 数据块(data block)：数据传送的最小单元，也称为cache line。
• 最小寻址单元：通过Offset找到的最小单元。ARM的最小寻址单元是字节。

两路组相连的性能

由上图可以看出：对于全相连必定发生冲突未命中的两个数据，组相连利用两个组避免了这种情况发生，同时不至于遍历所有的数据块，保证了效率。

如果是三个数据存入两路组相连：0x04,0x24,0x44，会发生什么？依旧会有冲突未命中。但我们要替换其中的一个数据…怎么做来让冲突未命中发生的概率最小？

缓存替换策略

在高速缓存“满”且需要载入新的数据块时，需要考虑何种旧数据块需要被移出高速缓存。

• 直接映射不存在替换策略问题，因为每个数据块对应唯一映射地址，其替换的数据块也是确定的；
• 对于组相联与全相联高速缓存，需要考虑替换策略：
  • Random：
    • 优点：硬件简单，耗费低
    • 缺点：命中率相对较低。
  • LRU：
    • 优点：命中率高
    • 缺点：硬件耗费大。
  • FIFO： 折中

如上图，我们存入三个数据，通过判断U位来决定缓存是否要被替换掉。

下次会讲虚拟内存了……