Сбрасывает ли ошибочное предсказание ветвление весь конвейер, даже для очень короткого тела оператора if?

Большинство универсальных процессоров действительно очищают конвейер при неверном предсказании ветвления. Негативное влияние условных переходов на производительность побудило предложения по активному выполнению (где оба пути выполняются, а правильный путь выбирается позже) и динамическому предсказанию (где предсказываются инструкции в тени ветвления) в дополнение к обширным исследованиям прогнозирования ветвлений (а также как и другие техники). (Страница Марка Смотермана о нетерпеливом исполнении содержит некоторые подробности и ссылки. Я бы добавил Хесун Ким и др. «Ветви желаний: сочетание условного ветвления и предсказания для адаптивного предсказанного выполнения», 2005 г., в качестве важной статьи.)

IBM POWER7, по-видимому, является первым массовым процессором, который реализует что-то более сложное, чем предварительная выборка альтернативного пути (например, активная выборка), и обрабатывает только один регистр инструкции. (POWER7 использует оценку достоверности предсказания ветвления, чтобы выбрать, использовать ли предсказание или предсказывать.)

У нетерпеливого исполнения есть очевидная проблема резкого увеличения использования ресурсов. Даже с избирательным рвением, основанным на достоверности предсказания ветвления, глубине предположений и доступности ресурсов (информация, доступная для внешнего интерфейса), легко может быть более эффективным спекулировать глубже на одном пути. Обнаружение точек соединения нескольких путей и избежание чрезмерных избыточных вычислений также может добавить сложности. (В идеале независимые от управления операции должны выполняться только один раз, а объединение и поток данных должны быть оптимизированы, но такая оптимизация добавляет сложности.)

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

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

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

В качестве примера рассмотрим скалярный конвейер (инструкции без ветвления на цикл равны 1,0) с разрешением ветвлений в конце восьмого этапа и без штрафа за перенаправление выборки на правильно спрогнозированных взятых ветвях, обрабатывая переходы с одной инструкцией. Предположим, что точность предсказателя перехода составляет 75% (без смещения по направлению) для таких коротких прямых переходов (2% инструкций, выполняемых в 30% случаев) и 93% точности для других переходов (18% инструкций). Восемь циклов будут сохранены для коротких ветвей, которые будут ошибочно предсказаны как взятые (17,5% таких ветвей; 0,35% инструкций), семь циклов, если они будут ошибочно предсказаны как невыполненные (7,2%; 0,144%), и один цикл будет потерян, если правильно прогнозируется как принято (22,5%; 0,45%). Всего будет сохранено 0,03358 циклов на инструкцию. Без этой оптимизации количество циклов на инструкцию составило бы 1,2758.

(Хотя приведенные выше числа приведены только для примера, они, вероятно, не далеки от реальности, за исключением IPC 1.0 для инструкций без ветвления. Предоставление небольшого кэша цикла уменьшит штраф за неправильное предсказание (и сэкономит энергию в коротких циклах), поскольку доступ к кешу инструкций вероятно, будет три из восьми циклов. Добавление эффекта промахов в кэше еще больше снизит процентное улучшение от этой оптимизации ветвления. Избегание накладных расходов для прогнозируемых "сильно занятых" коротких ветвей может иметь смысл.)

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

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

Реализация вне очереди также не остановится, когда условие ветвления недоступно. Это компромисс между зависимостью элемента управления и зависимостью данных. При точном прогнозировании ветвлений зависимость управления чрезвычайно недорога, но зависимость данных может задерживать продвижение вперед, ожидая операндов данных. (Конечно, с булевой зависимостью данных предсказание значения становится несколько более привлекательным. Использование предсказания предиката может быть желательным в некоторых случаях и будет иметь преимущество перед простым предсказанием с использованием динамических оценок стоимости и достоверности.)

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

Проблемы с компилятором

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

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

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

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

Современные высокопроизводительные ЦП, вышедшие из строя, обычно не очищают весь конвейер ⁰ из-за неверного прогноза, но на самом деле это не зависит от расстояния ответвления или работы, как вы предлагаете.

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

Это означает, что стоимость перехода по крайней мере частично связана с окружающими инструкциями: если условие перехода можно проверить раньше, влияние ошибочного предсказания может быть ограничено или даже равно нулю ¹ . С другой стороны, если условие ветвления обрабатывается поздно, после того, как значительные ресурсы были потрачены на неправильный путь, стоимость может быть большой (например, больше, чем штраф за ошибочное предсказание «опубликованного» перехода за 12-20 циклов, который вы часто увидите ).

⁰ Здесь обсуждается точная терминология: значение очистки конвейера не совсем понятно для вышедших из строя процессоров. Здесь я имею в виду, что ЦП не сбрасывает все текущие, но, возможно, не выполненные инструкции.

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

«Если он предсказал неверно и ветвление было действительно выполнено, то ЦП действительно должен отбросить только одну инструкцию из конвейера (ту, что находится в теле if)».

Это не так просто, как вы думаете. Инструкции изменяют различные состояния в архитектуре, от которых зависят другие инструкции (результаты регистров, флаги условий, память и т. Д.). К тому времени, когда вы поймете, что ошиблись в своем прогнозе, у вас потенциально может быть множество инструкций в конвейере, которые начали выполнение в зависимости от состояния, измененного этими инструкциями и всеми последующими инструкциями в конвейере ... Не говоря уже об инструкциях, которые могут вызывать неисправности / исключения.

Простой пример:

b = 0
f (a == 0) {
    b = 1;
}
c = b * 10;
if (b == 0)
    printf("\nc = %d.",c);
foo(b);
etc..

Чтобы отменить эту «одну простую инструкцию», потребовалось бы много работы.

Для простых ветвей с плохой предсказуемостью предпочтительно использовать predication / cmovs / etc.

По крайней мере, с большинством процессоров неверно предсказанная ветвь очищает весь конвейер.

Это большая часть того, почему многие (большинство?) Современных процессоров также предоставляют предопределенные инструкции.

В ARM большинство инструкций являются предикативными, то есть сама инструкция может включать условие, по сути, «сделай X, но только если следующее условие истинно».

Аналогичным образом, недавние итерации x86 / x64 включают некоторые предикативные инструкции, такие как «CMOV» (условное перемещение), которые работают одинаково - выполняйте инструкцию только при выполнении условия.

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

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

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