Есть ли код, который приводит к 50% -ному провалу прогноза ветвления?

Проблема:

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

Таким образом, это должна быть часть кода, которая "является imune" для оптимизаций компилятора, связанных с ветвлением, а также все предсказания ветвления 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 из командной строки в script. Я смог перейти на прохождение BP на 49,67%. Этого достаточно для моей цели, и у меня есть методология для создания этого на разных архитектурах.

Ответ 1

Если вы знаете, как работает предиктор отрасли, вы можете получить 100% -ное неверное предсказание. Просто принимайте ожидаемое предсказание предсказателя каждый раз и делайте противоположное. Проблема в том, что мы не знаем, как это реализовано.

Я читал, что типичные предсказатели способны прогнозировать такие параметры, как 0,1,0,1 и т.д. Но я уверен, что существует ограничение на то, как долго может быть шаблон. Мое предложение состояло бы в том, чтобы попробовать каждый узор определенной длины (например, 4) и посмотреть, какой из них наиболее близок к вашему целевому проценту. Вы должны быть в состоянии ориентироваться как на 50%, так и на 100% и очень близко. Это профилирование должно выполняться для каждой платформы один раз или во время выполнения.

Я сомневаюсь, что 3% от общего числа веток находятся в системном коде, как вы сказали. Ядро не занимает 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 вашей ОС, чтобы получить числа, которые неотличимы (от любого человека) от истинных случайных чисел.

Ответ 2

Заполните массив байтами и напишите цикл, который проверяет каждый байт и ветки в зависимости от значения байта.

Теперь внимательно изучите архитектуру вашего процессора и его предсказание ветвлений. Заполните начальные байты массива, чтобы после их изучения процессор находился в предсказуемом известном состоянии. Из этого известного состояния вы можете узнать, предвидится ли следующая ветвь или нет. Установите следующий байт, чтобы предсказание было неправильным. Опять же, выясните, предвидится ли следующая ветвь или нет, и установите следующий байт, чтобы предсказание было неправильным и так далее.

Если вы также отключите прерывания (что может изменить предсказание ветвления), вы можете приблизиться к 100% неверно предсказанным ветвям.

Как простой случай, на старом процессоре PowerPC с сильным/слабым предсказанием после трех принятых ветвей он всегда будет находиться в состоянии "сильный", а одна ветвь не будет изменена на "слабый". Если теперь у вас есть последовательность чередующихся не взятых/принятых ветвей, предсказание всегда неверно и переключается между слабыми, а не принятыми и слабыми.

Это, конечно, будет работать только с этим конкретным процессором. Большинство современных процессоров увидели бы эту последовательность почти на 100% предсказуемой. Например, они могут использовать два отдельных предиктора; один для случая "последняя ветвь была взята", а одна для случая "последняя ветвь не была взята". Но для такого процессора другая последовательность байтов даст тот же 100-процентный коэффициент неверного предсказания.

Ответ 3

Самый простой способ избежать оптимизации компилятора состоит в том, чтобы иметь void f(void) { } и void g(void) { } фиктивные функции в другом модуле перевода и отключить оптимизацию времени соединения. Это заставит if (*++p) f(); else g(); быть реальной непредсказуемой ветвью, предполагая, что p указывает на массив случайных булевых (это уменьшает проблему предсказания ветвления внутри rand()), просто делайте это до измерения)

Если цикл for(;;) дает вам проблемы, просто введите goto.

Обратите внимание, что "комментарий для циклического разворота" в комментарии несколько вводит в заблуждение. Вы создаете тысячи веток. Каждая ветвь будет индивидуально предсказана, за исключением того, что, вероятно, ни один из них не будет предсказан, так как процессор просто не может удерживать тысячи различных прогнозов. Это может быть или не быть полезной для вашей реальной цели.