2.6.2 缓存映射关系

缓存不仅需要大容量，还需要科学的管理方式，其逻辑构成对于我们了解缓存工作机制很重要。缓存由许多“行”或“块”组成，这些行被组织成一个或多个集合。每行包含实际的数据，以及一个标签字段，这个标签字段指示这些数据来自主内存的哪个地址。

当CPU需要访问一个内存地址时，这个地址被分成三个部分：块偏移量（Block Offset）、索引（Index）和标签（Tag）。

● 块偏移量：这部分确定在一个缓存行（也称为缓存块）内的哪个字节或字中包含了我们需要的数据。这取决于我们的系统是按字节寻址的还是按字寻址的。

● 索引：这部分用于确定数据应该存储在哪个缓存集合中，或者我们应该在哪个缓存集合中查找这个数据。

● 标签：标签部分用于确定数据是否真的在缓存中。我们将这部分与缓存行中的标签字段进行比较。如果它们匹配，那么我们就有一个“命中”，可以直接从缓存中获取数据，而不必去主内存中查找。

通过这种方式，我们可以快速地检查缓存是否包含我们需要的数据，并在它存在的情况下立即获取它，这通常比从主内存中获取数据要快得多。缓存的组织有以下几种典型方式。

● 直接映射（Direct Mapped）：在直接映射的缓存中，每个内存地址都对应一个固定的缓存位置。这种设计的优点是简单和高效，因为我们可以快速地找到任何给定内存地址在缓存中的位置。缺点是它可能导致高缓存冲突率，如果两个经常访问的内存地址被映射到同一个缓存位置，它们就会不断地替换彼此，导致缓存命中率下降。

● 全相联（Fully Associative）：在全相联的缓存中，任何内存地址都可以被映射到缓存中的任何位置。这可以大大减少缓存冲突，提高缓存命中率。全相联缓存的缺点是，若查找给定的内存地址是否在缓存中存在，则需要查找整个缓存，这会导致查找速度下降和硬件复杂度的提高。

● 组相联（Set Associative）：组相联缓存是直接映射缓存和全相联缓存的折中方案。在组相联缓存中，缓存被分为多个组，每个内存地址被映射到一个特定的组，但可以在该组的任何位置。组相联缓存在减少缓存冲突和提高查找速度之间实现了平衡。

在组相联映射中，缓存被划分为多个组或集合，每个集合包含一定数量的缓存行（Cache Line），而每个缓存行又包含多个字节或字。每个集合中的缓存行数量被称为关联度（Degree of Associativity）。在缓存中有两个重要的组件：数据阵列（Data Array）和标签阵列（Tag Array）。

● 数据阵列：数据阵列用于存储实际的数据。当我们在缓存中查找数据时，数据阵列将为我们提供所需的数据。

● 标签阵列：标签阵列存储的是元数据，包括标签和有效位（Valid Bit）等。当我们在缓存中查找数据时，标签阵列将帮助我们确定这些数据实际上是否在缓存中。

在并行的数据阵列和标签阵列的架构中，这两个阵列都会接收到内存访问地址，并对其进行译码。地址的索引部分会指定哪个集合可能包含所访问的数据。数据阵列会将目标集合中的所有数据读出并发送到Way Mux（这是一个多路复用器，用于选择正确的数据）。同时，标签阵列会将目标集合中的所有标签与内存访问地址的标签部分进行比较，比较的结果将告诉我们内存访问是否在缓存中命中。在实际应用中，这种架构允许我们快速并行地检查数据和标签，从而提高缓存查找的速度。

关于缓存的映射，我们需要熟悉Set和Way这两个概念。Set是指缓存中的一组行，每个地址都会映射到一个特定的Set。Way是指一个Set中的行的数量。在“N-way set associative”（N路组相联）缓存中，每个Set有N行，意味着任何给定的内存地址都可以映射到这N个位置之一。CPU缓存设计中的一个关键权衡是映射程度。

● 低映射程度：当一个Set中的行数较少时（例如，在直接映射的缓存中，每个Set只有一行），可能出现的问题是冲突失效（Conflict Miss）。这是因为多个内存地址可能映射到同一个 Set。如果一个程序反复访问这些冲突的地址，那么它们就会互相替换出缓存，从而导致失效。低映射程度会有较高概率的冲突失效，也就是很多地址会映射到同一个Set，造成Set中的缓存行不断互相取代。

● 高映射程度：当一个Set中的行数较多时，冲突失效的问题就可以减少，因为给定的内存地址可以映射到Set中的多个位置。然而，这样做有一些代价。增加每个Set的大小（也就是Way的数量）会增加标签所需的硬件（这是确定一个给定地址是否已在缓存中的步骤），也会增加芯片面积和提高功耗，并可能降低处理器频率。

考虑到缓存容量是有限的，所以当缓存满了以后，如果新的数据要进入缓存，则需要随时更新缓存中的数据，但是删除谁、保留谁需要抉择，所以数据替换策略是缓存设计的核心问题，它和分支预测一样，也最能体现设计思路。

常见的替换策略主要有以下几种。

● 随机（Random）替换：当需要替换一个缓存块时，随机选择一个缓存块进行替换。

● 先进先出（First In First Out，FIFO）：把最先进入缓存的块替换出去。

● 最近最少使用（Least Recently Used，LRU）：在所有缓存中，选择最长时间没有被访问过的块进行替换。这是一种比较常用的缓存替换策略，因为它基于一个合理的假设：最近被访问过的数据在未来被再次访问的可能性更高。

● 最不经常使用（Least Frequently Used，LFU）：在所有缓存中，选择被访问次数最少的块进行替换。

● 最近最多使用（Most Recently Used，MRU）：在所有缓存中，选择最近被访问过的块进行替换。这种策略和 LRU 策略恰好相反，它的假设是最近被访问的数据可能在未来不会被频繁访问，所以选择它进行替换。

● 最经常使用（Most Frequently Used，MFU）：在所有缓存中，选择保留最近或在短期内被访问次数较少的数据项。这种策略和 LFU 策略恰好相反，它的假设是最频繁被访问的数据可能在未来不会被频繁访问，所以选择它进行替换。

● 时钟（Clock）替换策略：这是一种试图模拟LRU策略的实现，但是实现的复杂性较低，性能损失也不大。

到目前为止，最常见的缓存替换策略还是LRU和它的各种变体，因为它的性能相对较好，且实现起来也较为简单。LRU和FIFO本质上都是先进先出的思路，只是LRU用数据最近被访问的时间来进行排序，每一次访问数据的时候会动态地调整数据记录之间的先后顺序；而FIFO用数据进入缓存的时间来进行排序，这个时间是固定不变的，所以各数据记录之间的先后顺序也是固定的。

在实现上，一个常见的做法是使用一个链表来记录缓存数据的使用情况，当一个数据被访问时，将这个数据移动到链表头部，这样链表尾部的数据就是最近最少被使用的。当需要淘汰数据时，直接淘汰链表尾部的数据即可。

这种实现在并发环境下可能需要使用锁来保护这个链表，因为多个线程可能同时修改这个链表，这可能会成为一个瓶颈。因此在实践中通常使用一些近似的算法来实现LRU，例如使用多个LRU链表等。

LRU算法是一种高效的缓存替换策略，但是它并不总是产生最优的结果。例如，对于访问模式为周期性重复访问的情况，如果缓存空间小于访问周期，则LRU策略可能会每次都需要从外部存储器加载数据，导致缓存命中率非常低。