如何引起指令高速缓存未命中？

Question

如何引起指令高速缓存未命中？

clinuxperformancemicroprocessors

22

我被委托生成一定数量的数据缓存未命中和指令缓存未命中。我已经顺利处理了数据缓存部分。

所以我现在需要生成指令缓存未命中，但我不知道是什么原因导致的。有人可以建议一种生成方法吗？

我在Linux上使用GCC。

- William the Pleaser

1

分支预测是一个值得关注的话题：http://zh.wikipedia.org/wiki/%E5%88%86%E6%94%AF%E9%A2%84%E6%B5%8B器 - Ed S.

你能否分享一下如何生成数据缓存未命中的代码？ - Guru Prasad

许多架构都有一条指令来使特定的缓存行失效。您可以使用内联汇编或内部函数来执行相应的指令。 - Nate Eldredge

6个回答

11

除了其他提到的方式外，强制指令缓存未命中的另一种非常可靠的方式是使用自修改代码。

如果您将代码写入内存中的页面（假设您配置了操作系统以允许此操作），那么相应的指令缓存行立即变为无效状态，并且处理器被迫重新获取该行。

顺便说一下，引起icache未命中的不是分支预测，而只是分支跳转。每当处理器尝试运行最近未运行过的指令时，都会错过指令缓存。现代x86足够聪明，可以按顺序预取指令，因此您很难仅通过普通地从一个指令向前推进到下一个指令来错过icache。但是，任何分支（有条件或没有条件）都会跳转到一个新地址（顺序不同）。如果新的指令地址最近未运行，并且不靠近您已经运行的代码，则很可能会超出缓存范围，处理器必须停止并等待从主RAM中获取指令。这与数据缓存完全相同。

一些非常现代的处理器（如新的i7）能够查看代码中即将到来的分支并开始icache预取可能的目标，但是许多处理器不能这样做（例如视频游戏主机）。从主RAM中提取数据到icache与流水线的“指令获取”阶段完全不同，后者是关于分支预测的。

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

导致指令缓存未命中的另一种方法是编写（或生成）大量非常大的函数，使得您的代码段变得庞大。然后从一个函数狂呼另一个函数，这样从CPU的角度来看，您正在内存中执行疯狂的GOTO操作。

- Crashworks

2

@MooingDuck 并没有。你会获得一个函数指针，将其强制转换为 char *，并通过它编写一些指令。当然，这完全是“未指定行为”，但如果你知道你在做什么，它仍然可以工作。我以前用它来动态构建 DMA 链和顶点着色器。 - Crashworks

你需要了解你处理器的机器码，并且不能出错。这是可以做到的，但非常困难。 - Mooing Duck

仅仅将相同的数据写入代码内存（即将代码复制到内存缓冲区，然后将该缓冲区复制回去）是否足以强制使指令高速缓存失效？我想缓存控制可能不够复杂，无法检测到这些写操作实际上正在改变任何内容（但我可能猜错了）。 - Michael Burr

@MichaelBurr 这是个好主意！你可能是对的。虽然我只是猜测，但我不太了解英特尔icache的内部电路。 - Crashworks

@Crashworks：在任何安全平台上，修改已映射到内存中的现有代码都是困难或不可能的，创建一个新的可执行内存块也是如此。这至少需要使用mprotect或等效功能... - R.. GitHub STOP HELPING ICE

显示剩余3条评论

4

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

您提到您有一个使用“大整数数组a[100]…”的工作数据缓存测试，该数组“以使两个元素之间的距离大于缓存行大小（在我的情况下为32字节）”的方式访问元素。我很好奇您是如何确定您的测试算法是否有效以及您是如何确定有多少数据缓存未命中是由您的算法引起的，而不是由其他刺激引起的。实际上，对于大多数通用平台，您的测试数据区域仅有400字节长（如果您在64位平台上，则可能为800字节，如果您使用16位平台，则为200字节）。对于绝大多数缓存架构，整个测试数组将多次适合于缓存，这意味着对数组的随机访问将在大约（400/缓存行大小）*2次访问中将整个数组带入缓存，并且除了硬件或操作系统滴答定时器中断弹出一些或所有已缓存的数据之外，每次访问都将是一个缓存命中，无论您如何排序访问。

关于指令缓存：其他人建议使用大型switch() -case语句或调用分散位置的函数，这两种方法都不能预测地有效，除非仔细（我是说小心翼翼地）设计相应情况分支代码的大小或分散位置和函数的大小。原因是内存中的字节会以完全可预测的模式“折叠”到（在技术上，“别名一个另一个”）缓存中。如果您仔细控制switch() -case语句中每个分支中的指令数量，您可能会通过测试，但如果您只是在每个分支中随意添加大量指令，则不知道它们将如何折叠到缓存中，以及switch() -case语句的哪些情况会别名彼此以便将它们驱逐出缓存。

我猜你对汇编代码不是很熟悉，但你必须相信我，这个项目非常需要它。相信我，我不会在不必要的情况下使用汇编代码，我强烈倾向于使用面向对象的C++编程，尽可能使用STL和多态ADT层次结构。但在你的情况下，没有其他可靠的方法来做到这一点，汇编将为你提供绝对控制代码块大小的能力，以便有效地生成指定的缓存命中率。你不需要成为一个汇编专家，甚至可能不需要学习实现C语言序言和尾声所需的指令和结构（请Google搜索“C-callable assembly function”）。你可以为你的汇编函数编写一些extern "C"函数原型，然后就可以开始了。如果你想学习一些汇编知识，越多的测试逻辑放在汇编函数中，你就越少会给你的测试带来“Heisenberg效应”，因为你可以精确控制测试控制指令的位置（从而控制其对指令缓存的影响）。但对于大部分的测试代码，你只需要使用一堆“nop”指令（指令缓存并不关心它包含什么指令），并且可能只需要在每个代码块的底部放置处理器的“返回”指令即可。

现在假设你的指令缓存为32K（按今天的标准来说相当小，但在许多嵌入式系统中可能仍然很常见）。如果你的缓存是4路组相联，则可以创建8个相同内容的8K汇编函数（你可能已经注意到这是64K的代码，是缓存大小的两倍），其中大部分只是一堆NOP指令。你让它们在内存中一个接一个地排列（通常只需在源文件中依次定义每个函数）。然后，使用精心计算的序列从测试控制函数调用它们，以生成任何所需的缓存命中率（由于每个函数都有完整的8K长度，因此粒度相当粗糙）。如果依次调用第1、2、3和4个函数，则知道已使用这些测试函数的代码填充了整个缓存。此时再调用它们中的任何一个将不会导致指令缓存未命中（除了被测试控制函数本身的指令驱逐的行之外），但调用其他任何一个（第5、6、7或8个；我们选择第5个）将驱逐其他一个（但驱逐哪一个取决于您的缓存替换策略）。此时，您唯一可以调用并且知道不会驱逐其他函数的是刚刚调用的那个（第5个），而您唯一可以调用并且知道会驱逐其他函数的是尚未调用的一个（第6、7或8个）。为了使这更容易，只需维护一个静态数组，其大小与您拥有的测试函数数量相同。要触发驱逐，请调用数组末尾的函数，并将其指针移动到数组顶部，将其他函数向下移动。要不触发驱逐，请调用最近调用的函数（即在数组顶部的函数；请确保在这种情况下不要将其他函数向下移动！）。如果需要更精细的粒度，可以进行一些变化（例如创建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函数原型中加下划线）。

- phonetagger

我认为switch语句中的语句不应该很大或任意。如果在每个case:中使用非常简单的语句，例如n += 16bitint;，那么可以使每个case:的大小规则和可预测，并且控制函数的大小。 - gbulmer

@gbulmer：好的，我同意...至少在原则上是这样。我猜测试函数不必太大；你只需要创建至少n+1个这样的函数或case子句，其中n是缓存中关联“路径”的数量。但为了有效，它们必须在内存中完美地间隔，以便它们在缓存中彼此别名。这在“高”级源代码（C或C++）中很难做到，因为你实际上无法控制编译后的高级源代码函数中任何指令的位置。或者按照我上面描述的确定和简单的方法去做。 - phonetagger

请不要误解。我并不是在说这些东西很琐碎，但我认为汇编语言对于这些问题来说并非必需，甚至在某种程度上也不可取。我还认为，让人们学会如何以非传统的方式运用他们的技能是非常棒的；在我看来，人们可以快速提高他们的理解深度，这既令人兴奋又能完成工作。让我思考一下。我将尝试用高级工具的知识来解决问题。我想我可以做到，但我非常饥饿 :-) - gbulmer

现在回到ICACHE测试的内容：没有什么好理由使用switch-case结构或一堆虚拟函数，因为你需要经历多次迭代（编译、检查每个case的代码大小、调整代码、重复）直到得到合适大小的代码块，以便在正确的顺序中调用时能够互相驱逐。这种方式没有任何好处，因为它比从一开始就编写一堆适当大小的汇编函数更困难，因为你对汇编函数的大小有绝对控制权。 - phonetagger

在我的3月21日12:27的评论中，我承认在内存中完美地分隔小测试函数可以用于驱逐彼此。这将允许您引起icache未命中，但它不会帮助实现（如果有这样的目标）近似指定的缓存命中率。要做到这一点，您必须控制导致驱逐的执行指令的比率，并且您的测试控制函数的指令计数为已执行的指令。 "测试函数"与"测试控制函数"指令的比率越高，您控制的缓存命中率的准确性就越高。因此，较大的汇编函数更好。 - phonetagger

显示剩余2条评论

0

对于指令高速缓存未命中，您需要执行远离的代码段。将逻辑分割成多个函数调用是一种方法。

- AShelly

你的缓存有多大？我的处理器缓存可容纳128位，最多可存放8条指令。 TMS320C28x - AShelly

我认为这是一个缓存行，现代处理器的指令缓存应该会更大一些。 - Mooing Duck

英特尔 Atom 拥有 32k 的指令缓存（比我想象的还要多得多） - Mooing Duck

这个150Mhz的DSP并不是一个现代处理器 :) - AShelly

2

在这种情况下，几乎任何代码都会导致指令缓存未命中 :( - Mooing Duck

0

我正在使用ARM M7 CPU进行类似的实验，以探究Playdate硬件的能力，并尝试确认指令缓存的大小和行为。

我做了与@phonetagger's answer类似的事情，使用内联汇编创建已知大小的函数。我认为最好生成许多小函数，因为没有分支的大函数将允许分支预测逻辑无误地工作，并且非常有效地预加载指令缓存。

我的当前测试场景基于一个包含256个函数指针的表格，每个指针指向一个64字节长或两个缓存行（在ARM M7的情况下）的函数。总共，这256个函数占用256 x 64 = 16K的内存，这是4K指令缓存大小的四倍 - 基于data sheet，我认为这符合Playdate中的部分，该数据表还表明指令缓存是2路关联的。

我的测试策略是反复运行一些功能，这些功能加起来达到已知的内存量，并变化覆盖的内存量以评估当所有东西都适合缓存和不适合缓存时的时间。例如，要测试2K指令内存，我需要运行2048/64 = 32个函数，因此我的代码将是：

int n = 32;
for (int calls = 0; calls < 100000; calls++)
{
    functable[calls%n]();
}

我进行了100,000次调用，以确保它需要足够长的时间才能获得一致的计时。显然，循环逻辑也在运行，但这只应该消耗几个缓存行，因此不应该对结果产生太大影响。

我重复上述测试，n从1到256运行，因此测试64字节到16K指令的时间。以下是结果：

我对以下几点感到困惑：

为什么在时间花费方面会有一个早期的峰值，达到并略高于1K标记？
为什么性能在8K标记处开始下降，而不是我从4K缓存大小预期的4K标记处下降？
为什么性能没有更大的下降？当明显缺失缓存时，性能超过一半。从玩弄数据缓存中，我预计缓存加载时间会比这更显著。

我所有的函数都是按照线性方式排列在内存中，所以我想知道CPU是否正在预取后续函数，因此我尝试以随机顺序调用函数。在开始计时循环之前，我使用插入排序来随机化函数表中前n个条目。结果非常相似，但令人惊讶的是，时间花费的早期峰值 - 虽然仍然存在 - 比线性顺序情况下要低。

总之，我认为我的过程相当可靠，但我对结果感到困惑，并希望获得额外的见解。

- yoyo

-1

一个由 if else 组成的链，其条件不可预测（例如输入或随机生成的数据），if 情况和 else 情况中包含的指令数量都比缓存行大。

- selalerer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gbulmer · Accepted Answer

正如其他人已经解释过的那样，指令缓存未命中与数据缓存未命中在概念上是相同的——指令不在缓存中。这是因为处理器的程序计数器（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等。您可以使用还生成的switch来调用它。

如果您可以使每个函数（大约）占据一些i-cache行的大小，并且生成的函数多于可以容纳的函数，则生成指令缓存未命中的问题更容易控制。

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