Реклама:

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

Единственная проблема состоит в том, что эта модель совершенно нереалистична. Программы вовсе не являются линейными кодами. В них полно команд переходов. Рассмотрим простые команды листинга 4.4. Переменная i сравнивается с 0 (вероятно, на практике это самое распространенное сравнение). В зависимости от результата другой переменной, к, присваивается одно из двух возможных значений.

Листинг 4.4. Фрагмент программы

if(i-O)

к=1;

el se к=2;

Возможный вариант трансляции на язык ассемблера показан в листинге 4.5. Язык ассемблера мы будем рассматривать позже в этой книге, а сейчас достаточно знать, что программа, более или менее похожая на программу из листинга 4.5, вполне возможна. Первая команда сравнивает переменную i с нулем. Вторая совершает переход к предложению El se, если i не равно 0. Третья команда присваивает значение 1 переменной к. Четвертая команда выполняет переход к следующему оператору программы. Компилятор поместил там метку Next. Пятая команда присваивает значение 2 переменной к.

Листинг 4.5. Программа из листинга 4.4 после трансляции на язык ассемблера

 

CMP

i. 0

; сравнение i с 0

 

BNE

Else

; переход к Else, если они не равны

Then:

MOV

k, 1

: присваивание значения 1 переменной к

 

BR Next

: безусловный переход к Next

Else:

MOV

k, 2

; присваивание значения 2 переменной к

Next:

     

Мы видим, что две из пяти команд являются командами перехода. Более того, одна из них, BNE, - это команда условного перехода (переход, который осуществляется тогда и только тогда, когда выполняется определенное условие, в данном случае - это равенство двух операндов предыдущей команды СМР). Самый длинный линейный код состоит здесь из двух команд, поэтому очень трудно организовать высокоскоростной конвейер.

На первый взгляд может показаться, что безусловные переходы, например, команда BR Next в листинге 4.5, не влекут за собой никаких проблем. Вообще говоря, в данном случае нет никакой двусмысленности в том, куда дальше идти. Почему же блок выборки команд не может просто продолжать считывать команды с целевого адреса (то есть с того места, куда осуществляется переход)?

Сложность объясняется самой природой конвейера. На рис. 4.24, например, мы видим, что декодирование происходит на второй ступени. Следовательно, блоку выборки команд приходится решать, откуда вызывать следующую команду еще до того, как он узнает, команду какого типа он только что вызвал. Только в очередном цикле он сможет выяснить, что получил команду безусловного перехода, хотя еще до этого он вызывает команду, следующую за командой безусловного перехода. То есть в значительной части конвейеризированных машин (например, UltraSPARC III) сначала выполняется команда, следующая после команды безусловного перехода, хотя по логике вещей так быть не должно. Позиция после перехода называется слотом отсрочки (delay slot). Pentium II (а также машина, используемая в листинге 4.5) не поддерживают слот отсрочки, а обойти эту проблему путем внутреннего усложнения часто сложно. Оптимизирующий компилятор постарается найти какую-нибудь полезную команду, чтобы поместить ее в слот отсрочки, но часто ничего подходящего нет, поэтому компилятор вынужден вставлять туда команду NOP. Хотя программа остается корректной, объем ее растет и работает она медленнее.

С условными переходами дело обстоит еще хуже. Во-первых, они тоже содержат слоты отсрочки, во-вторых, блок выборки команд узнает, откуда нужно считывать команду, гораздо позже. Первые конвейеризированные машины просто простаивали, пока выяснялось, нужно совершать переход или нет. Простой по три или четыре цикла при каждом условном переходе, особенно если 20 %

команд являются командами условного перехода, значительно снижает производительность.

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

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

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

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

Динамическое прогнозирование ветвлений

Ясно, что точные прогнозы очень ценны, поскольку позволяют процессору работать с полной скоростью. В настоящее время проводится множество исследований, целью которых является усовершенствование алгоритмов прогнозирования ветвлений [41, 64, 103, 160]. Один из подходов - хранить (в особом устройстве) специальную таблицу, в которую центральный процессор будет записывать условные переходы, когда они встретятся. Если условный переход встретится снова, его можно будет найти в этой таблице. Простейшая версия такой схемы показана на рис. 4.28, а. В данном случае таблица содержит по одной ячейке для каждой команды условного перехода. В ячейке находится адрес команды перехода, а также бит, который указывает, произошел ли переход, когда эта команда встретилась в последний раз. Прогноз заключается в выборе того же пути, по которому программа пошла в предыдущий раз при выполнении команды перехода. Если прогноз оказывается неправильным, бит в таблице меняется.

Прогнозирование ветвлений

Рис. 4.28. Таблица динамики ветвлений с одноразрядным указателем перехода (а); таблица динамики ветвлений с 2-разрядным указателем перехода (б); соответствие между адресом команды перехода и целевым адресом (в)

Существует несколько вариантов организации данной таблицы. Фактически они полностью аналогичны вариантам организации кэш-памяти. Рассмотрим машину с 32-разрядными командами, которые расположены таким образом, что два младших бита каждого адреса памяти равны 00. Таблица содержит 2я ячеек (строк). Из команды перехода можно извлечь п + 2 младших бита и осуществить сдвиг вправо на два бита. Это гг-разрядное число можно использовать в качестве индекса в таблице, проверяя, совпадает ли адрес, сохраненный там, с адресом перехода. Как и в случае с кэш-памятью, здесь нет необходимости сохранять п + 2 младших бита, поэтому их можно опустить (то есть сохраняются только старшие адресные биты - тег). Если адреса совпали, бит прогнозирования используется для прогнозирования перехода. Если тег неправильный или элемент недействителен, значит, имеет место промах. В этом случае можно применять правило перехода вперед/назад.

Если таблица динамики переходов содержит, скажем, 4096 элементов, то адреса 0, 16384, 32768 и т. д. будут конфликтовать; аналогичная проблема встречается и при работе с кэш-памятью. Здесь возможно такое же решение: 2-альтерна-тивный, 4-альтернативный или гг-альтернативный ассоциативный элемент. Как и в случае кэш-памяти, предельный случай - один //-альтернативный ассоциативный элемент.

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

Для решения проблемы можно немного изменить метод прогнозирования, чтобы прогноз менялся не после одного, а только после двух последовательных неправильных прогнозов. Такой подход требует наличия в таблице двух битов прогнозирования переходов (рис. 4.28, б): один должен указывать, предполагается совершать переход или нет, а второй - был сделан переход в прошлый раз или нет.

Этот алгоритм можно представить в виде конечного автомата с четырьмя состояниями (рис. 4.29). После ряда последовательных успешных прогнозов отсутствия перехода конечный автомат будет находиться в состоянии 00 и в следующий раз также покажет, что перехода нет.

Прогнозирование ветвлений

Рис. 4.29. 2-разрядный конечный автомат для прогнозирования переходов

Если этот прогноз окажется неправильным, автомат перейдет в состояние 01, но в следующий раз он все равно покажет отсутствие перехода. Только в том случае, если этот последний прогноз тоже окажется ошибочным, конечный автомат перейдет в состояние 11, прогнозируя наличие перехода. Фактически левый бит - это прогноз, а правый бит - то, что случилось в прошлый раз (то есть был ли переход). В данной разработке используются только 2 бита, но возможно применение и 4, и 8 бит.

Это не первый конечный автомат, который мы рассматриваем. На рис. 4.19 тоже изображен конечный автомат. На самом деле все наши микропрограммы можно считать конечными автоматами, поскольку каждая строка представляет особое состояние, в котором может находиться автомат, с четко определенными переходами к конечному набору других состояний. Конечные автоматы очень широко используются при разработке аппаратного обеспечения.

До сих пор мы предполагали, что цель каждого условного перехода известна. Обычно либо в явном виде давался адрес, к которому нужно перейти (он содержался непосредственно в команде), либо было известно смещение относительно текущей команды (то есть число со знаком, которое нужно было прибавить к счетчику команд). Часто это предположение имеет силу, но некоторые команды условного перехода вычисляют целевой адрес, предварительно выполняя определенные арифметические действия над значениями регистров. Даже если взять конечный автомат, изображенный на рис. 4.29, который точно прогнозирует переходы, прогноз окажется невостребованным, поскольку неизвестен целевой адрес. Один из возможных выходов из подобной ситуации - сохранить в таблице адрес, к которому был осуществлен переход в прошлый раз, как показано на рис. 4.28, е. Тогда, если в таблице указано, что в прошлый раз, когда встретилась команда перехода по адресу 516, переход был совершен к адресу 4000, целевым снова будет адрес 4000 (в случае, если предсказывается переход).

Еще один подход к прогнозированию перехода - следить, были ли совершены последние k условных переходов независимо от того, какие это были команды. Это ^-разрядное число, которое хранится в сдвиговом регистре динамики переходов, затем сравнивается параллельно со всеми элементами таблицы с ^-разрядным ключом, и в случае совпадения применяется тот прогноз, который найден в этом элементе. Удивительно, но эта технология работает достаточно хорошо.

Статическое прогнозирование ветвлений

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

Можно пойти другим путем, призвав на помощь компилятор. Обратите внимание на следующий оператор:

for (I = 0: i < 1000000; i++) { ... }

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

Хотя такой подход связан с изменением архитектуры (а не только реализации), в некоторых машинах, например, UltraSPARC III, помимо обычных команд условного перехода (которые нужны для обратной совместимости), имеется еще один набор команд. Новые команды содержат бит, по которому компилятор определяет, совершать переход или не совершать. Когда встречается такой бит, блок выборки команд просто делает то, что ему положено. Более того, нет необходимости тратить драгоценное пространство в таблице динамики переходов для этих команд, что сокращает количество конфликтных ситуаций.

Наконец, наша последняя технология прогнозирования ветвлений основана на профилировании [65]. Это тоже статическая технология, только в данном случае программа не заставляет компилятор вычислять, какие переходы нужно совершать, а какие нет. Программа реально выполняется, а ветвления фиксируются, эта информация поступает в компилятор, который затем использует специальные команды условного перехода для того, чтобы сообщить аппаратуре, что нужно делать.

Кэш-память4 || Оглавление || Исполнение с изменением последовательности и подмена регистров