Танненбаум Е. Архітектура компютера [pdf]
.pdf
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 тоже изображен конечный автомат. На самом деле все наши микропрограммы можно считать конечными автоматами, поскольку каждая строка представляет особое состояние, в котором может находиться автомат, с четко определенными переходами к конечному набору других состояний. Конечные автоматы очень широко используются во всех аспектах разработки аппаратного обеспечения.
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. Суперскалярныйпроцессорспоследовательнойвыдачей и последовательным завершением команд
Цикл # |
Команда |
Выдача |
Завер- |
Считываемые регистры |
Записываемые регистры |
|||||||||||||||
|
|
|
|
шение |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
1 |
R3=R0*R1 |
1 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
2 |
R4=R0+R2 |
2 |
|
2 |
1 |
1 |
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
2 |
3 |
R5=R0+R1 |
3 |
|
3 |
2 |
1 |
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
4 |
R6=R1+R4 |
- |
|
3 |
2 |
1 |
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
3 |
|
|
|
|
3 |
2 |
1 |
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
4 |
|
|
|
1 |
2 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
2 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
4 |
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
5 |
R7=R1'R2 |
5 |
|
|
2 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
6 |
6 |
R1=R0-R2 |
- |
|
|
2 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
7 |
|
|
|
4 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
8 |
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
6 |
|
1 |
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
7 |
R3=R3*R1 |
- |
|
1 |
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
10 |
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
11 |
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
7 |
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
8 |
R1=R4+R4 |
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
13 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
14 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
15 |
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
8 |
|
|
|
|
|
2 |
|
|
|
|
1 |
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
1 |
|
|
|
|
|
|
18 |
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Увеличение производительности |
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 циклов из-за многочисленных ситуаций взаимозависимости, хотя аппаратное обеспечение
Увеличение производительности |
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), поэтому при трансляции на машинный язык нет никаких ветвлений. Базовые элементы связываются операторами управления.
