В компьютерной архитектуре предсказатель ветвления [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 возможных шаблонов истории. Этот метод проиллюстрирован на рисунке 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 глобальной истории и ветвящегося ПК, и «gselect», если он объединяет их. Глобальное предсказание ветвлений используется в процессорах AMD , а также в процессорах Atom на базе Intel Pentium M , Core , Core 2 и 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 году нейронный предиктор быстрого пути , в котором предиктор перцептрона выбирает свои веса в соответствии с путем текущей ветви, а не в соответствии с ПК ветки. Эту концепцию развивали многие другие исследователи (А. Сезнец, М. Монкьеро, Д. Тарьян и К. Скадрон, В. Десмет, Аккари и др., К. Аасарааи, Майкл Блэк и др.). [ нужна цитата ]
Большинство современных предсказателей ветвей используют предсказатель перцептрона (см. Intel «Чемпионат по предсказанию ветвей» [29] ). Intel уже реализовала эту идею в одном из симуляторов IA-64 (2003 г.). [30]
Infinity Fabric многоядерного процессора AMD Ryzen [31] [32] [33] и процессор 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 . Все эти процессоры полагаются на однобитные или простые бимодальные предикторы.
DEC Alpha 21264 (EV6) использует предиктор следующей строки, переопределяемый комбинированным локальным предсказателем и глобальным предсказателем, где выбор объединения осуществляется бимодальным предсказателем. [37]
AMD K8 имеет комбинированный бимодальный и глобальный предиктор, где комбинированным выбором является другой бимодальный предиктор. Этот процессор кэширует базовые счетчики бимодальных предсказателей и счетчики выбора в битах кэша L2, которые в противном случае используются для ECC. В результате он фактически имеет очень большие базовые таблицы и таблицы предикторов выбора, а также четность, а не ECC для инструкций в кэше L2. Конструкция четности достаточна, поскольку любая инструкция, содержащая ошибку четности, может быть признана недействительной и повторно выбрана из памяти.
Alpha 21464 [37] (EV8, отмененный на поздних стадиях разработки) имел минимальный штраф за неправильное предсказание ветвления в 14 циклов. Он должен был использовать сложный, но быстрый предиктор следующей строки, переопределяемый комбинированным бимодальным предиктором и предиктором с большинством голосов. Большинство голосов было между бимодальным и двумя предикторами gskew.
В 2018 году проект Google Project Zero и другие исследователи обнародовали катастрофическую уязвимость системы безопасности под названием Spectre . Затрагивая практически все современные процессоры , уязвимость предполагает извлечение частных данных из оставшихся кэшей данных в результате неверных прогнозов ветвей. [38]