问题:

我正在尝试弄清楚如何编写一个代码(首选 C，只有在没有其他解决方案时才使用 ASM)在 50% 的情况下会导致分支预测失败。

因此，它必须是一段“免疫”与分支相关的编译器优化的代码，并且所有硬件分支预测不应超过 50%(抛硬币)。更大的挑战是能够在多 CPU 架构上运行代码并获得相同的 50% 未命中率。

我设法在 x86 平台上编写了一个达到 47% 分支未命中率的代码。我怀疑失踪者可能有 3% 来自:

• 其中包含分支的程序启动开销(虽然非常小)
• Profiler 开销 - 基本上每次读取计数器都会引发一个中断，因此这可能会增加额外的可预测分支。
• 在后台运行的系统调用包含循环和可预测的分支

我编写了自己的随机数生成器，以避免调用可能具有隐藏可预测分支的 rand。如果可用，它也可以使用 rdrand。延迟对我来说并不重要。

问题:

1. 我能比我的代码版本做得更好吗？更好意味着对所有 CPU 架构获得更高的分支错误预测和相同的结果。
2. 此代码可以谓词吗？这意味着什么？

代码:

#include <stdio.h>
#include <time.h>

#define RDRAND
#define LCG_A   1103515245
#define LCG_C   22345
#define LCG_M   2147483648
#define ULL64   unsigned long long

ULL64 generated;

ULL64 rand_lcg(ULL64 seed)
{
#ifdef RDRAND
    ULL64 result = 0;
    asm volatile ("rdrand %0;" : "=r" (result));
    return result;
#else
    return (LCG_A * seed + LCG_C) % LCG_M;
#endif
}

ULL64 rand_rec1()
{
    generated = rand_lcg(generated) % 1024;

    if (generated < 512)
        return generated;
    else return rand_rec1();
}

ULL64 rand_rec2()
{
    generated = rand_lcg(generated) % 1024;

    if (!(generated >= 512))
        return generated;
    else return rand_rec2();
}

#define BROP(num, sum)                  \
    num = rand_lcg(generated);          \
    asm volatile("": : :"memory");      \
    if (num % 2)                        \
        sum += rand_rec1();             \
    else                                \
        sum -= rand_rec2();

#define BROP5(num, sum)     BROP(num, sum) BROP(num, sum) BROP(num, sum) BROP(num, sum) BROP(num, sum)
#define BROP25(num, sum)    BROP5(num, sum) BROP5(num, sum) BROP5(num, sum) BROP5(num, sum) BROP5(num, sum)
#define BROP100(num, sum)   BROP25(num, sum) BROP25(num, sum) BROP25(num, sum) BROP25(num, sum)

int main()
{
    int i = 0;
    int iterations = 500000;    
    ULL64 num = 0;
    ULL64 sum = 0;

    generated = rand_lcg(0) % 54321;

    for (i = 0; i < iterations; i++)
    {
        BROP100(num, sum);
        // ... repeat the line above 10 times
    }

    printf("Sum = %llu\n", sum);
}

更新 v1:

按照 usr 的建议，我通过在脚本的命令行中改变 LCG_C 参数来生成各种模式。 我能够去 49.67% BP 错过。这对我的目的来说已经足够了，而且我有方法可以在各种架构上生成它。

最佳答案

如果您知道分支预测器的工作原理，那么您可能会遇到 100% 的错误预测。每次只取预测器的预期预测值，反其道而行之。问题是我们不知道它是如何实现的。

我了解到典型的预测器能够预测诸如 0,1,0,1 之类的模式。等等。但我确信模式的长度是有限度的。我的建议是尝试给定长度(例如 4)的每种模式，看看哪个最接近您的目标百分比。您应该能够同时瞄准 50% 和 100% 并且非常接近。需要对每个平台进行一次或在运行时进行此分析。

我怀疑分支总数的 3% 是否像您所说的那样在系统代码中。内核不会在纯 CPU 绑定(bind)的用户代码上占用 3% 的开销。将调度优先级提高到最大。

您可以通过生成一次随机数据并多次迭代相同数据来将 RNG 排除在游戏之外。分支预测器不太可能检测到这一点(尽管它显然可以)。

我将通过填写 bool[1 << 20] 来实现这一点使用我描述的零一模式。然后，您可以多次运行以下循环:

int sum0 = 0, sum1 = 0;
for (...) {
 //unroll this a lot
 if (array[i]) sum0++;
 else sum1++;
}
//print both sums here to make sure the computation is not being optimized out

您需要检查反汇编以确保编译器没有做任何聪明的事情。

我不明白为什么你现在的复杂设置是必要的。 RNG 可以排除在外，我不明白为什么需要这个简单的循环。如果编译器在玩诡计，您可能需要将变量标记为 volatile这使得编译器(更好:大多数编译器)将它们视为外部函数调用。

由于 RNG 现在不再重要，因为它几乎从未被调用过，您甚至可以调用操作系统的加密 RNG 来获取(任何人)无法与真正的随机数区分的数字。

关于c++ - 是否有导致 50% 分支预测未命中的代码？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28961405/