缓存优化 III
AP SHANTHI博士
本模块的目标是讨论影响分层内存系统中平均内存访问时间的各种因素，并讨论一些可以用来改进它的技术。
内存访问时间：为了查看缓存的性能，我们需要查看平均内存访问时间以及会影响它的因素。我们知道平均内存访问时间（AMAT）定义为
AMAT = htc + (1 – h) (tm + tc)，其中第二项中的 tc 通常被忽略。
h：缓存命中率，tc：缓存访问时间，1-h：缓存未命中率和
tm : 主存访问时间
AMAT 可以写为命中时间 +（未命中率 x 未命中惩罚）。减少这些因素中的任何一个都会降低 AMAT。前面的模块讨论了一些优化，这些优化是为了减少未命中惩罚和未命中率。我们将在此模块中查看更多优化。我们将讨论可用于通过并行性减少未命中惩罚和未命中率的技术，以及可用于减少命中时间的技术。将讨论以下技术：
通过并行性减少未命中惩罚或未命中率
非阻塞缓存
多组缓存
硬件和编译器预取
减少命中缓存的时间
小而简单的缓存
避免地址转换
流水线缓存访问，以及
跟踪缓存
我们将详细研究每一个。对于第一类，我们尝试通过并行性来减少未命中惩罚或未命中率，指令的执行与内存层次结构中发生的活动存在重叠。
非阻塞缓存： 它们也称为无锁定缓存。对于支持乱序完成的处理器，CPU 不需要因缓存未命中而停顿。例如，CPU 在等待数据缓存返回丢失的数据的同时，继续从指令缓存中获取指令。有可能在未命中的情况下被击中。这种“未命中”优化通过在未命中时提供帮助而不是忽略 CPU 的请求来减少有效的未命中惩罚。我们还可以进行进一步的优化，例如“多次未命中”或“未命中未命中”优化。也就是说，即使有多个未完成的未命中，我们仍然允许处理器访问。然而，所有这些都显着增加了缓存控制器的复杂性，因为可能存在多个未完成的内存访问。还，绩效评估会有困难。高速缓存未命中不一定会使 CPU 停顿，并且有可能对同一块发生多个未命中请求。这必须小心处理。硬件必须检查未命中以避免不一致问题并节省时间。
图 29.1 显示了 8 KB 数据缓存的缓存未命中的平均时钟周期时间，因为未完成的未命中数是变化的。浮点程序受益于与多个未命中相关的日益增加的复杂性，而整数程序几乎可以从简单的一次未命中方案中获得所有好处。
多组缓存：我们可以将缓存组织为独立组的集合，以支持同时访问，而不是将缓存视为单个内存块。这里也使用了用于促进并行访问和增加主存储器带宽的相同概念 。ARM Cortex A8 支持 1-4 个 L2 组。Intel i7 支持 L1 的 4 个 bank 和 L2 的 8 个 bank。
只有当地址分布在多个银行时，银行才支持同时访问。地址到存储体的映射会影响内存系统的行为。将访问分散到多个块的一种简单方法是顺序交错，如图 29.2 所示。该图显示了使用块寻址的四路交错高速缓存组。Block 0 在 bank 0，block 1 在 bank1，block 2 在 bank 2，block 3 在 bank 3。现在，block 4 在 bank 0，依此类推。块 0、4、8 和 12 映射到存储体 0，块 1、5、9、13 映射到块 1，依此类推。因此，块编号 mod number of bank 决定了 bank 号。假设每个块有 64 个字节，这些地址中的每一个都将乘以 64 以获得字节寻址。多组也有助于降低功耗。
基于硬件的预取： 另一种减少未命中损失的技术是在处理器请求项目之前预取项目。指令和数据都可以预取，可以直接预取到缓存中，也可以预取到访问速度比主存储器更快的外部缓冲区中。对于指令预取，处理器通常会在未命中时取两个块——请求的块和下一个连续的块。请求的块放置在指令缓存中，而预取的块放置在指令流缓冲区中。如果请求的块存在于指令流缓冲区中，则取消原始缓存请求，从流缓冲区中读取该块，并发出下一个预取请求。人们已经表明，这种预取已经有了很多改进。
类似的方法也可以应用于数据访问。人们已经证明，单个数据流缓冲区可以从 4 KB 直接映射缓存中捕获大约 25% 的未命中。数据缓存之外可能有多个流缓冲区，而不是单个流，每个缓冲区都在不同的地址进行预取，这会增加数据命中率。UltraSPARC III 使用这种预取方案。预取缓存记住用于预取数据的地址。如果加载命中预取缓存，则从预取缓存中读取块，并发出下一个预取请求。它使用当前地址和前一个地址之间的差异计算下一个预取块的“步幅”。最多可以同时进行 8 个预取 UltraSPARC III。但是，这些预取不应干扰基于需求的提取。在这种情况下，性能会下降。图 29.3 显示了 Pentium 4 中预取的性能改进。
基于编译器的预取：就像基于硬件的预取一样，编译器也可以预取以降低未命中率和未命中惩罚。编译器插入预取指令以在需要数据之前请求数据。两种类型的预取是：
寄存器预取将值加载到寄存器中。
缓存预取，它只将数据加载到缓存而不是寄存器。
这些中的任何一个都可以是有故障的或无故障的。 That is, the address does or does not cause an exception for virtual address faults and protection violations. Non-faulting prefetches simply turn into no-ops if they would normally result in an exception. A normal load instruction could be considered a faulting register prefetch instruction. The most effective prefetch is “semantically invisible” to a program . It does not change the contents of registers and memory and it cannot cause virtual memory faults. Most processors today offer non-faulting cache prefetches. Like hardware-controlled prefetching, the goal is to overlap execution with the prefetching of data. Loops are the important targets, as they lend themselves to prefetch optimizations. If the miss penalty is small, the compiler just unrolls the loop once or twice and it schedules the prefetches with the execution. If the miss penalty is large, it uses software pipelining or unrolls many times to prefetch data for a future iteration. Issuing prefetch instructions incurs an instruction overhead, however, so care must be taken to ensure that such overheads do not exceed the benefits.
到目前为止，我们已经研究了通过并行来减少未命中惩罚和未命中率的不同技术。现在，我们将讨论用于减少 AMAT 的第三个组件的各种技术，即。命中时间。这是关于如何减少访问缓存中数据的时间。我们将研究有助于快速有效地找出数据是否在缓存中，如果是，从缓存中取出数据的技术。命中时间很关键，因为它会影响处理器的时钟频率。在当今的许多处理器中，高速缓存访问时间限制了时钟周期速率，即使对于需要多个时钟周期才能访问高速缓存的处理器也是如此。因此，快速命中时间比平均内存访问时间公式更重要，因为它有助于一切。
小而简单的一级缓存： 小硬件更快，因此小而简单的缓存肯定有助于缩短命中时间。较小的高速缓存还使其能够在芯片上并避免与芯片外高速缓存相关的损失。访问缓存的关键时序路径包括寻址（索引）标签内存、比较标签然后获取数据。直接映射缓存可以重叠标签比较和数据传输。由于大部分数据都在缓存中命中，因此节省了缓存中数据访问的周期是一个显着的结果。较低的关联性也会降低功耗，因为访问的缓存行较少。图 29.4 显示了缓存大小和关联性对访问时间的影响。随着大小/关联性的增加，访问时间也会增加。图 29.5 显示了缓存大小和关联性对每次读取能量的影响。
Avoiding address translation during indexing of the caches: With the support for virtual memory, virtual addresses will have to first be translated to physical addresses and only then the indexing of the cache can happen. Going by the general guideline of making the common case fast, we can use virtual addresses for the cache, since hits are much more common than misses. Such caches are termed virtual caches, with physical cache used to identify the traditional cache that uses physical addresses.
As already pointed out, we have two tasks associated with accessing the cache – indexing the cache and the tag comparison. Thus, the issues are whether a virtual or physical address is used to index the cache and whether a virtual or physical index is used in the tag comparison. Full virtual addressing for both index and tags eliminates address translation time from a cache hit. But there are several reasons for not looking at such virtually addressed caches.
原因之一是保护。通常，非常重要的页面级保护是作为虚拟到物理地址转换的一部分进行检查的。当我们使用虚拟缓存时，一种解决方案是在未命中时从 TLB 复制保护信息，添加一个字段来保存它，并在每次访问虚拟寻址缓存时检查它。另一个原因是每次进程切换时，虚拟地址指向不同的物理地址，需要刷新缓存。这可以通过进程标识符标签(PID)来处理。如果操作系统将这些标签分配给进程，PID 会区分缓存中的数据是否用于该程序。虚拟缓存不受欢迎的第三个原因是操作系统和用户程序 可以为同一个物理地址使用两个不同的虚拟地址。这些重复的地址，称为同义词或别名，可能会导致虚拟缓存中相同数据的两个副本。如果修改了一个，另一个将具有错误的值。同义词问题的硬件解决方案，称为抗锯齿，确保不会发生此类问题。Alpha 21264 使用 64 KB 指令缓存和 8 KB 页和双向集关联性。因此，硬件必须处理与两组中的 2 个虚拟地址位相关的别名。它通过简单地检查所有 8 个可能的位置来避免别名——每组四个条目，以确保没有一个与正在获取的数据的物理地址匹配。如果找到一个，它就失效了，所以当新数据加载到缓存中时，它的物理地址保证是唯一的。通过强制别名共享一些地址位，软件可以使这个问题变得更容易。最后，与虚拟地址相关的最后一个领域是 I/O。I/O 通常使用物理地址，因此需要映射到虚拟地址以与虚拟缓存交互。
获得虚拟和物理缓存优势的一种方法是使用部分页面偏移量，即虚拟和物理地址中相同的部分来索引缓存。当使用虚拟地址索引缓存时，地址的虚拟部分被转换，标签匹配使用物理地址。这称为虚拟索引物理标记缓存。这种替代方法允许立即开始缓存读取，而标签比较仍然是物理地址。这种类型的缓存的限制是直接映射缓存不能大于页面大小。
缓存访问流水线化：可用于减少命中时间的下一项技术是对缓存访问进行流水线化，以便一级缓存命中的有效延迟可以是多个时钟周期，从而提供快速循环时间和慢速命中。例如，Pentium 的流水线访问指令缓存需要一个时钟周期，Pentium Pro 到 Pentium III 需要两个时钟，而 Pentium 4 到 i7 需要四个时钟。这种拆分增加了流水线阶段的数量，导致对错误预测分支的更大惩罚以及加载问题和数据使用之间的更多时钟周期。实际上，这种技术增加了指令的带宽，而不是减少了缓存命中的实际延迟。它还可以更轻松地增加关联性。
跟踪缓存：我们讨论的最后一项技术是使用跟踪缓存。现代处理器的主要挑战之一是找到每个周期超过四条指令的指令级并行性，以便集成指令单元能够在每个周期提供足够的指令而没有依赖性。一种解决方案称为跟踪 缓存。跟踪缓存不是将静态缓存块中的指令限制为空间局部性，而是查找动态指令序列，包括要加载的 分支进入缓存块。它被称为跟踪缓存，因为缓存块包含由 CPU 确定的已执行指令的动态跟踪，而不是包含由内存确定的静态指令序列。因此，分支预测被折叠到缓存中，并且必须与地址一起验证以获得有效的提取。作为 Pentium 4 及其后续产品的基础的 Intel Netburst 微体系结构使用跟踪缓存。
跟踪缓存具有更复杂的地址映射机制，因为地址不再与字长的 2 次幂对齐。然而，它们在利用指令高速缓存的数据部分方面还有其他好处。由于分支非常频繁，大块可能会浪费在传统缓存中。对于像 AMD Athlon 这样的处理器来说，空间利用率是一个真正的问题，它的 64 字节块可能包含 16 到 24 条 80×86 指令。更高的教学问题的趋势使问题变得更糟。跟踪缓存仅存储从分支入口点到跟踪出口的指令，从而避免这种未充分利用的情况。然而，跟踪缓存的缺点是它们在指令缓存中多次存储相同的指令。
总而言之，我们在这个模块中定义了平均内存访问时间。AMAT 取决于命中时间、未命中率和未命中惩罚。存在多种优化来处理这些因素中的每一个。我们讨论了通过并行性减少未命中惩罚和未命中率以及减少命中时间的不同技术。他们是：
Ø 通过并行性降低未命中惩罚或未命中率
§ 非阻塞缓存
§ 多组缓存
§ 硬件和编译器预取
Ø 减少命中缓存的时间
§ 小而简单的缓存
§ 避免地址转换
§ 流水线缓存访问，以及
§ 跟踪缓存
图 29.6
作为一个现成的计算器，图 29.6 总结了我们在过去三个模块中讨论过的所有缓存优化技术。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A.Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。
计算机组织，Carl Hamacher、Zvonko Vranesic 和 Safwat Zaky，第 5 版，McGraw-Hill 高等教育，2011