Предсказание переходов спекулятивное выполнение

Предсказание переходов

Более эффективными для снижения потерь от конфликтов по управлению являются методы предсказания переходов. Они призваны максимально ускорить определение адреса команды, выполняемой после команды перехода.

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

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

Существуют статические и динамические методы предсказания переходов. При использовании статических методов до выполнения программы для каждой команды условного перехода указывается направление наиболее вероятного ветвления. Это указание делается программой-компилятором по заложенным в ней алгоритмам. Также это может делать и сам программист по опыту выполнения аналогичных программ либо по результатам тестового выполнения программы.

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

Ядро процессора начинает выбирать из подсистемы памяти и выполнять команды по предсказанной ветви программы (так называемое выполнение по предположению, или «спекулятивное» выполнение). Однако так как направление перехода может быть предсказано неверно, получаемые результаты с целью обеспечения возможности их аннулирования не записываются в память или регистры (то есть для них не выполняется этап ЗР), а накапливаются в специальном буфере результатов.

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

При этом буфер результатов и конвейер, содержащий команды, которые следуют за командой условного перехода и находятся на разных этапах обработки, — очищаются. Аннулируются результаты всех уже выполненных этапов этих команд. Конвейер начинает загружаться с первой команды другой ветви программы.

Следует отметить, что конфликты по управлению не исчерпываются только проблемами, связанными с командами условных переходов. Они возникают при выполнении всех команд, меняющих значение счетчика команд. Это хорошо видно из табл. 30.1. Если команда i является командой такого типа (например, команда безусловного перехода), то адрес перехода будет вычислен ею в такте 5, в то время как уже в такте 2 необходимо выбирать следующую команду по этому адресу.

Для команд безусловных переходов однажды вычисленный целевой адрес сохраняется в специальной памяти BTB (Branch Target Buffer), откуда он извлекается сразу же при дешифрации данной команды.

Аналогичный подход используется для команд вызова процедуры и — возврата из нее (анализ связок CALL — RETURN).

Источник

Спекулятивное исполнение — Speculative execution

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

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

Спекулятивная многопоточность — это частный случай спекулятивного исполнения.

Содержание

Обзор

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

Варианты

Спекулятивные вычисления были родственной более ранней концепцией.

Нетерпеливое исполнение

Нетерпеливое исполнение — это форма спекулятивного исполнения, при которой выполняются обе стороны условной ветви; однако результаты фиксируются, только если предикат истинен. При неограниченных ресурсах активное выполнение (также известное как выполнение оракула ) теоретически обеспечит ту же производительность, что и идеальное предсказание ветвления . При ограниченных ресурсах активное выполнение следует использовать осторожно, поскольку количество необходимых ресурсов растет экспоненциально с каждым уровнем активного выполнения ветви.

Прогнозируемое исполнение

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

Связанные понятия

Ленивая казнь

Ленивое исполнение противоположно нетерпеливому исполнению и не предполагает спекуляций. Включение спекулятивного исполнения в реализации языка программирования Haskell , ленивого языка, является актуальной темой исследований. Eager Haskell , вариант языка, основан на идее спекулятивного исполнения. Кандидатская диссертация 2003 года заставила GHC поддержать своего рода спекулятивное исполнение с механизмом прерывания беременности, позволяющим отказаться от неудачного выбора, называемого оптимистическим исполнением . Это сочли слишком сложным.

Уязвимости безопасности

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

Источник

Спекулятивное исполнение — Speculative execution

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

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

Спекулятивная многопоточность — это частный случай спекулятивного исполнения.

СОДЕРЖАНИЕ

Обзор

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

Варианты

Спекулятивное вычисление было связано с более ранней концепцией.

Нетерпеливое исполнение

Нетерпеливое исполнение — это форма спекулятивного исполнения, при которой выполняются обе стороны условной ветви; однако результаты фиксируются только в том случае, если предикат истинен. При неограниченных ресурсах активное выполнение (также известное как выполнение оракула ) теоретически обеспечит ту же производительность, что и идеальное предсказание ветвления . При ограниченных ресурсах активное выполнение следует использовать осторожно, поскольку количество необходимых ресурсов растет экспоненциально с каждым уровнем активного выполнения ветви.

Прогнозируемое исполнение

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

Связанные понятия

Ленивая казнь

Ленивое исполнение противоположно нетерпеливому исполнению и не предполагает спекуляций. Включение спекулятивного исполнения в реализации ленивого языка программирования Haskell — это текущая тема исследований. Вариант языка Eager Haskell основан на идее спекулятивного исполнения. Кандидатская диссертация 2003 года заставила GHC поддержать своего рода спекулятивное исполнение с механизмом прерывания беременности, позволяющим отказаться от неудачного выбора, называемого оптимистическим исполнением . Это сочли слишком сложным.

Уязвимости безопасности

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

Источник

Предсказание переходов

Предсказание переходов на сегодняшний день рассматривается как один из наибо­лее эффективных способов борьбы с конфликтами по управлению. Идея заключа­ется в том, что еще до момента выполнения команды условного перехода или сразу же после ее поступления на конвейер делается предположение о наиболее вероят­ном исходе такой команды (переход произойдет или не произойдет). Последую­щие команды подаются на конвейер в соответствии с предсказанием. Для иллюст­рации вернемся к примеру (см. рис. 9.5), где команда 3 является командой УП. Пусть для команды 3 предсказано, что переход не произойдет. Тогда вслед за ко­мандой 3 на конвейер будут поданы команды 4-6 и т. д. Если предсказан переход, то после команды 3 на конвейер подаются команды 15-17. При ошибочном пред­сказании конвейер необходимо вернуть к состоянию, с которого началась выборка «ненужных» команд (очистить начальные ступени конвейера), и приступить к заг­рузке, начиная с «правильной» точки, что по эффекту эквивалентно приостановке конвейера. Цена ошибки может оказаться достаточно высокой, но при правиль­ных предсказаниях крупен и выигрыш — конвейер функционирует ритмично без остановок и задержек, причем выигрыш тем больше, чем выше точность предска­зания. Термин «точность предсказания* в дальнейшем будем трактовать как про­центное отношение числа правильных предсказаний к их общему количеству. В работе [70] дается следующая оценка: чтобы снижение производительности кон­вейера из-за его остановок по причине конфликтов по управлению не превысило 10%, точность предсказания переходов должна быть выше 97,7%.

К настоящему моменту известно более двух десятков различных способов реа­лизации идеи предсказания переходов [165,230-232], отличающихся друг от дру­га исходной информацией, на основании которой делается прогноз, сложностью реализации и, главное, точностью предсказания. При классификации схем пред­сказания переходов обычно выделяют два подхода: статический и динамический, в зависимости от того, когда и на базе какой информации делается предсказание. Эффективность большинства из приводимых в учебнике методов предсказа­ния переходов иллюстрируется результатами исследований, опубликованными в [68,95,107,197,207,228]. Все эксперименты проводились по примерно одинако­вой методике: численные показатели получены путем имитации методов предска­зания переходов при выполнении наборов стандартных тестовых программ. Глав­ное различие заключалось в выборе тестовых программ, что и нашло отражение в существенном расхождении полученных оценок.

Так, в работе Смита [197] использовались шесть тестовых программ, написан­ных на языке Фортран: Л ADVAN: решение системы из трех дифференциальных уравнений в частных

производных; Ш GIBSON: искусственная программа компиляции набора команд, примерно удов­летворяющего так называемой смеси Гибсона № 5;

Я SCI2: обращение матрицы;

* SINCOS: преобразование массива координат из полярной системы отсчета
в прямоугольную;

Ш SORTST: сортировка массива из 10 000 целых чисел;

II TBLINK: работа со связанным списком.

В-прочих исследованиях участвовали программы, входящие в различные вер­сии тестовых пакетов SPEC, в частности пакетов SPEC_92, SPEC_95 и CPU2000.

Последующий материал раздела посвящен рассмотрению различных механиз­мов предсказания переходов.

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

Статическое предсказание переходов осуществляется на основе некоторой апри­орной информации о подлежащей выполнению программе. Предсказание делает­ся на этапе компиляции программы и в процессе вычислений уже не меняется. -J Главное различие между известными механизмами статического прогнозирования заключается в виде информации, используемой для предсказания, и ее трактовке. Исходная информация может быть получена двумя путями: на основе анализа кода . программы или в результате ее профилирования (термин «профилирование» по- .1 ясняется ниже).

Известные стратегии статического предсказания для команд УП можно клас-исифицировать следующим образом:

• переход происходит всегда (ПВ);

‘ переход не происходит никогда (ПН); Ш предсказание определяется по результатам профилирования;

i предсказание определяется кодом операции команды перехода;

ш предсказание зависит от направления перехода;

Ш при первом выполнении команды переход имеет место всегда.

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

Интуитивное представление, что обе стратегии должны приводить к верному предсказанию в среднем в 50% случаев, на практике не подтверждается. Так, по результатам тестирования (рис. 9.8), приведенным в [197], предсказание об обяза­тельном переходе оказалось правильным в среднем для 76% команд УП.

Точность предсказания Рис. 9.8. Точность предсказания переходов при стратегии «переход происходит всегда»

Аналогичный показатель, полученный на ином наборе тестовых программ [ 150], составил 68%. В работе [228] приводятся результаты проверки стратегии ПВ на тестах CPU2000 отдельно для программ с интенсивными целочисленными вычис­лениями и программ с преимущественной обработкой чисел в форме с плавающей запятой. Для первых средняя точность предсказаний составила 55,2%, а для вто­рых — 59,9%. В других источниках встречаются и иные численные оценки точнос­ти прогноза при стратегии ПВ, в частности 60% и 71,9%. В то же время в работе [233] отмечается, что для ряда программ, связанных с целочисленной обработкой, процент правильных предсказаний может опускаться ниже 50%.

Цифры свидетельствуют, что успешность стратегии ПВ существенно зависит от характера программы и методов программирования, что, естественно, можно рассматривать как недостаток. Тем не менее стратегия все же используется в ряде ВМ, в частности MIPS-X, SuperSPARC, микропроцессорах i486 фирмы Intel. Свя­зано это, скорее всего, с простотой реализации и с тем, что для определенного класса программ стратегию можно считать достаточно эффективной.

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

Стратегия ПН реализована в конвейерах микропроцессоров М68020 и МС88000, вычислительной машине VAX 11/780. Сравнительная оценка стратегий ПВ и ПН, полученная при выполнении тестов CPU2000 для целочисленных и веществен­ных вычислений [228], показана на рис. 9.9.

Рис. 9.9. Сравнение статических стратегий ПВ и ПН

Из диаграммы видно, что ни одна из двух стратегий не обладает явным преиму­ществом над другой. Тем не менее анализ большого количества программ [154] показывает, что условные переходы имеют место более чем в 50% случаев, поэто­му если стоимость реализации двух рассмотренных вариантов одинакова, то пред­почтение следует отдать стратегии ПВ.

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

Средняя вероятность правильного предсказания, полученная на программах тестового набора SPEC_92, составила 75%. Стратегия используется в процессорах MIPS 4×00 и PowerPC 603.

При предсказании на основе кода операции команды перехода для одних команд предполагается, что переход произойдет, для других — его не случится. Например, для команды перехода по переполнению логично предположить, что перехода не будет. На практике назначение разным видам команд УП наиболее вероятного исхода чаще производится по результатам профилирования программ. В исследо­ваниях Е. Смита [197] стратегия ПВ была назначена командам перехода по усло­виям: «меньше нуля», «равно», «больше или равно», а ПН — всем прочим коман­дам условного перехода. Результаты показаны на рис. 9.10.

Эффективность предсказания зависит от характера программы. Этим, в част­ности, объясняется различие в выводах, полученных на основе разных исследова­ний. Так, согласно [154] стратегия приводит к успеху в среднем более чем в 75% случаев, а исследования Е. Смита дают цифру 86,7%.

Достаточно логичным представляется предсказание исходя из направления пе- I рехода. Если указанный в команде адрес перехода меньше содержимого счетчика _;

Рис. 9.10. Точность предсказания переходов при стратегии «переход зависит от кода операции»

команд, говорят о переходе «назад», и для такой команды назначается стратегия ПВ. Переход к адресу, превышающему адрес команды перехода, считается перехо­дом «вперед», и такой команде назначается стратегия ПН. В основе рассматривае­мого подхода лежит статистика по множеству программ, согласно которой боль­шинство команд УП в программах используются для организации циклов, причем, как правило, переходы происходят к началу цикла (переходы «назад»). Согласно [120], для команд, выполняющих переход «назад», фактический переход имеет место в 85% случаев. Для переходов «вперед» эта цифра составляет 65%. Таким образом, для команд условного перехода «назад» логично принять, что переход происходит всегда. Рассматриваемую стратегию иногда называют «Переход назад происходит всегда». Результаты ее оценки [197] приведены на рис. 9.11.

Рис. 9.11. Точность предсказания переходов при стратегии «переход зависит от направления перехода»

Здесь при тестировании на пакете SPEC_89 средняя точность предсказания со­ставила 65%. Среди ВМ, где описанная стратегия является основной, можно упомя­нуть MicroSPARC-2 и РА-7х00. Чаще, однако, стратегия используется в качестве вто­ричного механизма в схемах динамического прогнозирования переходов.

В последней из рассматриваемых статических стратегий при первом выполне­нии любой команды условного перехода делается предсказание, что переход обязательно будет. Предсказания на последующее выполнение команды зависят от правильнос­ти начального предсказания. Стратегию можно считать статической только частич­но, поскольку она однозначно определяет исход команды лишь при первом ее выпол­нении. Точность прогноза в соответствии с данной стратегией выше, чем у всех предшествующих, что подтверждают результаты, приведенные на рис. 9.12 [197].

К сожалению, при больших объемах программ вариант практически нереа­лизуем из-за того, что нужно отслеживать слишком много команд условного перехода.

Рис. 9.12. Точность предсказания переходов при стратегии «при первом выполнении переход обязательно происходит»

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

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

Идея динамического предсказания переходов предполагает накопление инфор­мации об исходе предшествующих команд УП. История переходов фиксируется в форме таблицы, каждый элемент которой состоит из т битов. Нужный элемент таблицы указывается с помощью ^-разрядной двоичной комбинации — шаблона (pattern). Этим объясняется общепринятое название таблицы предыстории пере­ходов — таблица истории для шаблонов (PHT, Pattern History Table).

При описании динамических схем предсказания переходов их часто расцени­вают как один из видов автоматов Мура, при этом содержимое элементов РНТ трактуется как информация, отображающая’текущее состояние автомата. В рабо­те [230] рассмотрены различные варианты подобных автоматов, однако реально осмысленно говорить лишь о трех вариантах, которые условно обозначим Al, А2 и A3.

Автомат А1 имеет только два состояния, поэтому каждый элемент РНТ состоит из одного бита (т = 1), значение которого отражает исход последнего выполнения команды условного перехода. Диаграмма состояний автомата А1 приведена на рис. 9.13.

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник