Файл: 401-455.pdf

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

Если команда завершилась переходом, то в соответствующий элемент РНТ за-

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

мое элемента корректируется.

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

используются РНТ с многоразрядными элементами. Чаще всего ограничиваются

двумя разрядами

 (т =

2) и, соответственно, автоматами c четырьмя состояниями.

В двухразрядном автомате А2 элементы РНТ отражают исходы двух последних

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

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

томата показана на рис. 9.14.

э

Рис. 9.14. Диаграмма состояний двухразрядного автомата А2

Двухразрядная схема автомата А2 используется относительно редко. Большую

известность получила трехразрядная модель. Она, в частности, реализована в про-
цессоре HP PA 8000.

Элементы РНТ в автомате A3 можно рассматривать как реверсивные счетчики,

работающие в режиме с насыщением. При поступлении на конвейер команды ус-

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

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

мое счетчика увеличивается на единицу (если команда завершилась переходом)

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

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

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

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

Интуитивное представление о том, что с увеличением глубины предыстории

(увеличением

 т)

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

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

дований, свидетельствующие, что при

 т >

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

жаться.

Разрядность счетчика в РНТ

Рис. 9.15. Зависимость точности предсказания от разрядности элементов РНТ

График показывает также, что различие в точности предсказания при

 т

 = 3 и

т

 - 2 незначительно, что удостоверяют также результаты, приведенные в [197]

(рис. 9.16).

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

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

и трехразрядных счетчиков

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

рядные счетчики (m= 2). Логика предсказания переходов применительно к двух-
разрядным счетчикам известна как

 алгоритм Смита

 [193]. Алгоритм предполага-

ет четыре состояния счетчика:

-

 00 — перехода не будет (сильное предсказание);

-

 01 — перехода не будет (слабое предсказание);

-

 10 — переход будет (слабое предсказание); ;

-

 11 — переход будет (сильное предсказание). ;

\

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

Рис. 9.17. Диаграмма состояний двухразрядного автомата A3

Логику предсказания можно описать диаграммой состояний двухразрядного

автомата A3 (рис. 9.17).

Поскольку вариант РНТ со счетчиками получил наиболее широкое распрост-

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

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

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

бах использования РНТ определяют ту или иную стратегию предсказания.

В качестве шаблонов для доступа к РНТ могут быть взяты:

- адрес команды условного перехода;
- регистр глобальной истории;

-

 регистр локальной истории;

- комбинация предшествующих вариантов.

Схема, где для доступа к РНТ выбран адрес команды условного перехода (со-

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

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

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

 бимодальное распределение

исходов).

 Индексация РНТ с помощью адреса команды УП дает возможность от-

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

дой команде условного перехода в РНТ соответствует свой счетчик. Когда коман-

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

ки счета с насыщением). В качестве шаблона для поиска в РНТ служат младшие

 k

разрядов содержимого счетчика команд (рис. 9.18).

При k-разрядном индексе таблица может содержать 2

k

 элементов.

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

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

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

Рис. 9.18. Индексирование РНТ с помощью адреса команды перехода

предназначены для управления циклом. В то же время в любой программе имеет-

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

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

Регистр глобальной истории

 (GHR, Global History Register) представляет со-

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

 k

 младших разряда GHR (чаще всего l -

 k).

 Каждой k-разрядной комбинации

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

ответствует свой счетчик. Таким образом, счетчик РНТ определяется тем, какая

комбинация исходов имела место в

 k

 предшествовавших командах перехода. Со-

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

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

Рис. 9.19. Индексирование РНТ с помощью регистра глобальной истории

Регистр локальной ucmopuu(LHR,

 Local History Register) пo логике работы ана-

логичен регистру глобальной истории, но предназначен для фиксации последова-

тельных исходов одной и той же команды УП. В схемах предсказания с LHR при-
сутствует так называемая

 таблица локальной истории,

 представляющая собой

массив регистров локальной истории (рис. 9.20).

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

  4 3 5

Рис.

 9.20. Индексирование РНТ с помощью регистров локальной истории

Как и в схеме с адресом команды перехода, каждый счетчик в РНТ фиксирует

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

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

только от результатов предшествующих выполнений данной команды, но и от ис-
хода других команд перехода. Учет обоих факторов позволяет повысить точность
предсказаний. С этой целью в ряде динамических методов предсказания шаблон
для доступа к РНТ формируется путем объединения адреса команды перехода и со-
держимого GHR (либо LHR), при этом используется одна из двух операций: кон-
катенация (сцепление) и сложение по модулю 2 («исключающее ИЛИ»),

При конкатенации k-разрядный шаблон для обращения к РНТ образуется по-

средством взятия

 q

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

ваются

 k-q

 младших разрядов, взятых из второго источника (рис, 9.21).

Рис. 9.21

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

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

шения количества разрядов

 (q

 и

 k-q),

 выбранных от каждого из двух источников.

Здесь многое определяется и характером программы. В качестве иллюстрации на

рис. 9.22 приведена зависимость точности предсказания от соотношения числа
битов, взятых от счетчика команд (СК) и регистра глобальной истории (GHR).
Данные получены на тестовой программе xlisp (интерпретатор языка LISP) при
объеме РНТ, равном 1024 входам.