ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12211
Скачиваний: 10
Увеличение производительности
303
Динамическое прогнозирование ветвления
Ясно, что точные прогнозы очень ценны, поскольку это позволяет процессору ра-
ботать с полной скоростью. В настоящее время проводится множество исследова-
ний, целью которых является усовершенствование алгоритмов прогнозирования
ветвления (например, [32,70,108,125,138,163]). Один из подходов — хранить спе-
циальную таблицу (в особом аппаратном обеспечении), в которую центральный
процессор записывает условные переходы, когда они встречаются, и там их можно
искать, когда они снова появятся. Простейшая версия такой схемы показана на
рис. 4.28,
а.
В данном случае эта таблица содержит одну ячейку для каждой коман-
ды условного перехода. В ячейке находится адрес команды перехода, а также бит,
который указывает, был ли сделан переход, когда эта команда встретилась по-
следний раз. Прогноз состоит в том, что программа пойдет тем же путем, каким
она пошла в прошлый раз после этой команды перехода. Если прогноз неверен,
бит в таблице меняется.
Бит
достоверности
-лот
Бит
перехода
Адрес/ 1
тег перехода
1
Бит
достоверности
Слот
Биты
прогнозирования
Адрес/ перехода
тег перехода *
II.
6
5
4
3
2
1
0
J
Бит
достоверности
Слот
Адрес/
тег перехода
Бит
перехода
Целевой адрес
Рис.
4.28. Таблица динамики ветвлений с 1 -битным указателем перехода (а), таблица
динамики ветвлений с 2-битным указателем перехода (б), соответствие между адресом
команды перехода и целевым адресом (в)
Существует несколько способов организации данной таблицы. В действи-
тельности точно такие же способы используются при организации кэш-памяти,
304 Глава 4. Микроархитектурный уровень
Рассмотрим машину с 32-битными командами, которые расположены таким обра-
зом, что два младших бита каждого адреса памяти — 00. Таблица содержит 2
П
ячеек
(строк). Из команды перехода можно извлечь п+2 младших бита и осуществить
сдвиг вправо на два бита. Это n-битное число можно использовать в качестве
индекса в таблице, где проверяется, совпадает ли адрес, сохраненный там, с адре-
сом перехода. Как и в случае с кэш-памятью, здесь нет необходимости сохранять
п+2 младших бита, поэтому их можно опустить (то есть сохраняются только стар-
шие адресные биты — тег). Если адреса совпали, бит прогнозирования использу-
ется для предсказания перехода. Если тег неправильный или элемент недействи-
телен, значит, имеет место несовпадение. В этом случае можно применять правило
перехода вперед/назад.
Если таблица динамики переходов содержит, скажем, 4096 элементов, то адре-
са 0, 16384, 32768,... будут конфликтовать; аналогичная проблема встречается и
при работе с кэш-памятью. Здесь возможно такое же решение: двухальтернатив-
ный, четырехальтернативный, n-альтернативный ассоциативный элемент. Как и у
кэш-памяти, предельный случай — один п-альтернативный ассоциативный элемент.
При достаточно большом размере таблицы и достаточной ассоциативности эта
схема хорошо работает в большинстве ситуаций. Тем не менее систематически
встречается одна проблема. Когда происходит выход из цикла, переход в конце
будет предсказан неправильно, и, что еще хуже, этот неправильный прогноз изме-
нит бит в таблице, который теперь будет указывать, что переход совершать не надо.
В следующий раз, когда опять будет выполняться цикл, переход в конце первого
прохождения цикла будет спрогнозирован неправильно. Если цикл находится внут-
ри другого цикла или внутри часто вызываемой процедуры, эта ошибка будет по-
вторяться слишком часто.
Для устранения такой ситуации мы немного изменим метод, чтобы прогноз
менялся только после двух последовательных неправильных предсказаний. Такой
подход требует наличия двух предсказывающих битов в таблице: один указывает,
предполагается ли совершить переход или нет, а второй указывает, что было сде-
лано в прошлый раз. Таблица показана на рис. 4.28,
6.
Этот алгоритм можно представить в виде конечного автомата с четырьмя со-
стояниями (рис. 4.29). После ряда последовательных успешных предсказаний
«перехода нет» конечный автомат будет находиться в состоянии 00 и в следую-
щий раз также прогнозировать, что «перехода нет». Если этот прогноз неправиль-
ный, автомат переходит в состояние 01, но в следующий раз все равно предсказы-
вает отсутствие перехода. Только в том случае, если это последнее предсказание
ошибочно, конечный автомат перейдет в состояние 11 и будет все время прогнози-
ровать наличие перехода. Фактически, левый бит — это прогноз, а правый бит —
это то, что было сделано в прошлый раз (то есть был ли совершен переход). В дан-
ной разработке используется только 2 специальных бита, но возможно примене-
ние и 4, и 8 битов.
Это не первый конечный автомат, который мы рассматриваем. На рис. 4.19
тоже изображен конечный автомат. На самом деле все наши микропрограммы мож-
но считать конечными автоматами, поскольку каждая строка представляет особое
состояние, в котором может находиться автомат, с четко определенными перехо-
дами к конечному набору других состояний. Конечные автоматы очень широко
используются во всех аспектах разработки аппаратного обеспечения.
Увеличение производительности 305
Нет перехода
Переход
Переход
Повторное
предсказание
отсутствия
перехода
Повторное
предсказание
перехода
Предсказание
перехода
Предсказание
отсутствия
перехода
Нет перехода
Рис. 4.29. Двубитный конечный автомат для прогнозирования переходов
До сих пор мы предполагали, что цель каждого условного перехода известна.
Обычно или в явном виде давался адрес, к которому нужно перейти (он содержал-
ся прямо в самой команде), или было известно смещение относительно текущей
команды (то есть число со знаком, которое нужно было прибавить к счетчику ко-
манд). Часто это предположение имеет силу, но некоторые команды условного
перехода вычисляют целевой адрес, выполняя определенные арифметические дей-
ствия над значениями регистров, а затем уже переходят туда. Даже если взять ко-
нечный автомат, изображенный на рис. 4.29, который точно прогнозирует перехо-
ды, такой прогноз будет не нужен, поскольку целевой адрес неизвестен. Один из
возможных выходов из подобной ситуации — сохранить в таблице адрес, к которо-
му был осуществлен переход в прошлый раз, как показано на рис. 4.28,
в.
Тогда,
если в таблице указано, что в прошлый раз, когда встретилась команда перехода по
адресу 516, переход был совершен в адрес 4000, и если сейчас предсказывается
совершение перехода, то целевым адресом снова будет 4000.
Еще один подход к прогнозированию ветвления — следить, были ли соверше-
ны последние к условных переходов, независимо от того, какие это были команды
[108]. Это k-битное число, которое хранится в
сдвиговом регистре динамики пе-
реходов,
затем сравнивается параллельно со всеми элементами таблицы с к-бит-
ным ключом, и в случае совпадения применяется то предсказание, которое найде-
но в этом элементе. Удивительно, но эта технология работает достаточно хорошо.
Статическое прогнозирование ветвления
Все технологии прогнозирования ветвления, которые обсуждались до сих пор, яв-
ляются динамическими, то есть выполняются во время работы программы. Они
также приспосабливаются к текущему поведению программы, и это их положи-
тельное качество. Отрицательной стороной этих технологий является то, что они
требуют специализированного и дорогостоящего аппаратного обеспечения, а так-
же наличия очень сложных микросхем.
Можно пойти другим путем и призвать на помощь компилятор. Когда компи-
лятор получает такое выражение, как
for (1=0 1 < 1000000, 1++) { }
306 Глава 4. Микроархитектурный уровень
это знает, что переход в конце цикла будет происходить практически всегда. Если
бы только был способ сообщить это аппаратному обеспечению, можно было бы
избавиться от огромного количества работы. '
Хотя это связано с изменением архитектуры (а не только с вопросом реализа-
ции), в некоторых машинах, например UltraSPARC II, имеется еще один набор
команд условного перехода помимо обычных (которые нужны для обратной со-
вместимости). Новые команды содержат бит, по которому компилятор определя-
ет, совершать переход или не совершать. Когда встречается такой бит, блок выбор-
ки команд просто делает то, что ему сказано. Более того, нет необходимости тратить
драгоценное пространство в таблице предыстории переходов для этих команд, что
сокращает количество конфликтных ситуаций.
Наконец, наша последняя технология прогнозирования ветвления основана на
профилировании [37]. Это тоже статическая технология, только в данном случае
программа не заставляет компилятор вычислять, какие переходы нужно совершать,
а какие нет. В данном случае программа действительно выполняется, а ветвления
фиксируются. Эта информация поступает в компилятор, который затем использу-
ет специальные команды условного перехода для того, чтобы сообщить аппарат-
ному обеспечению, что нужно делать.
Исполнение с изменением последовательности
и подмена регистров
Большинство современных процессоров являются и конвейеризированными и
суперскалярными, как показано на рис. 2.5. Это значит, что там есть блок выборки
команд, который заранее вызывает команды из памяти и передает их в блок деко-
дирования. Блок декодирования, в свою очередь, передает декодированные коман-
ды в соответствующие функциональные блоки для выполнения. В некоторых слу-
чаях этот блок может разбивать отдельные команды на микрооперации, перед тем
как отправить их в функциональные блоки.
Ясно, что самым простым является компьютер, в котором все команды выпол-
няются в том порядке, в котором они вызываются из памяти (предполагается, что
прогнозирование переходов всегда оказывается верным). Однако такое последо-
вательное выполнение не всегда дает оптимальную производительность из-за вза-
имной зависимости команд. Если команде требуется значение, которое вычисля-
ется предыдущей командой, вторая команда не может начать выполняться, пока
первая не выдаст нужную величину. В такой ситуации реальной взаимозависимо-
сти второй команде приходится ждать. Существуют и другие виды взаимозависи-
мостей, но о них мы поговорим позже.
Чтобы обойти эти проблемы и достичь лучшей производительности, некото-
рые процессоры пропускают взаимозависимые команды и переходят к следующим
(независимым) командам. Думаю, не нужно говорить, что алгоритм распределе-
ния команд должен давать такой же результат, как если бы все команды выполня-
лись в том порядке, в котором они написаны. А теперь продемонстрируем на кон-
кретном примере, как происходит переупорядочение команд.
Чтобы изложить основную суть проблемы, начнем с машины, которая запуска-
ет команды в том порядке, в котором они расположены в программе, и требует,
чтобы выполнение команд завершалось также в порядке, соответствующем про-
граммному. Важность второго требования прояснится позднее.
Увеличение производительности
3 0 7
Наша машина содержит 8 регистров, видимых для программиста, от R0 до
R7. Все арифметические команды используют три регистра: два — для операндов
и один — для результата, как и в микроархитектуре Mic-4. Мы предполагаем, что
если команда декодируется в цикле п, выполнение начинается в цикле п+1. В случае
с простой командой, например командой сложения или вычитания, запись обрат-
но в выходной регистр происходит в конце цикла п+2. В случае с более сложной
командой, например командой умножения, запись в регистр происходит в конце
цикла n+З Чтобы сделать наш пример реалистичным, мы позволим блоку декоди-
рования выпускать до двух команд за цикл. Некоторые суперскалярные процессо-
ры могут выпускать 4 или даже 6 команд за цикл.
Последовательность выполнения команд показана в табл. 4.12. В первом столб-
це приводится номер цикла, во втором — номер команды, а в третьем — сама ко-
манда. В четвертом столбце указано, выдача каких команд произошла (максимум
две команды за цикл). Цифры в пятом столбце сообщают, какие команды заверше-
ны Помните, что в нашем примере мы требуем, чтобы команды и запускались, и
завершались в строгом порядке, поэтому выдача команды к+1 может произойти
только после выдачи команды к, а результат команды к+1 не может быть записан
в выходной регистр до того, как завершится выполнение команды к. Оставшиеся
16 столбцов мы обсудим ниже.
Таблица 4.12.
Суперскалярный процессор с последовательной выдачей
и последовательным завершением команд
Цикл
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#
1
2
3
4
5
6
7
8
Команда
R3=R0*R1
R4=R0+R2
R5=R0+R1
R6=R1+R4
R7=R1'R2
R1=R0-R2
R3=R3*R1
R1=R4+R4
Выдача
1
2
3
-
4
5
-
6
-
7
8
Завер-
шение
1
2
3
4
5
6
7
8
Считываемые регистры Записываемые регистры
0
1
2
3
3
3
2
1
1
1
1
1
1
1
2
2
2
1
1
1
2
2
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
4 5 6 7
1
1
1
2
2
0 1
1
1
1
1
1
2 3
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
5
1
1
1
1
1
6
1
1
1
7
1
1
1