В архитектуре компьютера предсказатель ветвления [1] [2] [3] [4] [5] — это цифровая схема , которая пытается угадать, в каком направлении пойдет ветвь (например, структура if–then–else ), прежде чем это станет известно окончательно. Цель предсказателя ветвления — улучшить поток в конвейере инструкций . Предсказатели ветвления играют важную роль в достижении высокой производительности во многих современных архитектурах конвейерных микропроцессоров .
Двустороннее ветвление обычно реализуется с помощью инструкции условного перехода . Условный переход может быть либо «принят», и перейти в другое место в памяти программы, либо «не принят», и выполнение продолжится сразу после условного перехода. Неизвестно наверняка, будет ли выполнен условный переход или нет, пока условие не будет вычислено и условный переход не пройдет стадию выполнения в конвейере инструкций (см. рис. 1).
Без прогнозирования ветвлений процессору пришлось бы ждать, пока инструкция условного перехода не пройдет стадию выполнения, прежде чем следующая инструкция сможет войти в стадию выборки в конвейере. Предсказатель ветвлений пытается избежать этой траты времени, пытаясь угадать, будет ли выполнен условный переход наиболее вероятно или нет. Затем выбирается ветвь, которая, как предполагается, является наиболее вероятной, и выполняется спекулятивно . Если позже обнаруживается, что предположение было неверным, то спекулятивно выполненные или частично выполненные инструкции отбрасываются, и конвейер начинает заново с правильной ветви, что приводит к задержке.
Время, которое тратится впустую в случае неправильного предсказания ветвления , равно числу стадий в конвейере от стадии выборки до стадии выполнения. Современные микропроцессоры, как правило, имеют довольно длинные конвейеры, так что задержка неправильного предсказания составляет от 10 до 20 тактов . В результате, увеличение длины конвейера увеличивает потребность в более продвинутом предсказателе ветвления. [6]
Когда впервые встречается инструкция условного перехода, информации для прогнозирования не так много. Но предсказатель ветвлений сохраняет записи о том, были ли выполнены переходы или нет. Когда он сталкивается с условным переходом, который встречался несколько раз, он может основывать прогноз на истории. Предсказатель ветвлений может, например, распознать, что условный переход выполняется чаще, чем нет, или что он выполняется каждый второй раз.
Предсказание ветвления не то же самое, что предсказание цели ветвления . Предсказание ветвления пытается угадать, будет ли выполнен условный переход или нет. Предсказание цели ветвления пытается угадать цель выполненного условного или безусловного перехода до того, как она будет вычислена путем декодирования и выполнения самой инструкции. Предсказание ветвления и предсказание цели ветвления часто объединяются в одну и ту же схему.
Статическое предсказание — это простейший метод предсказания ветвлений, поскольку он не опирается на информацию о динамической истории выполнения кода. Вместо этого он предсказывает результат ветвления, основываясь исключительно на инструкции ветвления. [7]
Ранние реализации SPARC и MIPS (две из первых коммерческих архитектур RISC ) использовали однонаправленное статическое предсказание ветвлений: они всегда предсказывают, что условный переход не будет выполнен, поэтому они всегда выбирают следующую последовательную инструкцию. Только когда оценивается ветвь или переход и обнаруживается, что они выполнены, указатель инструкции устанавливается на непоследовательный адрес.
Оба ЦП оценивают ветви на этапе декодирования и имеют одноцикловую выборку инструкций. В результате целевой цикл повторения ветви длится два цикла, и машина всегда выбирает инструкцию сразу после любой взятой ветви. Обе архитектуры определяют слоты задержки ветвления для использования этих извлеченных инструкций.
Более продвинутая форма статического прогнозирования предполагает, что обратные переходы будут выполнены, а прямые — нет. Обратная ветвь — это ветвь, целевой адрес которой ниже ее собственного адреса. Эта техника может помочь с точностью прогнозирования циклов, которые обычно являются ветвями, указывающими назад, и чаще выполняются, чем не выполняются.
Некоторые процессоры позволяют вставлять подсказки предсказания ветвлений в код, чтобы указать, следует ли использовать статическое предсказание или нет. Intel Pentium 4 принимает подсказки предсказания ветвлений, но эта функция была заброшена в более поздних процессорах Intel. [8]
Статическое предсказание используется как резервный метод в некоторых процессорах с динамическим предсказанием ветвлений, когда динамические предикторы не имеют достаточной информации для использования. И Motorola MPC7450 (G4e) , и Intel Pentium 4 используют этот метод как резервный метод. [9]
При статическом прогнозировании все решения принимаются во время компиляции, до выполнения программы. [10]
Динамическое предсказание ветвлений [2] использует информацию о принятых или непринятых ветвях, собранную во время выполнения, для прогнозирования результата ветвления. [1]
Использование случайного или псевдослучайного бита (чистое предположение) гарантировало бы каждой ветви 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-битный насыщающийся счетчик [1] представляет собой конечный автомат с четырьмя состояниями:
Когда оценивается ветвь, обновляется соответствующая машина состояний. Ветви, оцененные как не принятые, изменяют состояние в сторону строго не принятые, а ветви, оцененные как принятые, изменяют состояние в сторону строго принятые. Преимущество двухбитовой схемы счетчика над однобитовой схемой заключается в том, что условный переход должен дважды отклониться от того, что он делал больше всего в прошлом, прежде чем изменится предсказание. Например, условный переход, замыкающий цикл, неверно предсказан один раз, а не два.
Оригинальный процессор Intel Pentium без MMX использует насыщающийся счетчик, хотя и с несовершенной реализацией. [8]
В тестах SPEC '89 очень большие бимодальные предикторы достигают 93,5% точности, как только каждая ветвь сопоставляется с уникальным счетчиком. [11] : 3
Таблица предиктора индексируется битами адреса инструкции , так что процессор может получить прогноз для каждой инструкции до того, как инструкция будет декодирована.
Двухуровневый предиктор ветвлений, также называемый предиктором ветвлений на основе корреляции, использует двумерную таблицу счетчиков, также называемую «Таблица истории шаблонов». Записи таблицы представляют собой двухбитовые счетчики.
Если ifоператор выполняется три раза, решение, принятое при третьем выполнении, может зависеть от того, были ли выполнены предыдущие два или нет. В таких сценариях двухуровневый адаптивный предиктор работает эффективнее счетчика насыщения. Условные переходы, которые выполняются каждый второй раз или имеют какой-либо другой регулярно повторяющийся шаблон, не предсказываются хорошо счетчиком насыщения. Двухуровневый адаптивный предиктор запоминает историю последних n вхождений ветви и использует один счетчик насыщения для каждого из возможных 2 n шаблонов истории. Этот метод проиллюстрирован на рисунке 3.
Рассмотрим пример n = 2. Это означает, что последние два вхождения ветви хранятся в двухбитном сдвиговом регистре . Этот регистр истории ветвей может иметь четыре различных двоичных значения, 00, 01, 10 и 11, где ноль означает «не принято», а единица означает «принято». Таблица истории шаблонов содержит четыре записи на ветвь, по одной для каждой из 2 2 = 4 возможных историй ветвей, и каждая запись в таблице содержит двухбитный счетчик насыщения того же типа, что и на рисунке 2 для каждой ветви. Регистр истории ветвей используется для выбора того, какой из четырех счетчиков насыщения использовать. Если история равна 00, то используется первый счетчик; если история равна 11, то используется последний из четырех счетчиков.
Предположим, например, что условный переход выполняется каждый третий раз. Последовательность ветвления — 001001001... В этом случае запись под номером 00 в таблице истории шаблонов перейдет в состояние «строго принято», указывая на то, что после двух нулей идет единица. Запись под номером 01 перейдет в состояние «строго не принято», указывая на то, что после 01 идет ноль. То же самое и с записью под номером 10, в то время как запись под номером 11 никогда не используется, поскольку никогда не бывает двух последовательных единиц.
Общее правило для двухуровневого адаптивного предиктора с n-битной историей заключается в том, что он может предсказать любую повторяющуюся последовательность с любым периодом, если все n-битные подпоследовательности различны. [8]
Преимущество двухуровневого адаптивного предиктора в том, что он может быстро научиться предсказывать произвольный повторяющийся шаблон. Этот метод был изобретен Т.-Й. Йе и Йейлом Паттом в Мичиганском университете . [13] С момента первой публикации в 1991 году этот метод стал очень популярным. Варианты этого метода предсказания используются в большинстве современных микропроцессоров. [ необходима цитата ]
Был предложен двухуровневый предсказатель ветвлений, в котором второй уровень заменен нейронной сетью . [14]
Локальный предсказатель ветвления имеет отдельный буфер истории для каждой инструкции условного перехода. Он может использовать двухуровневый адаптивный предсказатель. Буфер истории является отдельным для каждой инструкции условного перехода, в то время как таблица истории шаблона может быть также отдельной или может быть общей для всех условных переходов.
Intel Pentium MMX , Pentium II и Pentium III имеют локальные предсказатели переходов с локальной 4-битной историей и локальной таблицей истории шаблонов с 16 записями для каждого условного перехода .
В тестах SPEC '89 очень большие локальные предикторы дают 97,1% правильных результатов. [11] : 6
Глобальный предсказатель ветвлений не хранит отдельную запись истории для каждого условного перехода. Вместо этого он хранит общую историю всех условных переходов. Преимущество общей истории в том, что любая корреляция между различными условными переходами является частью создания прогнозов. Недостаток в том, что история разбавляется нерелевантной информацией, если различные условные переходы не коррелируют, и что буфер истории может не включать биты из той же ветви, если между ними есть много других ветвей. Он может использовать двухуровневый адаптивный предсказатель.
Эта схема лучше схемы насыщающего счетчика только для больших размеров таблиц, и она редко бывает так же хороша, как локальное предсказание. Буфер истории должен быть больше, чтобы сделать хорошее предсказание. Размер таблицы истории шаблонов растет экспоненциально с размером буфера истории. Следовательно, большая таблица истории шаблонов должна быть общей для всех условных переходов.
Двухуровневый адаптивный предиктор с глобально общим буфером истории и таблицей истории шаблонов называется предиктором "gshare", если он xor'ит глобальную историю и ветвь PC, и "gselect", если он их объединяет . Глобальное предсказание ветвей используется в процессорах AMD , а также в процессорах Intel Pentium M , Core , Core 2 и Atom на базе Silvermont .
Сплавленный предсказатель ветвлений [15] объединяет локальные и глобальные принципы предсказания, объединяя локальные и глобальные истории ветвлений, возможно, также с некоторыми битами из счетчика программ . Тесты показывают, что процессор VIA Nano может использовать эту технику. [8]
Согласованный предиктор — это двухуровневый адаптивный предиктор с глобально общим буфером истории и таблицей истории шаблонов, а также дополнительным локальным насыщающим счетчиком. Выходы локального и глобального предиктора объединяются с помощью операции XOR друг с другом для получения окончательного прогноза. Цель состоит в том, чтобы уменьшить конфликты в таблице истории шаблонов, где две ветви с противоположным прогнозом случайно разделяют одну и ту же запись в таблице истории шаблонов. [16]
Гибридный предиктор, также называемый комбинированным предиктором, реализует более одного механизма прогнозирования. Окончательное прогнозирование основано либо на мета-предсказателе, который помнит, какой из предсказателей сделал лучшие прогнозы в прошлом, либо на функции голосования большинства, основанной на нечетном числе различных предикторов.
Скотт Макфарлинг предложил комбинированное предсказание ветвлений в своей статье 1993 года. [11]
В тестах SPEC'89 такой предиктор примерно так же хорош, как и локальный предиктор. [ необходима цитата ]
Предикторы, такие как gshare, используют несколько записей таблицы для отслеживания поведения любой конкретной ветви. Это умножение записей делает гораздо более вероятным, что две ветви будут отображаться в одной и той же записи таблицы (ситуация, называемая псевдонимом), что, в свою очередь, делает гораздо более вероятным, что точность прогнозирования для этих ветвей пострадает. Когда у вас есть несколько предикторов, полезно организовать так, чтобы каждый предиктор имел разные шаблоны псевдонимов, так что более вероятно, что по крайней мере один предиктор не будет иметь псевдонимов. Комбинированные предикторы с разными функциями индексации для разных предикторов называются предикторами gskew и аналогичны перекошенным ассоциативным кэшам , используемым для кэширования данных и инструкций.
Условный переход , который управляет циклом, лучше всего предсказать с помощью специального предиктора цикла. Условный переход в нижней части цикла, который повторяется N раз, будет выполнен N-1 раз, а затем не будет выполнен один раз. Если условный переход помещен в верхнюю часть цикла, он не будет выполнен N-1 раз, а затем не будет выполнен один раз. Условный переход, который идет много раз в одну сторону, а затем один раз в другую сторону, определяется как имеющий циклическое поведение. Такой условный переход можно легко предсказать с помощью простого счетчика. Предиктор цикла является частью гибридного предиктора, где мета-предиктор определяет, имеет ли условный переход циклическое поведение.
Инструкция косвенного перехода может выбирать из более чем двух ветвей. Некоторые процессоры имеют специализированные предикторы косвенных ветвей. [17] [18] Более новые процессоры от Intel [19] и AMD [20] могут предсказывать косвенные ветвления, используя двухуровневый адаптивный предиктор. Этот тип инструкций вносит более одного бита в буфер истории. Процессоры zEC12 и более поздние процессоры z/Architecture от IBM поддерживают инструкцию BRANCH PREDICTION PRELOAD , которая может предварительно загружать запись предиктора ветвления для данной инструкции с целевым адресом ветвления, созданным путем добавления содержимого регистра общего назначения к значению непосредственного смещения. [21] [22]
Процессоры без этого механизма просто предскажут косвенный переход к той же цели, что и в прошлый раз. [8]
Функция обычно возвращается туда, откуда она была вызвана. Инструкция возврата — это косвенный переход, который считывает свой целевой адрес из стека вызовов . Многие микропроцессоры имеют отдельный механизм прогнозирования для инструкций возврата. Этот механизм основан на так называемом буфере стека возврата , который является локальным зеркалом стека вызовов. Размер буфера стека возврата обычно составляет 4–16 записей. [8]
Компромисс между быстрым предсказанием ветвлений и хорошим предсказанием ветвлений иногда решается с помощью двух предсказателей ветвлений. Первый предсказатель ветвлений быстрый и простой. Второй предсказатель ветвлений, который медленнее, сложнее и с большими таблицами, переопределит возможно неверное предсказание, сделанное первым предсказателем .
Микропроцессоры Alpha 21264 и Alpha EV8 использовали быстрый однотактный предсказатель следующей строки для обработки целевой рекуррентности ветвления и обеспечения простого и быстрого предсказания ветвления. Поскольку предсказатель следующей строки настолько неточен, а рекуррентность разрешения ветвления занимает так много времени, оба ядра имеют двухтактные вторичные предсказатели ветвления, которые могут переопределить предсказание предиктора следующей строки ценой одного потерянного цикла выборки.
Intel Core i7 имеет два буфера целевых переходов и, возможно, два или более предсказателей переходов. [23]
Машинное обучение для предсказания ветвлений с использованием LVQ и многослойных персептронов , называемое « нейронным предсказанием ветвлений», было предложено Лучианом Винтаном ( Университет Лучиана Благи в Сибиу ). [24] Год спустя он разработал предсказатель ветвлений персептрона. [25] Исследования в области нейронного предсказателя ветвлений были значительно расширены Дэниелом Хименесом. [26] В 2001 году [26] был представлен первый предсказатель персептрона , который можно было реализовать на оборудовании. Первая коммерческая реализация предсказателя ветвлений персептрона была реализована в микроархитектуре Piledriver компании AMD . [27]
Главное преимущество нейронного предиктора — его способность использовать длинные истории, требуя при этом только линейного роста ресурсов. Классические предикторы требуют экспоненциального роста ресурсов. Хименес сообщает о глобальном улучшении на 5,7% по сравнению с гибридным предиктором в стиле Макфарлинга. [28] Он также использовал gshare/perceptron, переопределяющий гибридные предикторы. [28]
Главным недостатком предиктора персептрона является его высокая задержка. Даже после использования высокоскоростных арифметических трюков задержка вычислений относительно высока по сравнению с тактовым периодом многих современных микроархитектур. Чтобы уменьшить задержку предсказания, Хименес предложил в 2003 году нейронный предиктор быстрого пути , в котором предиктор персептрона выбирает свои веса в соответствии с путем текущей ветви, а не в соответствии с PC ветви. Многие другие исследователи развивали эту концепцию (A. Seznec, M. Monchiero, D. Tarjan & K. Skadron, V. Desmet, Akkary et al., K. Aasaraai, Michael Black и др.). [ необходима цитата ]
Большинство современных предсказателей ветвлений используют предсказатель персептрона (см. "Championship Branch Prediction Competition" от Intel [29] ). Intel уже реализует эту идею в одном из симуляторов IA-64 (2003). [30]
Многоядерный процессор AMD Ryzen [31] [ 32] [33] Infinity Fabric и процессор Samsung Exynos включают в себя нейронный предсказатель ветвлений на основе персептрона.
IBM 7030 Stretch , разработанный в конце 1950-х годов, предварительно выполняет все безусловные переходы и любые условные переходы, зависящие от индексных регистров. Для других условных переходов первые две производственные модели реализовали прогнозирование непринятых; последующие модели были изменены для реализации прогнозов на основе текущих значений битов индикатора (соответствующих сегодняшним кодам условий). [34] Разработчики Stretch рассматривали статические биты подсказок в инструкциях ветвления на ранней стадии проекта, но решили отказаться от них. Восстановление после неправильного предсказания обеспечивалось блоком опережающего просмотра в Stretch, и часть репутации Stretch как не совсем звездной производительности была связана со временем, необходимым для восстановления после неправильного предсказания. Последующие проекты больших компьютеров IBM не использовали предсказание ветвлений с спекулятивным выполнением до IBM 3090 в 1985 году.
Двухбитные предикторы были введены Томом Мак-Вильямсом и Куртом Уиддоусом в 1977 году для суперкомпьютера S-1 Национальной лаборатории Лоуренса в Ливерморе и независимо Джимом Смитом в 1979 году в CDC. [35]
Микропрограммируемые процессоры, популярные с 1960-х по 1980-е годы и позже, занимали несколько циклов на инструкцию и, как правило, не требовали предсказания ветвлений. Однако, помимо IBM 3090, есть несколько других примеров микропрограммируемых конструкций, которые включали предсказание ветвлений.
Burroughs B4900 , микропрограммируемая машина COBOL, выпущенная около 1982 года, была конвейерной и использовала прогнозирование ветвлений. Состояние истории прогнозирования ветвлений B4900 сохраняется обратно в инструкциях в памяти во время выполнения программы. B4900 реализует прогнозирование ветвлений с 4 состояниями, используя 4 семантически эквивалентных кода операции ветвления для представления каждого типа оператора ветвления. Используемый код операции указывает на историю этой конкретной инструкции ветвления. Если оборудование определяет, что состояние прогнозирования ветвлений конкретной ветви необходимо обновить, оно перезаписывает код операции семантически эквивалентным кодом операции, который намекает на правильную историю. Эта схема достигает 93% попаданий. На эту схему были выданы патенты США 4,435,756 и другие.
DEC VAX 9000 , анонсированный в 1989 году, является как микропрограммным, так и конвейерным процессором, а также выполняет прогнозирование ветвлений. [36]
Первые коммерческие RISC-процессоры, MIPS R2000 и R3000 , а также более ранние процессоры SPARC , делают только тривиальное "непринятое" предсказание ветвлений. Поскольку они используют слоты задержки ветвлений, извлекают только одну инструкцию за цикл и выполняют по порядку, потери производительности нет. Более поздний R4000 использует то же самое тривиальное "непринятое" предсказание ветвлений и теряет два цикла на каждую принятую ветвь, поскольку повторение разрешения ветвлений длится четыре цикла.
Предсказание ветвлений стало более важным с появлением конвейерных суперскалярных процессоров, таких как Intel Pentium , DEC Alpha 21064 , MIPS R8000 и IBM POWER series. Все эти процессоры полагаются на однобитные или простые бимодальные предикторы.
DEC Alpha 21264 (EV6) использует предиктор следующей строки, переопределенный комбинированным локальным предиктором и глобальным предиктором, где выбор комбинирования осуществляется бимодальным предиктором. [37]
AMD K8 имеет комбинированный бимодальный и глобальный предиктор, где объединенный выбор является другим бимодальным предиктором. Этот процессор кэширует счетчики базового и выборочного бимодального предиктора в битах кэша L2, которые в противном случае использовались для ECC. В результате он имеет фактически очень большие таблицы базового и выборочного предиктора и четность вместо ECC для инструкций в кэше L2. Конструкция четности достаточна, поскольку любая инструкция, в которой возникла ошибка четности, может быть признана недействительной и повторно извлечена из памяти.
Alpha 21464 [37] (EV8, отменен на поздней стадии проектирования) имел минимальный штраф за неверное предсказание ветвления в 14 циклов. Он должен был использовать сложный, но быстрый предиктор следующей строки, переопределенный комбинированным бимодальным и мажоритарным предиктором. Большинство голосов было между бимодальным и двумя gskew-предикторами.
В 2018 году катастрофическая уязвимость безопасности под названием Spectre была обнародована Project Zero от Google и другими исследователями. Затрагивая практически все современные процессоры , уязвимость включает в себя подготовку предсказателей ветвлений, так что другой процесс (или ядро) неправильно предскажет ветвь и будет использовать секретные данные в качестве индекса массива, вытесняя одну из строк кэша злоумышленника. Злоумышленник может засечь доступ к своему собственному массиву, чтобы выяснить, какой именно, превращая это внутреннее (микроархитектурное) состояние ЦП в значение, которое злоумышленник может сохранить, и которое содержит информацию о значениях, которые он не мог прочитать напрямую. [38]