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

■ предсказание определяется кодом операции команды перехода;

■ предсказание зависит от направления перехода;

■ при первом выполнении команды переход имеет место всегда.

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

Интуитивное представление, что обе стратегии должны приводить к верному предсказанию в среднем в 50% случаев, на практике не подтверждается. Так, по результатам тестирования (рис. 9.8), приведенным в [197], предсказание об обязательном переходе оказалось правильным в среднем для 76% команд УП.

Рис. 9.8. Точность предсказания переходов при стратегии «переход происходит всегда»

Аналогичный показатель, полученный на ином наборе тестовых программ [150], составил 68%. В работе [228] приводятся результаты проверки стратегии ПБ на тестах CPU2000 отдельно для программ с интенсивными целочисленными вычислениями и программ с преимущественной обработкой чисел в форме с плавающей запятой. Для первых средняя точность предсказаний составила 55,2%, а для вторых — 59,9%. В других источниках встречаются и иные численные оценки точности прогноза при стратегии ПВ, в частности 60% и 71,9%. В то же время в работе [233] отмечается, что для ряда программ, связанных с целочисленной обработкой, процент правильных предсказаний может опускаться ниже 50%.

Цифры свидетельствуют, что успешность стратегии ПВ существенно зависит от характера программы и методов программирования, что, естественно, можно рассматривать как недостаток. Тем не менее стратегия все же используется в ряде ВМ, в частности MIPS-X, SuperSPARC, микропроцессорах i486 фирмы Intel. Связано это, скорее всего, с простотой реализации и с тем, что для определенного класса программ стратегию можно считать достаточно эффективной.

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

Стратегия ПН реализована в конвейерах микропроцессоров М68020 и MC88000, вычислительной машине VAX 11/780. Сравнительная оценка стратегий ПВ и ПН, Полученная при выполнении тестов CPU2000 для целочисленных и вещественных вычислений [228], показана на рис. 9.9.

Рис. 9.9. Сравнение статических стратегий ПВ и ПН

Из диаграммы видно, что ни одна из двух стратегий не обладает явным преимуществом над другой. Тем не менее анализ большого количества программ [1541 показывает, что условные переходы имеют место более чем в 50% случаев, поэтому если стоимость реализации двух рассмотренных вариантов одинакова, то предпочтение следует отдать стратегии ПВ.

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

Средняя вероятность правильного предсказания, полученная на программах тестового набора SPEC 92, составила 75%. Стратегия используется в процессорах MIPS 4x00 и PowerPC 603.

При предсказании на основе кода операции команды перехода для одних команд предполагается, что переход произойдет, для других — его не случится. Например, для команды перехода по переполнению логично предположить, что перехода не будет. На практике назначение разным видам команд УП наиболее вероятного исхода чаще производится по результатам профилирования программ. В исследованиях Е. Смита [197] стратегия ПВ была назначена командам перехода по условиям: «меньше нуля», «равно», «больше или равно», а ПН — всем прочим командам условного перехода. Результаты показаны на рис. 9.10.

Эффективность предсказания зависит от характера программы. Этим, в частности, объясняется различие в выводах, полученных на основе разных исследований. Так, согласно [154] стратегия приводит к успеху в среднем более чем в 75% случаев, а исследования Е. Смита дают цифру 86,7%.

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

Рис. 9.10. Точность предсказания переходов при стратегии «переход зависит от кода операции»

команд, говорят о переходе «назад», и для такой команды назначается стратегия ПВ. Переход к адресу, превышающему адрес команды перехода, считается переходом «вперед», и такой команде назначается стратегия ПН. В основе рассматриваемого подхода лежит статистика по множеству программ, согласно которой большинство команд УП в программах используются для организации циклов, причем, как правило, переходы происходят к началу цикла (переходы «назад»). Согласно [120], для команд, выполняющих переход «назад», фактический переход имеет место в 85% случаев. Для переходов «вперед» эта цифра составляет 65%. Таким образом, для команд условного перехода «назад» логично принять, что переход происходит всегда. Рассматриваемую стратегию иногда называют «Переход назад происходит всегда». Результаты ее оценки [197] приведены на рис. 9.11.

Рис. 9.11. Точность предсказания переходов при стратегии «переход зависит от направления перехода»

Здесь при тестировании на пакете SPEC_89 средняя точность предсказания составила 65%. Среди ВМ, где описанная стратегия является основной, можно упомянуть MicroSPARC-2 и РА-7х00. Чаще, однако, стратегия используется в качестве вторичного механизма в схемах динамического прогнозирования переходов.

В последней из рассматриваемых статических стратегий при первом выполнении любой команды условного перехода делается предсказание, что переход обязательно будет. Предсказания на последующее выполнение команды зависят от правильности начального предсказания. Стратегию можно считать статической только частично, поскольку она однозначно определяет исход команды лишь при первом ее выполнении. Точность прогноза в соответствии с данной стратегией выше, чем у всех предшествующих, что подтверждают результаты, приведенные на рис. 9.12[197].

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

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

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

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

Идея динамического предсказания переходов предполагает накопление информации об исходе предшествующих команд УН. История переходов фиксируется в форме таблицы, каждый элемент которой состоит из т битов. Нужный элемент таблицы указывается с помощью k-разрядной двоичной комбинации — шаблона (pattern). Этим объясняется общепринятое название таблицы предыстории переходов — таблица истории для шаблонов (РНТ, Pattern History Table).

При описании динамических схем предсказания переходов их часто расценивают как один из видов автоматов Мура, при этом содержимое элементов РНТ трактуется как информация, отображающая текущее состояние автомата. В работе [230] рассмотрены различные варианты подобных автоматов, однако реально осмысленно говорить лишь о трех вариантах, которые условно обозначим Al, A2 и A3.

Автомат А1 имеет только два состояния, поэтому каждый элемент РНТ состоит из одного бита (m = 1), значение которого отражает исход последнего выполнения команды условного перехода. Диаграмма состояний автомата А1 приведена на рис. 9.13.

Рис. 9.13. Диаграмма состояний автомата А1

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

Два других автомата предполагают большее число состояний, поэтому в них используются РНТ с многоразрядными элементами. Чаще всего ограничиваются двумя разрядами (т = 2) и, соответственно, автоматами с четырьмя состояниями.

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

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

Двухразрядная схема автомата А2 используется относительно редко. Большую известность получила трехразрядная модель. Она, в частности, реализована в процессоре HP PA 8000.

Элементы РНТ в автомате A3 можно рассматривать как реверсивные счетчики, работающие в режиме с насыщением. При поступлении на конвейер команды условного перехода происходит обращение к соответствующему счетчику РНТ, и в зависимости от текущего состояния счетчика делается прогноз, определяющий дальнейший порядок извлечения команд программы. После прохождения ступени исполнения, когда фактический исход команды становится ясным, содержимое счетчика увеличивается на единицу (если команда завершилась переходом) или уменьшается на единицу (если перехода не было). Счетчики работают в режиме насыщения. Это означает, что добавление единиц сверх максимального числа в счетчике, а также вычитание единиц при пулевом содержимом счетчика уже не производятся. Основанием для предсказания служит состояние старшего разряда счетчика. Если он содержит единицу, то принимается, что переход произойдет, в противном случае предполагается, что перехода не будет.

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

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

График показывает также, что различие в точности предсказания при т = 3 и т = 2 незначительно, что удостоверяют также результаты, приведенные в [197] (рис. 9.16).

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

Как следствие, в большинстве известных процессоров используются двухразрядные счетчики (т = 2). Логика предсказания переходов применительно к двухразрядным счетчикам известна как алгоритм Смита [193]. Алгоритм предполагает четыре состояния счетчика:

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

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

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

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

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

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

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

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

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

■ адрес команды условного перехода;

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

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

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

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

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

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

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

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

Регистр глобальной истории (GHR, Global History Register) представляет собой l - разрядный сдвиговый регистр (рис. 9.19). После выполнения очередной команды условного перехода содержимое регистра сдвигается на один разряд, а в освободившуюся позицию заносится единица (если исходом команды был переход) или ноль (если перехода не было). Следовательно, кодовая комбинация в GHR отражает историю выполнения последних l команд условного перехода. Под индексирование массива предикторов (элементов механизма предсказания) выделяются k младших разряда GHR (чаще всего l = k). Каждой k-разрядной комбинации исходов последовательно выполнявшихся команд УП в массиве дескрипторов соответствует свой счетчик. Таким образом, счетчик РНТ определяется тем, какая комбинация исходов имела место в k предшествовавших командах перехода. Содержимое счетчика используется для предсказания исхода текущей команды перехода и впоследствии модифицируется по результату фактического выполнения команды.

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

Регистр локальной истории (LHR, Local History Register) no логике работы аналогичен регистру глобальной истории, но предназначен для фиксации последовательных исходов одной и той же команды УП. В схемах предсказания с LHR присутствует так называемая таблица локальной истории, представляющая собой массив регистров локальной истории (рис. 9.20).

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

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

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

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

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

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

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

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

Вариант со сложением по модулю 2 предполагает побитовое применение операции «Исключающее ИЛИ» к обоим источникам (рис. 9.23). В качестве шаблона используются k младших разрядов результата. Сформированный шаблон содержит больше полезной информации для предсказания, чем каждый из источников по отдельности.

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

Для сравнительной оценки рассмотренных вариантов доступа к РНТ обратимся к результатам экспериментов, приведенным в [64]. Исследовались четыре тестовых программы:

■ compress — сжатие файлов (10 млн. УП);

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

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

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

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

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

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

В реальных схемах предсказания переходов размер таблицы РНТ ограничен. Типичное количество элементов РНТ (элементарных счетчиков) в разных процессорах варьируется от 256 до 4096. Для выбора определенного входа в РНТ (нужного счетчика) применяется k-разрядный шаблон, где k определяется размером массива. Для упомянутых выше размеров РНТ значение k лежит в диапазоне от 8 до 12. Если обращение к РНТ определяется счетчиком команд, разрядность которого обычно больше, чем k, в качестве шаблона выступают k младших битов СК. Как следствие, две команды условного перехода, адреса которых в младших k разрядах совпадают, будут обращаться к одному и тому же элементу РНТ, и история выполнения одной команды будет накладываться на историю выполнения другой, что, естественно, будет влиять на точность предсказания. Ситуация известна как эффект наложения (aliasing). Та же проблема существует и при доступе к РНТ на основании содержимого регистра глобальной истории или регистра локальной истории. В зависимости от типа программы и других факторов наложение может приводить к повышению точности предсказания, ее ухудшению либо вообще не сказываться па точности предсказания. Соответственно, эффекты наложения классифицируют как конструктивный, деструктивный и нейтральный.

Рассмотрим, насколько часто предсказания производятся на основании тех счетчиков РНТ, при обращении к которым имел место эффект наложения (рис. 9,25) [164].

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

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

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

■ одноуровневые или бимодальные;

■ двухуровневые или коррелированные;

■ гибридные;

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

Одноуровневые схемы предсказания переходов. В многочисленных исследованиях, проводившихся на самых разнообразных программах, была отмечена интересная закономерность. В поведении многих команд условного перехода явно прослеживается тенденция повторяемости исхода: одни команды программы, как правило, завершаются переходом, в то время как другие — остаются без оного, то есть имеет место бимодальное распределение исходов. Идея одноуровневых схем предсказания, известных также под вторым названием — бимодальные схемы [165], сводится к отделению команд, имеющих склонность завершаться переходом, от команд, при выполнении которых переход обычно не происходит. Такая дифференциация позволяет для каждой команды выбрать наиболее подходящее предсказание. Для реализации идеи в составе схемы предсказания достаточно иметь лишь одну таблицу, каждый элемент которой отображает историю исходов одной команды УП. Для обращения к элементу, ассоциированному с определенной командой УП, используется адрес этой команды (или его младшие биты). Таким образом, одноуровневые схемы предсказания переходов можно определить как схемы, содержащие один уровень таблиц истории переходов (обычно единственную таблицу), адресуемых с немощью адреса команды условного перехода.

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

Вторая схема ориентирована на то, что команды программы извлекаются из кэш-памяти команд. Каждая ячейка кэш-памяти содержит дополнительный разряд, который используется только применительно к командам условного перехода. Состояние разряда отражает исход предыдущего выполнения команды (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%.

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

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

Для обозначения таблицы истории переходов в данной схеме используют аббревиатуру DHT (Decode History Table). Слово «decode» (декодирование) в названии отражает особенность работы с таблицей. Если к обычной ВНТ обращение происходит при выборке любой команды, вне зависимости от того, на самом ли деле она команда условного перехода, поиск в DHT начинается только после декодирования команды, то есть когда выяснилось, что данная команда является командой условного перехода. Реализуется DHT на базе обычного ЗУ с произвольным доступом.

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

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

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

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

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

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

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

Двухуровневые схемы предсказания переходов. Одноуровневые схемы предсказания ориентированы на те команды УП, очередной исход которых существенно зависит от их собственных предыдущих исходов. В то же время для многих команд программы наблюдается сильная зависимость не от собственных исходов, а от результатов выполнения других предшествующих им команд УП. Это обстоятельство призваны учесть двухуровневые адаптивные схемы предсказания переходов, впервые предложенные в [229]. Такие схемы часто называют коррелированными, подчеркивая тот факт, что они отражают взаимозависимость команд условного перехода.

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

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

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

Гибридные схемы предсказания переходов. Для всех ранее рассмотренных стратегий характерна сильная зависимость точности предсказания от особенностей программ, в рамках которых эти стратегии реализуются. Та же самая схема прекрасно проявляя себя с одними программными продуктами, с другими может давать совершенно неудовлетворительные результаты. Кроме того, необходимо учитывать еще один фактор. Прежде уже отмечалось, что точность предсказания повышается с увеличением глубины предыстории переходов, но происходит это лишь после накопления соответствующей информации, на что требуется определенное время. Период накопления предыстории принято называть временем «разогрева». Пока идет «разогрев», точность предсказания весьма низка. Иными словами, ни одна из элементарных стратегий предсказания переходов не является универсальной — со всех сторон лучшей в любых ситуациях. Гибридные или соревновательные схемы объединяют в себе несколько различных механизмов предсказания — элементарных предикторов. Идея состоит в том, чтобы в каждой конкретной ситуации задействовать тот элементарный предиктор, от которого в данном случае можно ожидать наибольшей точности предсказания.