Э. Таненбаум - Архитектура компьютера (1127755), страница 85
Текст из файла (страница 85)
После ряда последовательных успешных прогнозов отсутствия перехода конечный автомат будет находиться в состоянии 00 и в следующий раз также покажет, что перехода нет. Переход Нет перехода Рис. 4.29. 2-разрядный конечный автомат дпя прогнозирования переходов Если этот прогноз окажется неправильным, автомат перейдет в состояние 01, но в следующий раз он все равно покажет отсутствие перехода. Только в том Повышение производительности 341 случае, если этот последний прогноз тоже окажется ошибочным, конечный автомат перейдет в состояние 11, прогнозируя наличие перехода. Фактически левый бит — это прогноз, а правый бит — то, что случилось в прошлый раз (то есть был ли переход).
В данной разработке используются только 2 бита, но возможно применение и 4, и 8 бит. Это не первый конечный автомат, который мы рассматриваем. На рис. 4.19 тоже изображен конечный автомат. На самом деле все наши микропрограммы можно считать конечными автоматами, поскольку каждая строка представляет особое состояние, в котором может находиться автомат, с четко определенными переходами к конечному набору других состояний. Конечные автоматы очень широко используются при разработке аппаратного обеспечения. До сих пор мы предполагали, что цель каждого условного перехода известна.
Обычно либо в явном виде давался адрес, к которому нужно перейти (он содержался непосредственно в команде), либо было известно смещение относительно текущей команды (то есть число со знаком, которое нужно было прибавить к счетчику команд). Часто это предположение имеет силу, но некоторые команды условного перехода вычисляют целевой адрес, предварительно выполняя определенные арифметические действия над значениями регистров. Даже если взять конечный автомат, изображенный на рис.
4.29, который точно прогнозирует переходы, прогноз окажется невостребованным, поскольку неизвестен целевой адрес. Один из возможных выходов из подобной ситуации — сохранить в таблице адрес, к которому был осуществлен переход в прошлый раз, как показано на рис. 4.28, в. Тогда, если в таблице указано, что в прошлый раз, когда встретилась команда перехода по адресу 516, переход был совершен к адресу 4000, целевым снова будет адрес 4000 (в случае, если предсказывается переход). Еще один подход к прогнозированию перехода — следить, были ли совершены последние /г условных переходов независимо от того, какие это были команды. Это Й-разрядное число, которое хранится в сдвиговом регистре динамики переходов, затем сравнивается параллельно со всеми элементами таблицы с /г-разрядным ключом, и в случае совпадения применяется тот прогноз, который найден в этом элементе.
Удивительно, но эта технология работает достаточно хорошо. Статическое прогнозирование ветвлений Все технологии прогнозирования ветвлений, которые обсуждались до сих пор, являются динамическими, то есть выполняются во время работы программы. Они приспосабливаются к текущему режиму работы программы, и это их положительное качество. Отрицательной стороной этих технологий является то, что они требуют специализированной и дорогостоящей аппаратуры, и микросхемы для реализации этих технологий получаются очень сложными.
Можно пойти другим путем, призвав на помощь компилятор. Обратите внимание на следующий оператор: 1ог 11 - 0; 1 < 1000000, ы+) 1 ... ) Когда компилятор встречает такой оператор, он знает, что переход в конце цикла будет происходить практически всегда. Если бы был способ сообщить это аппаратуре, можно было бы избавиться от огромного обьема работы. 342 Глава 4.
Уровень микроархитектуры Хотя такой подход связан с изменением архитектуры (а не только реализации), в некоторых машинах, например, П!сгаБРАКС Ш, помимо обычных команд условного перехода (которые нужны для обратной совместимости), имеется еще один набор команд. Новые команды содержат бит, по которому компилятор определяет, совершать переход или не совершать. Когда встречается такой бит, блок выборки команд просто делает то, что ему положено.
Более того, нет необходимости тратить драгоценное пространство в таблице динамики переходов для этих команд, что сокращает количество конфликтных ситуаций. Наконец, наша последняя технология прогнозирования ветвлений основана на профилировании 1651. Это тоже статическая технология, только в данном случае программа не заставляет компилятор вычислять, какие переходы нужно совершать, а какие нет.
Программа реально выполняется, а ветвления фиксируются, эта информация поступает в компилятор, который затем использует специальные команды условного перехода для того, чтобы сообщить аппаратуре, что нужно делать. Исполнение с изменением последовательности и подмена регистров Большинство современных процессоров являются и конвейеризированными и суперскалярными, как показано на рис. 2.5. Это означает, что имеется блок выборки команд (1Р13), который заранее вызывает команды из памяти и передает их в блок декодирования. Блок декодирования, в свою очередь, передает декодированные команды соответствующим функциональным блокам для выполнения. В некоторых случаях блок декодирования может разбивать отдельные команды на микрооперации перед тем, как отправить их функциональным блокам. Ясно, что проще всего выполнять все команды в том порядке, в котором они вызываются из памяти (предполагается, что прогнозирование ветвлений всегда оказывается верным).
Однако нз-за взаимозависимости команд такое последовательное выполнение не всегда дает оптимальную производительность. Если команде требуется значение, которое вычисляется предыдущей командой, вторая команда не сможет выполняться, пока первая не выдаст нужную величину. Таким образом, в ситуации реальной взаимозависимости второй команде приходится ждать.
Существуют и другие виды взаимозависимостей, но о них мы поговорим позже. Чтобы обойти эти проблемы и достичь оптимальной производительности, некоторые процессоры пропускают взаимозависимые команды и переходят к следующим (независимым) командам. Естественно, что при этом алгоритм распределения команд должен давать такой же результат, как если бы все команды выполнялись в том порядке, в котором они написаны. А теперь продемонстрируем на конкретном примере, как происходит переупорядоченне команд.
Чтобы изложить суть проблемы, начнем с машины, которая запускает команды в том порядке, в котором они расположены в программе, и требует, чтобы выполнение команд также завершалось в порядке, соответствующем программному. Важность второго требования прояснится позднее. Повышение производительности 343 Наша машина содержит 8 доступных программисту регистров, от ВО до й7. Все арифметические команды используют три регистра: два для операндов и один для результата, как и в микроархитектуре М1с-4. Мы предполагаем, что, если команда декодируется в цикле п, выполнение начинается в цикле п + 1.
В случае простой команды, например команды сложения или вычитания, запись обратно в выходной регистр происходит в конце цикла п + 2. В случае с более сложной командой, например командой умножения, запись в регистр происходит в конце цикла и + 3. Чтобы сделать наш пример реалистичным, мы позволим блоку декодирования выдавать до двух команд за цикл. Некоторые суперскалярные процессоры могут генерировать 4 или даже 6 команд за цикл. Последовательность выполнения команд иллюстрирует табл. 4.11. В первом столбце приводится номер цикла, во втором — номер команды, в третьем — сама команда. В четвертом столбце показаны выданные команды (максимум две команды за цикл). Цифры в пятом столбце сообщают, какие команды завершены.
Помните, что в нашем примере мы требуем, чтобы команды и запускались, и завершались в строго опрсделенном порядке, поэтому выдача команды я + 1 может произойти только после выдачи команды я, а результат команды я + 1 не может быть записан в выходной регистр до того, как заверпштся команда я. Оставшиеся 16 столбцов мы обсудим позже. После декодирования команды блок декодирования должен определить, запускать команду сразу или нет. Для этого блок декодирования должен знать состояние всех регистров. Если, например, текущей команде требуется регистр, значение которого еще не подсчитано, текущая команда не выдается, и центральный процессор вынужден простаивать.
Следить за состоянием регистров призвано специальное устройство — счетчик обращений (зсогеЬоагс)), впервые появившийся в системе СРС 6600. Для каждого регистра счетчик обращений содержит небольшую схему, которая подсчитывает, сколько раз этот регистр используется выполняющимися командами в качестве источника. Если одновременно может выполняться максимум 15 команд, будет достаточно 4-разрядного счетчика. Когда запускается команда, элементы счетчика обращений, соответствуюгцие регистрам операндов, увеличиваются на 1.
Когда выполнение команды завершено, соответствующие элементы счетчика уменьшаются на 1. Счетчик обращений содержит аналогичные схемы подсчета для целевых регистров. Поскольку допускается только одна запись за раз, эти схемы могут быть размером в один бит, Правые 16 столбцов в табл. 4.11 демонстриру|от показания счетчика обращений. В реальных машинах счетчик обращений также следит за использованием функционального блока, чтобы избежать выдачи команды, для которой нет доступного функционального блока.
Для простоты мы предполагаем, что подходящий функциональный блок всегда есть в наличии, поэтому функциональные блоки в таблице не показаны. В первой строке табл. 4.11 представлена команда 1, которая перемножает значения регистров йО и К1 и помещает результат в регистр КЗ. Поскольку ни один из этих регистров еще не используется, команда запускается, а счетчик обращений показывает, что регистры КО и К1 считываются, а регистр йЗ записывается.
3 з й 3 ЗИ Ф) Я И Ф 3 3 3 з Р а р в й Л3 л Ю ФЧ ~Е 1Е х 3й ~с о о а СЧ (й х К л ~Е 'Ф <С Ф Ы П <С СЧ (С 1 С> К И 1Е ~С х \'Ъ Ы И РЭ ~С .\. о К 1Е П Н О Ю ~й ~С с~ Ф Б о М й Ф Б Ф з С1 О й (О Б л с Ф о Ф с~ о с о Б Ф Г~ л )Б о х л с Ф Ю о Ф с~ о с о с о О. о о о Ф о «1 >Е л х О. з (Э С1 Ф % о СЧ Я СЧ о ~ и З с 10 Ю 1 в ~ и о я С'Ъ ~ й е л в Повышение производительности 345 Ни одна из последующих команд не может записывать результат в эти регистры и не может считывать регистр ЙЗ до тех пор, пока не завершится выполнение команды 1.
Поскольку это команда умножения, она закончится в конце цикла 4. Значения счетчика обращений, приведенные в каждой строке, отражают состояние регистров после запуска команды, записанной в этой же строке. Пустые клетки соответствуют значению О. Поскольку в качестве примера рассматривается суперскалярная машина, которая может запускать две команды за цикл, вторая команда выдается также во время цикла 1. Она складывает значения регистров КО и В2, а результат сохраняет в регистре К4.
Чтобы определить, можно ли запускать эту команду, применяются следующие правила: 1. Если какой-нибудь операнд записывается, запускать команду нельзя (ВА%'- взаимозависимость). 2. Если считывается регистр результатов, запускать команду нельзя (7КАК- взаимозависимость). 3. Если записывается регистр результатов, запускать команду нельзя (тт"АЪУ- взаимозависимость). Мы уже рассматривали реальные взаимозависимости (КАЖ-взаимозависимости), имеющие место, когда команде в качестве источника нужно использовать результат предыдущей команды, которая еще не завершилась. Два других типа взаимозависимостей менее серьезные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
