缓存中的相关性

现代计算机体系结构必须包含缓存，因为它们对于缩小快速处理器和较慢的主内存之间的速度差距至关重要。关联性是缓存设计中的一个关键组成部分，因为它控制着缓存行如何分配到特定的缓存位置，以及当多个内存块争用同一个缓存槽时如何发生冲突。这本详尽的书将探讨缓存中的关联性、它的各种形式、优点、缺点和实际应用。

引言

1. 缓存的作用

缓存对于计算机设计至关重要，因为它提供了对常用数据的快速临时存储。缓存可以缩小快速处理器和较慢的主内存（RAM）之间的延迟差距。如果没有缓存，CPU将不得不花费更长的时间等待来自RAM的数据，这将大大降低系统性能。

2. 关联性的必要性

在构建缓存时，最重要的考虑因素之一是将数据从主内存移动到缓存中的特定位置，以及处理多个内存块争用同一缓存槽时发生的冲突。处理此问题的一个基本思想是关联性。它确定了特定内存地址可用的缓存槽（也称为缓存行或缓存集）的数量。缓存存储和检索数据的效率在很大程度上取决于关联性级别。

缓存基础知识

1. 缓存的组织

缓存是一小块快速内存，用于存储较大、较慢的主内存中的部分信息。根据空间局部性和时间局部性原理（缓存的功能基于此），程序倾向于检索最近使用过的数据附近的以及最近已经访问过的数据。缓存组织是缓存设计的一个基本组成部分，包括以下元素：

• 缓存行：可以存储在缓存中的最小数据块称为缓存行。数据从主内存中获取后，会加载到缓存行中。
• 缓存槽：缓存中的独立存储空间称为缓存槽，也称为缓存条目或缓存集。每个槽可以容纳一个缓存行。
• 缓存大小：缓存可以容纳的总数据量称为缓存大小，通常以字节或千字节为单位表示。

2. 缓存块和缓存行

缓存块是缓存行的另一种说法。数据以固定大小的块的形式输入到缓存中，这些块的位置与内存地址对应。例如，在传统架构中，每个缓存行可以长64字节。当 CPU 请求内存中的数据时，它会加载整个缓存行，该缓存行除了请求的数据外，还包含多个连续字节。

这种基于块的方法之所以有效，是因为它利用了空间局部性。如果 CPU 使用了缓存行中的一个字节，它很可能很快就会使用附近的字节。将整个缓存行加载到缓存中，可以最大化后续访问命中缓存的可能性。

3. 缓存层次结构

大多数现代计算机系统都采用分层缓存结构。层次结构中的每个缓存级别都有不同的尺寸、速度和关联性级别。层次结构的设置如下：

• L1 缓存：一级缓存，最靠近 CPU 核心，通常分为指令缓存和数据缓存。这是层次结构中最小、最快的缓存。
• L2 缓存：二级缓存由芯片上的多个 CPU 核心共享，比 L1 缓存更大。虽然比 L1 缓存大，但通常速度稍慢。
• L3 缓存：在多核处理器上，如果存在三级缓存，则由所有 CPU 核心共享。它用于减少共享数据的拥塞，比 L2 缓存更大但更慢。
• 主内存（RAM）：当数据在任何缓存中都找不到时，它会被保存在层次结构中最大、最慢的存储器——主内存（RAM）中。

缓存层次结构利用了时间和空间局部性。主内存和较大、较慢的缓存（L3）提供了额外的空间来容纳不太常用的数据，而较小、较快的缓存（L1 和 L2）则存储具有高关联性的常用数据。

关联性级别

关联性描述了在缓存内存中存储特定缓存行的缓存槽的数量。在缓存设计中，有三种标准的关联性级别：

1. 直接映射缓存

直接映射缓存是最简单的缓存组织类型。这种配置只将每个主内存块分配给一个缓存槽。模运算（一种数学运算）决定了这种转换。例如，在 4 路直接映射缓存中，每个内存块可以根据其地址映射到四个可能的缓存槽中的一个。

直接映射缓存的优点

• 简单性：直接映射缓存易于设置，不需要大量硬件。
• 低功耗：由于每个内存块映射到单个缓存槽，因此在缓存访问期间不会发生冲突。

直接映射缓存的缺点

• 关联性有限：由于一对一的映射容易导致缓存冲突，直接映射缓存的命中率较低。
• 空间利用效率低下：由于特定的内存访问模式，可能会出现缓存槽的利用不足。

2. 路联想缓存

路联想缓存提供了直接映射缓存的简单性和全关联缓存的灵活性之间的折衷。路联想缓存将其槽分成若干组，每组包含多个槽。内存块可以映射到其对应组中的任何一个槽。

每组中的槽数决定了缓存的关联性级别。例如，在 4 路路联想缓存中，每组有四个槽，内存块可以插入到为其分配的组中的四个槽中的任何一个。

路联想缓存的优点

• 更高的关联性：路联想缓存比直接映射缓存具有更高的命中率，因为它们不太可能发生缓存冲突。
• 中等简单的硬件：路联想缓存虽然比直接映射缓存复杂，但比全关联缓存更容易设计。

路联想缓存的缺点

• 灵活性有限：由于关联性级别是固定的，内存块只能在其分配的组内使用，这可能导致缓存槽的利用不足。
• 硬件复杂性增加：随着关联性级别的提高，缓存管理硬件的复杂性也会增加。

3. 全关联缓存

全关联缓存提供了最高级别的关联性。在这种组织中，没有用于内存块的组或分配的槽。相反，整个缓存中的所有缓存槽都可以放置任何内存块。这种方法完全消除了缓存冲突。

全关联缓存的优点

• 最大关联性：由于内存块在缓存中的存储位置没有限制，全关联缓存具有最高的命中率。
• 空间有效利用：这种布局将每个缓存槽都发挥到了最大作用。

全关联缓存的缺点

• 硬件复杂：在实现全关联缓存时，需要复杂的硬件来进行标签匹配和缓存管理。
• 高功耗：由于块放置没有限制，频繁访问缓存可能会导致高功耗。

关联性权衡

在决定缓存关联性级别时，需要在命中率、硬件复杂性和缓存容量之间做出权衡。不同的关联性级别可能对不同的应用程序和使用场景有利。考虑以下重要的权衡：

1. 命中率与硬件复杂性

由于消除了缓存冲突，具有更高关联性级别的缓存（包括路联想和全关联缓存）通常具有更高的命中率。然而，要实现更高的命中率，需要更高的硬件复杂性。全关联缓存需要大量的标签比较逻辑，这会消耗更多的功率和芯片空间。

在决定是否提高关联性时，应考虑应用程序的个体需求和可用的硬件资源。对于减少缓存未命中至关重要的关键系统，增加更具关联性的缓存的复杂性可能是合理的。相反，低功耗设备或硬件资源受限的应用程序可能更喜欢较低的关联性级别。

2. 替换策略

缓存关联性也会影响替换策略的选择。当需要将新行放入已占用的缓存槽时，替换策略决定了应逐出哪个缓存行。最近最少使用（LRU）、先进先出（FIFO）和随机是常见的替换策略的示例。

• 在直接映射缓存中，由于每个缓存槽都对应一个特定的内存块，因此替换策略很简单。
• 路联想缓存和全关联缓存中的替换策略必须考虑每个内存块的多个潜在缓存槽。

LRU 由于逐出了最近最少使用的缓存行，因此通常被认为是最高效的替换策略。然而，在硬件中实现 LRU 可能具有挑战性且资源密集，尤其是在高度关联的缓存中。实际的缓存设计通常采用伪 LRU (PLRU) 或随机替换等不太复杂的规则，以平衡准确性和硬件复杂性。

3. 缓存大小与关联性

关联性和缓存大小是相关的。随着关联性级别的提高，通常需要更多的缓存槽，从而增加了整个缓存的大小。这种权衡会影响芯片面积、功耗和生产成本。

对于给定的缓存大小，更高的关联性级别会导致更小的组，从而每个组中拥有更多的缓存行。这可以提高命中率并降低缓存冲突的可能性。然而，它也增加了缓存管理技术的复杂性，增加了功耗和制造成本。

另一方面，较低的关联性值会导致更大的组，每个组中的缓存行更少。尽管缓存的管理更简单，但更多的缓存冲突可能会影响命中率。

目标应用程序的需求应指导缓存大小和关联性级别的选择。虽然某些应用程序可能受益于具有更高关联性的小型缓存，但其他应用程序可能会发现具有较低关联性的大型缓存更具成本效益和能效。

实际应用

各种实际计算机系统都严重依赖缓存内存，从通用 CPU 到 GPU 等专用处理器。以下是一些关联性在各种情况下的应用示例：

1. CPU 缓存

关联性是现代 CPU 片上缓存架构的一个关键设计因素。为了实现高命中率并减少缓存冲突，最靠近 CPU 核心的 L1 缓存通常是路联想或全关联的。根据计划的工作负载和设计目标，L2 和 L3 缓存可能表现出不同程度的关联性。

CPU 缓存关联性经过精心调整，以平衡效率、功耗和生产成本。虽然移动处理器和低功耗 CPU 有时会牺牲缓存大小和关联性以降低功耗，但在服务器和台式计算机中使用的高性能处理器通常拥有更大、更具关联性的缓存。

2. GPU 缓存

图形处理单元 (GPU) 也使用缓存，缓存关联性的选择取决于 GPU 的设计和预期用途。由于 GPU 经常同时处理大量数据集，因此内存访问模式比 CPU 更复杂。

现代 GPU 使用片上 L1 和 L2 缓存，有时也使用 L3 缓存。这些缓存的关联性旨在适应各种工作负载，包括机器学习、科学计算和游戏。

在 GPU 缓存中，L1 和 L2 缓存通常偏好高关联性，以处理图形和并行计算工作负载中看到的各种内存访问模式。然而，GPU 制造商的目标和优先事项决定了设计决策。

3. 现代处理器中的内存组织

现代处理器采用复杂的内存结构来最大化性能，无论是通用计算还是特定活动。这种层次结构包括主内存，有时还包括非易失性内存，以及具有不同关联性级别和缓存大小的多个缓存级别（例如，英特尔系统中的 Optane 内存）。

这种内存层次结构的设计是一个多方面的优化问题，它考虑了以下因素：

• 工作负载：缓存的架构受处理器旨在处理的任务（例如，游戏、科学计算、网页浏览）的影响。对于具有各种内存访问模式的工作负载，更高的缓存关联性可能是有益的。
• 功耗：移动设备和电池供电设备优先考虑低功耗。缓存关联性可能会影响功耗，尤其是在高性能 CPU 和 GPU 中。
• 生产成本：生产更小、更易于使用的缓存成本更低。另一方面，高关联性需要更大的芯片空间，并可能增加生产成本。
• 性能： CPU 和 GPU 的性能直接受到缓存设计的影响。缓存大小-关联性比率必须恰到好处，才能最大化系统性能。