Файл: 401-455.pdf

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

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

Результаты моделирования бимодальной схемы с двухразрядными счетчика-

ми показаны на рис. 9.30. По этим данным среднюю точность предсказания можно
оценить как 92,6%.

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

Рис. 9.30. Точность предсказания двухразрядной бимодальной схемы [197]

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

SPEC_95, средняя точность предсказания по всем программам пакета составила
53,9%. Несмотря на это, бимодальная схема с двухразрядными счетчиками довольно
распространена. На ее основе построены схемы предсказания переходов в процес-
сорах Alpha 21164, R10000, PowerPC 620, UltraSPARC и др.

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

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

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

 Одноуровневые схемы пред-

сказания ориентированы на те команды У П, очередной исход которых существен-

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

ятельство призваны учесть

 двухуровневые адаптивные схемы

 предсказания

переходов, впервые предложенные в [229]. Такие схемы часто называют

 коррели-

условного перехода.

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

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

 глобальной.

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

следних исходов одной команды УП. Такая схема предсказания носит название

локальной.

 Каждый элемент таблицы второго уровня служит для хранения исто-

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

ды содержимое регистра и счетчика обновляется.

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

Рис. 9.31. Общая структура двухуровневой схемы предсказания переходов

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

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

 ВНТ

 использовать шаблон, сфор-

мированный путем сложения по модулю 2, как это показано на рис. 9.23. Такая

схема известна под названием

 gshare.

Гибридные схемы предсказания переходов.

 Для всех ранее рассмотренных

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

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

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

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

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

 временем

 «

ра-

зогрева».

 Пока идет «разогрев», точность предсказания весьма низка. Иными сло-

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

 Гибридные

 или

 со-

ревновательные схемы

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

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

Гибридная схема предсказания переходов, предложенная Макфарлингом [ 165],

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

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

счетчиков, которые часто называют

 счетчиками выбора предиктора

 (рис. 9.32),

Адресация конкретного счетчика в таблице (индексирование) осуществляется

k

 младшими разрядами адреса команды условного перехода, для которой осуще-

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

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

Рис. 9.32. Гибридный предиктор Макфарлинга

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

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

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

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

соответствующего счетчика селектора.

В работе [95] идея гибридного механизма была обобщена на случай

 п

 предик-

торов. Общая структура такой схемы предсказания переходов показана на рис. 9.33.

При выполнении команды УП предсказания формируются одновременно всеми
предикторами, однако реальные действия осуществляются на основании только

одного из них.

Рис. 9.33. Общая схема гибридного предиктора

Выбор подходящего предиктора обеспечивает механизм селекции (рис. 9.34).

В схеме имеется буфер предыстории переходов (ВТВ), в котором каждая запись

дополнена

 п

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

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

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

Рис. 9.34. Механизм выбора предиктора

При записи в

 ВТВ

 нового элемента во все ассоциированные с ним счетчики

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

 п

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

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

щий алгоритм. Если среди предикторов, счетчики которых равнялись 3, хотя бы

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

дился, увеличивается на единицу. Такая политика гарантирует, что по крайней

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

По имеющимся оценкам, точность предсказания переходов с помощью гибрид-

ных стратегий в среднем составляет 97,13%, что существенно выше по сравнению
с прочими вариантами.

Асимметричная схема предсказания переходов.

 Асимметричная схема соче-

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

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

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

да, так и содержимое регистра глобальной истории (рис. 9.35).

Шаблон для обращения к каждой из трех РНТ формируется по-разному (при-

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

 свое

 предположение, но оконча-

тельное решение принимается по мажоритарной схеме. После завершения коман-

ды условного перехода содержимое всех трех таблиц обновляется.

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

Рис. 9.35. Структура асимметричной схемы предсказания переходов

Правильный подбор алгоритмов хэширования позволяет практически исклю-

чить влияние на точность предсказания эффекта наложения. Средняя точность

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

SPEC_95, составила 72,6%.

Суперконвейерные процессоры

Эффективность конвейера находится в прямой зависимости от того, с какой час-

тотой на его вход подаются объекты обработки. Добиться n-кратного увеличения
темпа работы конвейера можно двумя путями:

-

 разбиением каждой ступени конвейера на

 п

 «подступеней» при одновремен-

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

 п

 раз;

-

 включением в состав процессора

 п

 конвейеров, работающих с перекрытием.

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

ce

перконвейеризация

 (термин впервые был применен в 1988 году). Иллюстрацией

эффекта суперконвейеризации может служить диаграмма, приведенная на рис. 9.36,
где рассмотрен ранее обсуждавшийся пример (см. рис. 9.3). Каждая из шести сту-
пеней стандартного конвейера разбита на две более простые подступени, обозна-
ченные индексами 1 и 2. Выполнение операции в подступенях занимает половину

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

В сущности, суперконвейеризация сводится к увеличению количества сту-

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

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

Критерием для причисления процессора к суперконвейерным служит число

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

считается MIPS R4000, конвейер команд которого включает в себя восемь ступе-