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

Предсказание ветвлений

Модуль предсказания условных переходов (англ. Branch Prediction Unit ) — устройство, входящее в состав микропроцессоров, имеющих конвейерную архитектуру, определяющее направление ветвлений (предсказывающее, будет ли выполнен условный переход, или нет) в исполняемой программе. Предсказание ветвлений позволяет осуществлять предварительную выборку инструкций и данных из памяти, а также выполнять инструкции, находящиеся после условного перехода, до того, как будет определено его направление. Предсказатель переходов является неотъемлемой частью всех современных суперскалярных микропроцессоров, так как в большинстве случаев (точность предсказания переходов в современных процессорах превышает 90 %) позволяет оптимально использовать вычислительные ресурсы процессора. [1]

Существует два основных метода предсказания переходов: статический и динамический.

Статическое предсказание

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

Примерами статического предсказания могут служить тривиальное предсказание переходов, применявшееся в ранних процессорах архитектуры MIPS (предполагается, что условные переходы никогда не выполняются), а также статическое предсказание, использующееся в современных процессорах в качестве «подстраховки» (предполагается, что любой обратный переход является циклом и выполняется, а любой прямой переход не выполняется).

Динамическое предсказание

Динамические методы, широко используемые в современных процессорах, подразумевают анализ истории ветвлений. Примером динамического предсказания может служить двухуровневый адаптивный исторический алгоритм (англ. Bimodal branch prediction ), использовавшийся процессорами архитектуры P6 (анализируется таблица истории переходов, содержащая младшие значимые биты адреса инструкции и соответствующую им вероятность условного перехода: «скорее всего, будет выполнен», «возможно, будет выполнен», «возможно, не будет выполнен», «скорее всего, не будет выполнен» и обновляемая после каждого перехода).

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое «Предсказание ветвлений» в других словарях:

Предсказатель переходов — Модуль предсказания условных переходов (англ. Branch Prediction Unit) устройство, входящее в состав микропроцессоров, имеющих конвейерную архитектуру, определяющее направление ветвлений (предсказывающее, будет ли выполнен условный… … Википедия

NetBurst — (рабочее название P68) суперскалярная гиперконвейерная микроархитектура, разработанная компанией Intel и лежавшая в основе микропроцессоров Pentium 4, Pentium D, Celeron и Xeon. Содержание 1 История 2 … Википедия

Intel P6 — P6 суперскалярная суперконвейерная архитектура, разработанная компанией Intel и лежащая в основе микропроцессоров Pentium Pro, Pentium II, Pentium III, Celeron и Xeon. В отличие от x86 совместимых процессоров предыдущих поколений с CISC… … Википедия

Pentium III — > Центральный процессор Производство … Википедия

Вычислительный конвейер — У этого термина существуют и другие значения, см. Конвейер (значения). Конвейер способ организации вычислений, используемый в современных процессорах и контроллерах с целью повышения их производительности (увеличения числа инструкций,… … Википедия

X86 — 80486 DX2 x86 (Intel 80×86) аппаратная платформа: архитектура микропроцессора и соответствующий набор инструкций, как разработанных и выпускаемых компанией Intel, так и совместимых с ними процессоров других производителей (AMD, VIA … Википедия

IDT WinChip — Центральный процессор Производство: с 1997 по 1999 год Производитель: IDT … Википедия

WinChip — IDT WinChip Центральный процессор Производство: с 1997 по 1999 год … Википедия

x86 — 80486 DX2 x86 (англ. Intel 80×86) архитектура процессора c одноимённым наборо … Википедия

EPIC (архитектура микропроцессора) — У этого термина существуют и другие значения, см. EPIC. EPIC (англ. explicitly parallel instruction computing) микропроцессорная архитектура с явным параллелизмом команд. Термин введён в 1997 году альянсом HP и Intel[1] для… … Википедия

Источник

Русские Блоги

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

1. Предпосылки

Запустите результаты в Intellij idea:

1.1. Вопросы

В приведенном выше коде добавлена ​​функция разделения при заполнении массива, чтобы полностью гарантировать случайность значения заполнения. Расчет также основан на половине элементов, поэтому здесь нет особого случая. Более того, в расчетах вообще не учитывается порядок данных, то есть, упорядочен массив или нет, теоретически не влияет на расчет. В соответствии с этой предпосылкой, почемуПосле сортировкиМассив лучше, чемНесортированныйМассив работает более чем в 3 раза быстрее?

2. Напоминание

2.1. Трубопровод

Позвольте мне вкратце объяснить конвейер команд ЦП, в дальнейшем называемый конвейером. Pipieline предполагает, что существует ряд инструкций, которые должны выполняться во время работы программы.Он делит работу программы на несколько этапов и обрабатывает их параллельно в определенном порядке, так что скорость прохождения инструкций может быть увеличена.
Большинство конвейеров управляется тактовой частотой (тактовой частотой). В цифровых схемах тактовая частота управляет логическим циклом и триггером. При запуске по тактовой частоте , Триггер получает новое значение, логическому элементу требуется некоторый период времени для определения нового значения, триггер получает новое значение при срабатывании следующей тактовой частоты и так далее.
Распределяя логические элементы на множество небольших блоков, а затем позволяя триггеру связывать эти небольшие группы блоков, можно уменьшить временную задержку для логического элемента для вывода правильного значения, так что инструкции могут быть сокращены Цикл, необходимый для запуска. Это соответствует различным этапам конвейера.
Команда получения инструкции, декодирование инструкции, выполнение инструкции Считается, что это трехэтапный конвейер
Если мы далее разделим «инструкцию выполнения» на «вычисление ALU (выполнение инструкции) — доступ к памяти — обратная запись», тогда она превратится в пятиступенчатый конвейер.
Как и в наших современных процессорах ARM или Intel, количество этапов конвейера достигло 14 этапов.
Чем больше этапов в конвейере, тем лучше?
Выходные данные, соответствующие каждому этапу конвейера, должны быть помещены в регистр конвейера (регистр конвейера), а затем переданы следующему этапу конвейера для обработки в следующем тактовом цикле. Следовательно, каждый дополнительный уровень конвейера требует дополнительного уровня записи в регистр конвейера. Хотя конвейерный регистр очень быстрый, например, всего 20 пикосекунд (пс, 10-12 секунд)
Если выполнение нашей команды занимает 3 наносекунды, это 3000 пикосекунд. Нам нужен конвейер из 20 этапов, и на запись в регистр конвейера уходит 400 пикосекунд, что составляет более 10%. Если нам нужен 50-ступенчатый конвейер, мы потратим дополнительную 1 наносекунду на регистр конвейера, что составляет 25%. Это также означает, что простое увеличение числа стадий конвейера не только не улучшит производительность, но и приведет к увеличению накладных расходов.

Все операции остановки конвейера должны начинаться со стадии выполнения инструкции. Первые два этапа конвейера, а именно этапы выборки команд (IF) и декодирования команд (ID), не нужно приостанавливать. ЦП будет напрямую выбирать следующую команду в конвейере и затем декодировать ее.
При выборке и декодировании инструкций не требуется никаких пауз. Это основано на предположении. Предполагается, что все коды инструкций загружаются и выполняются последовательно. Однако эта гипотеза в исполняемом коде, как только он встречает условную ветвь, например if . else или цикл for / while, не выполняется.

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

2.2. Предиктор ветвления

2.2.1. Долгая история

Представьте себе железнодорожный переезд.

Чтобы продемонстрировать эту проблему, вернемся в 19 век, когда беспроводная связь на большие расстояния не была популярна. Вы стрелочник на железнодорожном переезде. Когда вы слышите приближающийся поезд, вы не можете угадать, в каком направлении он должен идти. Итак, вы остановили поезд, пошли вперед и спросили машиниста, в какую сторону ехать, чтобы правильно переключить пути.
Вы должны знать, что поезда очень большие и обладают огромной инерцией при быстром движении. Чтобы выполнить вышеупомянутые действия «стоп-запрос-резка пути», поезду требуется много времени для замедления, остановки и перезапуска.
Поскольку указанная выше передача занимает очень много времени, есть ли лучший способ? Конечно, есть! Когда поезд приближается, вы можете угадать, в каком направлении он должен идти.

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

Если вы каждый раз ошибаетесь, к сожалению, поезд будет тратить много времени на остановку-перемотку-перезапуск.
Если вам повезло, угадывали ли вы каждый раз правильно? Поезд никогда не остановится и не пойдет!

2.2.2. Ситуация в современных процессорах

Предиктор ветвления — это цифровая схема, которая угадывает, какая ветвь будет выполнена до выполнения инструкции ветвления, что может значительно улучшить производительность конвейеров.
У условных ветвей обычно есть две последовательные ветви выполнения. Если нет токена, пропустите следующую инструкцию JMP и продолжите выполнение. В случае токена выполните команду JMP и перейдите к другому блоку программной памяти. выполненный.
Чтобы проиллюстрировать эту проблему, сначала рассмотрим следующие вопросы.

2.2.2.1. Что делать, если нет предиктора перехода?

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

На рисунке пузырек создается с постоянной частотой 3, а выполнение команды задерживается.
Явление прерывания потока часто встречается в процессорах с ранней архитектурой RISC.

2.2.2.2. Трубопровод с периодом прогнозирования ответвления

Давайте посмотрим на применение предикторов перехода в условных переходах перехода.
У условных ветвей обычно есть две последовательные ветви выполнения. Если нет токена, пропустите следующую инструкцию JMP и продолжите выполнение. В случае токена выполните команду JMP и перейдите к другому блоку программной памяти. выполненный.
После добавления предиктора ветвления, чтобы избежать остановок конвейера, он угадывает, какая из двух ветвей с наибольшей вероятностью будет выполняться, а затем выполнит предположительно. Если предположение неверно, предполагается, что конвейер Все промежуточные результаты выполнения отбрасываются, и снова выполняется выполнение инструкции на правильном маршруте перехода. Видно, что неправильные прогнозы вызовут задержки в выполнении программы.
Из вышеизложенного видно, что выполнение конвейера в основном включает этапы выборки, декодирования, выполнения и обратной записи, а ошибка прогнозирования ветвления приведет к потере количества этапов конвейера до обратной записи. Число этапов конвейера современных ЦП очень велико, и сбой прогнозирования ветвления может привести к потере около 20 тактовых циклов.Поэтому для сложных конвейеров очень важен хороший предсказатель ветвления.

2.2.2.3. Общие предикторы ветвления

• Статический предсказатель ветвления

Простейший метод прогнозирования ветвления называется «притвориться, что ветвление не происходит». Как следует из названия, конечно, инструкции по-прежнему выполняются по порядку. Фактически, это предсказание ЦП, и условный переход не должен происходить. Такой метод прогнозирования на самом деле является методом статического прогнозирования. Это похоже на то, как если вы угадываете монету, вы продолжаете угадывать орел и получаете 50% правильную ставку.
Если прогноз ветвления верен, мы, естественно, получим прибыль. Это означает, что мы экономим время, которое в противном случае пришлось бы останавливать и ждать. Что делать, если предсказание ветвления не удается? Тогда мы отбросим выполненную часть инструкции, которая была снята позже. Эта операция сброса называется Zap или Flush в конвейере. ЦП не только должен выполнить следующие инструкции, но и для тех инструкций, которые были выполнены на полпути через конвейер, нам также необходимо выполнить соответствующие операции очистки. Например, очистка данных в используемых регистрах и т. Д., Эти операции очистки также имеют определенные накладные расходы. Следовательно, ЦП должен обеспечить соответствующую функцию сброса инструкций и очистить инструкции, которые были выполнены в конвейере, с помощью управляющего сигнала. Пока соответствующая стоимость удаления не слишком велика, мы можем себе это позволить.

Вышеупомянутая стратегия статического прогнозирования выглядит относительно простой, а точность прогноза может составлять 50%. Но если вам не повезет, это может быть особенно плохо. Поэтому инженеры задумались: а есть ли у нас способ лучше? Например, будет ли более точным прогнозирование на основе результата сравнения предыдущего условного перехода? В нашей повседневной жизни наиболее часто встречающийся прогноз — это прогноз погоды. Если нет метеостанции, которая могла бы дать вам прогноз погоды, и вы хотите угадать, пойдет ли завтра дождь, что бы вы сделали? Простая стратегия — угадать, полностью основываясь на сегодняшней погоде. Если сегодня пойдет дождь, мы прогнозируем, что пойдет дождь завтра. Если сегодня будет хорошо, то завтра дождя не будет. Это предсказание, которое соответствует нашему повседневному жизненному опыту. Поскольку обычно это дождливые дни, это несколько дней подряд, и редко, когда с интервалами случаются «мелкий дождь-мелкий дождь». Итак, эффективно ли претворять такую ​​практику в жизнь? Я здесь, чтобы дать таблицу погодных условий в Шанхае в январе 2019 года.

Мы используем, был ли дождь накануне, и напрямую прогнозируем, будет ли дождь на следующий день. В этой таблице 31 день, поэтому мы можем предсказать 30 раз. Вы можете посчитать. Согласно этому методу предсказания, мы можем предсказывать 23 раза правильно, и правильный показатель составляет 76,7%, что намного лучше, чем случайное предсказание в 50%.

И ту же стратегию мы также можем использовать для прогнозирования ветвлений. Эта стратегия называетсяПредсказание ветвления первого уровня(Одноуровневое предсказание переходов) или называется ** 1-битным счетчиком насыщения ** (1-битный счетчик насыщения). Этот метод фактически использует один бит для записи сравнения текущей ветви и напрямую использует сравнение текущей ветви для прогнозирования сравнения следующей ветви. Для дождя требуется всего один день, а на следующий день будет дождь. Этот метод все еще несколько «небрежный». Для прогнозов мы можем использовать больше информации, а не только информацию об одной ветви. Следовательно, для этого мы можем ввести конечный автомат. Если идет непрерывный дождь, мы думаем, что дождь пойдет с большей вероятностью. Если прояснится хоть один день, мы все равно думаем, что пойдет дождь. После продолжительного дождя потребуется два дня подряд, чтобы прояснить ситуацию, прежде чем мы думаем, что она исчезнет позже.
В этом конечном автомате у нас всего 4 состояния, поэтому нам нужно 2 бита для записи соответствующего состояния. Таким образом, всю эту стратегию можно назвать 2-битным счетчиком насыщения или бимодальным предсказателем (Bimodal Predictor).

Два состояния слева не являются токенами, а два справа — токенами. Есть два состояния перехода от не токена к токену. Переход от красного к синему требует выбора двух последовательных ветвей.
в технической реализации может быть представлен двумя двоичными битами, 00, 01, 10, 11 Отвечаем соответственно strongly not token, weakly not token, weakly token, strongly token . Простой способ определить, изменились ли два правила прогнозирования ветвления, — это определить, изменился ли старший бит статуса вторичной системы. Старший бит изменяется с 0 на 1, а сильное состояние переворачивается, и следующая инструкция ветвления предсказывает от not token Становится token ,наоборот.
Согласно оценке, точность бимодального предсказателя может достигать 93,5%. Период предсказания обычно вступает в силу до декодирования инструкции перехода.
Другие распространенные предикторы ветвления, такие как двухуровневые адаптивные предикторы, локальные / глобальные предикторы ветвления, предикторы слияния ветвей, согласованные периоды прогнозирования, предикторы нейронных ветвей и т. д.

3. Анализ

В оригинальной программе:

Вернемся к вопросу в начале статьи. Теперь предположим, что вы процессор.Когда вы видите вышеупомянутые ветви, когда вы не можете решить, как спуститься, что вам делать? Вы можете только приостановить операцию и дождаться окончания предыдущей инструкции. Затем вы можете продолжать идти по правильному пути.
Вы должны знать, что современные компиляторы очень сложны, с очень длинными конвейерами во время выполнения, замедление и горячий запуск отнимают огромное количество времени.
Итак, есть ли хороший способ сэкономить время на переключение этих состояний? Вы можете догадаться, куда пойдет ветка дальше!

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

Если вы каждый раз угадаете неверно, процессор будет проводить много времени в периодическом процессе остановки-отката-горячего старта.
Если вам повезет каждый раз делать правильные предположения, процессор никогда не будет останавливаться и работать до конца.
Вышеупомянутый процесс — это прогнозирование перехода. Хотя небольшой флажок можно использовать в качестве сигнала для определения направления поезда при фактическом переключении путей на железнодорожном переезде, процессор не может предсказать направление ответвления, как поезд, если не будет завершена последняя инструкция.
Итак, какую стратегию следует использовать процессору, чтобы использовать наименьшее количество раз, чтобы угадать следующее направление ветвления инструкции? Ответ состоит в том, чтобы проанализировать исторические данные о беге: если поезд ехал по левому пути 90% времени, вы можете предположить, что направление остается левым во время этого переключения пути, в противном случае оно правильное. Если вы шли в определенном направлении 3 раза, то можете догадаться, что поезд продолжит движение в этом направлении .
Другими словами, вы пытаетесь идентифицировать неявный шаблон через исторические записи и пытаетесь продолжать применять его при принятии решения о последующем переключении железной дороги. Это более или менее похоже на принцип предсказания ветвлений процессора.
Большинство приложений имеют ветки с хорошим поведением, поэтому современные предикторы ветвления обычно имеют процент попаданий более 90%. Но перед лицом непредсказуемых ветвей и отсутствия подходящих шаблонов предсказатель ветвления бесполезен.
Что касается периода прогнозирования ветвления, см. соответствующие записи в Википедии.»Branch predictor» article on Wikipedia..
В начале статьи причиной значительного увеличения затрат времени на добавление несортированных массивов является логика if:

Обратите внимание, что элементы в массиве данных хранятся равномерно в соответствии со значением от 0 до 255 (аналогично равномерному сегментированию). Когда данные массива упорядочены, итерация первой половины элементов не будет входить в оператор if, а когда больше половины, итерация всех элементов войдет в оператор if.
Такие итерации, которые продолжают переключаться в том же направлении, очень удобны для предсказателя ветвления. После итерации первой половины элементов последующие итерации предсказателя ветвления будут предсказывать переключение направления ветвления. отлично.
Просто проанализируйте:
Процесс прогнозирования ветвления упорядоченного массива:

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

4. Вывод

• Используйте прогнозирование ветвлений: серьезно ли влияет сортировка на производительность
• Использовать битхак: не влияет ли сортировка существенно на производительность

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

Хорошо видно, что количество операций в секунду перед if больше, а эффективность выше

Источник