Почему Intel изменила механизм статического прогнозирования ветвлений за эти годы?

Question

Почему Intel изменила механизм статического прогнозирования ветвлений за эти годы?

Отсюда я знаю, что Intel внедрила несколько статических механизмов прогнозирования ветвлений в эти годы:

80486 возраст: всегда не принимается
Pentium4 возраст: назад взяты / вперед не взяты
Новые процессоры, такие как Ivy Bridge, Haswell, становятся все более неосязаемыми, см . Эксперимент Мэтта Джи здесь.

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

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

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

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

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

27

x86 compiler-construction cpu-architecture intel branch-prediction

Источник

user5413164 13 авг '18 в 12:46

3 ответа

Другие вопросы по тегам x86 compiler-construction cpu-architecture intel branch-prediction

user149138 14 авг '18 в 19:19 2018-08-14 19:19 · Answer 1 · 2018-08-14 19:19

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

Более подробно...

CPU Pipelining

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

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

Перенаправление Fetch

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

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

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

Динамическое предсказание на помощь

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

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

Добавление его

Все это способствует снижению полезности статического предсказания.

Во-первых, прогноз приходит слишком поздно, поэтому даже при безупречной работе он предполагает пузырь в 6–8 циклов на современном Intel для взятых ветвей (на самом деле, это наблюдаемые цифры от так называемых "передовых конечных пользователей" на Intel). Это резко меняет уравнение затрат / выгод для прогнозирования вообще. Если у вас есть динамический предиктор до того, как вы получите прогноз, вы более или менее хотите сделать какой-то прогноз, и если он имеет точность даже 51%, он, вероятно, окупится.

Однако для статических прогнозов вам нужна высокая точность, если вы когда-нибудь захотите сделать "принятый" прогноз. Возьмем, к примеру, 8-тактную стоимость переднего плана, вместо 16-тактной "полной неверной оценки". Допустим, в какой-то программе холодные обратные ветви берутся в два раза чаще, чем не принимаются Это должно быть победой для статического предсказания ветвления, которое предсказывает обратное взятие, верно (по сравнению со стратегией по умолчанию всегда "предсказывать"² непроявленных)?

Не так быстро! Если вы возьмете на себя стоимость повторного управления с 8 циклами и полную стоимость неправильного прогнозирования с 16 циклами, они в конечном итоге будут иметь одинаковую смешанную стоимость в 10,67 циклов - потому что даже в правильно спрогнозированном принятом случае, где пузырь с 8 циклами, но в в случае сбоя соответствующая стоимость для случая без статического прогнозирования отсутствует.

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

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

Сохранение ресурсов динамического прогнозирования

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

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

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

user4230618 13 авг '18 в 22:10 2018-08-13 22:10 · Answer 2 · 2018-08-13 22:10

Предсказание статических ветвлений, как описано в разделе 3.4.1.3 Руководства по оптимизации Intel, выглядит следующим образом:

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

Компиляторы могут организовать код соответствующим образом. В этом же разделе говорится следующее:

Микроархитектура Intel Core не использует эвристику статического прогнозирования. Однако для обеспечения согласованности между процессорами Intel 64 и IA-32 программное обеспечение должно поддерживать эвристику статического прогнозирования по умолчанию.

Это утверждение указывает на то, что Раздел 3.4.1.3 не обновлялся в течение многих лет.

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

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

В целом, я думаю, что это деталь реализации, которую Intel больше не документирует.

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

user224132 13 авг '18 в 12:59 2018-08-13 12:59 · Answer 3 · 2018-08-13 12:59

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

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

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

Как отмечает @Paul A Clayton, промах BTB может позволить процессору принять решение использовать статическое прогнозирование вместо того, что он обнаружил в динамическом предикторе "взят / не взят". Возможно, мы просто видим, что гораздо сложнее заставить пропустить динамический предиктор достаточно часто, чтобы измерить статическое предсказание.

(Я, возможно, искажаю вещи. Современные предикторы TAGE могут предсказывать сложные паттерны и для косвенных ветвей, поэтому я не уверен, что они даже пытаются предсказать с точки зрения взятого / не взятого или первый шаг всегда состоит в том, чтобы просто попытаться предсказывать следующий адрес, независимо от того, является ли это следующей инструкцией. Индексированные издержки ветвления в 64-битном режиме X86.)

Неиспользованные ветви все же немного дешевле в правильно предсказанном случае, потому что клиентский интерфейс может легче получать более ранние и более поздние инструкции в одном и том же цикле из кэша UOP. (Кэш UOP в семействе Sandybridge не является кэшем трассировки; строка UOP-кэша может кэшировать мопы только из непрерывного блока машинного кода x86.) В коде с высокой пропускной способностью извлеченные ветви могут быть небольшим узким местом внешнего интерфейса. Они также обычно распределяют код по большему количеству строк L1i и uop-cache.

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

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

Intel фактически публикует информацию о пропускной способности / задержке / порте выполнения самостоятельно (через IACA и некоторые документы), но это довольно просто проверить экспериментально (например, https://agner.org/optimize/ и http://instlatx64.atw.hu/ сделали), поэтому Intel не может сохранить эту тайну, даже если бы захотела.

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