Файл: 401-455.pdf

4 3 6

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

Точность предсказания

Рис. 9.22.

 Зависимость точности предсказания от соотношения разрядов в шаблоне

при конкатенации [197]

Вариант со сложением по модулю 2 предполагает побитовое применение опе-

рации «Исключающее ИЛИ» к обоим источникам (рис. 9,23). В качестве шаблона

используются

 k

 младших разрядов результата. Сформированный шаблон содер-

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

по отдельности.

Рис. 9.23.

 Формирование шаблона для доступа к РНТ путем сложения по модулю 2

Для сравнительной оценки рассмотренных вариантов доступа к РНТ обратим-

ся к результатам экспериментов, приведенным в [64]. Исследовались четыре тес-
товых программы:

- compress— сжатиефайлов(10млнУП);
- eqntott — преобразование логических функций, заданных таблицей истиннос-

ти(178млнУП);

- espresso — минимизация логических функций (73 млн УП);

- xlisp — интерпретатор LISP (772 млн УП).

Результаты, усредненные по всем четырем программам для различных по объему

таблиц РНТ, показаны на рис. 9.24.

Первый вывод, вытекающий из представленных данных, очевиден — с увели-

чением размера РНТ точность предсказания возрастает. Среди четырех рассмот-
ренных схем наилучшую точность обеспечивает схема со сложением по модулю
два. Схема со счетчиком команд относится к наименее эффективным. Объясняет-
ся это тем, что каждый отдельный счетчик РНТ в схеме со счетчикок команд за-

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

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

  4 3 7

Рис. 9.24.

 Зависимость точности предсказания от способа доступа к РНТ и размера таблицы

ния. Результаты для схемы с конкатенацией получены для случая, когда в шабло-
не используется одинаковое число разрядов из СК и GHR. При малых объемах
РНТ вариант с конкатенацией дает наихудшие результаты, но при больших РНТ

эта схема превосходит модель со счетчиком команд.

В реальных схемах предсказания переходов размер таблицы РНТ ограничен.

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

 k

 определяется размером

массива. Для упомянутых выше размеров РНТ значение

 k

 лежит в диапазоне от 8

до 12. Если обращение к РНТ определяется счетчиком команд, разрядность кото-

рого обычно больше, чем

 k,

 в качестве шаблона выступают

 k

 младших битов СК.

Как следствие, две команды условного перехода, адреса которых в младших

 k

 раз-

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

 эффект наложения

 (aliasing). Та же проблема существует и при доступе к РНТ на

основании содержимого регистра глобальной истории или регистра локальной исто-

рии. В зависимости от типа программы и других факторов наложение может при-

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

ваться на точности предсказания. Соответственно, эффекты наложения класси-
фицируют как

 конструктивный, деструктивный

 и

 нейтральный.

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

счетчиков РНТ, при обращении к которым имел место эффект наложения

(рис. 9.25) [64].

Рис.

 9.25. Интенсивность наложения при различных способах доступа к РНТ

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

В больших РНТ частота перекрытия снижается по причине большего числа

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

и обычно отрицательно влияет на точность предсказания переходов.

При классификации динамических стратегий обычно выделяют следующие их

виды:
- одноуровневые или бимодальные;
- двухуровневые или коррелированные;
- гибридные;

- асимметричные.

Одноуровневые схемы предсказания переходов. В

 многочисленных исследо-

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

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

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

 бимодальные схемы

 [165],

сводится к отделению команд, имеющих склонность завершаться переходом, от

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

лишь одну таблицу, каждый элемент которой отображает историю исходов одной

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

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

но небольшая таблица, куда заносятся адреса

 п

 последних команд У П, при выпол-

нении которых переход не случился. В сущности, это ранее упоминавшийся

 буфер

адресов перехода

 (ВТВ), но с противоположным правилом занесения информа-

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

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

ном случае предсказывается переход. С этих позиций для каждой новой команды

УП по умолчанию принимается, что переход произойдет. После того как факти-

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

Если же перехода не было, то адрес команды заносится в таблицу при условии, что

до этого он там отсутствовал. При заполнении таблицы опираются на алгоритмы

LRU или FIFO. По точности предсказания стратегия превосходит большинство
стратегий статического предсказания.

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

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

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

Состояние разряда отражает исход предыдущего выполнения команды (1 — пере-

ход был, 0 — перехода не было). Новое предсказание совпадает с результатом пред-
шествующего выполнения данной команды. При занесении такой команды
в кэш-память рассматриваемый разряд устанавливается в единицу. Это напоми-

нает стратегию «при первом выполнении переход обязательно происходит» с той

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

исходит в ходе заполнения кэш-памяти, то есть динамически. После выполнения
команды состояние дополнительного бита корректируется: если переход имел ме-
сто, в него заносится единица, а в противном случае — ноль. Эффективность стра-
тегии характеризуют данные, полученные в [ 197] (рис. 9.26).

Точность предсказания

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

Главный ее недостаток заключается в дополнительных затратах времени на

обновление состояния контрольного разряда в кэш-памяти команд.

В третьей схеме (рис. 9.27) РНТ состоит из одноразрядных элементов и носит

название

 таблицы истории переходов

 (ВНТ, Branch History Table).

Рис. 9.27. Однобитовая бимодальная схема предсказания

Состояние элемента ВНТ определяет, произошел ли переход в ходе последнего

выполнения команды условного перехода (1) или нет (0). Каждой команде УП
в ВНТ соответствует свой элемент, для обращения к которому используются

 k

младших разрядов адреса команды. Предсказание совпадает с исходом предыду-

щего выполнения команды. Если команда условного перехода участвует в органи-

зации цикла, то стратегия всегда приводит к неправильному предсказанию пере-

хода в первой и последней итерациях цикла.

Схема была реализована в процессорах Alpha 21064 и AMD K5. Согласно

результатам большинства исследовании, средняя точность успешного прогно-

за с помощью однобитовой бимодальной схемы не превышает 78%. В то же время

в работе [197] получено значение 90,4%.

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

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

рядности элементов ВНТ. В четвертой из рассматриваемых одноуровневых схем

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

ся алгоритм Смита. Каждый-счетчик отображает историю выполнения одной ко-

манды УП, то есть адресуется младшими разрядами счетчика команд (рис. 9.28).

Рис. 9.28. Одноуровневая схема предсказания с таблицей DHT

Для обозначения таблицы истории переходов в данной схеме используют абб-

ревиатуру DHT (Decode History Table). Слово «decoder

»

декодирование) в назва-

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

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

мандой условного перехода. Реализуется DHT на базе обычного ЗУ с произволь-
ным доступом.

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

схема Смита

 или

 бимодальный предиктор.

 Отличие от предыдущего варианта вы-

ражается лишь в способе реализации ВНТ (в схеме Смита сохранено именно это

название таблицы). Таблица истории переходов организуется на базе кэш-памяти

с ассоциативным отображением (рис. 9.29).

Рис. 9.29. Схема с таблицей истории переходов

В качестве ассоциативного признака (тега) при поиске нужного счетчика вы-

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