Файл: 401-455.pdf

Конвейеризация вычислений  4 2 1

Первый фактор характерен для любой команды перехода и связан с выборкой

команды из точки перехода (по адресу, указанному в команде перехода). То, что
текущая команда относится к командам перехода, становится ясным только после

декодирования (после прохождения ступени декодирования), то есть спустя два

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

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

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

новке конвейера как минимум на два такта.

Вторая причина нарушения ритмичности работы конвейера имеет отношение

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

 9.5).

Рис. 9.5. Влияние условного перехода на работу конвейера команд

Пусть команда 3 — это условный переход к команде 15. До завершения коман-

ды 3 невозможно определить, какая из команд (4-я или 15-я) должна выполняться

следующей, поэтому конвейер просто загружает следующую команду в последо-
вательности (команду 4) и продолжает свою работу. В варианте, показанном на
рис. 9.3, переход не произошел и получена максимально возможная производи-
тельность. На рис. 9.5 переход имеет место, о чем неизвестно до 7-го шага. В этой

точке конвейер должен быть очищен от ненужных команд, выполнявшихся до дан-

ного момента. Лишь на шаге 8 на конвейер поступает нужная команда 15, из-за
чего в течение тактов от 9 до 12 не будет завершена ни одна другая команда. Это
и есть издержки из-за невозможности предвидения исхода команды условного

4 2 2 Глава 9. Основные направления в архитектуре процессоров

перехода. Как видно, они либо существенно больше, чем для прочих команд
перехода (если переход происходит), либо отсутствуют вовсе (если переход
не происходит).

Для сокращений задержек, обусловленных выборкой команды из точки пере-

хода, применяются несколько подходов:
» вычисление исполнительного адреса перехода на ступени декодирования ко-

манды;

-

 использование буфера адресов перехода;

-

 использование кэш-памяти для хранения команд, расположенных в точке пе-

рехода;

-

 использование буфера цикла.

В результате декодирования команды выясняется не только ее принадлежность

к командам перехода, но также способ адресации и адресный код точки перехода.

Это позволяет сразу же приступить к вычислению исполнительного адреса пере-

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

Буфер адресов перехода (ВТВ, Branch Target Buffer) представляет собой кэш-

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

манды ее адрес (содержимое счетчика команд) сравнивается с адресами команд,

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

Команда, ссылка на которую в ВТВ отсутствует, обрабатывается стандартным

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

шилась переходом. При замещении информации в ВТВ обычно применяется ал-

горитм LRU.

Применение ВТВ дает наибольший эффект, когда отдельные команды перехо-

да в программе выполняются многократно, что типично для циклов. Обычно ВТВ

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

Кэш-память команд, расположенных в точке перехода (BTIC, Branch Target

Instruction Cache), — это усовершенствованный вариант ВТВ, где в кэш-память

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

Конвейеризация вычислений  4 2 3

Буфер цикла

 представляет собой маленькую быстродействующую память, вхо-

дящую в состав первой ступени конвейера, где производится выборка команд.

В буфере сохраняются коды « последних команд в той последовательности, в ко-

торой они выбирались. Когда имеет место переход, аппаратура сначала проверяет,

нет ли нужной команды в буфере, и если это так, то команда извлекается из буфера.
Стратегия наиболее эффективна при реализации циклов и итераций, чем и объяс-

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

По принципу использования буфер цикла похож на BTIC, с той разницей, что

в нем сохраняется последовательность выполнения команд, а сам буфер меньше
по емкости и дешевле.

Среди ВМ, где реализован буфер цикла, можно упомянуть некоторые вычис-

лительные машины фирмы CDC (Star 100,6600,7600) и суперЭВМ CRAY-1. Спе-
циализированная версия буфера цикла имеется и в микропроцессоре Motoro-
la 68010, где он используется для особых циклов, включающих в себя команду
«Уменьшение и переход по условию».

Методы решения проблемы условного перехода

Несмотря на важность аспекта вычисления исполнительного адреса точки пере-

хода, основные усилия проектировщиков ВМ направлены на решение проблемы
условных переходов, поскольку именно последние приводят к наибольшим издерж-

кам в работе конвейера. Для устранения или частичного сокращения этих издер-

жек были предложены различные способы, которые условно можно разделить на
четыре группы:

- буферы предвыборки;
- множественные потоки;
- задержанный переход;
- предсказание перехода.

Равномерность поступления команд на вход конвейера часто нарушается, на-

пример из-за занятости памяти или при выборке команд, состоящих из несколь-
ких слов. Чтобы добиться ритмичности подачи команд на вход конвейера, между

ступенью выборки команды и остальной частью конвейера часто размещают бу-
ферную память, организованную по принципу очереди (FIFO) и называемую

 бу-

фером предвыборки.

 Буфер предвыборки можно рассматривать как несколько до-

полнительных ступеней конвейера. Подобное удлинение конвейера не сказывается
на его производительности (при заданной тактовой частоте); оно лишь приводит
к увеличению времени прохождения команды через конвейер. Типичные буферы
предвыборки в известных процессорах рассчитаны на 2-8 команд.

Чтобы одновременно с обеспечением ритмичной работы конвейера решить

и проблему условных переходов, в конвейер включают два таких буфера (рис. 9.6).

Каждая извлеченная из памяти и помещенная в основной буфер команда ана-

лизируется блоком перехода. При обнаружении команды условного перехода (УП)

4 2 4 Глава 9. Основные направления в архитектуре процессоров

Рис. 9.6. Конвейер с буферами предвыборки команд

блок перехода вычисляет исполнительный адрес точки перехода и параллельно
с продолжением последовательной выборки в основной буфер организует выбор-
ку в дополнительный буфер команд, начиная с точки УП. Далее блок перехода
определяет исход команды УП, в зависимости от которого подключает к остатку
конвейера нужный буфер, при этом содержимое другого буфера сбрасывается. Уп-
рощенный вариант подобного подхода применен в IBM 360/91, где дополнитель-
ный буфер рассчитан на одну команду, то есть выигрыш достигается за счет ис-
ключения времени на выборку команды из точки перехода.

Помимо необходимости дублирования части оборудования, у метода имеется

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

Другим решением проблемы переходов служит дублирование начальных

ступеней конвейера и создание тем самым двух параллельных потоков команд
(рис. 9.7).

Рис. 9.7. Конвейер с множественными потоками

В одной из ветвей такого «раздвоенного» конвейера последовательность вы-

борки и выполнения команд соответствует случаю, когда условие перехода не вы-

полнилось, во второй ветви — случаю выполнения этого условия. Для ранее рас-

смотренного примера (см. рис. 9,5) в одном из потоков может обрабатываться

последовательность команд 4-6, а в другом— 15-17. Оба потока сходятся в точке,

Конвейеризация вычислений  4 2 5

где итог проверки условия перехода становится очевидным. Дальнейшее продви-

жение по конвейеру продолжает только «правильный» поток. Основной недоста-

ток метода состоит в том, что на конвейер или в поток может поступить новая ко-
манда У П до того, как будет принято окончательное решение по текущей команде
перехода. Каждая такая команда требует дополнительного потока. Несмотря
на это, стратегия позволяет улучшить производительность конвейера. При-

мерами ВМ, где используются два или более конвейерных потоков, служат

IBM 370/168 и IBM 3033.

Стратегия

 задержанного перехода

 предполагает продолжение выполнения ко-

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

»

, то

есть такими, которые все равно должны быть когда-то выполнены, независимо от

того, происходит переход или нет, и если команда перехода никак не влияет на

результат их выполнения.

Для реализации этой идеи на этапе компиляции программы после каждой ко-

манды перехода вставляется команда «Нет операции». Затем на стадии оптимиза-
ции программы производятся попытки «перемешать» команды таким образом,
чтобы по возможности большее количество команд «Нет операции

»

- заменить «по-

лезными» командами программы. Разумеется, замещать команду «Нет операции»

можно лишь на такую, которая не влияет на условие выполняемого перехода, ина-
че полученная последовательность команд не будет функционально эквивалент-
ной исходной. В оптимизированной программе удается заменить более 20% ко-
манд «Нет операции» [120].

Предсказание переходов

Предсказание переходов

 на сегодняшний день рассматривается как один из наибо-

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

щие команды подаются на конвейер в соответствии с предсказанием. Для иллюст-

рации вернемся к примеру (см. рис. 9.5), где команда 3 является командой УП.

Пусть для команды 3 предсказано, что переход не произойдет. Тогда вслед за ко-

мандой 3 на конвейер будут поданы команды 4-6 и т. д. Если предсказан переход,
то после команды 3 на конвейер подаются команды 15-17,... При ошибочном пред-
сказании конвейер необходимо вернуть к состоянию, с которого началась выборка

«ненужных» команд (очистить начальные ступени конвейера), и приступить к заг-

рузке, начиная с «правильной» точки, что по эффекту эквивалентно приостановке

конвейера. Цена ошибки может оказаться достаточно высокой, но при правиль-

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

 «точность предсказаниям »

в дальнейшем будем трактовать как про-

центное отношение числа правильных предсказаний к их общему количеству.
В работе [70] дается следующая оценка: чтобы снижение производительности кон-

вейера из-за его остановок по причине конфликтов по управлению не превысило

10%, точность предсказания переходов должна быть выше 97,7%.