计算机的哪个部分管理缓存替换?

Which part of the computer manages cache replacement?

我还没有找到明确的答案:是控制单元本身获取预定义指令来执行缓存逐出,还是操作系统进行干预?如果是,怎么做?

Which part of the computer manages cache replacement?

通常;缓存自己管理缓存替换(不是由单独的部分完成)。

有许多类型的缓存,其中一些由软件实现(DNS 缓存、网页缓存、文件数据缓存),一些由硬件实现(指令缓存、数据缓存、翻译后备缓冲区)。

对于所有情况;每当需要将新数据插入到缓存中并且没有足够的 space 时,其他数据需要快速被逐出以便为新数据创建 space。理想情况下,应该驱逐“最不可能很快被需要”的数据,但这很难确定,因此大多数缓存做出(可能不正确的)假设“最近最少使用”是“最不可能很快被需要”的一个很好的预测指标。

通常这意味着存储某种“上次使用时间”以及数据(对于缓存中的每个项目);这意味着(为了性能)通常将“最近最少使用”(和逐出本身)直接构建到缓存的设计中(例如,“上次使用时间”信息与其他元数据一起存储在“缓存标签”中).

硬件缓存管理它们自己的替换,通常使用 pseudo-LRU approach to choosing which way of a set to evict. (True LRU takes too many bits for state, especially with 8-way or more associative.) See also http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/ - 大型较慢的缓存(如现代 Intel CPUs 中的 L3 缓存)可能会使用自适应替换策略来尝试保留一些有价值的行,即使在没有太多未来价值的巨大工作集中存在大量缓存未命中时也是如此。

如果我们考虑让 OS 参与管理硬件缓存会是什么样子,我们很快就会发现仅仅实现它是多么疯狂(处理程序可以访问内存吗?如果它需要替换一组中的一行怎么办?)那性能将是一场灾难,以及实现的复杂性。从这个推理中,我们可以看出为什么专用逻辑门被内置到相同的缓存检查和更新硬件中。

在每次缓存未命中时陷入 OS 会使缓存未命中的代价更高。 有些会触发 lot 缓存替换,例如遍历大型数组,其中大多数访问至少在一级缓存中丢失(如果您没有为硬件预取进行足够的计算以保持领先)。它还会损害内存级并行性(一次运行中的多个缓存未命中),这对于隐藏大内存延迟非常重要。我想如果你只是选择一行来逐出,处理程序可以 return 而无需真正等待缓存未命中本身解决,所以你可能会在另一个缓存未命中仍在运行时再次 运行 .但是内存排序规则会使这个变得粗略:例如,一些 ISA 保证加载似乎是按程序顺序发生的。

捕获到 OS 的处理程序将在大多数正常 CPU 秒刷新管道。

此外,硬件预取:硬件能够推测性地提前读取负载流当前正在读取的位置非常重要。这样当实际需求负载发生时,它就有希望命中 L2 甚至 L1d 缓存。 (如果真实缓存中的替换必须由 OS 管理,您需要一些单独的预取缓冲区,以便 OS 可以读取?如果您想要预取到工作,但它是正确性所必需的)。

此外,OS 打算做什么? 运行 加载数据以找出要替换哪一行的指令?如果这些 loads/stores 造成更多缓存未命中怎么办。

此外:存储在 之后才真正提交给 L1d 缓存,它们在 OoO exec CPU 中从无序后端退出。也就是说,直到他们被认为是非投机性的。 (存储缓冲区允许这种解耦)。此时没有办法回滚它们;他们绝对需要发生。如果在检测到第一个之前(或缓存未命中加载同步发生时),存储缓冲区中有多个缓存未命中存储,假设的缓存未命中异常处理程序如何在不违反内存模型的情况下执行任何操作,如果它需要商店订购。这似乎是一场噩梦。

我一直假设“高速缓存未命中处理程序”类似于软件 TLB 未命中处理程序(例如,在 MIPS 或其他不执行硬件页面遍历的 ISA 上)。 (在 MIPS 中,TLB 未命中异常处理程序必须使用具有固定转换的特殊区域中的内存,以便可以在不导致更多 TLB 未命中的情况下进行访问。)唯一有意义的是 OS提供某种实现替换策略的“微代码”,并且 CPU 运行 在需要替换时在内部执行它,而不是按正常执行主 CPU 指令的顺序.

但实际上可编程微码的效率太低了;它没有时间检查内存或任何东西(除非有持久缓存速度状态保留供此微代码使用)。 专用硬件可以在一两个时钟周期内做出决定,逻辑直接连接到该缓存的状态位。

选择提供和跟踪的状态与替换算法的选择密切相关。因此,只有在有更多选择或很多状态时,可编程才有意义。

LRU 需要在缓存命中时更新状态跟踪 捕获到 OS 以让它选择如何更新事物对于可接受的性能来说,每次缓存命中显然是不合理的;每次内存访问都会陷入困境。