В.А. Фисун - Прикладное программирование в задачах математической физики. Архитектурные принципы построения ЭВМ (pdf) (1127762), страница 13
Текст из файла (страница 13)
Признаватьже результаты этой обработки действительными следует только после вычисления условия. Если случайно выбранная ветка не должна обрабатываться, то следует пропуск рабочих тактов оборудования, так как необходимокоды неверно выбранной ветки убрать из конвейера. Выполнение условного перехода, при котором происходит обработка одной из веток операторазаранее, называется “спекулятивным”. При этом производится исполнениевыбранного фрагмента программы, предвосхищая результаты неизвестногов этом момент вычисления условия перехода.
Дальнейшее развитие идеиопережающего выполнения фрагментов условных операторов привело к появлению механизмов предсказания результатов вычисления условных выражений в условных операторах.Предсказание переходов в условных операторах программы (branchprediction) позволяет продолжать выборку и декодирование потока инструкций после выборки инструкции ветвления (условного перехода), не дожидаясь проверки самого условия. Механизм предсказания переходов направляетпоток выборки и декодирования команд программы по одной из ветвей.
Исполнение по предположению, называемое также спекулятивным (speculativeexecution), идет дальше - предсказанные после перехода инструкции нетолько декодируются, но и по возможности исполняются до проверки условия перехода. Если предсказание сбывается, то работа предсказателя оказывается оправданной, если не сбывается - конвейер оказывается недогруженным и простаивает. Методы реализации предсказателей разделяются на статические и динамические методы.Статический метод предсказания реализуется по алгоритмам, заложенным в компиляторы в процессе трансляции программ. Известны особенности программ, характерные признаки того, что переходы по одним условиям, вероятнее всего, произойдут, а по другим - нет.
Так, для циклическихконструкций вероятность перехода на повторение цикла выше вероятностивыхода из него. Некоторые системы программирования дают возможностьпрограммисту указывать предполагаемую вероятность перехода непосредственно в программе на языке высокого уровня. Статическая схема выбораальтернативной ветки вычислений (результат предсказания переходов) в условных операторах фиксируются в объектных кодах следующим образом.Некоторые ЭВМ продолжают выбор в конвейер команд, текстуально следующих за командами передачи управления, тогда реализовать статическийметод предсказания переходов можно, помещая код с наибольшей вероятно-Пособие 17.09.0947стью перехода непосредственно за командой условного перехода (в примере, приведенном выше, это код оператора S1).
Для такого оборудованиякомпиляторы могут формировать объектный код с размещением наиболеевероятно выполняемого фрагмента программы непосредственно за командойусловного перехода. Некоторые системы команд содержат в коде условныхкоманд разряды, флаги для указания статических предположений о вероятности перехода по метке в условных операторах.Одним из методов уменьшения потерь на выполнение команд переходов, как условных, так и безусловных, является использования кэш-памятипрогнозирования переходов, называемой таблицей, буфером целевых адресов переходов - BTB (Branch Target Buffer).
Буфер содержат информацию окомандах переходов, последних по времени выполнения программы. Есливыполняемая команда перехода не представлена в таблице (пусть её объемравен 2n ), то в i-строку таблицы записывается TAG и <целевые адреса команды>. Номер строки таблицы – i есть значения n-младших разрядов адреса команды перехода (счетчика команд), а старшие разряды адреса этой команды перехода заносятся в поле TAG.
Поле <целевые адреса команды>может состоять из исполнительного адреса перехода, который формируетсяпри выполнении команды перехода. Если при выборки очередной командывыясняется факт нахождения ее в таблице ВТВ, тогда для команды безусловного перехода сразу известен исполнительный адрес перехода еще додешифрации выбранной команды. Выбранная команда игнорируется, всчетчик команд заносится исполнительный адрес перехода из таблицы.
Более того, в поле <целевые адреса команды> можно хранить код команды, накоторую указывает исполнительный адрес перехода. Для обработки командусловного перехода ВТВ используется совместно с аппаратом динамического предсказания переходов.Динамическое предсказание переходов опирается на предысторию выполнения вычислительного процесса - для каждого конкретного случая перехода накапливается статистика поведения.Аппаратный механизм учета вероятности перехода (динамический) состоит из блока предсказания переходов.
Этот блок, кроме учета статическиопределенных предпочтений для ветвлений, использует таблицу переходов, вкоторой хранится история переходов для каждого (в рамках объема таблицы)перехода программы. Большинство современных микропроцессоров обещают точность предсказаний переходов этим способом выше 90%.Для динамического прогнозирования переходов аппаратура собираетстатистику переходов, которая помещается в – BHT (Branch History Table).Реализация этой схемы имеет ряд красивых архитектурных решений. Таблица ВНТ содержит статистику о результатах вычисления условных выражений: каждая её строка соответствует выполненным условным операторам иона содержит информацию о том, как выполнялись переходы при предыдущих обращениях к данному оператору. Такой информацией в общем случаеПособие 17.09.0948является значение n-битового счетчика в строке таблицы и принципиальнаясхема прогнозирования перехода для текущего условного оператора такова.1.
Если значение счетчика больше нуля, то переход прогнозируется каквыполняемый. Если направление перехода предсказано верно, к значениюсчетчика прибавляется единица, иначе значение счетчика уменьшается наединицу.2. Если значение счетчика меньше нуля, то переход прогнозируется какневыполняемый.
Если направление перехода предсказано верно, из значениясчетчика вычитается единица, при неверном прогнозе - к значению счетчикаединица добавляется.Для упрощения работы со счетчиком в качестве “нуля”, нейтральнойточки отсчета, обычно выбирается точка из середины интервала значенийсчетчика (например, значение 2n – 1). При этом отказ от работы с отрицательными числами не отменяет процедуры проверки выхода значения счетчика за пределы интервала.Исследования n-битовых схем прогнозирования на тестовых задачахSPEC показало, что наилучшие результаты прогнозирования обеспечиваюттрех-битовые счетчики, причем результаты двух-битовых отличаются оттрех-битовых незначительно.
Большинство схем прогнозирования используют двух-битовые счетчики, причем для работы с ними используется алгоритм Смита. В соответствии с этим алгоритмом, значения счетчиков определяют четыре вероятности: ветвь часто исполняется (strongly taken, код – 11),ветвь выполняется (taken, код – 10), ветвь не выполняется (not taken, код 01), ветвь часто не выполняется (strongly not taken, код – 00). В этой схемепрогнозирования переход прогнозируется, если первый, левый бит равенединице. Правый бит в этой схеме показывает результат вычисления условия на предыдущем шаге.Другой проблемой является выбор размера таблицы ВНТ. Статистические исследования показывают, что таблица, состоящая из 4096 строк, даетвысокую точность прогнозов и на ряде тестовых пакетах работает практически также как и таблица бесконечного размера.Для идентификации строк таблицы ВНТ редко используют "честные"схемы с хранением в таблице значений счетчиков команд условного перехода (в виде тегов) из-за большого расхода памяти.
Обычно таблица ВНТ индексируется младшими разрядами адреса команды перехода. Возникающийпри этом эффект наложения (aliasing), адресации одной строки таблицыдвумя или более разными командами перехода может быть конструктивным,деструктивным и нейтральным. Считается, что при многократном выполнении команды условного перехода влияние эффекта наложения будет незначительным для прогнозирования работы этого оператора.Рассмотренная схема прогнозирования переходов является примеромодноуровневой схемы.
Более точный прогноз обеспечивают двухуровневые,коррелированные и гибридные схемы предсказания переходов. В такихсхемах кроме статистических данных используется дополнительно качест-Пособие 17.09.0949венная история переходов при помощи регистров переходов. Регистр глобальной истории (Global History Register) есть логическая шкала, в младшийразряд которой после сдвига шкалы заносится результат вычисления условного выражения текущего условного оператора перехода. Затем эташкала складывается по модулю 2 с младшими разрядами адреса командыперехода и полученное значение используется для индексации таблицыВНТ. Наконец, для каждой команды перехода можно хранить локальную историю переходов и её также использовать для предсказания переходов.Гибридные схемы предсказания переходов используют одновременнонесколько схем предсказания – предикторов, причем для предсказания перехода динамически выбирают результаты работы наиболее точного предиктора.
При этом выбор предиктора, наиболее адекватного ходу выполненияпрограммы, может производиться суперпредиктором по вышеперечисленным алгоритмам.Как динамический, так и статический подходы к предсказанию переходов в условных операторах имеют свои преимущества и недостатки. Преимущество статического подхода - отсутствие необходимости интегрироватьна чипе микропроцессора дополнительную аппаратуру предсказания переходов. Большинство современных микропроцессоров оборудованы различными средствами динамического предсказания переходов, производимогона базе анализа "предыстории". Динамическое предсказание переходов"мощнее" статического.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
