Как справиться с прогнозированием ветвлений при использовании переключателя в эмуляции ЦП

Наоборот, операторы switch скорее всего будут преобразованы в таблицы перехода, что означает, что они могут выполнять несколько ifs (для диапазона проверка) и одиночный прыжок. if не должны вызывать проблемы с прогнозированием ветвлений, потому что маловероятно, что у вас будет плохой код операции. Прыжок не так дружен с пайплайном, но в итоге он всего один на весь switch оператор..

Я не верю, что вы можете преобразовать длинную switch инструкцию кодов операций в любую другую форму, которая приведет к лучшей производительности. Это, конечно, если ваш компилятор достаточно умен, чтобы преобразовать его в таблицу переходов. Если нет, вы можете сделать это вручную.

Если вы сомневаетесь, примените другие методы и измерьте производительность.

Редактировать

Прежде всего, убедитесь, что вы не путаете предсказание ветвления и предсказание целевой ветви.

Предсказание ветвления работает исключительно с операторами ветвления. Он решает, будет ли условие ветвления неудачным или успешным. Они не имеют ничего общего с оператором перехода.

С другой стороны, предсказание цели ветвления пытается угадать, где закончится прыжок.

Таким образом, ваше утверждение «предсказатель ветвления никак не может предсказать скачок» должно звучать так: «предсказатель ветвления target никак не может предсказать скачок».

В вашем конкретном случае, я не думаю, что вы действительно можете избежать этого. Если бы у вас был очень небольшой набор операций, возможно, вы могли бы придумать формулу, охватывающую все ваши операции, подобные тем, которые выполняются в логических схемах. Однако при таком большом наборе инструкций, как у процессора, даже если бы это был РИСК, стоимость этих вычислений намного выше, чем штраф за один переход.

Поскольку ветви в вашем операторе 256-way switch плотно упакованы, компилятор реализует это как таблицу переходов, так что вы правы в том, что вы будете запускать неверное предсказание единственной ветви каждый раз, когда вы проходите через этот код (как косвенный переход не будет отображать какое-либо предсказуемое поведение). Штраф, связанный с этим, составит около 15 тактов на современном ЦП (Sandy Bridge) или, возможно, до 25 на более старых микроархитектурах, в которых отсутствует кэш микроопераций. Хороший справочник по такого рода вещам — «Ресурсы по оптимизации программного обеспечения» на agner.org. Страница 43 в разделе «Оптимизация программного обеспечения на C++» — хорошее место для начала.

http://www.agner.org/optimize/?e=0,34

Непрямой переход, вероятно, лучший способ декодирования инструкций.

На старых машинах, таких как, скажем, Intel P6 1997 года, непрямой переход, вероятно, приведет к неправильному предсказанию ветвления.

На современных машинах, таких как, скажем, Intel Core i7, есть предсказатель косвенного перехода, который довольно хорошо помогает избежать неправильного предсказания ветвления.

Но даже на старых машинах, не имеющих косвенного предсказателя ветвления, можно подшутить. Этот трюк, кстати, задокументирован в Руководстве по оптимизации кода Intel еще во времена Intel P6:

Вместо создания чего-то похожего на

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       jmp loop
    label_instruction_01h_SUB: ...
       jmp loop
    ...

сгенерировать код как

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_01h_SUB: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    ...

то есть заменить переход к началу цикла выборки/декодирования/выполнения инструкции кодом в начале цикла в каждом месте.

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

Большинство наборов инструкций имеют специальные шаблоны - например. на Intel x86 за инструкцией сравнения почти всегда следует ветвь.

Удачи и приятного времяпровождения!

(Если вам небезразлично, декодеры команд, используемые симуляторами наборов команд в промышленности, почти всегда выполняют дерево переходов по N или управляемый данными двойной переход по дереву таблиц N, при этом каждая запись в дереве указывает на к другим узлам или к функции для оценки.

О, и, возможно, я должен упомянуть: эти таблицы, эти операторы переключения или структуры данных генерируются специальными инструментами.

Дерево переходов по N, потому что бывают проблемы, когда количество случаев в таблице переходов становится очень большим - в инструменте mkIrecog (сделать распознаватель инструкций), который я написал в 1980-х, я обычно делал таблицы переходов до 64К. записи по размеру, т.е. скачки на 16 бит. Компиляторы того времени сломались, когда размер таблиц переходов превысил 16M (24 бита).

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

Я был очень агрессивен в mkIrecog, как я уже говорил, позволяя использовать до 32 бит в коммутаторе, хотя практические ограничения почти всегда останавливали меня на 16-24 битах. Я помню, что я часто видел первое декодирование как 16- или 18-битный переключатель (64K-256K записей), а все остальные декодирования были намного меньше, не больше 10 бит.

Хм: я разместил mkIrecog в Usenet примерно в 1990 году. /pub/unix/programming/misc/mkIrecog.tar.gz Вы можете увидеть используемые таблицы, если хотите. (Будьте добры: тогда я был молод. Я не могу вспомнить, был ли это Паскаль или Си. С тех пор я переписывал его много раз, хотя я еще не переписывал его для использования битовых векторов С++.)

Большинство других парней, которых я знаю, которые делают такие вещи, делают что-то побайтно за раз, то есть 8-битный, 256-й способ, ветвь или поиск по таблице.)

Я думал, что добавлю что-то, так как никто не упомянул об этом.

Конечно, непрямой прыжок, вероятно, будет лучшим вариантом.

Однако, если вы пойдете по пути N-compare, мне на ум приходят две вещи:

Во-первых, вместо сравнения N на равенство вы можете выполнить сравнение неравенства log(N), проверяя свои инструкции на основе их числового кода операции с помощью дихотомии (или проверяя число побитно, если пространство значений близко к заполнению). Это немного похоже на хеш-таблицу, вы реализуете статическое дерево, чтобы найти последний элемент.

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

Но я не вижу, чтобы это было быстрее, чем средний штраф в 15 циклов, если только у вас нет 99% MOV ​​и вы не поставили равенство для кода операции MOV перед другими тестами.