Эта проблема:

Я пытаюсь выяснить, как написать код (предпочтительно C, ASM, только если нет другого решения), который быв 50% случаев пропустить прогноз ветвления.

Таким образом, это должен быть кусок кода, который «подходит» для оптимизаций компилятора, связанных с ветвлением, а также весь прогноз ветвления HW не должен идти лучше, чем 50% (подбрасывание монеты). Еще более сложная задача - запустить код наархитектура с несколькими процессорами и получите тот же коэффициент промаха 50%.

Мне удалось написать код, который идет кКоэффициент пропадания ветвей 47% на платформе x86. Я подозреваю, что без вести пропавшие могли 3% прибыть из:

Затраты на запуск программы с разветвлением (хотя и очень маленькие)Издержки профилировщика - в основном для каждого считываемого счетчика возникает прерывание, поэтому это может добавить дополнительные предсказуемые ветви.Системные вызовы, выполняющиеся в фоновом режиме, которые содержат циклы и предсказуемое ветвление

Я написал свой собственный генератор случайных чисел, чтобы избежать вызовов rand, реализация которого может иметь скрытые предсказуемые ветви. Можно также использоватьrdrand по мере доступности. Латентность не имеет значения для меня.

Вопросы:

Могу ли я сделать лучше, чем моя версия кода? Лучше означает получить более высокий прогноз ошибок и одинаковые результаты для всех архитектур ЦП.Может ли этот код бытьосновывается? Что бы это значило?

Код:

#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, Этого достаточно для моей цели, и у меня есть методология для создания этого на различных архитектурах.