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

Текст из файла (страница 9)

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

Положение усложняется для команд условного перехода. Так, для условного оператора:

IF (A<B) GO TO L; S1; L:S2;

еще до вычисления значе­ния условного выражения (А<В) необходимо решать задачу о выборе ветки исполнения программы: заполнении кон­вейера команд кодами операторов S1 или S2. В процессорах прежних поколений инструкция перехода приостанавливала конвейер (выборку инструкций) до исполнения собственно команды перехода. При этом, естественно, терялась производительность. Банальная схема ускорения - вычисление условия перенести, по возможности, на ранние стадии выполнения программы. Статистика показывает, что такое переупорядочение порядка выполнения команд возможно не часто. Следующее простое решение – начать обработку одной из ветвей (любой) не дожидаясь окончания вычисления условия. Признавать же результаты этой обработки действительными следует только после вычисления условия. Если случайно выбранная ветка не должна обрабатываться, то следует пропуск рабочих тактов оборудования, так как необходимо коды неверно выбранной ветки убрать из конвейера. Выполнение условного перехода, при котором происходит обработка одной из веток оператора заранее, называется “спекулятивным”. При этом производится исполнение выбранного фрагмента программы, предвосхищая результаты неизвестного в этом момент вычисления условия перехода. Дальнейшее развитие идеи опережающего выполнения фрагментов условных операторов привело к появлению механизмов предсказания результатов вычисления условных выражений в условных операторах.

Предсказание переходов в условных операторах программы (branch prediction) позволяет продолжать выборку и декодирование потока инструкций после выборки инструкции ветвления (условного перехода), не дожидаясь проверки самого условия. Механизм предсказания переходов направляет поток выборки и декодирования команд программы по одной из ветвей. Исполнение по предположению, называемое также спекулятивным (speculative execution), идет дальше - предсказанные после перехода инструкции не только декодируются, но и по возможности исполняются до проверки условия перехода. Если предсказание сбывается, то работа предсказателя оказывается оправданной, если не сбывается - конвейер оказывается недогруженным и простаивает. Методы реализации предсказателей разделяются на статические и динамические методы.

Статический метод предсказания реализуется по алгоритмам, заложенным в компиляторы в процессе трансляции программ. Известны особенности программ, характерные признаки того, что переходы по одним условиям, вероятнее всего, произойдут, а по другим - нет. Так, для циклических конструкций вероятность перехода на повто­рение цикла выше вероятности выхода из него. Некоторые системы программирования дают возможность программисту указывать предполагаемую вероятность перехода непосредственно в программе на языке высокого уровня. Статическая схема выбора альтернативной ветки вычислений (результат предсказания переходов) в условных операторах фиксируются в объектных кодах следующим образом. Некоторые ЭВМ продолжают выбор в конвейер команд, текстуально следующих за командами передачи управления, тогда реализовать статический метод предсказания переходов можно, помещая код с наибольшей вероятностью перехода непосредственно за командой условного перехода (в примере, приведенном выше, это код оператора S1). Для такого оборудования компиляторы могут формировать объектный код с размещением наиболее вероятно выполняемого фрагмента программы непосредственно за командой условного перехода. Некоторые системы команд содержат в коде условных команд разряды, флаги для указания статических предположений о вероятности перехода по метке в условных операторах.

Одним из методов уменьшения потерь на выполнение команд переходов, как условных, так и безусловных, является использования кэш-памяти прогнозирования переходов, называемой таблицей, буфером целевых адресов переходов - BTB (Branch Target Buffer). Буфер содержат информацию о командах переходов, последних по времени выполнения программы. Если выполняемая команда перехода не представлена в таблице (пусть её объем равен 2ⁿ ), то в i-строку таблицы записывается TAG и <целевые адреса команды>. Номер строки таблицы – i есть значения n-младших разрядов адреса команды перехода (счетчика команд), а старшие разряды адреса этой команды перехода заносятся в поле TAG. Поле <целевые адреса команды> может состоять из исполнительного адреса перехода, который формируется при выполнении команды перехода. Если при выборки очередной команды выясняется факт нахождения ее в таблице ВТВ, тогда для команды безусловного перехода сразу известен исполнительный адрес перехода еще до дешифрации выбранной команды. Выбранная команда игнорируется, в счетчик команд заносится исполнительный адрес перехода из таблицы. Более того, в поле <целевые адреса команды> можно хранить код команды, на которую указывает исполнительный адрес перехода. Для обработки команд условного перехода ВТВ используется совместно с аппаратом динамического предсказания переходов.

Динамическое предсказание переходов опирается на предысторию выполнения вычислительного процесса - для каждого конкретного случая перехода накапливается статистика поведения.

Аппаратный механизм учета вероятности перехода (динамический) состоит из блока предсказания переходов. Этот блок, кроме учета статически определенных предпочтений для ветвлений, использует таблицу переходов, в которой хранится история переходов для каждого (в рамках объема таблицы) перехода программы. Большинство современных микропроцессоров обещают точность предсказаний переходов этим способом выше 90%.

Для динамического прогнозирования переходов аппаратура собирает статистику переходов, которая помещается в – BHT (Branch History Table). Реализация этой схемы имеет ряд красивых архитектурных решений. Таблица ВНТ содержит статистику о результатах вычисления условных выражений: каждая её строка соответствует выполненным условным операторам и она содержит информацию о том, как выполнялись переходы при предыдущих обращениях к данному оператору. Такой информацией в общем случае является значение n-битового счетчика в строке таблицы и принципиальная схема прогнозирования перехода для текущего условного оператора такова.

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

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

Для упрощения работы со счетчиком в качестве “нуля”, нейтральной точки отсчета, обычно выбирается точка из середины интервала значений счетчика (например, значение 2n – 1). При этом отказ от работы с отрицательными числами не отменяет процедуры проверки выхода значения счетчика за пределы интервала.

Исследования n-битовых схем прогнозирования на тестовых задачах SPEC показало, что наилучшие результаты прогнозирования обеспечивают трех-битовые счетчики, причем результаты двух-битовых отличаются от трех-битовых незначительно. Большинство схем прогнозирования используют двух-битовые счетчики, причем для работы с ними используется алгоритм Смита. В соответствии с этим алгоритмом, значения счетчиков определяют четыре вероятности: ветвь часто исполняется (strongly taken, код – 11), ветвь выполняется (taken, код – 10), ветвь не выполняется (not taken, код -01), ветвь часто не выполняется (strongly not taken, код – 00). В этой схеме прогнозирования переход прогнозируется, если первый, левый бит равен единице. Правый бит в этой схеме показывает результат вычисления условия на предыдущем шаге.

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

Для идентификации строк таблицы ВНТ редко используют "честные" схемы с хранением в таблице значений счетчиков команд условного перехода (в виде тегов) из-за большого расхода памяти. Обычно таблица ВНТ индексируется младшими разрядами адреса команды перехода. Возникающий при этом эффект наложения (aliasing), адресации одной строки таблицы двумя или более разными командами перехода может быть конструктивным, деструктивным и нейтральным. Считается, что при многократном выполнении команды условного перехода влияние эффекта наложения будет незначительным для прогнозирования работы этого оператора.

Рассмотренная схема прогнозирования переходов является примером одноуровневой схемы. Более точный прогноз обеспечивают двухуровневые, коррелированные и гибридные схемы предсказания переходов. В таких схемах кроме статистических данных используется дополнительно качественная история переходов при помощи регистров переходов. Регистр глобальной истории (Global History Register) есть логическая шкала, в младший разряд которой после сдвига шкалы заносится результат вычисления условного выражения текущего условного оператора перехода. Затем эта шкала складывается по модулю 2 с младшими разрядами адреса команды перехода и полученное значение используется для индексации таблицы ВНТ. Наконец, для каждой команды перехода можно хранить локальную историю переходов и её также использовать для предсказания переходов.

Гибридные схемы предсказания переходов используют одновременно несколько схем предсказания – предикторов, причем для предсказания перехода динамически выбирают результаты работы наиболее точного предиктора. При этом выбор предиктора, наиболее адекватного ходу выполнения программы, может производиться суперпредиктором по вышеперечисленным алгоритмам.

Как динамический, так и статический подходы к предсказанию переходов в условных операторах имеют свои преимущества и недостатки. Преимущество статического подхода - отсутствие необходимости интегрировать на чипе микропроцессора дополнительную аппаратуру предсказания переходов. Большинство современных микропроцессоров оборудованы различными средствами динамического предсказания переходов, производимого на базе анализа "предыстории". Динамическое предсказание пере­ходов "мощнее" статического. Однако у динамического предсказания есть и свои слабые места - это проблемы, возникающие из-за ограниченности ресурсов для сбора статистики. Статические методы предсказания используются совместно с динамическими методами.

5. Глава 5

Архитектура ЭВМ

5.1. Системы команд

Архитектура набора команд (ISA), называемая иногда системой команд ЭВМ, восходит к фон-неймановской архитектуре, содержавшей всего 21 команду. Эволюция системы команд непосредственно связана с развитием всей архитектуры ЭВМ и будет рассматриваться, в основном, на примере наиболее характерных команд обработки данных - инструкций выполнения арифметических или логических функций, инструкций управления. Команда ЭВМ - это инструкция для аппаратной реализация единичного акта преобразования информации в ЭВМ, состоящая из кода операции команды (имени функции преобразования) и адреса (ов) - ссылки на аргументы и на результат функции. Кроме основного результата, каждая команда вырабатывает дополнительный, который служит служебной информацией для последующих команд. Служебная информация фиксируется в системных регистрах – битах индикации. В них хранится информация об особенностях выполнения текущей команды, например, был ли результат арифметической операции равен нулю или отрицателен. К служебной информации относится также значение программного счетчика команд (СК) – адреса размещения в ОЗУ исполняемой команды. Набор команд разделяется на команды, предоставляемые прикладным программистам, и привилегированные команды.

Команды для программирования приложений обеспечивают реализацию арифметических и логических операций, команд управления, пересылок. Состав арифметических команд, кроме базовых операций: +, -, *, /, может содержать команды вычисления тригонометрических функций и др. Набор аргументов таких операций трансформировался от чисел с фиксированной запятой до вещественных чисел обычной и двойной точности, от скалярных аргументов до векторных аргументов. Объявлены планы реализации ЭВМ для арифметики с иными системами счисления, например, интервальной арифметики. Логические команды реализуют операции Булевой алгебры, формирования логических шкал: сдвиги, сборки, разборки и директивы для по-байтовой обработки текста. Команды управления служат для управления ходом выполнения программы. Команды безусловной передачи управления – требование начать выполнение команды, адрес размещения которой в ОЗУ указан в команде. Команды условной передачи нарушают последовательный перебор команд для исполнения только тогда, когда характеристика результата выполнения предыдущей команды соответствует заданному условию. К командам управления относятся и команды организации циклов, примитивы для проверки окончания цикла с одновременной индексацией параметра цикла. Особую группу команд управления составляют команды обращения к подпрограммам и возврата из них.

Адреса команд – аргументы операции - бывают следующих типов. Литералы - это задание, запись в команде аргумента в явном виде. Например, в трехадресной команде можно задать в виде (*, А1, “2”, А3) арифметическую операцию – число из А1 умножить на число 2 и отправить в А3. Частой, а иногда и единственной, формой адресов в некоторых архитектурах ЭВМ является ссылки на регистры, элементы из набора ячеек сверхоперативной памяти процессора. В таких регистрах хранятся аргументы операции, в них же может записываться результат. Наконец, адресом может служить ссылка на байт оперативной памяти, который определяет первую компоненту аргумента (если аргумент длиннее одного байта). На этом примере прямой адресации простота адресации операндов в командах ЭВМ заканчивается, появляется возможность косвенной адресации данных. В таких схемах адрес памяти, по которому хранится аргумент - исполнительный (эффективный) адрес - формируется по заданным правилам из элементов, указанных в адресе команды. Косвенная адресация (адрес в адресе) состоит в том, что по указанному в команде адресу (ссылка на слово памяти в регистре или в ОЗУ) хранится не сам аргумент - операнд, а адрес памяти, где и содержится требуемый операнд. Исполнительный адрес в команде может вычисляться, например путем сложения содержимого заданного регистра с константой, которая указана в адресе команды. В архитектуре IА32 определяются 12 способов формирования исполнительных адресов. “А смерть Кащеева находится в яйце, которое хранится в ларце, который и т.д.”.

Характеристики

Список файлов книги