19

我的任务是生成一定数量的数据缓存未命中和指令缓存未命中。我已经能够毫无问题地处理数据缓存部分。

所以我只剩下生成指令缓存未命中的工作了。我不知道是什么导致了这些。有人可以建议一种生成它们的方法吗？

我在 Linux 中使用 GCC。

4

5 回答 5

19

正如人们所解释的，指令缓存未命中在概念上与数据缓存未命中相同——指令不在缓存中。这是因为处理器的程序计数器 (PC) 已跳转到尚未加载到缓存中的位置，或者由于缓存已满而已被刷新，并且该缓存行是选择用于驱逐的缓存行（通常是最近用过的）。

手动生成足够的代码来强制指令未命中比强制数据缓存未命中要困难一些。

不费吹灰之力就能获得大量代码的一种方法是编写一个生成源代码的程序。

例如，编写一个程序来生成一个带有巨大 switch 语句的函数（在 C 中）[警告，未经测试]：

printf("void bigswitch(int n) {\n    switch (n) {");
for (int i=1; i<100000; ++i) {
    printf("        case %d: n += %d;\n", n, n+i/2);
}
printf("    }\n    return n;}\n");

然后你可以从另一个函数中调用它，你可以控制它沿着缓存线的跳跃量。

switch 语句的一个属性是代码可以被强制向后执行，或者通过选择参数以模式执行。所以你可以使用预取和预测机制，或者尝试对抗它们。

同样的技术也可以应用于生成许多函数，以确保可以随意“破坏”缓存。所以你可能有 bigswitch001、bigswitch002 等。你可以使用你也生成的开关来调用它。

如果您可以使每个函数（大约）具有一定数量的 i-cache 行大小，并且还可以生成比缓存中容纳的更多的函数，那么生成指令缓存未命中的问题将变得更容易控制。

您可以通过转储汇编程序（使用 gcc -S）或 objdump .o 文件来准确查看函数、整个 switch 语句或 switch 语句的每个分支有多大。因此，您可以通过调整case:语句的数量来“调整”函数的大小。您还可以通过明智地选择 bigswitchNNN() 的参数来选择命中多少缓存行。

于 2012-03-20T23:58:28.390 回答
10

除了这里提到的所有其他方法之外，另一个非常可靠的强制指令缓存未命中的方法是使用自修改代码。

如果您写入内存中的一页代码（假设您将操作系统配置为允许这样做），那么相应的指令缓存行当然会立即变得无效，并且处理器被迫重新获取它。

顺便说一下，导致 icache 未命中的不是分支预测，而是简单的分支。每当处理器尝试运行最近未运行的指令时，您就会错过指令缓存。现代 x86 足够智能，可以按顺序预取指令，因此您不太可能通过从一条指令向前移动到下一条指令来错过 icache。但是任何分支（有条件的或其他的）都会乱序跳转到新地址。如果新的指令地址最近没有运行，并且不在你已经运行的代码附近，它很可能超出缓存，处理器必须停止并等待指令从主 RAM 进入。这与数据缓存完全相同。

一些非常现代的处理器（最近的 i7）能够查看代码中即将出现的分支并启动 icache 预取可能的目标，但许多不能（视频游戏控制台）。从主 RAM 获取数据到 icache 与管道的“指令获取”阶段完全不同，这就是分支预测的内容。

“指令获取”是 CPU 执行管道的一部分，是指将操作码从 icache 带入 CPU 的执行单元，在那里它可以开始解码和工作。这与“指令高速缓存”获取不同，后者必须提前多个周期发生，并且涉及高速缓存电路向主存储器单元发出请求以通过总线发送一些字节。第一个是 CPU 流水线的两个阶段之间的交互。第二个是流水线与内存缓存和主 RAM 之间的交互，这是一个更复杂的电路。这些名称令人困惑地相似，但它们是完全独立的操作。

因此，导致指令缓存未命中的另一种方法是编写（或生成）许多非常大的函数，这样您的代码段就会很大。然后疯狂地从一个函数调用到另一个函数，这样从 CPU 的角度来看，你正在对内存进行疯狂的 GOTO。

于 2012-03-21T00:03:57.473 回答
3

您的项目需要了解目标系统的缓存硬件，包括但不限于其缓存大小（缓存的整体大小）、缓存行大小（最小的可缓存实体）、关联性以及写入和替换策略。任何设计用于测试缓存性能的真正好的算法都必须考虑所有这些，因为没有一个通用算法可以有效地测试所有缓存配置，尽管您可以设计一个有效的参数化测试例程生成器，它可能会生成一个合适的测试例程，给出足够多的关于给定目标缓存架构的细节。尽管如此，我认为我下面的建议是一个很好的一般情况测试，但首先我想提一下：

您提到您有一个有效的数据缓存测试，它使用“大整数数组 a[100].... [访问] 元素，使得两个元素之间的距离大于缓存行大小（在我的情况下是 32 个字节）。” 我很好奇您如何确定您的测试算法有效，以及您如何确定有多少数据缓存未命中是您的算法的结果，而不是其他刺激引起的未命中。实际上，对于 100*sizeof(int) 的测试数组，您的测试数据区域在当今大多数通用平台上只有 400 字节长（如果您在 64 位平台上可能是 800 字节，或者如果您使用的是 200 字节） '正在使用 16 位平台）。对于绝大多数缓存架构，整个测试阵列将多次放入缓存中，

关于指令缓存：其他人建议使用大型 switch()-case 语句或函数调用不同位置的函数，如果不仔细（我的意思是小心地）设计代码的大小，这两种方法都不会有效不同位置的功能的相应案例分支或位置和大小。这样做的原因是整个内存中的字节以一种完全可预测的模式“折叠”（技术上，“相互别名”）缓存。如果您仔细控制 switch()-case 语句的每个分支中的指令数量，您可能会在测试中取得进展，但如果您只是在每个分支中抛出大量不加选择的指令，

我猜你对汇编代码并不太熟悉，但你必须相信我，这个项目正在为它尖叫。相信我，我不是在不需要的地方使用汇编代码的人，而且我非常喜欢在 OO C++ 中编程，尽可能使用 STL 和多态 ADT 层次结构。但是在您的情况下，确实没有其他万无一失的方法可以做到这一点，并且汇编将为您提供对您真正需要的代码块大小的绝对控制，以便能够有效地生成指定的缓存命中率。您不必成为汇编专家，甚至可能不需要学习实现 C 语言序言和结语所需的指令和结构（Google 为“C 可调用汇编函数”）。你为你的汇编函数编写了一些外部“C”函数原型，你走了。如果您确实想学习一些汇编，那么您在汇编函数中放入的测试逻辑越多，您对测试施加的“海森堡效应”就越少，因为您可以仔细控制测试控制指令的位置（因此它们对指令缓存的影响）。但是对于你的大部分测试代码，你可以只使用一堆“nop”指令（指令缓存并不真正关心它包含什么指令），并且可能只是将处理器的“return”指令放在每个指令的底部代码块。

现在假设您的指令缓存为 32K（按照今天的标准，这非常小，但在许多嵌入式系统中可能仍然很常见）。如果您的缓存是 4 路关联的，您可以创建 8 个独立的内容相同的 8K 汇编函数（希望您注意到的是 64K 的代码，缓存大小的两倍），其中大部分只是一堆 NOP 指令. 您使它们在内存中一个接一个地下降（通常通过简单地在源文件中一个接一个地定义）。然后，您使用仔细计算的序列从测试控制函数中调用它们，以生成您想要的任何缓存命中率（具有相当粗略的粒度，因为每个函数都是完整的 8K 长）。如果你一个接一个地调用第 1、2、3 和 4 个函数，你知道你已经用这些测试函数的代码填充了整个缓存。此时再次调用其中任何一个都不会导致指令缓存未命中（测试控制函数自己的指令驱逐的行除外），但调用其他任何一个（第 5、第 6、第 7 或第 8；让我们只是选择第 5 个）将驱逐其他之一（尽管驱逐哪一个取决于您的缓存的替换策略）。在这一点上，你唯一可以打电话并且知道你不会驱逐另一个人的是你刚刚打电话的人（第 5 个），唯一你可以打电话知道你会驱逐另一个人的是你还没有打电话的人称为（第 6、第 7 或第 8）。为了使这更容易，只需维护一个大小与您拥有的测试函数数量相同的静态数组。要触发驱逐，请调用数组末尾的函数并将其指针移动到数组的顶部，将其他指针向下移动。要不触发驱逐，请调用您最近调用的那个（在数组顶部的那个；在这种情况下，请确保不要将其他的下移！）。如果您需要更精细的粒度，请对此进行一些更改（可能制作 16 个单独的 4K 组装功能）。当然，所有这些都取决于测试控制逻辑的大小与缓存的每个关联“路”的大小相比是微不足道的；对于更积极的控制，您可以将测试控制逻辑放在测试函数本身中，但是为了完美控制，您必须完全设计控制逻辑而没有内部分支（仅在每个组装函数结束时分支），但我认为我会在这里停下来，因为这可能会使事情过于复杂。在这种情况下，请务必不要将其他人向下移动！）。如果您需要更精细的粒度，请对此进行一些更改（可能制作 16 个单独的 4K 组装功能）。当然，所有这些都取决于测试控制逻辑的大小与缓存的每个关联“路”的大小相比是微不足道的；对于更积极的控制，您可以将测试控制逻辑放在测试函数本身中，但是为了完美控制，您必须完全设计控制逻辑而没有内部分支（仅在每个组装函数结束时分支），但我认为我会在这里停下来，因为这可能会使事情过于复杂。在这种情况下，请务必不要将其他人向下移动！）。如果您需要更精细的粒度，请对此进行一些更改（可能制作 16 个单独的 4K 组装功能）。当然，所有这些都取决于测试控制逻辑的大小与缓存的每个关联“路”的大小相比是微不足道的；对于更积极的控制，您可以将测试控制逻辑放在测试功能本身中，但为了完美控制，您必须完全设计控制逻辑而无需内部分支（仅在每个组装功能结束时分支），但我认为我会在这里停下来，因为这可能会使事情过于复杂。当然，所有这些都取决于测试控制逻辑的大小与缓存的每个关联“路”的大小相比是微不足道的；对于更积极的控制，您可以将测试控制逻辑放在测试功能本身中，但为了完美控制，您必须完全设计控制逻辑而无需内部分支（仅在每个组装功能结束时分支），但我认为我会在这里停下来，因为这可能会使事情过于复杂。当然，所有这些都取决于测试控制逻辑的大小与缓存的每个关联“路”的大小相比是微不足道的；对于更积极的控制，您可以将测试控制逻辑放在测试功能本身中，但为了完美控制，您必须完全设计控制逻辑而无需内部分支（仅在每个组装功能结束时分支），但我认为我会在这里停下来，因为这可能会使事情过于复杂。

即开即用且未经测试，x86 的一个汇编函数的全部可能如下所示：

myAsmFunc1:
   nop
   nop
   nop  # ...exactly enough NOPs to fill one "way" of the cache
   nop  # minus however many bytes a "ret" instruction is (1?)
   .
   .
   .
   nop
   ret  # return to the caller

对于 PowerPC，它可能看起来像这样（也未经测试）：

myAsmFunc1:
   nop
   nop
   nop   # ...exactly enough NOPs to fill one "way" of the cache
   .     # minus 4 bytes for the "blr" instruction.  Note that
   .     # on PPC, all instructions (including NOP) are 4 bytes.
   .
   nop
   blr   # return to the caller

在这两种情况下，调用这些函数的 C++ 和 C 原型都是：

extern "C" void myAsmFunc1();    // Prototype for calling from C++ code
void myAsmFunc1(void);           /* Prototype for calling from C code */

根据您的编译器，您可能需要在汇编代码本身的函数名称前加上下划线（但在您的 C++/C 函数原型中不需要）。

于 2012-03-21T01:27:39.190 回答
0

对于指令缓存未命中，您需要执行相距较远的代码段。在多个函数调用之间拆分您的逻辑将是一种方法。

于 2012-03-20T20:01:52.870 回答
-1

在不可预测的条件（例如输入或随机生成的数据）上的 if else 链，在 if 情况和 else 情况下都有大量指令，其大小大于缓存行。

于 2012-03-20T19:59:03.757 回答