Войти
В компьютерной архитектуре предиктор переходов представляет собой цифровую схему, который пытается угадать, в какую сторону пойдет ветвь (например, структура if – then – else ) до того, как это станет окончательно известно. Целью предсказателя ветвления является улучшение потока в конвейере команд . Предикторы ветвления играют критически важную роль в достижении высокой эффективной производительности во многих современных конвейерных микропроцессорных архитектурах, таких как x86.
Пример 4-этапного конвейера. Цветные прямоугольники представляют инструкции, независимые друг от друга. Двустороннее ветвление обычно реализуется с помощью инструкции условного перехода. Условный переход может быть либо «не выполнен» и продолжить выполнение с первой ветвью кода, которая следует сразу после условного перехода, либо его можно «взять» и перейти в другое место в памяти программы, где находится вторая ветвь кода. хранится. Неизвестно наверняка, будет ли выполнен условный переход или нет, пока условие не будет вычислено и условный переход не пройдет стадию выполнения в конвейере команд (см. Рис. 1).
Без предсказания ветвления процессору пришлось бы ждать, пока команда условного перехода не пройдет стадию выполнения, прежде чем следующая инструкция сможет войти в стадию выборки в конвейере. Предиктор перехода пытается избежать этой траты времени, пытаясь угадать, будет ли условный переход скорее всего выполнен или нет. Затем выбирается наиболее вероятная ветвь и спекулятивно выполняется. Если позже обнаруживается, что предположение было ошибочным, то предположительно выполненные или частично выполненные инструкции отбрасываются, и конвейер запускается заново с правильной ветвью, вызывая задержку.
Время, потраченное впустую в случае неверного предсказания перехода, равно количеству этапов в конвейере от этапа выборки до этапа выполнения. Современные микропроцессоры, как правило, имеют довольно длинные конвейеры, поэтому задержка неверного прогнозирования составляет от 10 до 20 тактовых циклов. В результате увеличение длины конвейера увеличивает потребность в более продвинутом предсказателе ветвления.
Когда впервые встречается команда условного перехода, не так много информации, на которой можно было бы основывать прогноз. Но предсказатель ветвлений хранит записи о том, приняты ли ветки или нет. Когда он встречает условный переход, который наблюдался несколько раз раньше, он может основывать свой прогноз на истории. Предиктор перехода может, например, распознать, что условный переход выполняется чаще, чем нет, или что он выполняется каждый второй раз.
Прогнозирование перехода не то же самое, что прогнозирование целевого перехода. Предсказание ветвления пытается угадать, будет ли выполнен условный переход или нет. Прогнозирование цели перехода пытается угадать цель принятого условного или безусловного перехода до того, как она будет вычислена путем декодирования и выполнения самой инструкции. Прогнозирование переходов и прогнозирование целевых переходов часто объединяются в одной схеме.
Статическое предсказание - это простейший метод предсказания ветвления, поскольку он не полагается на информацию о динамических история выполнения кода. Вместо этого он предсказывает результат перехода, основываясь исключительно на инструкции перехода.
Ранние реализации SPARC и MIPS (два из первых коммерческих RISC ) использовали однонаправленное статическое предсказание ветвления: они всегда предсказывают, что условный переход не будет выполнен, поэтому они всегда выбирают следующую последовательную инструкцию. Указатель инструкции устанавливается на непоследовательный адрес только тогда, когда оценивается переход или переход.
Оба процессора оценивают переходы на этапе декодирования и имеют выборку команды за один цикл. В результате повторение целевого перехода длится два цикла, и машина всегда извлекает инструкцию сразу после любого принятого перехода. Обе архитектуры определяют слоты задержки перехода, чтобы использовать эти извлеченные инструкции.
Более продвинутая форма статического прогнозирования предполагает, что обратные переходы будут выполняться, а прямые - нет. Обратная ветвь - это ветвь, у которой целевой адрес ниже, чем ее собственный адрес. Этот метод может помочь с точностью прогнозирования петель, которые обычно являются ветвями, указывающими назад, и которые используются чаще, чем не используются.
Некоторые процессоры позволяют вставлять в код подсказки прогнозирования ветвления, чтобы определить, следует ли выполнять статическое прогнозирование или нет. Intel Pentium 4 принимает подсказки предсказания ветвления, но от этой функции отказались в более поздних процессорах Intel.
Статическое предсказание используется в качестве метода отката в некоторых процессорах с динамическим предсказанием ветвления при динамическом предикторы не имеют достаточной информации для использования. И Motorola MPC7450 (G4e), и Intel Pentium 4 используют этот метод как запасной вариант.
При статическом прогнозировании все решения принимаются во время компиляции перед выполнением программы.
Динамическое предсказание ветвлений использует информацию о взятых или невыполненных ветвях, собранную во время выполнения, для прогнозирования результата ветвления.
Использование случайного или псевдослучайного бита (чистое предположение) гарантировало бы для каждой ветви 50% правильного предсказания, которое нельзя улучшить (или ухудшить) путем переупорядочения инструкций. (С помощью простейшего статического предсказания типа «предположить дубль» компиляторы могут переупорядочить инструкции, чтобы добиться более точного предсказания, чем 50%.) Кроме того, это сделало бы время [гораздо более] недетерминированным.
Некоторые суперскалярные процессоры (MIPS R8000, Alpha 21264 и Alpha 21464 (EV8)) выбирает каждую строку инструкций с указателем на следующую строку. Этот предсказатель следующей строки обрабатывает целевое предсказание, а также предсказание направления ветвления.
Когда предсказатель следующей строки указывает на выровненные группы из 2, 4 или 8 команд, целью ветвления обычно не будет первая извлеченная команда, и поэтому исходные извлеченные команды теряются. Предположим для простоты, что при равномерном распределении целевых объектов ветвления отбрасываются команды 0,5, 1,5 и 3,5 соответственно.
Поскольку сама ветвь обычно не будет последней инструкцией в выровненной группе, инструкции после взятой ветви (или ее слота задержки ) будут отброшены. Еще раз, предполагая равномерное распределение размещений инструкций ветвления, выбранные инструкции 0,5, 1,5 и 3,5 отбрасываются.
Отброшенные инструкции на линиях ветвления и назначения составляют почти полный цикл выборки, даже для одноциклового предсказателя следующей строки.
1-битный счетчик насыщения (по сути, триггер ) записывает последний результат филиал. Это самая простая из возможных версий динамического предсказателя ветвлений, хотя и не очень точная.
2-битный счетчик насыщения - это конечный автомат с четырьмя состояниями:
Рисунок 2: Диаграмма состояний 2-битного счетчика насыщения При оценке перехода обновляется соответствующий конечный автомат. Ветви, оцененные как непринятые, изменяют состояние в сторону категорически непринятые, а ветки, оцененные как принятые, изменяют состояние в сторону строго принятого. Преимущество схемы двухбитового счетчика перед однобитовой схемой состоит в том, что условный переход должен дважды отклоняться от того, что он делал в прошлом, прежде чем прогноз изменится. Например, условный переход при закрытии цикла неверно предсказывается один раз, а не дважды.
Исходный процессор Intel Pentium без MMX использует счетчик насыщения, хотя и с несовершенной реализацией.
На тестах SPEC '89, очень большие бимодальные предикторы насыщаются на 93,5% правильно, как только каждая ветвь отображается на уникальный счетчик.
Таблица предикторов индексируется с помощью битов адреса инструкции, так что процессор может получить предсказание для каждой инструкции перед ее декодированием.
Двухуровневый предсказатель ветвлений, также называемый предсказателем ветвления на основе корреляции, использует двумерную таблицу счетчиков, также называемую «таблицей истории шаблонов». Записи в таблице представляют собой двухбитовые счетчики.
Рисунок 3: Двухуровневый адаптивный предсказатель ветвления. Каждая запись в таблице истории паттернов представляет собой 2-битный счетчик насыщения типа, показанного на рисунке 2. Если оператор ifвыполняется три раза, решение, принятое о третьем выполнении, может зависеть от были ли взяты два предыдущих или нет. В таких сценариях двухуровневый адаптивный предсказатель работает более эффективно, чем счетчик насыщения. Условные скачки, которые выполняются каждый второй раз или имеют какую-либо другую регулярно повторяющуюся схему, плохо предсказываются счетчиком насыщения. Двухуровневый адаптивный предсказатель запоминает историю последних n вхождений ветви и использует один счетчик насыщения для каждого из двух возможных шаблонов истории. Этот метод проиллюстрирован на рисунке 3.
Рассмотрим пример n = 2. Это означает, что два последних вхождения ветви сохраняются в двухбитовом регистре сдвига. Этот регистр истории переходов может иметь четыре различных двоичных значения, 00, 01, 10 и 11, где ноль означает «не принят», а один означает «принято». Таблица истории паттернов содержит четыре записи на каждую ветвь, по одной для каждой из 2 = 4 возможных историй ветвей, и каждая запись в таблице содержит двухбитовый счетчик насыщения того же типа, что и на рисунке 2 для каждой ветви. Регистр истории ветвей используется для выбора того, какой из четырех счетчиков насыщения использовать. Если история 00, то используется первый счетчик; если в истории 11, то используется последний из четырех счетчиков.
Предположим, например, что условный переход выполняется каждый третий раз. Последовательность ветвления - 001001001... В этом случае запись номер 00 в таблице истории паттернов перейдет в состояние «сильно занято», что означает, что после двух нулей следует единица. Запись с номером 01 перейдет в состояние «категорически не принимается», что означает, что после 01 идет ноль. То же самое и с записью номер 10, в то время как запись с номером 11 никогда не используется, потому что никогда не бывает двух подряд идущих.
Общее правило для двухуровневого адаптивного предсказателя с n-битной историей состоит в том, что он может предсказывать любую повторяющуюся последовательность с любым периодом, если все n-битные подпоследовательности различны.
Преимущество двухуровневого адаптивного предсказателя заключается в том, что он может быстро научиться предсказывать произвольный повторяющийся шаблон. Этот метод был изобретен Т.-Ю. Да и Йель Патт в Мичиганском университете. С момента первой публикации в 1991 году этот метод стал очень популярным. Варианты этого метода прогнозирования используются в большинстве современных микропроцессоров.
Предиктор локального перехода имеет отдельный буфер истории для каждой инструкции условного перехода. Он может использовать двухуровневый адаптивный предсказатель. Буфер истории является отдельным для каждой инструкции условного перехода, в то время как таблица истории шаблона также может быть отдельной или может быть общей для всех условных переходов.
Intel Pentium MMX, Pentium II и Pentium III имеют локальные предикторы ветвления с локальным 4- битовая история и локальная таблица истории паттернов с 16 записями для каждого условного перехода.
В тестах SPEC '89 очень большие локальные предикторы верны на 97,1%.
Глобальный предсказатель ветвления не вести отдельную запись истории для каждого условного перехода. Вместо этого он хранит общую историю всех условных переходов. Преимущество общей истории состоит в том, что любая корреляция между разными условными переходами является частью прогнозирования. Недостатком является то, что история разбавляется нерелевантной информацией, если различные условные переходы некоррелированы, и что буфер истории может не включать в себя какие-либо биты из одной и той же ветви, если между ними много других ветвей. Он может использовать двухуровневый адаптивный предсказатель.
Эта схема лучше схемы счетчика насыщения только для больших размеров таблиц и редко бывает так же хороша, как локальное прогнозирование. Буфер истории должен быть длиннее, чтобы можно было делать хороший прогноз. Размер таблицы истории паттернов увеличивается экспоненциально с размером буфера истории. Следовательно, большая таблица истории паттернов должна использоваться всеми условными переходами.
Двухуровневый адаптивный предсказатель с глобальным общим буфером истории и таблицей истории паттернов называется предиктором "gshare", если он xors глобальной истории и ПК ветви, и "gselect", если он объединяет их. Глобальное предсказание ветвлений используется в процессорах AMD и в Intel Pentium M, Core, Core 2 и Silvermont на основе процессоров Atom.
Средство прогнозирования переходов со сплавлением объединяет принципы локального и глобального прогнозирования путем конкатенации локального и глобального истории переходов, возможно, с некоторыми битами из программного счетчика . Тесты показывают, что процессор VIA Nano может использовать этот метод.
Согласованный предсказатель - это двухуровневый адаптивный предсказатель с глобальным общим буфером истории и шаблоном таблица истории и дополнительный локальный счетчик насыщения. Выходные данные локального и глобального предикторов подвергаются операции XOR друг с другом, чтобы получить окончательный прогноз. Цель состоит в том, чтобы уменьшить количество конфликтов в таблице истории паттернов, где две ветви с противоположным прогнозом имеют одну и ту же запись в таблице истории паттернов.
Предиктор согласования использовался в первой версии Intel Pentium 4, но позже был заброшен.
Гибридный предсказатель, также называемый комбинированным предсказателем, реализует более одного механизма предсказания. Окончательный прогноз основан либо на мета-предикторе, который запоминает, какой из предикторов делал наилучшие прогнозы в прошлом, либо на функции большинства голосов, основанной на нечетном количестве разных предикторов.
предложил комбинированное предсказание ветвлений в своей статье 1993 года.
В тестах SPEC'89 такой предсказатель примерно так же хорош, как и локальный предсказатель.
Предикторы, такие как gshare, используют несколько записей таблицы для отслеживания поведения любой конкретной ветви. Такое умножение записей увеличивает вероятность того, что две ветви будут отображаться в одну и ту же запись таблицы (ситуация, называемая псевдонимом), что, в свою очередь, значительно повышает вероятность того, что точность прогнозирования для этих ветвей будет снижена. Если у вас есть несколько предикторов, полезно настроить, чтобы каждый предиктор имел разные шаблоны наложения, чтобы было более вероятно, что хотя бы один предиктор не будет иметь наложения. Комбинированные предикторы с разными функциями индексации для разных предикторов называются предикторами gskew и аналогичны асимметричным ассоциативным кэшам, используемым для кэширования данных и инструкций.
Условный переход, который управляет циклом, лучше всего предсказывается с помощью специального предиктора цикла. Условный переход в нижней части цикла, который повторяется N раз, будет выполнен N-1 раз, а затем не будет выполнен ни разу. Если условный переход помещен в начало цикла, он не будет выполняться N-1 раз, а затем будет выполнен один раз. Условный переход, который выполняется много раз в одну сторону, а затем один раз в другую, определяется как имеющий поведение цикла. Такой условный скачок легко предсказать с помощью простого счетчика. Предиктор цикла является частью гибридного предиктора, где мета-предиктор определяет, имеет ли условный переход поведение цикла.
Команда косвенного перехода может выбирать из более чем двух ветвей. Некоторые процессоры имеют специализированные косвенные предикторы ветвлений. Новые процессоры Intel и AMD могут предсказывать непрямые переходы с помощью двухуровневого адаптивного предсказателя. Этот вид инструкций вносит более одного бита в буфер истории. Процессоры zEC12 и более поздние версии z / Architecture от IBM поддерживают команду BRANCH PREDICTION PRELOAD, которая может предварительно загрузить запись предиктора ветвления для данной инструкции с целевым адресом ветвления, созданным путем добавления содержимого регистр общего назначения для значения немедленного смещения.
Процессоры без этого механизма просто предсказывают косвенный переход, чтобы перейти к той же цели, что и в прошлый раз.
A функция обычно возвращается туда, откуда она вызывается. Команда возврата представляет собой косвенный переход, который считывает свой целевой адрес из стека вызовов . Многие микропроцессоры имеют отдельный механизм прогнозирования для команд возврата. Этот механизм основан на так называемом буфере стека возврата, который является локальным зеркалом стека вызовов. Размер буфера стека возврата обычно составляет от 4 до 16 записей.
Иногда компромисс между быстрым предсказанием ветвления и хорошим предсказанием ветвления с двумя предикторами ветвления. Первый предсказатель ветвления быстрый и простой. Второй предиктор ветвления, который работает медленнее, сложнее и с большими таблицами, переопределит, возможно, неверный прогноз, сделанный первым предиктором.
Микропроцессоры Alpha 21264 и Alpha EV8 использовали быстрый одноцикловый предсказатель следующей строки для обработки повторения целевого перехода и обеспечения простого и быстрого предсказания перехода. Поскольку предсказатель следующей строки настолько неточен, а повторение разрешения ветвления занимает так много времени, оба ядра имеют двухцикловые вторичные предсказатели ветвления, которые могут отменять предсказание предсказателя следующей строки за счет одного цикла потерянной выборки.
Intel Core i7 имеет два целевых буфера ветвления и, возможно, два или более предиктора ветвления.
Машинное обучение для прогнозирования ветвлений с использованием LVQ и многослойных перцептронов, называемого «прогнозирование нейронных ветвей», было предложено Лучианом Винтаном (Университет Лучиана Блага Сибиу ). Год спустя он разработал предсказатель ветвления персептрона. Даниэль Хименес значительно развил исследования в области прогнозирования нейронных ветвей. В 2001 году был представлен первый предсказатель персептрона, который можно было реализовать аппаратно. Первая коммерческая реализация предсказателя ветвления персептрона была в микроархитектуре AMD Piledriver.
. Основным преимуществом нейронного предсказателя является его способность использовать длинные истории, требуя только линейного роста ресурсов. Классические предикторы требуют экспоненциального роста ресурсов. Хименес сообщает о глобальном улучшении на 5,7% по сравнению с гибридным предсказателем в стиле Макфарлинга. Он также использовал гибридные предикторы с переопределением gshare / персептрона.
Основным недостатком предиктора персептрона является его высокая задержка. Даже после использования преимуществ высокоскоростных арифметических приемов задержка вычислений относительно высока по сравнению с тактовым периодом многих современных микроархитектур. Чтобы уменьшить задержку предсказания, Хименес предложил в 2003 году нейронный предсказатель быстрого пути, где предсказатель персептрона выбирает свои веса в соответствии с текущим путем ветвления, а не в соответствии с ПК ветви. Эту концепцию разработали многие другие исследователи (А. Сезнец, М. Монкиеро, Д. Тарьян и К. Скадрон, В. Десмет, Аккари и др., К. Аасараай, Майкл Блэк и др.)
Большая часть в современных предсказателях ветвей используется предсказатель персептрона (см. Intel «Соревнование по предсказанию ветвей чемпионата»). Intel уже реализует эту идею в одном из симуляторов IA-64 (2003 г.).
Многоядерный процессор AMD Ryzen Infinity Fabric и процессор Samsung Exynos включают в себя предсказатель нейронного ветвления на основе персептрона.
IBM 7030 Stretch, разработанный в конце 1950-х годов, предварительно выполняет все безусловные переходы и любые условные переходы, которые зависят от индексных регистров. Для других условных ветвей первые две реализованные производственные модели прогнозируют невыполненное; последующие модели были изменены для реализации прогнозов на основе текущих значений бит индикатора (соответствующих сегодняшним кодам состояния). Дизайнеры Stretch учли статические подсказки в инструкциях ветвления в начале проекта, но отказались от них. Восстановление ошибочного прогноза было обеспечено модулем прогнозирования на Stretch, и часть репутации Stretch в отношении невысокой производительности объяснялась временем, необходимым для восстановления ошибочного прогноза. Последующие разработки больших компьютеров IBM не использовали предсказание ветвлений со спекулятивным исполнением до IBM 3090 в 1985 году.
Двухбитовые предикторы были введены Томом МакВильямсом и Куртом Виддоусом в 1977 году для журнала Lawrence Livermore. Суперкомпьютер National Lab S-1 и независимо от Джима Смита в 1979 году в CDC.
Микропрограммные процессоры, популярные с 1960-х по 1980-е годы и позже, выполняли несколько циклов на инструкцию и обычно не требовали предсказания ветвлений. Однако, помимо IBM 3090, есть несколько других примеров микропрограммных проектов, которые включают прогнозирование ветвлений.
Burroughs B4900, микропрограммная машина на языке COBOL, выпущенная примерно в 1982 году, была конвейерной и использовала предсказание ветвлений. Состояние предыстории предсказания ветвления B4900 сохраняется обратно в инструкции в памяти во время выполнения программы. B4900 реализует предсказание ветвления с 4 состояниями с использованием 4 семантически эквивалентных кодов операций ветвления для представления каждого типа оператора ветвления. Используемый код операции указывает на историю этой конкретной инструкции перехода. Если аппаратное обеспечение определяет, что состояние прогнозирования ветвления конкретной ветви необходимо обновить, оно перезаписывает код операции семантически эквивалентным кодом операции, намекающим на правильную историю. Эта схема имеет процент совпадений 93%. Патент США 4,435,756 и другие были выданы по этой схеме.
VAX 9000, анонсированный в 1989 году, является одновременно микропрограммным и конвейерным и выполняет прогнозирование ветвлений.
Первые коммерческие процессоры RISC, MIPS R2000 и R3000, а также более ранние процессоры SPARC выполняют только тривиальное предсказание ветвления «не использованное». Поскольку они используют слоты задержки переходов, выбирают только одну инструкцию за цикл и выполняются по порядку, потери производительности нет. Более поздний R4000 использует такое же тривиальное предсказание «невыполненного» ветвления и теряет два цикла для каждой взятой ветки, потому что повторение разрешения ветвлений длится четыре цикла.
Прогнозирование ветвлений стало более важным с появлением конвейерных суперскалярных процессоров, таких как Intel Pentium, DEC Alpha 21064, MIPS R8000 и серия IBM POWER. Все эти процессоры полагаются на однобитовые или простые бимодальные предикторы.
DEC Alpha 21264 (EV6) использует предиктор следующей строки, переопределенный комбинированным локальным предиктором и глобальным предиктором, где выбор комбинирования осуществляется бимодальным предиктором.
AMD K8 имеет комбинированный бимодальный и глобальный предсказатель, где выбор комбинирования является другим бимодальным предсказателем. Этот процессор кэширует базовый и выбранный счетчики бимодального предсказания в битах кэша L2, который иначе используется для ECC. В результате он имеет очень большую базу и таблицы предикторов выбора, а также контроль четности, а не ECC для инструкций в кэше L2. Схема контроля четности достаточна, так как любая инструкция, в которой возникла ошибка четности, может быть признана недействительной и повторно загружена из памяти.
Alpha 21464 (EV8, отменен на поздней стадии разработки) имел минимальный штраф за неправильное предсказание перехода в 14 циклов. Он должен был использовать сложный, но быстрый предсказатель следующей строки, замененный комбинированным бимодальным предсказателем и предсказателем с большинством голосов. Большинство голосов было между двухрежимным и двумя предикторами gskew.
В 2018 году Project Zero Google и другие исследователи обнародовали катастрофическую уязвимость системы безопасности под названием Spectre. Эта уязвимость затрагивает практически все современные ЦП и заключается в извлечении личных данных из оставшихся кэшей данных неверных предсказаний переходов.
