caching - PIPT L1 缓存也是 VIPT 的最小关联性，访问集合而不将索引转换为物理

Question

这个问题是在本科计算机体系结构类(class)中虚拟内存部分的上下文中提出的。助教和教授都回答不上来，网上资源也有限。

问题:

假设处理器具有以下规范:

8KB 页面

32 位虚拟地址

28 位物理地址

一个两级页表，第一级有 1KB 页表，后级有 8KB 页表
二级

4 字节页表条目

16 项 8 路组关联 TLB

除了物理帧(页)号，页表条目还包含一个有效位，一个
可读位、可写位、可执行位和仅内核位。

现在假设这个处理器有一个 32KB 的 L1 缓存，它的标签是根据物理地址计算的。在计算对应于虚拟地址的物理地址之前，缓存必须允许访问适当的缓存集的最小关联性是多少？

直觉:

我的直觉是，如果缓存中的索引数量和虚拟页面(也就是页表条目)的数量可以相互整除，那么我们可以直接从缓存中检索物理页面中包含的字节，而无需计算物理页面，从而提供小的加速。但是，我不确定这是否是正确的直觉，并且绝对不知道如何遵循它。有人可以解释一下吗？

注意:我已经计算出页表条目的数量为 2^19，如果这对任何人有帮助的话。

Answer 1

What is the minimum associativity that cache must have to allow the appropriate cache set to be accessed before computing the physical address that corresponds to a virtual address?

他们只指定缓存是物理标记的。

您始终可以构建虚拟索引缓存，没有最小关联性。即使是直接映射(每组 1 路)也能工作。见 Cache Addressing Methods Confusion有关 VIPT 与 PIPT(以及 VIVT，甚至不寻常的 PIVT)的详细信息。

为了这个问题不是微不足道的，我认为它们也意味着“不产生混叠问题” ，所以 VIPT 只是比 PIPT(物理索引，物理标记)的加速。您可以获得允许 TLB 查找与索引集方式的标签(和数据)并行查找的好处，没有任何缺点。

My intuition is that if the number of indices in the cache and the number of virtual pages (aka page table entries) is evenly divisible by each other, then we could retrieve the bytes contained within the physical page directly from the cache without ever computing that physical page

您需要物理地址来检查标签；记住你的缓存是物理标记的。 (虚拟标记缓存确实存在，但通常必须在上下文切换到具有不同页表 = 不同虚拟地址空间的进程时刷新。这曾经用于旧 CPU 上的小型 L1 缓存。)

通常假设两个数字都是 2 的幂，因此它们总是可整除的。

页大小始终是 2 的幂，因此您可以将地址拆分为页码和页内偏移量，只需在地址中取不同范围的位即可。

小/快速缓存大小也总是具有 2 个集合的幂，因此索引“函数”只是从地址中获取一定范围的位。对于虚拟索引缓存:来自虚拟地址。对于物理索引缓存:来自物理地址。 (像大型共享 L3 缓存这样的外部缓存可能具有更高级的索引功能，比如更多地址位的散列，以避免地址相互偏移的别名为 2 的大幂。)

缓存大小可能不是 2 的幂，但您可以通过非 2 的幂关联性(例如，10 或 12 路并不罕见)而不是非 2 的幂的行大小来实现或套数。在索引一个集合后，缓存为该集合的所有方式获取标签并并行比较它们。 (对于快速 L1 缓存，通常也并行获取由行偏移位选择的数据，然后比较器只是将该数据多路复用到输出中，或者引发不匹配的标志。)

没有混叠的 VIPT 要求(如 PIPT)

对于这种情况， 您需要所有索引位都来自页面偏移以下 .它们将“免费”从虚拟转换为物理，因此 VIPT 缓存(在 TLB 查找之前索引一组)没有同义词/同义词问题。除了性能，它是 PIPT。

我在 Why is the size of L1 cache smaller than that of the L2 cache in most of the processors?上的详细回答包括有关该速度黑客的部分。

Virtually indexed physically tagged cache Synonym显示了缓存不具有该属性的情况，并且需要操作系统对页面进行着色以避免同义词问题。

How to compute cache bit widths for tags, indices and offsets in a set-associative cache and TLB有更多关于缓存大小/关联性的注释，这些注释赋予该属性。

公式:

最小关联性 = 缓存大小/页大小

例如具有 8kiB 页的系统需要 32kiB 的 L1 缓存至少是 4 路关联的，以便索引位仅来自低 13。

直接映射缓存(每组 1 路)只能与 1 页一样大:行内字节和索引位总计达到页内字节偏移。直接映射(1 路)缓存中的每个字节都必须有一个唯一的索引:偏移地址，这些位来自完整地址的连续低位。

换句话说， 2^(idx_bits + within_line_bits)是每组只有一种方式的总缓存大小。 2^N 是页面大小，对于 N 的页面偏移量(免费转换的页面内字节地址位的数量)。

实际的组数(在这种情况下 = 行)取决于行大小和页面大小。使用更小/更大的行只会改变偏移和索引位之间的鸿沟。

从那里开始，在不从更高地址位进行索引的情况下使缓存更大的唯一方法是为每个集合添加更多路，而不是更多路。