Почти в любой компьютерной программе есть части кода, которые разветвляются на отдельные пути. Например, оператор if-then-else имеет два возможных результата. Эти операторы не представляют проблемы для последовательных процессоров, поскольку ЦП обрабатывает каждую команду по порядку. Ветви представляют собой большую проблему для конвейерных процессоров, поскольку одновременно выполняется несколько инструкций.
Сценарий
В случае программы с оператором ветвления с двумя возможными результатами два возможных пути кода не могут находиться в одном и том же месте. Обработка, необходимая для завершения любого варианта, будет отличаться. В противном случае программа не разветвлялась бы. Скорее всего, будет изрядное количество операторов ветвления, которые выполняются только один раз, например оператор if.
Существуют также операторы ветвления, которые образуют цикл. Хотя в численном отношении они могут быть не такими распространенными, как утверждения одноразового использования, они, как правило, статистически повторяются. Можно предположить, что более вероятно, что ветвь вернет вас назад по петле, чем нет.
Почему это проблема?
Неважно, как эта проблема формулируется в полностью последовательном процессоре. Это просто не проблема. Какая ветвь будет выбрана, известно до того, как будет обработана первая часть следующей инструкции.
Однако в конвейерном процессоре в очередь ставятся следующие инструкции. Они уже обрабатываются, когда процессор знает, какая ветвь берется. Итак, как процессор должен справиться с этим сценарием? Есть несколько вариантов. Хуже всего просто ждать и оставлять конвейер бездействующим, пока он ждет ответа, по какой ветке брать. Это означало бы, что каждый раз, когда у вас есть оператор ветвления, вы всегда будете терять по крайней мере столько циклов процессорного времени, сколько у вас есть этапов в конвейере.
В качестве альтернативы вы можете попробовать запустить оба варианта в конвейере и отказаться от неправильного выбора. Это будет иметь половину штрафа за то, что ничего не будет делать, но все же повлечет за собой снижение производительности для каждого оператора ветвления. Учитывая, что современные процессоры также могут запускать инструкции не по порядку, вы потенциально можете попытаться запустить каждую инструкцию ветвления как можно скорее. Поэтому его результат известен до того, как он понадобится. Этот вариант может быть полезен, но он не масштабируется. Предположим, у вас относительно высокая плотность операторов ветвления. В этом случае вы просто не сможете запустить их все раньше, не имея времени простоя.
Как на самом деле решается эта проблема
На самом деле процессор включает в себя предсказатель ветвления. Предсказатель ветвления пытается угадать, какой результат выбора ветвления будет выбран. Затем процессор предполагает, что прогноз верен, и планирует выполнение инструкций. Если предиктор ветвления точен, производительность не снижается.
Если предсказатель ветвления делает ошибку, вы должны очистить конвейер и начать обработку фактического результата. Это приводит к несколько худшему снижению производительности, чем если бы вы ничего не делали и просто ждали результата. Чтобы получить наилучшую производительность, важно убедиться, что предсказатель ветвления является максимально точным. Существует целый ряд различных подходов к этому.
Соответствующий код
В машинном коде ветвь — это всегда выбор между чтением следующей инструкции или переходом к набору инструкций в другом месте. Некоторые ранние реализации предсказателей ветвлений просто предполагали, что все ветвления будут выполняться всегда или никогда не будут выполняться. Эта реализация может иметь удивительно хороший уровень успеха, если компиляторы знают об этом поведении и предназначен для корректировки машинного кода таким образом, чтобы наиболее вероятный результат совпадал с общими параметрами процессора. предположение. Это требует большой настройки и корректировки привычек разработки программного обеспечения.
Другая альтернатива состояла в том, чтобы узнать из статистики, что петли обычно берутся и всегда перескакивают, если ветвь идет в обратном направлении. потока инструкций и никогда не переходить, если переход выполняется вперед, потому что это обычно статистически менее вероятное состояние выхода из петля. Это оба типа статического предсказания ветвления, когда результат ветвления предсказывается во время компиляции.
Динамические предикторы переходов
Современные предсказатели ветвлений являются динамическими и используют статистику текущей запущенной программы для достижения более высоких показателей успешных предсказаний. Насыщающий счетчик является основой для всех текущих предсказателей переходов. Первое предположение определяется статически или случайным образом. Как только ветвь была выбрана или не выбрана, этот результат сохраняется в части памяти. В следующий раз, когда появится та же ветвь, предсказатель ветвления предсказывает тот же результат, что и раньше.
Это, естественно, приводит к хорошим показателям предсказания циклов. Есть две версии этого. Ранние версии просто использовали один бит данных, чтобы указать, была ли ветвь взята или нет. В более поздних версиях используются два бита, чтобы указать слабо или сильно принятый или не принятый выбор. Эта настройка все еще может предсказать результат выполнения цикла, если программа вернется к нему, что обычно увеличивает вероятность успеха.
Отслеживание шаблонов
Чтобы отслеживать шаблоны, некоторые предсказатели ветвлений отслеживают историю того, какой выбор был сделан. Например, предположим, что цикл вызывается непрерывно, но повторяется всего четыре раза, прежде чем выйти из цикла. В этом случае двухуровневый адаптивный предиктор может идентифицировать этот паттерн и предсказать его повторение. Это еще больше увеличивает вероятность успеха по сравнению с простым насыщенным счетчиком. Современные предсказатели ветвлений строятся на этом дальше, используя нейронную сеть для обнаружения и прогнозирования шаблонов.
Некоторые предикторы ветвлений используют несколько алгоритмов, а затем сравнивают результаты, чтобы решить, какой прогноз использовать. Некоторые системы отслеживают каждую инструкцию ветвления отдельно в так называемом локальном прогнозировании ветвлений. Другие используют глобальную систему предсказания переходов для отслеживания всех последних инструкций по переходу. У обоих есть свои преимущества и недостатки.
Вывод
Предсказатель ветвления — это особая часть конвейерного процессора. Он пытается предсказать результат инструкции ветвления до того, как будет обработана фактическая инструкция. Это основная функция конвейерного ЦП, поскольку она позволяет ЦП поддерживать насыщенность конвейера, даже если он не уверен, какие инструкции необходимо выполнить. Они не предлагают снижения производительности, когда они верны. Современные алгоритмы могут быть точными в относительно предсказуемых рабочих нагрузках до 97% времени.
Не существует идеального метода прогнозирования, поэтому реализации различаются. Влияние неправильного прогноза на производительность зависит от длины конвейера. В частности, длина конвейера до него может быть определена, если прогноз был неверным. Это также зависит от того, сколько инструкций находится на каждом этапе конвейера. Современные высокопроизводительные процессоры для настольных ПК имеют около 19 стадий конвейера и могут выполнять не менее четырех инструкций одновременно на каждой ступени.