直接映射缓存是如何工作的？

Question

直接映射缓存是如何工作的？

cachingsystemcpu-architecture

53

我正在学习系统架构课程，但是我不太理解直接映射高速缓存的工作原理。

我已经搜索了很多地方，但它们用不同的方式解释，让我更加困惑。

我不理解的是什么是标记和索引，以及它们是如何被选择的？

我的讲座解释是： “地址分为两部分索引（例如15位），用于直接寻址（32k）RAMs 剩余的地址，标记被存储并与传入的标记进行比较。”

这个标记从哪里来？它不能是RAM中内存位置的完整地址，因为与全关联高速缓存相比，这会使直接映射高速缓存无用。

非常感谢。

- Percentage

1

你应该阅读Morris Mano的《计算机体系结构》一书中的这个主题。那里有很好的解释。 - Jatin Khurana

1

请查看以下链接，我认为它将有助于您清楚地了解高速缓存中的直接映射概念和标记、索引等参数。http://csciwww.etsu.edu/tarnoff/labs4717/x86_sim/direct.html - user2891771

在你引用的链接中，为什么图表中最后两个块不是连续的(都是 2^n -1)？这不符合块标识符是连续的模式——1、2、3、...。 - committedandroider

@user2891771，在同一个链接中，“标签唯一地标识了该块来自哪个内存位置”的内存是指什么类型的内存？ - committedandroider

请参阅关联缓存的标签和索引术语。链接来自保罗·克莱顿（Paul Clayton）收藏的安迪·格鲁（Andy Glew）计算机体系结构维基。 - Peter Cordes

4个回答

13

让我们举一个例子。一个64千字节的缓存，有16字节的缓存行，有4096个不同的缓存行。

您需要将地址分解成三个不同的部分。

最低位用于告诉您缓存行内的字节，当您收到它时，此部分不直接用于缓存查找。（在此示例中为0-3位）
下一个位用于索引缓存。如果您将缓存视为一大列缓存行，则索引位告诉您需要查找哪一行以获取数据。（在此示例中为4-15位）
所有其他位都是标记位。这些位存储在标记存储器中，用于您在缓存中存储的数据，我们将缓存请求的相应位与所存储的内容进行比较，以确定我们正在缓存的数据是否为被请求的数据。

您用于索引的位数是log_base_2（number_of_cache_lines）[它实际上是集合的数量，但在直接映射的高速缓存中，线和集的数量相同]

- Danny

我想我明白了，但现在我有另一个问题。到目前为止，我将其想象为一个单表，其中地址和数据应以某种方式存储。在我看来，这个高速缓存最好用3个表来表示：一个是具有缓存行、标记、索引和选择位的表，一个是标记存储器，另一个是数据存储器。当CPU尝试访问位置时，它会检查标记以查看是否为其正在寻找的地址，然后检查其是否仍然有效，然后使用索引从数据存储器中加载数据。 - Percentage

2

@Percentage 我觉得你还没有理解。只有两个表格，一个是标签，另一个是数据。它们都使用相同的索引，也就是说你可以把它们看作是一个表格。这就是你所需要的全部。好好想一想。 - Mackie Messer

@MackieMesser 确认一下我的理解。每个高速缓存行都有不同的标记位来识别缓存行中的字节来自内存的哪个位置？ - committedandroider

1

@committedandroider，这不仅仅是TAG位，而是TAG和INDEX位的组合告诉你缓存行在主内存中的位置。聪明的地方在于，你不需要实际存储INDEX位，因为它们对于特定的缓存行总是相同的。 - Mackie Messer

1

@MackieMesser 像Danny上面说的和我所学到的一样，索引行不就是用来标识缓存地址中数据所在的缓存行吗？它与主内存没有任何关系。 - committedandroider

我认为示例中有一个错误。索引的位应该是4-15，而不是4-13，因为log2（4096）= 12位。 - SomeWittyUsername

2

一个直接映射的缓存就像一个有行（也称为缓存行）和至少2列（一个用于数据，另一个用于标记）的表格。

它是如何工作的：对缓存的读取访问会取地址的中间部分，即索引，并将其用作行号。同时查找数据和标记。接下来，需要将标记与地址的上半部分进行比较，以确定该行是否来自内存中相同的地址范围并且有效。同时，可以使用地址的下半部分从缓存行中选择所请求的数据（我假设缓存行可以保存多个字的数据）。

我强调了一下数据访问和标记访问+比较同时发生，因为这是减少延迟（缓存的目的）的关键。数据路径ram访问不需要两个步骤。

优点是读取基本上是一个简单的表格查找和比较。

但是它是直接映射的，这意味着对于每个读取地址，缓存中恰好有一个位置可以缓存此数据。因此，缺点是许多其他地址将被映射到相同的位置，并可能竞争此缓存行。

- deepsubmicron

1

谈到并行性：直接映射高速缓存的一个值得注意的特性是标记路径和数据路径是独立的。在标记路径中，读取和比较标记与地址是两个顺序操作，它们产生命中/未命中信号。在数据路径中，只有一个操作。地址的中间部分和下部分形成数据RAM的单个地址，以产生单个输出字。RAM在内部的组织方式并不重要。 - Mackie Messer

是的，感谢您指出这一点。我在数据路径中描述的两个步骤只是 RAM 的一个实现细节。 - deepsubmicron

@deepsubmicron，您能详细说明地址的低位和高位吗？您如何确定哪部分是低位，哪部分是高位？ - committedandroider

RAM的宽度有多少？高位地址中缓存行的字数决定了中间部分。中间部分由RAM中的行数确定。因此，剩余的位数就是高位地址的一部分。 - deepsubmicron

1

我在图书馆找到了一本好书，它给了我清晰的解释，现在我将在这里分享，以防其他学生在搜索缓存时偶然发现此线程。

这本书是《计算机体系结构：量化研究方法》第三版，作者是Hennesy和Patterson，第390页。

首先，请记住主内存被划分为缓存块。如果我们有一个64字节的缓存和1GB的RAM，那么RAM将被划分为128KB的块（1GB RAM / 64B Cache = 128KB块大小）。

来自书中的内容：

块可以放置在缓存中的哪里？

如果每个块只能出现在缓存中的一个位置，则称缓存为直接映射。目标块使用以下公式进行计算：<RAM Block Address> MOD <Number of Blocks in the Cache> 因此，假设我们有32个RAM块和8个缓存块。

如果我们想要把RAM的块12存储到高速缓存中，那么RAM块12将被存储到Cache块4中。为什么？因为12/8=1余数4。余数就是目标块。

如果一个块可以放置在缓存中的任何位置，那么该缓存被称为完全关联。
如果一个块可以放置在缓存中一组受限制的位置中的任何一个，那么该缓存为组关联。

基本上，一组是缓存中的一组块。首先将一个块映射到一个组中，然后该块可以放置在组中的任何位置。

公式是：<RAM块地址> MOD <缓存中集合的数量> 因此，假设我们有32个RAM块和一个分成4组的缓存（每组有两个块，即总共8个块）。这样，集合0将拥有块0和1，集合1将拥有块2和3，依此类推...

如果我们想要将RAM块12存储到缓存中，那么RAM块将被存储在缓存块0或1中。为什么？因为12 / 4 = 3余数0。因此选择集合0，并且块可以放置在集合0的任何位置（即块0和1）。

现在我会回到我的原始问题，关于地址。

如果一个块在缓存中，它是如何被找到的？

缓存中每个块框架都有一个地址。只是为了清楚起见，一个块具有地址和数据。

块地址被分成多个部分：标记、索引和偏移量。

标记用于在缓存中查找块，索引仅显示块所在的集合（使其相当冗余），偏移量用于选择数据。

“选择数据”是指在缓存块中显然会有多个内存位置，偏移量用于在它们之间进行选择。

因此，如果您想象一张表，这些将是列：

TAG | INDEX | OFFSET | DATA 1 | DATA 2 | ... | DATA N

标签将用于查找块，索引将显示块位于哪个集合中，偏移量将选择其右侧的一个字段。

我希望我的理解是正确的，如果不是，请告诉我。

- Percentage

5

这是错误的。该表仅包含标签和数据，但不包括索引和偏移量。 - Mackie Messer

我从这个链接中得到了一个好的答案：http://csciwww.etsu.edu/tarnoff/labs4717/x86_sim/direct.html - Percentage

1

索引和偏移量对应于表中的位置。它们不是显式存储的。我相信Hennesy和Patterson解释得很正确，因为那本教科书非常优秀且广为人知，但你在这个答案中搞砸了最后一部分。 - Peter Cordes

1

此外，索引并非您所说的多余，它是必不可少的。您不能仅使用标记在缓存中查找块，而是需要同时使用标记和索引。 - golddove

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SexyBeast · Accepted Answer

好的。那么让我们首先了解CPU如何与缓存交互。

大致而言，有三层内存-缓存（通常由 SRAM 芯片制成），主内存（通常由 DRAM 芯片制成）和存储（通常为磁性，如硬盘）。每当CPU需要来自特定位置的数据时，它首先搜索缓存以查看是否存在。缓存内存在内存层次结构中最靠近CPU，因此其访问时间最短（成本最高），因此如果CPU正在查找的数据可以在那里找到，则构成'命中'，并且从那里获取数据供CPU使用。如果不存在，那么数据必须从主内存移动到缓存中，然后才能被CPU访问（CPU通常仅与缓存交互），这会产生时间惩罚。

因此，为了确定缓存中是否存在数据，应用各种算法。其中之一是直接映射缓存方法。为简单起见，假设存在一个有10个缓存内存位置（编号0到9）和40个主内存位置（编号0到39）的内存系统。这张图片总结了它：

有40个主内存位置可用，但只能容纳最多10个缓存。因此，现在需要通过某种方式将来自CPU的请求重定向到缓存位置。那就有两个问题：

如何重定向？具体而言，在可预测且随时间不变的情况下如何进行？
如果缓存位置已经填满了一些数据，则来自CPU的传入请求必须确定其所需数据的地址是否与存储在该位置的地址相同。

在我们的简单示例中，我们可以通过简单的逻辑进行重定向。由于我们必须将40个主存储器位置从0到39按顺序映射到10个缓存位置从0到9，因此内存位置n的缓存位置可以是n％10。因此，21对应于1，37对应于7等。这成为索引。

但是，37、17、7都对应于7。因此，为了区分它们，出现了标记。所以就像索引是n％10一样，标记是int（n/10）。因此，现在37、17、7将具有相同的索引7，但不同的标记，如3、1、0等。也就是说，可以通过两个数据-标记和索引来完全指定映射。

因此，现在如果请求来自地址位置29，那将转换为标记2和索引9。索引对应于缓存位置号码，因此将查询缓存位置号码9以查看是否包含任何数据，如果有，则检查相关标记是否为2。如果是，则表示CPU命中，并立即从该位置获取数据。如果为空或标记不为2，则意味着它包含与某个其他内存地址而不是29对应的数据（尽管它将具有相同的索引，这意味着它包含来自地址9、19、39等的数据）。因此，这是一个CPU未命中，必须将主内存中位置29的数据加载到位置9的缓存中（并将标记更改为2，并删除以前存在的任何数据），之后CPU将获取它。