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

Question

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

Похоже, в некоторых случаях это было бы очень расточительно. Например, предположим, что у вас есть одиночный оператор if с очень простым телом, скомпилированный до 1 инструкции CPU. Предложение if будет скомпилировано в условный переход вперед одной инструкцией. Если процессор предсказывает, что ветвь не будет принята, то он начнет выполнять инструкцию if-body и может немедленно начать выполнение следующих инструкций. Теперь, когда оценка условия if достигла конца конвейера, что может быть, скажем, через 12 циклов, ЦПУ теперь знает, было ли это предсказание верным или неправильным. Если он был неверно предсказан, а ветвь фактически была взята, то ЦП действительно должен отбросить только одну инструкцию из конвейера (ту, которая находится в теле if). Однако, если он сбрасывает весь конвейер, то вся работа, которая была выполнена по следующим инструкциям, также была потрачена впустую, и будет повторяться без причины. Это много потраченных впустую циклов на глубоко конвейерной архитектуре.

Так есть ли у современных процессоров какой-либо механизм, позволяющий отбрасывать только те немногие инструкции, которые находятся внутри короткого тела if? Или это действительно промывает весь трубопровод? Если это последнее, то я полагаю, что использование инструкции условного перемещения улучшит производительность. Кроме того, кто-нибудь знает, хороши ли современные компиляторы в преобразовании коротких операторов if в команды cmov?

Answer 1

Большинство процессоров общего назначения очищают конвейер от неправильного предсказания ветвления. Негативное влияние на производительность условных переходов мотивировало предложения о стремительном выполнении (где оба пути выполняются, а правильный путь выбирается позже) и динамическом предикации (где указываются инструкции в тени перехода) в дополнение к обширным исследованиям по прогнозированию переходов (а также как и другие техники). ( На странице Марка Смотермана о стремительном исполнении представлены некоторые подробности и ссылки. Я хотел бы добавить в качестве важного документа Хесун Ким и др. "Желания ветвлений: объединение условного ветвления и предсказания для адаптивного предсказанного исполнения", 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. Хотя большая часть этого предназначена для кодирования команд, выгода от предикации для высокопроизводительных реализаций предположительно относительно низкая.)

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

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

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

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

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

Answer 2

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

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

---

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

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

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

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