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

EDIT: Моя путаница возникает, потому что, конечно, предсказывая, какая ветка взята, вы также эффективно выполняете целевое предсказание.

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

предсказание ветвления и предсказание целевой ветки

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

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

Бесконечная петля

goto

break или continue statement

Конец предложения "then" оператора if/else (чтобы перейти к предложению else)

Невиртуальный вызов функции
Безусловная ветвь, переменная target

Возврат из функции

вызов виртуальной функции

Вызов указателя функций

switch (если скомпилирован в таблицу перехода)
Условная ветвь, фиксированная цель

if

switch (если скомпилирован в ряд операторов if/else)

Проверка условий цикла

Операторы && и ||

Тернарный ?: оператор
Условная ветвь, переменная target

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

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

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

(BP = "Прогнозирование ветвей" и BTP = "Прогнозируемое предсказание ветвей" )

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

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

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

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

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

Второй связанный вопрос: как BP и BTP отличаются тем, как они взаимодействуют с конвейером fetch/decode/execute/write-back процессора? Начинается ли ВР на этапе выборки или декодирования? После этапа выполнения условного кода мы можем проверить правильность предсказания и обновление кэша предсказания ветвлений.

2) Как работает BTP в отношении этапов CPU fetch/decode/execute/write-back?

Ответ 1

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

Я приведу краткое изложение того, что найдено в руководстве, добавляя в соответствующих случаях информацию:

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

Таблица истории веток. Эта таблица отслеживает ранее принятые условные ветки и консультируется предиктором, чтобы решить, может ли ветвь быть принята. На него подаются записи от подразделения по отставке команды, который знает, действительно ли была занята ветка. Это подразделение, которое больше всего изменилось по мере улучшения архитектуры, становясь все глубже и умнее, когда стало доступно больше недвижимости.
Буфер BTB, Branch Target Buffer. Этот буфер хранит целевой адрес ранее принятого косвенного перехода или вызова. Это соотносится с "BTP" в вашем вопросе. В руководстве не указано, может ли буфер хранить несколько целей на каждый адрес, индексированный по таблице истории, я считаю это вероятным для более поздних архитектур.
Буфер возврата стека. Этот буфер выполняет "теневой" стек, сохраняя обратный адрес для инструкций CALL, что делает цель команды RET доступной с высокой степенью уверенности, если процессор не должен полагаться на BTB, что вряд ли будет столь же эффективным для вызовов. Он документирован как минимум 16 уровней.

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

Ответ 2

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

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

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

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

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

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

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

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