ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12198
Скачиваний: 10
3 0 8 Глава 4. Микроархитектурный уровень
После декодирования команды блок декодирования должен определить, за-
пускать ли команду сразу или нет. Для этого блок декодирования должен знать
состояния всех регистров. Если, например, текущей команде требуется регистр,
значение которого еще не подсчитано, текущая команда не может быть выпущена,
и центральный процессор должен простаивать.
Следить за состоянием регистров будет специальное устройство — счетчик об-
ращений (scoreboard), который впервые появился в CDC 6600. Счетчик обраще-
ний содержит небольшой счетчик для каждого регистра, который показывает,
сколько раз этот регистр используется командами, выполняющимися в данный
момент, в качестве источника. Если одновременно может выполняться максимум
15 команд, тогда будет достаточно 4-битного счетчика. Когда запускается коман-
да, элементы счетчика обращений, соответствующие регистрам операндов, увели-
чиваются на 1. Когда выполнение команды завершено, соответствующие элементы
счетчика уменьшаются на 1.
Счетчик обращений также содержит счетчики для регистров, которые исполь-
зуются в качестве пунктов назначения. Поскольку допускается только одна запись
за раз, эти счетчики могут быть размером в один бит. Правые 16 столбцов табл. 4.12
демонстрируют показания счетчика обращений.
В реальных машинах счетчик обращений также следит за использованием функ-
ционального блока, чтобы избежать выдачи команды, для которой нет доступ-
ного функционального блока. Для простоты мы предполагаем, что подходящий
функциональный блок всегда имеется в наличии, поэтому функциональные блоки
в таблице не показаны.
В первой строке табл. 4.12 показана команда 1, которая перемножает значения
регистров R0 и К1,ипомещаетрезультатврегистр113. Поскольку ни один из этих
регистров еще не используется, команда запускается, а счетчик обращений пока-
зывает, что регистры R0 и R1 считываются, а регистр R3 записывается. Ни одна из
последующих команд не может записывать результат в эти регистры и не может
считывать регистр R3 до тех пор, пока не завершится выполнение команды 1. По-
скольку это команда умножения, она закончится в конце цикла 4. Значения счет-
чика обращений, приведенные в каждой строке, отражают состояние регистров
после запуска команды, записанной в этой же строке. Пустые клетки соответству-
ют значению 0.
Поскольку рассматриваемый пример — это суперскалярная машина, которая
может запускать две команды за цикл, вторая команда выдается также во время
цикла 1. Она складывает значения регистров R0 и R2, а результат сохраняет в ре-
гистре R4. Чтобы определить, можно ли запускать эту команду, применяются сле-
дующие правила:
1. Если какой-нибудь операнд записывается, запускать команду нельзя (RAW-
взаимозависимость).
2. Если считывается регистр результатов, запускать команду нельзя (WAR-
взаимозависимость).
3. Если записывается регистр результатов, запускать команду нельзя (WAW-
взаимозависимость).
Мы уже рассматривали RAW-взаимозависимости, имеющие место, когда ко-
манде в качестве источника нужно использовать результат предыдущей команды,
Увеличение производительности 309
которая еще не завершилась. Два других типа взаимозависимостей менее серьез-
ные. По существу, они связаны с конфликтами ресурсов. В
WAR-взаимозависимо-
сти (Write After Read — запись после чтения) одна команда пытается перезаписать
регистр, который предыдущая команда еще не закончила считывать.
WAW-взаи-
мозависимость (Write After Write — запись после записи)
сходна с WAR-взаи-
мозависимостыо. Этого можно избежать, если вторая команда будет помещать ре-
зультат где-либо в другом месте еще (возможно, временно). Если ни одна из трех
упомянутых ситуаций не возникает и нужный функциональный блок доступен,
то команду можно выпустить. В этом случае команда 2 использует регистр R0, ко-
торый в данный момент считывается незаконченной командой, но подобное пере-
крытие допустимо, поэтому команда 2 может запускаться. Сходным образом ко-
манда 3 запускается во время цикла 2.
А теперь перейдем к команде 4, которая должна использовать регистр R4. К со-
жалению, из таблицы мы видим, что в регистр R4 в данный момент производится
запись (см. строку 3 в таблице). Здесь имеет место RAW-взаимозависимость, по-
этому блок декодирования простаивает до тех пор, пока регистр R4 не станет до-
ступен. Во время простаивания блок декодирования прекращает получать коман-
ды из блока выборки команд. Когда внутренние буферы блока выборки команд
заполнятся, он прекращает вызывать команды из памяти.
Следует упомянуть, что следующая команда, команда 5, не конфликтует ни с
одной из заверигенных команд. Ее можно было бы декодировать и выпустить, если
бы в нашей разработке не требовалось, чтобы команды выдавались по порядку.
Посмотрим, что происходит в цикле 3. Команда два, а это команда сложения
(два цикла), завершается в конце цикла 3. Но ее результат не может быть сохранен
в регистре R4 (который тогда освободится для команды 4). Почему? Потому что
данная разработка требует записи результатов в регистры в соответствии с поряд-
ком программы. Но зачем? Что плохого произойдет, если сохранить результат в
регистре R4 сейчас и сделать это значение доступным?
Ответ на этот вопрос очень важен. Предположим, что команды могут завер-
шаться в произвольном порядке. Тогда в случае прерывания будет очень сложно
сохранить состояние машины так, чтобы его можно было потом восстановить. В част-
ности, нельзя будет сказать, что все команды до какого-то адреса были выполне-
ны, а все команды после этого адреса не были выполнены. Это называется
точным
прерыванием
и является желательной характеристикой центрального процессора
[99]. Сохранение результатов в произвольном порядке делает прерывания неточ-
ными, и именно поэтому в некоторых машинах требуется соблюдение жесткого
порядка в завершении команд.
Вернемся к нашему примеру. В конце четвертого цикла результаты всех трех
команд могут быть сохранены, поэтому в цикле 5 может быть выпущена команда 4,
а также недавно декодированная команда 5. Всякий раз, когда завершается какая-
нибудь команда, блок декодирования должен проверять, нет ли простаивающей
команды, которую теперь уже можно выпустить.
В цикле б команда 6 простаивает, потому что ей нужно записать результат в ре-
гистр R1, а регистр R1 занят. Выполнение команды начинается только в цикле 9.
Чтобы завершить всю последовательность из 8 команд, требуется 15 циклов из-за
многочисленных ситуаций взаимозависимости, хотя аппаратное обеспечение
310 Глава 4. Микроархитектурный уровень
способно выдавать по две команды за цикл. В колонках «Выдача» и «Завершение»
табл. 4.12 видно, что все команды выдаются из блока декодирования по порядку и
завершаются эти команды тоже по порядку.
Рассмотрим альтернативный подход: исполнение с изменением последователь-
ности. В такой разработке выполнение команд может начинаться в произвольном
порядке и завершаться также в произвольном порядке. В табл. 4.13 показана та же
последовательность из восьми команд, только теперь разрешен другой порядок
выдачи команд и сохранения результатов в регистрах.
Первое различие встречается в цикле 3. Несмотря на то, что команда 4 проста-
ивает, мы можем декодировать и запустить команду 5, поскольку она не создает
конфликтной ситуации ни с одной из выполняющихся программ. Однако пропуск
команд порождает новую проблему. Предположим, что команда 5 использует опе-
ранд, который вычисляется пропущенной командой 4. При текущем состоянии
счетчика обращений мы этого не заметим. В результате нам придется расширить
счетчик обращений, чтобы следить за записями, которые совершают пропущен-
ные команды. Это можно сделать, добавив еще одно битовое отображение, по од-
ному биту на регистр, для контроля за записями, которые делают простаивающие
команды (эти счетчики в таблице не показаны). Правило для запуска команд следу-
ет расширить, с тем чтобы предотвратить запуск команды, операнд которой должен
быть записан той предшествующей командой, что шла до нее, но была пропущена.
Таблица 4.13. Работа суперскалярного процессора с изменением
последовательности запуска и завершения команд
Цикл
1
2
3
4
5
6
7
8
9
#
1
2
3
4
5
6
7
8
Команда
R3=R0*R1
R4=R0+R2
R5^R0+R1
R6=R1+R4
R7^R1*R2
S1=R0-R2
R3=R3*S1
S2=R4+R4
Выдача
1
2
3
-
5
6
4
-
8
7
Завер-
шение
2
1
3
6
4
5
8
7
Считываемые регистры Записываемые регистры
0
1
2
3
3
3
4
3
3
3
3
2
1
1
1
1
2
2
3
3
3
4
4
4
3
2
2
2
1
2
1
1
1
2
3
2
2
2
2
2
2
1
1
1
3
1
1
1
1
1
1
4 5 6 7
1
1
3
3
3
3
3
2
2
0 1
1
1
1
1
2 3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
7
1
1
1
1
1
1
1
1
1
1
1
Теперь посмотрим на команды 6, 7 и 8 в табл. 4.12. Здесь мы видим, что ко-
манда 6 помещает вычисленное значение в регистр R1, и это значение использует-
Увеличение производительности 3 1 1
ся командой 7. Мы также видим, что это значение больше не используется, потому
что команда 8 переписывает значение регистра R1. Нет никакой надобности исполь-
зовать регистр R1 для хранения результата команды 6. Еще хуже то, что далеко не
лучшим является выбор R1 в качестве промежуточного регистра, хотя с точки зре-
ния программиста, привыкшего к идее последовательного выполнения команд без
перекрытий, этот выбор является самым разумным.
В таблице 4.12 мы ввели новый метод для решения этой проблемы:
подмена
регистров.
Блок декодирования меняет регистр R1 в команде 6 (цикл 3) и в коман-
де 7 (цикл 4) на скрытый регистр S1, который невидим для программиста. Теперь
команда 6 может запускаться одновременно с командой 5. Современные процес-
соры содержат десятки скрытых регистров, которые используются для процедуры
подмены. Такая технология часто устраняет WAR- и WAW-взаимозависимости.
В команде 8 мы снова применяем подмену регистров. На этот раз регистр R1
переименовывается в S2, поэтому операция сложения может начаться до того, как
регистр R1 освободится, а освободится он только в конце цикла 6. Если окажется,
что результат в этот момент должен быть в регистре R1, содержимое регистра S2
всегда можно скопировать туда. Еще лучше то, что все будущие команды, которым
нужен этот результат, могут в качестве источника использовать регистры, пере-
именованные в тот регистр, где действительно хранится нужное значение. В лю-
бом случае выполнение команды 8 начнется раньше,
В настоящих (не гипотетических) компьютерах подмена регистров происхо-
дит с многократным вложением. Существует множество скрытых регистров и таб-
лица, в которой показывается соответствие видимых для программиста регистров
и скрытых регистров. Например, чтобы найти местоположение регистра R0, нуж-
но обратиться к элементу 0 этой таблицы. На самом деле реального регистра R0
нет, а есть только связь между именем R0 и одним из скрытых регистров. Эта связь
часто меняется во время выполнения программы, чтобы избежать взаимозависи-
мостей.
Обратите внимание на четвертый и пятый столбцы табл. 4.12. Вы видите, что
команды запускаются не по порядку и завершаются также не по порядку. Вывод
весьма прост: изменяя последовательность выполнения команд и подменяя регис-
тры, мы можем ускорить процесс вычисления почти в два раза.
Спекулятивное выполнение
В предыдущем разделе мы ввели понятие переупорядочения команд. Эта про-
цедура нужна для улучшения производительности. В действительности имелось
в виду переупорядочение команд в пределах одного базового элемента програм-
мы. Рассмотрим этот аспект подробнее.
Компьютерные программы можно разбить на
базовые элементы,
каждый из
которых представляет собой линейную последовательность команд с точкой входа
в начале и точкой выхода в конце. Базовый элемент не содержит никаких управля-
ющих структур (например, условных операторов i f или операторов цикла
whi
I e),
поэтому при трансляции на машинный язык нет никаких ветвлений. Базовые эле-
менты связываются операторами управления.
312
Глава 4. Микроархитектурный уровень
Программа в такой форме может быть представлена в виде ориентированного
графа, как показано на рис. 4.30. Здесь мы вычисляем сумму кубов четных и нечет-
ных целых чисел до какого-либо предела и помещаем результаты в
evensum
и
oddsum
соответственно (листинг 4.6). В пределах каждого базового элемента технологии,
упомянутые в предыдущем разделе, работают отлично.
Листинг 4.6.
Фрагмент программы
evesum=0,
oddsum-O;
i=0;
while (I<limit) {
k-i*i*i.
evens um=evensunH-k;
else
oddsum=oddsum+k;
i-i+l:
}
Проблема состоит в том, что большинство базовых элементов очень короткие
и в них недостаточно параллелизма. Следовательно, нужно сделать так, чтобы
переупорядочение последовательности команд можно было применять не только
в пределах конкретного базового элемента. Выгоднее всего будет передвинуть по-
тенциально медленную операцию в графе повыше, чтобы ее выполнение началось
раньше. Это может быть команда LOAD, операция с плавающей точкой или даже
начало длинной цепи зависимостей. Перемещение кода вверх по ребру графа на-
зывается подъемом.
evensum
=
0;
oddsum = 0;
= 0;
while (i < limit) {
k = i * i * i;
if ((1/2)* 2) ==0)
evensum = evensum + k;
else
oddsum
=
oddsum
+ k;
1 = 1 + 1;
evensum = 0;
oddsum = 0;
= 0;
\
while (i < limit)
t
k = i * i * i;
if((i/2)*2)= = 0)
evensum = evensum + k;
oddsum = oddsum
+ k;
. * i
+
1 ;
i
Рис. 4.30.
Граф базового элемента для фрагмента программы, приведенного в листинге 4.6
Посмотрите на рис. 4.30. Представим, что все переменные были помещены в ре-
гистры, кроме
evensum
и
oddsum
(из-за недостатка регистров). Тогда имело бы
смысл переместить команды LOAD в начало цикла до вычисления переменной к,