07. Предсказание переходов в процессорах с конвейерной структурой

Предсказание переходов на сегодняшний день рассматривается как один из наиболее эффективных способов борьбы с конфликтами по управлению. Идея заключается в том, что еще до момента выполнения команды условного перехода или сразу же после ее поступления па конвейер делается предположение о наиболее вероятном исходе такой команды (переход произойдет или не произойдет). Последующие команды подаются на конвейер в соответствии с предсказанием. Для иллюстрации вернемся к примеру (см. рис. 9.5), где команда 3 является командой УП. Пусть для команды 3 предсказано, что переход не произойдет. Тогда вслед за командой 3 на конвейер будут поданы команды 4-6 и т. д. Если предсказан переход, то после команды 3 на конвейер подаются команды 15-17, ... При ошибочном предсказании конвейер необходимо вернуть к состоянию, с которого началась выборка «ненужных» команд (очистить начальные ступени конвейера), и приступить к загрузке, начиная с «правильной» точки, что по эффекту эквивалентно приостановке конвейера. Цена ошибки может оказаться достаточно высокой, но при правильных предсказаниях крупен и выигрыш — конвейер функционирует ритмично без остановок и задержек, причем выигрыш тем больше, чем выше точность предсказания. Термин «точность предсказания» в дальнейшем будем трактовать как процентное отношение числа правильных предсказаний к их общему количеству. В работе [70] дается следующая оценка: чтобы снижение производительности конвейера из-за его остановок по причине конфликтом по управлению не превысило 10%, точность предсказания переходов должна быть выше 97,7%.

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

Статическое предсказание переходов

Статическое предсказание переходов осуществляется на основе некоторой априорной информации о подлежащей выполнению программе. Предсказание делается на этапе компиляции программы и в процессе вычислений уже не меняется. Главное различие между известными механизмами статического прогнозирования заключается в виде информации, используемой для предсказания, и ее трактовки. Исходная информация может быть получена двумя путями: на основе анализа кода программы или в результате ее профилирования (термин «профилирование» поясняется ниже).

Известные стратегии статического предсказания для команд УП можно классифицировать следующим образом:

■ переход происходит всегда (ПВ); ■ переход не происходит никогда (ПН); ■ предсказание определяется по результатам профилирования; ■ предсказание определяется кодом операции команды перехода; ■ предсказание зависит от направления перехода; ■ при первом выполнении команды переход имеет место всегда.

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

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

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

 

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

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

Интуитивное представление о том, что с увеличением глубины предыстории (увеличением т) точность предсказания должна возрастать, на практике не подтверждается, и при т > 3 точность предсказания начинает снижаться и различие в точности предсказания при т = 3 и т = 2 незначительно.

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

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

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

 

 

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

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

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

■ адрес команды условного перехода; ■ регистр глобальной истории; ■ регистр локальной истории; ■ комбинация предшествующих вариантов.

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

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

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

Рис. 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), выбранных от каждого из двух источников. Здесь многое определяется и характером программы.

 

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

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

 

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