缓存优化 II
AP SHANTHI博士
本模块的目标是讨论影响分层内存系统中平均内存访问时间的各种因素，并讨论一些可以用来改进它的技术。
内存访问时间：为了查看缓存的性能，我们需要查看平均内存访问时间以及会影响它的因素。平均内存访问时间 (AMAT) 定义为
AMAT = htc + (1 – h) (tm + tc)，其中第二项中的 tc 通常被忽略。
h : 缓存命中率
tc : 缓存访问时间
1 – h : 缓存未命中率
tm : 主存访问时间
AMAT 可以写为命中时间 +（未命中率 x 未命中惩罚）。减少这些因素中的任何一个都会降低 AMAT。可以很容易地观察到，当缓存的命中率接近 1（即 100%）时，所有引用都指向缓存，内存访问时间仅由缓存系统控制。那么只有缓存性能很重要。另一方面，如果我们在缓存中未命中，则未命中惩罚，即主内存访问时间也很重要。因此，所有三个因素都会影响 AMAT，并且可以进行优化以减少这些参数中的一个或多个。
有多种不同的方法可用于降低 AMAT。大约有 18 种不同的缓存优化，它们分为 4 类，如下所示：
Ø 减少失误惩罚：
§ 多级缓存，关键词优先，读未命中优先于写未命中，合并写缓冲区条目和牺牲缓存
Ø 降低漏检率
§ 更大的块大小、更大的缓存大小、更高的关联性、路预测和伪关联性以及编译器优化
Ø 通过并行性降低未命中惩罚或未命中率
§ 非阻塞缓存、多组缓存、硬件和编译器预取
Ø 减少命中缓存的时间
§ 小而简单的缓存，避免地址转换、流水线缓存访问和跟踪缓存
前面的模块讨论了一些为减少未命中惩罚而进行的优化。我们将在此模块中查看更多优化。在本模块中，我们将讨论可用于降低未命中率的技术。可用于解决提高未命中率问题的五种优化是：
更大的块大小
更大的缓存大小
更高的结合性
路预测和伪结合性，以及
编译器优化。
我们将详细研究每一个。
不同类型的未命中：在我们研究降低未命中率的优化之前，我们将查看 ‗3C' 模型并讨论各种类型的未命中。我们知道，未命中率只是导致未命中的缓存访问的比例，即缓存中未命中的访问次数除以访问次数。为了更好地洞察导致未命中率的原因，三 C 模型将所有未命中分为三个简单的类别：
强制 - 对块的第一次访问不能在缓存中，因此必须将该块带入缓存。强制未命中是即使您拥有无限缓存也会发生的未命中。它们也称为冷启动未命中或首次引用未命中。
容量——由于缓存的大小有限，如果缓存不能包含程序执行期间所需的所有块，除了强制丢失之外，还会由于块被丢弃和稍后检索而发生容量丢失。
冲突——如果块放置策略不是完全关联的，则会发生冲突未命中（除了强制和容量未命中之外），因为如果冲突块映射到其集合，则块可能会被丢弃并稍后检索。它们也称为碰撞未命中或干扰未命中。
图 28.1 和 28.2 给出了不同缓存大小的各种未命中率。减少这些未命中中的任何一个都应降低未命中率。然而，其中一些可能是矛盾的。减少一个可能会增加另一个。我们还将讨论第四种缺失，稍后在多处理器系统中称为一致性缺失。
更大的块大小： 降低未命中率的最简单和明显的方法是增加块大小。通过增加块大小，我们试图以更好的方式利用参考的空间局部性，从而降低未命中率。更大的块大小也将减少强制未命中。同时，较大的块会增加未命中惩罚。由于它们减少了缓存中的块数，如果缓存很小，较大的块可能会增加冲突未命中甚至容量未命中。图 28.3 显示了未命中率如何随不同缓存大小的块大小而变化。可以看出，超过一个点，增加块大小会增加未命中率。显然，没有理由将块大小增加到会增加未命中率的大小。如果增加平均内存访问时间，那么降低未命中率也没有任何好处。未命中惩罚的增加可能超过未命中率的降低。
Larger cache size: The next optimization that we consider for reducing the miss rates is increasing the cache size itself. This is again an obvious solution. Increasing the size of the cache will reduce the capacity misses, given the same line size, since more number of blocks can be accommodated. However, the drawback is that the hit time increases and the power and cost also increase. This technique is popular in off-chip caches. Always remember the fact that execution time is the only final measure we can believe. We will have to analyze whether the clock cycle time increases as a result of having a more complicated cache, and then take an appropriate decision.
Higher associativity: This is related to the mapping strategy adopted. Fully associative mapping has the best associativity and direct mapping, the worst. But, for all practical purposes, 8-way set associative mapping itself is as good as fully associative mapping. The flexibility offered by higher associativity reduces the conflict misses. The 2:1 cache rule needs to be recalled here. It states that the miss rate of a direct mapped cache of size N and the miss rate of 2-way set associative cache of size N/2 are the same. Such is the importance of associativity. However, increasing the associativity increases the complexity of the cache. The hit time increases.
Way prediction and pseudo associativity: 这是另一种减少冲突未命中并保持直接映射缓存的命中速度的方法。在这种情况下，缓存中保留了额外的位，称为块预测器位，以预测下一次缓存访问的路径或块。这些位选择在下一次缓存访问中尝试使用哪些块。如果预测器正确，则缓存访问延迟是快速命中时间。如果没有，它会尝试另一个块，改变预测器的方式，并有一个额外的时钟周期的延迟。这种预测意味着多路复用器被提前设置以选择所需的块，并且在该时钟周期中仅与读取缓存数据并行执行单个标签比较。当然，未命中会导致在下一个时钟周期检查其他块是否匹配。Pentium 4 使用方式预测。Alpha 21264 在其指令缓存中使用路径预测。除了提高性能之外，方式预测还可以降低嵌入式应用的功耗，因为电源只能应用于预期使用的一半标签。
一种相关的方法称为伪关联或列关联。访问就像在直接映射缓存中一样进行。但是，如果未命中，则在进入内存层次结构的下一个较低级别之前，会检查第二个缓存条目以查看它是否与那里匹配。一种简单的方法是反转索引字段的最高有效位以找到“伪集合”中的另一个块。然后伪关联缓存有一个快和一个慢的命中时间——对应于常规命中和伪命中——除了失手处罚。图 28.4 显示了相对时间。如果直接映射缓存的许多快速命中时间变成伪关联缓存中的慢命中时间，那么一种危险将是。然后性能会下降通过这种优化。因此，重要的是为每一组指示哪个块应该是快速命中，哪个应该是慢块。一种方法是简单地使上层变快并交换 块的内容。另一个危险是未命中惩罚可能会稍微变长，从而增加检查另一个缓存条目的时间。
编译器优化：到目前为止，我们已经讨论了用于降低未命中率的不同硬件相关技术。现在，我们将讨论编译器可以提供的一些选项来降低未命中率。编译器可以轻松地重新组织代码，而不会影响程序的正确性。编译器可以分析代码、识别冲突序列并进行相应的重组。对于具有 4 字节块的 2 KB 直接映射指令高速缓存，重新排序指令将未命中减少了 50%，在 8 KB 高速缓存中减少了 75%。另一种代码优化旨在提高长缓存块的效率。对齐基本块以使入口点位于缓存块的开头可降低顺序代码缓存未命中的机会。这改善了参考的空间和时间局部性。
Now, looking at the data, there are even fewer restrictions on location than code. These transformations try to improve the spatial and temporal locality of the data. The general rule that is always adopted is that, once a data has been brought to cache, use it to the fullest possibility and then put it back in memory. We should not keep shifting data between the cache and main memory. For example, exploit the spatial locality of reference when accessing arrays. If arrays are stored in a row major order (column major order), then also access them accordingly, so that they will be available within the same block. We should not blindly stride through arrays in the order the programmer happened to place the loop. The following techniques illustrate these concepts.
循环交换：一些程序具有嵌套循环，以非顺序访问内存中的数据。简单地交换循环的嵌套可以使代码按照数据存储的顺序访问数据。假设数组不适合缓存，该技术通过提高空间局部性来减少未命中。完成的重新排序可以最大限度地利用高速缓存块中的数据，然后再将其丢弃。
/* 前 */
对于 (j = 0; j < 100; j = j+1)
对于 (i = 0; i < 5000; i = i+1)
x[i][j] = 2 * x[i][j];
/* 后 */
对于 (i = 0; i < 5000; i = i+1)
对于 (j = 0; j < 100; j = j+1)
x[i][j] = 2 * x[i][j];
原始代码会以 100 个字的步长跳过内存，而修订版在进入下一个块之前访问一个缓存块中的所有字。这种优化提高了缓存性能，而不会影响执行的指令数量。
循环融合：我们可以融合两个或多个对相同数据进行操作的循环，而不是在两个不同的循环中进行操作。目标再次是在从缓存中替换数据之前最大化对加载到缓存中的数据的访问。
/* 前 */
对于 (i = 0; i < N; i = i + 1)
对于 (j = 0; j < N; j = j + 1)
a [i][j] = 1/b [i][j] * c [i][j];
对于 (i = 0; i < N; i = i + 1)
对于 (j = 0; j < N; j = j + 1)
d [i][j] = a [i][j] + c [i][j];
/* 后 */
对于 (i = 0; i < N; i = i + 1)
对于 (j = 0; j < N; j = j + 1)
{a [i][j] = 1/b [i][j] * c [i][j];
d [i][j] = a [i][j] + c [i][j]; }
请注意，不是每次访问 a 和 c 时可能发生两次未命中，而是每次访问只有一次未命中。这种技术改进了参考的时间局部性。
阻塞：此优化尝试通过改进时间局部性来减少未命中。有时，我们可能必须同时访问行和列。因此，逐行（行主序）或逐列（列主序）存储数组并不能解决问题，因为在循环的每次迭代中都使用行和列。因此，以前的技术将无济于事。块算法不是对数组的整行或整列进行操作，而是对子矩阵或
块。目标是在替换数据之前最大限度地访问加载到缓存中的数据。下面的代码示例执行矩阵乘法，有助于解释优化：
/* 前 */
对于 (i = 0; i < N; i = i+1)
对于 (j = 0; j < N; j = j+1)
{r = 0;
对于 (k = 0; k < N; k = k + 1)
r = r + y[i][k]*z[k][j];
x[i][j] = r;
};
两个内部循环读取 z 的所有 N × N 个元素，重复读取 y 一行中相同的 N 个元素，并写入 x 的一行 N 个元素。图 28.5 显示了访问三个数组的快照。深色表示最近访问，浅色表示较旧访问，白色表示尚未访问。
容量未命中的数量显然取决于 N 和缓存的大小。如果它可以保存所有三个 N × N 矩阵，那么只要没有缓存冲突，我们就没有任何问题。如果缓存可以保存一个 N × N 矩阵和一行 N，那么至少第 i 行 y 和数组 z 可以留在缓存中。如果我们甚至不能在缓存中容纳它，那么 x 和 z 都可能发生未命中。在最坏的情况下，N3 次操作将访问 2N3 + N2 个内存字。
为了确保被访问的元素可以放入缓存中，原始代码更改为在大小为 B 乘 B 的子矩阵上进行计算。两个内部循环现在 以大小为 B 的步长计算，而不是 x 和 z 的全长。B 称为阻塞 因子。（假设 x 初始化为零。）
/* 后 */
for (jj = 0; jj < N; jj = jj+B)
对于 (kk = 0; kk < N; kk = kk+B)
对于 (i = 0; i < N; i = i+1)
for (j = jj; j < min(jj+B,N); j = j+1)
{r = 0;
对于 (k = kk; k < min(kk+B,N); k = k + 1)
r = r + y[i][k]*z[k][j];
x[i][j] = x[i][j] + r;
};
图 28.6 说明了使用阻塞对三个数组的访问。仅查看容量未命中，访问的内存字总数为 2N3/B + N2。这个总数是大约 B 倍的改进。因此，阻塞利用空间和时间局部性的组合，因为 y 受益于空间局部性，而 z 受益于时间局部性。
尽管我们的目标是减少缓存未命中，但也可以使用阻塞来帮助寄存器分配。通过采用较小的块大小以便块可以保存在寄存器中，我们可以最大限度地减少程序中加载和存储的数量。
总而言之，我们在这个模块中定义了平均内存访问时间。AMAT 取决于命中时间、未命中率和未命中惩罚。存在多种优化 来处理这些因素中的每一个。我们讨论了降低未命中率的五种不同技术。他们是：
更大的块大小
更大的缓存大小
更高的结合性
路预测和伪结合性，以及
编译器优化。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，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 年。