Предсказание цели ветвления в сочетании с предсказанием ветвления?

Question

РЕДАКТИРОВАТЬ: Моя путаница возникает потому, что, конечно, предсказывая, какая ветвь берется, вы эффективно делаете целевой прогноз тоже??

Этот вопрос неразрывно связан с моим первым вопросом по теме:

прогнозирование ветвлений и прогнозирование ветвлений

Глядя на принятый ответ:

Безусловная ветвь, фиксированная цель

• Бесконечный цикл
• goto заявление
• break или же continue заявление
• Конец предложения then if/else заявление (прыгать мимо else оговорка)
• Не виртуальный вызов функции

Безусловная ветвь, переменная цель

• Возвращаясь из функции
• Вызов виртуальной функции
• Вызов указателя функции
• switch оператор (если скомпилирован в таблицу переходов)

Условная ветвь, фиксированная цель

• if заявление
• switch заявление (если составлено в серию if/else заявления)
• Проверка состояния петли
• && а также || операторы
• Троичный ?: оператор

Условная ветвь, переменная цель

• Менее вероятно, будет отображаться в нормальных условиях, но компилятор может синтезировать один в качестве оптимизации, объединяя два из вышеупомянутых случаев. Например, на x86 компилятор может оптимизировать код if (condition) { obj->VirtualFunctionCall(); } в условный косвенный скачок, как jne *%eax если он появляется в конце функции из-за оптимизации хвостового вызова.

Если у меня есть следующий код:

if(something){
    //a
}
else{
    //b
}

(BP = "Прогнозирование ветви" и BTP = "Прогнозирование цели филиала")

Его довольно очевидный АД используется для оценки условного something, Однако я пытаюсь понять, участвует ли BTP в определении того, что происходит в филиале a, BTP также случается, чтобы определить адрес кода, расположенного в филиале a/bв зависимости от результата БП?

Я спрашиваю, потому что на этой странице Википедии ( http://en.wikipedia.org/wiki/Branch_target_predictor):

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

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

1) Может кто-нибудь прояснить вышесказанное, пожалуйста?

Второй связанный вопрос - как BP и BTP отличаются тем, как они взаимодействуют с конвейером выборки / декодирования / выполнения / обратной записи ЦП? BP начинается на этапе извлечения или декодирования? После этапа выполнения условного кода мы можем проверить правильность прогноза и обновить кэш прогноза ветвления.

2) Как BTP работает в отношении этапов CPU выборки / декодирования / выполнения / обратной записи?

Answer 1

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

Я дам краткое изложение того, что найдено в руководстве, добавив детали, где это уместно:

Прогнозирование ветвлений - это работа блока BPU в ядре (блок прогнозирования ветвлений). Примерно коррелирует с "БП" в вашем вопросе. Он содержит несколько подразделов:

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

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

• Буфер возврата стека. Этот буфер действует как "теневой" стек, сохраняя адрес возврата для команд CALL, делая цель инструкции RET доступной с высокой степенью достоверности, при этом процессору не нужно полагаться на BTB, что вряд ли будет столь же эффективно для вызовов. Задокументировано, что это 16 уровней глубины.

Пуля 2) в немного трудно ответить точно, руководство говорит только о "Front End" и не разбивает детали конвейера. Достаточно уместно, это сильно зависит от архитектуры. Диаграмма в разделе 2.2.5, возможно, является иллюстративной. Кэш трассировки выполнения играет роль, он хранит ранее декодированные инструкции, поэтому является основным источником консультаций BPU. В противном случае сразу после переводчика инструкций (он же декодер).

Answer 2

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

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

Как вы процитировали себя в списке типов ветвей - вопрос о том, должна ли ветвь предсказывать, что она будет принята или нет (условно), и должна ли ветвь предсказывать цель (прямая / фиксированная цель, как вы ее называете) оба варианта применимы, и каждый может идти обоими путями, не связанными с другим, предоставляя вам 4 варианта, которые вы перечислили:

• Теоретически безусловные прямые ветвления не требуют какого-либо прогнозирования - интерфейс ЦП просто считал бы цель и "взял" ветвь (передавая код конвейера с нового адреса). Однако современным ЦП по-прежнему требуется время для декодирования ветви и определения цели, закодированной в ней, поэтому, чтобы избежать сбоев в предикторе перехода (который обычно находится в начале канала), им также придется прогнозировать этот адрес. Хотя подтвердить прогноз очень просто (сразу после декодирования), поэтому штраф за неправильное предсказание не очень высок. Он все еще может быть остановлен из-за ошибок в кэше кода / tlb, но в остальном он самый быстрый (но можно сказать, самый слабый)

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

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

• условные косвенные ответвления - ну, везет тебе, нужны оба прогноза...

Таким образом, решения являются ортогональными, но это не означает, что предсказатели должны быть такими. Имейте в виду, что у вас есть один "поток" истории ветвлений, так что, вероятно, стоит как-то связать предиктор, разделяя некоторые таблицы или некоторую логику. Насколько именно решение о дизайне и зависит от фактической реализации HW, вы, вероятно, не будете получать много подробностей о том, как Intel/AMD делают это, но есть много научных исследований на эту тему.

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

Эта диаграмма не говорит вам всего, в ней явно отсутствуют входные данные для BP/BTP или даже различие между ними (которое само по себе уже говорит о том, что они, вероятно, построены вместе), но оно действительно показывает, что это очевидно первая и главная часть трубопровода. Вам нужно предсказать указатель следующей инструкции, прежде чем вы сможете продолжить и подать его в конвейер fetch/decode/... (или альтернативный uop-cache). Это, вероятно, означает, что ЦПУ запускает каждый цикл (ну, да, все действительно выполняется параллельно, но это помогает думать о конвейере как о поэтапном процессе), думая, какую инструкцию выполнять дальше. Допустим, он знает, где мы были в последний раз, так что это либо инструкция без ветвления (ааа, но как насчет изменяющейся длины... еще одна сложность, которую необходимо решить этой единице), либо ветвь, и в этом случае эта единица должна угадать, какая из вышеперечисленных типов, к которым принадлежит эта ветвь, и соответственно предсказывает следующую инструкцию.

Обратите внимание, что я написал "угадай" - если диаграмма говорит правду, стадия декодирования действительно далеко, вы даже не знаете, что это ветвь на данном этапе. Таким образом, чтобы ответить на ваш вопрос - этот блок BP/BTP должен взаимодействовать с блоками исполнения /WB, чтобы он мог знать результат условных ветвлений, с блоком декодирования, чтобы он мог знать, какая команда, которая в настоящее время решается, является ветвью и какой ее тип есть, с различными конвейерами выборки, чтобы кормить их выводом. Я предполагаю, что есть дальнейшие отношения с другими модулями (например, некоторые проекты могут решить отправлять предварительные выборки кода на основе целевых предсказаний и т. Д.).