如何确定矩阵循环的行/列步幅以获得这些缓存命中率？

Question

给定 CPU：
L1缓存：4路，块大小= 32字节，缓存大小= 64KB，LRU（缓存替换策略）。
L2缓存：2路，块大小= 32字节，缓存大小= 512KB，LRU（缓存替换策略）。

数组：int32_t A[2048][128]; 因此元素大小为 4 个字节。

for(int k=0, k<50, k++)
   for(int i=0; i<2048; i+=Di)
       for(int j=0; j<128; j+=Dj)  
           S += A[i][j]^k;

对于常量 Di 和 Dj 的哪些值，我可以获得 L1 命中率 = 75% 和 L2 命中率大于 90%？

我尝试执行以下操作：
我知道对于 L1 缓存，地址是：offset = 5 位，set = 9 位。
因此，在 2^14 B = 2^12 元素之后，我们到达相同的集合（但以其他方式）。
在 L2 缓存中：offset = 5 位，set = 13 位。
因此，在 2^18 B = 2^16 个元素之后，我们到达相同的集合（但以其他方式）。 因为我们希望 L1 命中率 = 3/4 。所以我们将采用Dj=2。因此我们将得到任意 4 个元素：未击中、击中、击中、击中。 （L1 的任何块都可以包含 8 个元素）。

但我不知道如何确定 Di 的值。

Answer 1

理论背景

为了决定我们想要读取的内存行/列（步长）以获得所需的缓存命中/未命中率，我们需要了解 L1 和 L2 缓存如何工作以及输入参数的含义是什么我们是针对这个问题给出的。在这个问题中，我们已经有了最终的计算结果，但我将快速解释我们是如何得出这个数字的：

缓存是按块和集合组织的。每个集合可以包含n个块，因此我们将其称为“n路集合关联”缓存。在示例中，我们有 4 路和 2 路。块中字节的地址构造如下：

Cache address = INDEX[0:N] + OFFSET[0:M]

其中 INDEX 表示集合的索引，有 N 位，偏移量由块的大小确定，有 M 位。

从L1缓存开始，我们说这个缓存是“4路”的。这意味着缓存被组织成 32 字节的组，每个组可以映射到与其关联的 4 个不同的 L2 块。由于 L1 有 64KB，每个块都是 32 位，因此我们将有 2,048 个块 (64K/32)，或每组 512 个块 (2,048/4)。集合的地址由索引确定，因此我们的 L1 索引有 9 位（N = 9）。块中的字节由偏移量决定，由于我们有 32 个字节 (2^5)，因此我们将有 5 位 (M=5) 用于偏移量。

L2 缓存是“2 路”，512KB，32 位块，因此块数将为 16384 (512KB/32)，或 8,192 组 (16,384/2)，因此 N=13。由于 L2 块是 32 字节，因此偏移量将为 5 位 (M=5)。

解决方案

首先，我们假设缓存专用于 A 数组，即变量 k、i、j< /code> 和 S 存储在寄存器中，因此对它们的读写不会引起内存操作。

当执行指令 S += A[i][j]^k; 时，处理器需要从 i< 上的 A 中获取元素/code> 行和 j 列。假设我们刚开始执行，缓存是空的，因此当我们尝试访问A[i][j]时，CPU会尝试从L1加载值。由于 L1 是空的，因此 L1 将会“未命中”，这将导致 CPU 尝试从 L2 加载数据。 L2 也是空的，因此 L2 也“未命中”，CPU 会将整个块（32 字节）从内存移动到 L2，然后移动到 L1。

由于“A”是 32 位（4 字节），因此该块包含 8 个元素。如果后续读取都来自同一个块，则该块将已经在 L1 缓存中，因此我们将“命中”。这将为我们提供 7/8 的命中率 (87.5%)，这超出了我们的要求，因此为了降低比率并使其达到 3/4 (75%)，我们需要确保从 A 读取每个第二个元素（假设 A 与块大小边界对齐）。为此，我们需要选择 Dj 为 2。

为了确保保留 75%，我们需要确保 L1 将被覆盖，否则在下一个周期我们将找到这些值在缓存中，这将导致我们在后续周期中的命中率为 100%。只要我们确保在循环中读取超过 2,048 个块，这就不会成为问题，这意味着我们需要读取超过 8,192 (16,384/2) 个元素。为了确保这一点，我们将使用Di。

因此，根据我们目前所知，我们有：

   (max(i)/ Di) * (max(j)/Dj) * size(A[0][0]) / block size  > 2048   :>
   ((2048 * 128/2 * 4) / 32) / Di > 2048                             :> 
   16384 / Di > 2048                                                 :>
   Di < 16384/2048                                                   :>
   Di < 8                                                            :>
   1 <= Di < 8

这意味着 Di 需要是 1 到 7 之间的数字，以确保 L1 命中率保持在 75%。

此外，Di数的选择应保证L2命中率大于90%。

正如我们提到的，当 L1 为“未命中”时，CPU 将尝试从 L2 获取数据，正如我们之前所看到的，只有当 L1 位于块的第一个元素时才会发生这种情况。由于我们要求L2命中率> 90%，我们尽量让它接近100%。 L2 可以容纳 131,072 个元素，因此我们尝试在第一次运行时用元素填充缓存，然后在随后的 49 次运行（循环 k）中，我们将为每个元素命中缓存。这将为我们提供大约 98% 的命中率（超过 90%）。考虑到我们将从缓存中读取 128/Dj 元素，并且我们想要填充所有 13,1072 个元素，我们有以下约束：

    max(i) / Di = 131072 / max(j) / Dj  :>
    max(i) / Di = 131072 / 128 / 2      :>
    2048 / Di = 2048                    :>
    Di = 1

因此，如果我们选择 Di如果为 1，Dj 为 2，则 L1 上的缓存命中率为 75%，L2 上的命中率为 98%（这是所需的 90% 以上）。

事实上，由于外部循环（循环 k），任何小于 7 的 Di 数字都将为我们提供 98% 的缓存命中率，因为它将确保我们读取超过 2,048 个元素且小于或等于 131,072 个元素。

对真实 CPU 的更正

需要理解的重要一点是，当我们从包含数据的内存段中的数组“A”中获取数据时，我们还需要从内存中的代码段中获取指令。考虑到这一点，在真实的处理器中，对于为指令获取的数据量，高速缓存命中率将较低。

为了解决这个问题，我们假设将为代码保留一组块（一个“路”）。根据这一假设，我们的命中率可以高于所需的比率，但我们将确保该比率不低于所需的比率。

有了这个假设，我们将有 L1 而不是 2,048 个块和 512 个集合，我们将有 1,536 个组织在 512 个集合（3 路缓存）中，可用于“A”，而对于 L2，我们将有 1,536 个块，而不是组织在 8,192 个集合中的 16,384 个块，我们将有 8,192 个块组织在 8,192 个集合（或直接映射的缓存）中，可用于“A”。校正后，我们可以使用与上述相同的方法来查找 Di 和 Dj 的值。

校正后，Dj 的值不会改变，仍为 2，但 Di 将在 1 到 5 之间。