Я читал популярный ответ о Branch Prediction с /programming//q/11227809/555690 , и меня что-то смущает:
- Если вы угадали, это продолжается.
- Если вы догадались, капитан остановится, отступит и закричит на вас, чтобы щелкнуть выключателем. Затем он может перезапустить другой путь.
Если вы угадаете каждый раз, поезд никогда не остановится.
Если вы слишком часто угадываете неправильно, поезд будет тратить много времени на остановку, резервное копирование и перезапуск.
Но это то, чего я не понимаю: чтобы узнать, было ли ваше предположение правильным или нет, вы все равно должны проверить состояние . Так как же работает предсказание ветвления, если в любом случае вы все еще выполняете ту же условную проверку?
Я пытаюсь сказать, не является ли предсказание ветвлений точно таким же, как и отсутствие предсказания ветвлений, потому что вы все равно выполняете те же условные проверки? (очевидно, я ошибаюсь, но я не понимаю)
optimization
Омега
источник
источник
Ответы:
Конечно, состояние проверяется каждый раз. Но к тому времени, когда это проверено, это далеко в трубопровод ЦП. Между тем, другие инструкции также вошли в конвейер и находятся на разных этапах исполнения.
Обычно за условием немедленно следует условная инструкция ветвления, которая либо разветвляется, если условие оценивается как TRUE, либо проваливается, если условие оценивается как FALSE. Это означает, что есть два разных потока команд, которые могут быть загружены в конвейер после инструкции условия и инструкции ветвления, в зависимости от того, оценивается ли условие как ИСТИНА или ЛОЖЬ. К сожалению, сразу после загрузки инструкции условия и инструкции ветвления ЦП еще не знает, к какому условию будет относиться условие, но ему все равно придется продолжать загружать данные в конвейер. Таким образом, он выбирает один из двух наборов инструкций, основываясь на предположении относительно того, как будет оцениваться условие.
Позже, когда инструкция условия перемещается вверх по конвейеру, наступает время ее оценки. В это время процессор выясняет, была ли его догадка правильной или неправильной.
Если предположение оказывается верным, тогда ветвь переместилась в правильное место, и правильные инструкции были загружены в конвейер. Если оказывается, что предположение было неверным, то все инструкции, которые были загружены в конвейер после команды условного перехода, были неправильными, их необходимо отбросить, и выборка инструкций должна начаться снова с правильного места.
поправка
В ответ на комментарий StarWeaver, чтобы дать представление о том, что должен делать процессор, чтобы выполнить одну инструкцию:
Рассмотрим что-то столь же простое, о
MOV AX,[SI+10]
чем мы, люди, наивно думаем, как о «загрузке AX словом в SI плюс 10». Грубо говоря, процессор должен:Это колоссальные 10 шагов. Некоторые из этих шагов будут оптимизированы даже в непоточных ЦП, например, ЦП почти всегда будет увеличивать ПК параллельно со следующим шагом, что легко сделать, потому что ПК является очень, очень специальным регистром, который никогда не использовался для какой-либо другой работы, поэтому нет возможности конфликта между различными частями ЦП за доступ к этому конкретному регистру. Но, тем не менее, у нас осталось 8 шагов для такой простой инструкции, и обратите внимание, что я уже предполагаю некоторую степень сложности от имени процессора, например, я предполагаю, что не понадобится целый дополнительный шаг для сумматор, чтобы фактически выполнить сложение, прежде чем из него можно будет прочитать результат,
Теперь предположим, что существуют более сложные режимы адресации, например
MOV AX, [DX+SI*4+10]
, и даже более сложные инструкции, например,MUL AX, operand
которые фактически выполняют циклы внутри ЦП для вычисления своего результата.Итак, моя точка зрения заключается в том, что метафора «атомарного уровня» далеко не подходит для уровня команд ЦП. Это может быть подходящим для уровня шага конвейера, если вы не хотите заходить слишком далеко до фактического уровня логических элементов.
источник
MOV AX,[SI+10]
чуждо, а не «просто»; большинство программистов сегодня никогда не писали ассемблер. Мы не «наивно думаем» об этом как о чем-то значимом.Думайте об этом как о поездке без GPS. Вы приходите на перекресток и думаете, что вам нужно повернуть, но не совсем уверены. Таким образом, вы берете очередь, но попросите своего пассажира проверить карту. Может быть, вы находитесь в трех милях от дороги к тому времени, как заканчиваете спорить о том, где вы находитесь. Если бы ты был прав, ты на три мили дальше, чем был бы, если бы остановился и поспорил перед поворотом. Если вы ошиблись, вы должны обернуться.
Цепные конвейеры работают так же. К тому времени, когда они могут проверить состояние, они уже в пути. Разница в том, что им не нужно проезжать три мили назад, они просто теряют преимущество. Это означает, что в попытках нет вреда.
источник
Насколько я понимаю, прогноз ветвления наиболее полезен, когда условие, которое необходимо проверить, требует результата чего-то дорогостоящего или все еще в процессе, и в противном случае вы бы теребили большие пальцы в ожидании значения для оценки условия.
С такими вещами, как выполнение не по порядку, вы можете использовать прогнозирование ветвлений, чтобы начать заполнять пустые места в конвейере, которые в противном случае ЦП не смог бы использовать. В ситуации, когда по какой-то причине в конвейере нет никаких циклов простоя, тогда да, выигрыш в прогнозировании ветвлений не улучшается.
Но ключевой момент здесь заключается в том, что ЦПУ начинает работу для одной из предсказанных ветвей, потому что он еще не может оценить само условие.
источник
Краткая форма:
Некоторые процессоры могут начать работать с новой инструкцией, прежде чем закончить старую. Это процессоры, которые используют предсказание ветвления.
Пример псевдокода:
Приведенный выше код проверяет условие и на основании результата должен возвращать либо значение, хранящееся в ячейке памяти,
addThis
либо значение, хранящееся вreadThat
. Если прогнозирование ветвления предсказывает условие, которое будет выполненоtrue
, ЦП уже будет считывать значение, хранящееся в ячейке памятиaddThis
, выполняя вычисления, необходимые для оценкиif
оператора. Это упрощенный пример.источник
Да, условие проверяется в любом случае. Но преимущество прогнозирования ветвлений состоит в том, что вы можете выполнять работу, а не ждать результата проверки условия.
Допустим, вам нужно написать эссе, и оно может быть о теме А или теме Б. Из предыдущих эссе вы знаете, что вашему учителю нравится тема А лучше, чем Б, и она выбирает ее чаще. Вместо того, чтобы ждать его решения, вы можете начать писать сочинение по первой теме. Теперь есть два возможных результата:
Современные процессоры большую часть времени простаивают, потому что они ждут ответов ввода-вывода или результатов других вычислений. Это время можно использовать для дальнейшей работы.
Даже если вам придется отклонить то, что вы делаете в это простое время, - скорее всего, оно будет более эффективным, если у вас есть возможность угадать, какой путь выберет программа. И современные процессоры обладают этой способностью.
источник