Реклама:

Большинство современных процессоров являются и конвейеризированными и суперскалярными, как показано на рис. 2.5. Это означает, что имеется блок выборки команд (IFU), который заранее вызывает команды из памяти и передает их в блок декодирования. Блок декодирования, в свою очередь, передает декодированные команды соответствующим функциональным блокам для выполнения. В некоторых случаях блок декодирования может разбивать отдельные команды на микрооперации перед тем, как отправить их функциональным блокам.

Ясно, что проще всего выполнять все команды в том порядке, в котором они вызываются из памяти (предполагается, что прогнозирование ветвлений всегда оказывается верным). Однако из-за взаимозависимости команд такое последовательное выполнение не всегда дает оптимальную производительность. Если команде требуется значение, которое вычисляется предыдущей командой, вторая команда не сможет выполняться, пока первая не выдаст нужную величину. Таким образом, в ситуации реальной взаимозависимости второй команде приходится ждать. Существуют и другие виды взаимозависимостей, но о них мы поговорим позже.

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

Чтобы изложить суть проблемы, начнем с машины, которая запускает команды в том порядке, в котором они расположены в программе, и требует, чтобы выполнение команд также завершалось в порядке, соответствующем программному. Важность второго требования прояснится позднее.

Наша машина содержит 8 доступных программисту регистров, от R0 до R7. Все арифметические команды используют три регистра: два для операндов и один для результата, как и в микроархитектуре Mic-4. Мы предполагаем, что, если команда декодируется в цикле п, выполнение начинается в цикле п + 1. В случае простой команды, например команды сложения или вычитания, запись обратно в выходной регистр происходит в конце цикла п + 2. В случае с более сложной командой, например командой умножения, запись в регистр происходит в конце цикла /2 + 3. Чтобы сделать наш пример реалистичным, мы позволим блоку декодирования выдавать до двух команд за цикл. Некоторые суперскалярные процессоры могут генерировать 4 или даже 6 команд за цикл.

Последовательность выполнения команд иллюстрирует табл. 4.11. В первом столбце приводится номер цикла, во втором - номер команды, в третьем - сама команда. В четвертом столбце показаны выданные команды (максимум две команды за цикл). Цифры в пятом столбце сообщают, какие команды завершены. Помните, что в нашем примере мы требуем, чтобы команды и запускались, и завершались в строго определенном порядке, поэтому выдача команды k + 1 может произойти только после выдачи команды а результат команды k + 1 не может быть записан в выходной регистр до того, как завершится команда k. Оставшиеся 16 столбцов мы обсудим позже.

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

Следить за состоянием регистров призвано специальное устройство - счетчик обращений (scoreboard), впервые появившийся в системе CDC 6600. Для каждого регистра счетчик обращений содержит небольшую схему, которая подсчитывает, сколько раз этот регистр используется выполняющимися командами в качестве источника. Если одновременно может выполняться максимум 15 команд, будет достаточно 4-разрядного счетчика. Когда запускается команда, элементы счетчика обращений, соответствующие регистрам операндов, увеличиваются на 1. Когда выполнение команды завершено, соответствующие элементы счетчика уменьшаются на 1.

Счетчик обращений содержит аналогичные схемы подсчета для целевых регистров. Поскольку допускается только одна запись за раз, эти схемы могут быть размером в один бит. Правые 16 столбцов в табл. 4.11 демонстрируют показания счетчика обращений.

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

В первой строке табл. 4.11 представлена команда 1, которая перемножает значения регистров R0 и R1 и помещает результат в регистр R3. Поскольку ни один из этих регистров еще не используется, команда запускается, а счетчик обращений показывает, что регистры R0 и R1 считываются, а регистр R3 записывается.

Таблица 4,11, Суперскалярный процессор с последовательной выдачей и последовательным завершением команд

Исполнение с изменением последовательности и подмена регистров

Ни одна из последующих команд не может записывать результат в эти регистры и не может считывать регистр R3 до тех пор, пока не завершится выполнение команды 1. Поскольку это команда умножения, она закончится в конце цикла 4. Значения счетчика обращений, приведенные в каждой строке, отражают состояние регистров после запуска команды, записанной в этой же строке. Пустые клетки соответствуют значению 0.

Поскольку в качестве примера рассматривается суперскалярная машина, которая может запускать две команды за цикл, вторая команда выдается также во время цикла 1. Она складывает значения регистров R0 и R2, а результат сохраняет в регистре R4. Чтобы определить, можно ли запускать эту команду, применяются следующие правила:

1. Если какой-нибудь операнд записывается, запускать команду нельзя (RAW-взаимозависимость).

2. Если считывается регистр результатов, запускать команду нельзя (WAR-взаимозависимость).

3. Если записывается регистр результатов, запускать команду нельзя (WAW-взаимозависимость).

Мы уже рассматривали реальные взаимозависимости (RAW-взаимозависи-мости), имеющие место, когда команде в качестве источника нужно использовать результат предыдущей команды, которая еще не завершилась. Два других типа взаимозависимостей менее серьезные. По существу, они связаны с конфликтами ресурсов. При WAR-взаимозависимости (Write After Read - запись после чтения) одна команда пытается перезаписать регистр, который предыдущая команда еще не закончила считывать. WAW-взаимозависимость (Write After Write - запись после записи) похожа на WAR-взаимозависимость. Подобной взаимозависимости можно избежать, если вторая команда будет помещать результат где-либо в другом месте еще (возможно, временно). Если ни одна из трех упомянутых ситуаций не возникает и нужный функциональный блок доступен, команду можно выдать. В этом случае команда 2 использует регистр R0, который в данный момент считывается незаконченной командой, но подобное перекрытие допустимо, поэтому команда 2 может запускаться. Сходным образом команда 3 запускается во время цикла 2.

А теперь перейдем к команде 4, которая должна использовать регистр R4. К сожалению, из таблицы мы видим, что в регистр R4 в данный момент производится запись (см. строку 3 в таблице). Здесь имеет место RAW-взаимозависи-мость, поэтому блок декодирования простаивает до тех пор, пока регистр R4 не станет доступным. Во время простоя блок декодирования прекращает получать команды из блока выборки команд. Когда внутренние буферы блока выборки команд заполнятся, он прекращает вызывать команды из памяти.

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

Посмотрим, что происходит в цикле 3. Команда 2, а это команда сложения (два цикла), завершается в конце цикла 3. Но ее результат не может быть сохранен в регистре КА (который тогда освободится для команды 4). Почему? Из-за необходимости записи результатов в регистры в соответствии с порядком выполнения программы. Но зачем? Что плохого произойдет, если сохранить результат в регистре КА сейчас и сделать это значение доступным?

Ответ на этот вопрос очень важен. Предположим, что команды могут завершаться в произвольном порядке. Тогда в случае прерывания будет очень сложно сохранить состояние машины так, чтобы его можно было потом восстановить. В частности, нельзя будет сказать, что все команды до какого-то адреса были выполнены, а все команды после этого адреса выполнены не были, как было бы при так называемом точном прерывании, которое является желательной характеристикой центрального процессора [147]. Сохранение результатов в произвольном порядке делает прерывания неточными, и именно поэтому в некоторых машинах требуется соблюдение жесткого порядка завершения команд.

Вернемся к нашему примеру. В конце цикла 4 результаты всех трех команд могут быть сохранены, поэтому в цикле 5 может быть выдана команда 4, а также недавно декодированная команда 5. Всякий раз, когда завершается какая-нибудь команда, блок декодирования должен проверять, нет ли простаивающей команды, которую уже можно выдать.

В цикле 6 команда 6 простаивает, потому что ей нужно записать результат в регистр Ш, а регистр Ш занят. Выполнение команды начинается только в цикле 9. Чтобы завершить всю последовательность из 8 команд, требуется 15 циклов из-за многочисленных ситуаций взаимозависимости, хотя аппаратура способна выдавать по две команды за цикл. По колонкам "Выдача" и "Завершение" табл. 4.11 видно, что все команды выдаются из блока декодирования по порядку и завершаются эти команды тоже по порядку.

Рассмотрим альтернативный подход: выполнение с изменением последовательности. В такой системе выполнение команд может начинаться в произвольном порядке и завершаться также в произвольном порядке. В табл. 4.12 показана та же последовательность из восьми команд, только теперь разрешен произвольный порядок выдачи команд и сохранения результатов в регистрах.

Первое различие встречается в цикле 3. Несмотря на то, что команда 4 -простаивает, мы можем декодировать и запустить команду 5, поскольку она не создает конфликтной ситуации ни с одной из выполняющихся команд. Однако пропуск команд порождает новую проблему. Предположим, что команда 5 использует операнд, который вычисляется пропущенной командой 4. При текущем состоянии счетчика обращений мы этого не заметим. В результате нам придется расширить счетчик обращений, чтобы следить за записями, которые совершают пропущенные команды. Это можно сделать, добавив еще одно битовое отображение, по одному биту на регистр, для контроля за записями, которые делают простаивающие команды (эти счетчики в таблице не показаны). Правило запуска команд следует расширить, с тем чтобы предотвратить запуск команды, операнд которой должен был быть записан предшествующей, но пропущенной командой.

Теперь посмотрим на команды 6, 7 и 8 в табл. 4.11. Здесь мы видим, что команда 6 помещает вычисленное значение в регистр Ш и это значение используется командой 7.

Таблица 4,12, Работа суперскалярного процессора с изменением очередности запуска и завершения команд

Исполнение с изменением последовательности и подмена регистров

Мы также видим, что это значение больше не требуется, потому что команда 8 переписывает значение регистра R1. Нет никакой надобности использовать регистр R1 для хранения результата команды 6. Еще хуже то, что далеко не лучшим является выбор регистра R1 в качестве промежуточного, хотя, с точки зрения программиста, привыкшего к идее последовательного выполнения команд без перекрытий, этот выбор является самым разумным.

В табл. 4.12 мы ввели новый метод для решения этой проблемы - подмену регистров (register renaming). Блок декодирования заменяет регистр R1 в командах 6 (цикл 3) и 7 (цикл 4) скрытым для программиста регистром S1. После этого команда 6 может запускаться одновременно с командой 5. Современные процессоры содержат десятки скрытых регистров, которые используются для подмены. Такая технология часто позволяет устранить WAR- и WAW-взаимоза-висимости.

В команде 8 мы снова применяем подмену регистров. На этот раз регистр R1 заменяется регистром S2, поэтому операция сложения может начаться до того, как освободится регистр R1, а освободится он только в конце цикла 6. Если окажется, что результат в этот момент должен быть в регистре R1, содержимое регистра S2 всегда можно скопировать туда. Еще лучше то, что все будущие команды, использующие этот результат, смогут в качестве источника задействовать регистр подмены, в котором действительно хранится нужное значение. В любом случае выполнение команды 8 начнется раньше.

В настоящих (не гипотетических) компьютерах подмена регистров происходит с многократным вложением. Существует множество скрытых регистров и таблица, в которой показывается соответствие доступных программисту и скрытых регистров. Например, чтобы найти местоположение регистра R0, нужно обратиться к элементу 0 этой таблицы. На самом деле реального регистра R0 нет, а есть только связь между именем R0 и одним из скрытых регистров. Эта связь часто меняется во время выполнения программы, чтобы избежать взаимозависимостей.

Обратите внимание на четвертый и пятый столбец табл. 4.12. Вы видите, что команды запускаются не по порядку и завершаются также не по порядку. Вывод весьма прост: изменив последовательность выполнения команд и подменив регистры, мы можем ускорить процесс вычислений почти в два раза.

Прогнозирование ветвлений || Оглавление || Спекулятивное исполнение