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

Динамические стратегии переходов

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

1. Одноуровневые или бимодальные;

2. двухуровневые;

3. гибридные;

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

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

В первом варианте используется сравнительно небольшая таблица, в которую записываются адреса n последних команд УП, при выполнении которых переход не произошел. Фактически это есть буфер адресов переходов BTB с той лишь разницей, что в таблице фиксируются адреса команд оставшихся без перехода. Такая таблица строится на основе ассоциативной кэш-памяти. При поступлении на конвейер очередной команды УП ее адрес сравнивается с адресами, хранящимися в таблице. При совпадении адресов делается предположение о том, что перехода не будет, в противном случае предсказывается переход. Поэтому для тех команд УП, которые выполняются первый раз, делается предсказание, что переход будет. После выполнения команды, когда стал известным ее исход, содержимое таблицы корректируется. Если перехода не было, то адрес команды записывается в таблицу, в противном случае таблица остается без изменения. Для тех команд УП, адреса которых уже находятся в таблице, таблица корректируется следующим образом: если команда завершилась переходом, то соответствующая строка из таблицы удаляется, если перехода не было, то таблица остается без изменения. При замещении строк таблицы обычно используется алгоритм LRU. По точности предсказания такая схема превосходит большинство стратегий статического предсказания.

Вторая схема ориентирована на то, что команды программы извлекаются из кэш-памяти команд. Каждая ячейка кэш-памяти имеет дополнительный разряд, который используется только для команд УП. В этот разряд записывается единица, если при последнем исполнении команды завершилась переходом. Если при предыдущим исполнении перехода не было, то в дополнительный разряд записывается ноль. Все последующие предсказания делаются на основе состояния этого разряда: при единичном значении разряда делается предсказание о переходе, при нулевом – об отсутствии перехода. При записи команды УП в кэш дополнительный разряд устанавливается в единицу, т.е. при первом исполнении всегда предсказывается переход. После выполнения команды состояние разряда корректируется: если переход имел место, в него записывается единица, в противном случае – ноль. Точность предсказания лежит в диапазоне 76% - 99%. Недостаток схемы – дополнительные затраты времени на обновление состояния доп. разряда в кэш-памяти команд.

В третьей схеме РНТ состоит из одноразрядных элементов и носит название таблицы истории переходов – ВНТ, от Branch History Table.

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

По k младшим разрядам СК идентифицируется элемент ВНТ, по состоянию которого делается предсказание, совпадающее с исходом предыдущего выполнения команды.

Такая схема предсказания была реализована в микропроцессорах Alpha 21064 и AMD K5. Средняя точность предсказания в однобитовых бимодальных схемах не превышает 78%.

Точность предсказания перехода существенно повышается с увеличением разрядности ВНТ. Обычно используются двухразрядные элементы ВНТ, реализующие алгоритм Смита, в основе которого лежит двухразрядный счетчик, работающий в режиме насыщения. Каждый такой счетчик отображает историю переходов одной команды УП и адресуется k младшими разрядами СК. Для обозначения таблицы истории переходов используются три буквы DHT от англ. Decode History Table.

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

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

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

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

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

Схема Смита позволяет ускорить поиск нужного счетчика и устраняет эффект наложения, но связана со значительными аппаратными затратами, т.к. использует дорогую ассоциативную кэш-память. Средняя точность предсказания на основе схемы Смита примерно равна 92,6%. Схема Смита широко используется для предсказания переходом. На ее основе построены схемы переходов в процессорах Alpha 21164, Power PC 620, Ultra SPAPC и других. Обычно в одноуровневых схемах предсказания таблицы DHTили BHTсовмещены с буфером адреса перехода ВТВ, что позволяет сэкономить на вычислении исполнительных адресов точек перехода.

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