Как работает предсказание ветвления, если вам все еще нужно проверить условия?

30

Я читал популярный ответ о Branch Prediction с /programming//q/11227809/555690 , и меня что-то смущает:

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

Если вы угадаете каждый раз, поезд никогда не остановится.

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

Но это то, чего я не понимаю: чтобы узнать, было ли ваше предположение правильным или нет, вы все равно должны проверить состояние . Так как же работает предсказание ветвления, если в любом случае вы все еще выполняете ту же условную проверку?

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

Омега
источник
1
Эта вики- статья довольно хорошо объясняет это.
enderland
8
Современный процессор является конвейерным и может делать несколько вещей одновременно. Таким образом, он может начать выполнять свое предположение, пока еще не выяснил, правильно ли он угадал. Если предположение было верным, трубопровод продолжает работать. При неправильном предположении конвейер отбрасывается, и выполнение перезапускается с точки «правильного ответа».
Markspace
2
Связанное чтение: трубопровод . Я также рекомендовал бы перечитать принятый ответ на этот вопрос, так как он отвечает на ваш вопрос здесь.

Ответы:

19

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

Обычно за условием немедленно следует условная инструкция ветвления, которая либо разветвляется, если условие оценивается как TRUE, либо проваливается, если условие оценивается как FALSE. Это означает, что есть два разных потока команд, которые могут быть загружены в конвейер после инструкции условия и инструкции ветвления, в зависимости от того, оценивается ли условие как ИСТИНА или ЛОЖЬ. К сожалению, сразу после загрузки инструкции условия и инструкции ветвления ЦП еще не знает, к какому условию будет относиться условие, но ему все равно придется продолжать загружать данные в конвейер. Таким образом, он выбирает один из двух наборов инструкций, основываясь на предположении относительно того, как будет оцениваться условие.

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

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

поправка

В ответ на комментарий StarWeaver, чтобы дать представление о том, что должен делать процессор, чтобы выполнить одну инструкцию:

Рассмотрим что-то столь же простое, о MOV AX,[SI+10]чем мы, люди, наивно думаем, как о «загрузке AX словом в SI плюс 10». Грубо говоря, процессор должен:

  1. передать содержимое ПК («регистр счетчика программ») на адресную шину;
  2. прочитать код операции инструкции с шины данных;
  3. инкремент ПК;
  4. декодировать код операции, чтобы понять, что с ним делать;
  5. передать содержимое ПК на адресную шину;
  6. прочитать операнд инструкции (в данном случае 10) из шины данных;
  7. инкремент ПК;
  8. подать операнд и SI в сумматор;
  9. выдать результат сумматора на адресную шину;
  10. читать AX с шины данных.

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

Теперь предположим, что существуют более сложные режимы адресации, например MOV AX, [DX+SI*4+10], и даже более сложные инструкции, например, MUL AX, operandкоторые фактически выполняют циклы внутри ЦП для вычисления своего результата.

Итак, моя точка зрения заключается в том, что метафора «атомарного уровня» далеко не подходит для уровня команд ЦП. Это может быть подходящим для уровня шага конвейера, если вы не хотите заходить слишком далеко до фактического уровня логических элементов.

Майк Накис
источник
2
Да, мне интересно, есть ли у части людей (включая меня) проблемы с пониманием этого, что очень трудно (для меня в любом случае) представить процессор, имеющий лишь частичное знание одной инструкции; или получить полузаконченные инструкции «прохождение через печь для пиццы»… по крайней мере, для меня это похоже на изменение масштаба атомного, когда я привык работать с вещами между монтажным комплектом и металлическим токарным станком.
StarWeaver
1
@ StarWeaver Мне понравился твой комментарий, поэтому я исправил свой ответ, чтобы ответить на него.
Майк Накис
1
Вау, хорошее объяснение. Я склонен забывать, сколько всего уходит на перемещение слов в более полезные места. Я все еще представляю себе процессор как набор духовок для пиццы с ременным приводом: 3.
StarWeaver
Стоит помнить, что вопрос о переполнении стека, связанный с ОП - тот, у которого 1,3 миллиона просмотров, вероятно, представил более 1 миллиона программистов ранее незнакомому факту, что «предсказание ветвлений» даже существует - демонстрирует пример в Java . Людям, подобным мне, которые привыкли работать на уровне абстракции, которую предоставляют нам языки, подобные Java, даже MOV AX,[SI+10]чуждо, а не «просто»; большинство программистов сегодня никогда не писали ассемблер. Мы не «наивно думаем» об этом как о чем-то значимом.
Марк Амери
@MarkAmery ну, ладно, я подумал, что довольно очевидно, что под «мы, люди», я имею в виду «мы, люди, которые смеют писать ассемблер». Смысл в том, что даже программисты на ассемблере не думают о конвейере все время или даже вообще.
Майк Накис
28

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

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

Карл Билефельдт
источник
2
Это объяснение опрятно.
Sharp Bluetooth
2

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

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

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

Собаки
источник
1

Краткая форма:

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

Пример псевдокода:

int globalVariable;
int Read(int* readThis, int* readThat)
{
    if ((globalVariable*globalVariable % 17) < 5)
       return *readThis;
    else
       return *readThat;
}

Приведенный выше код проверяет условие и на основании результата должен возвращать либо значение, хранящееся в ячейке памяти, addThisлибо значение, хранящееся в readThat. Если прогнозирование ветвления предсказывает условие, которое будет выполнено true, ЦП уже будет считывать значение, хранящееся в ячейке памяти addThis, выполняя вычисления, необходимые для оценки ifоператора. Это упрощенный пример.

Питер
источник
1

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

Допустим, вам нужно написать эссе, и оно может быть о теме А или теме Б. Из предыдущих эссе вы знаете, что вашему учителю нравится тема А лучше, чем Б, и она выбирает ее чаще. Вместо того, чтобы ждать его решения, вы можете начать писать сочинение по первой теме. Теперь есть два возможных результата:

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

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

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

Отомо
источник