Динамическое предсказание переходов
В динамических стратегиях решение о наиболее вероятном исходе команды условного перехода принимается в ходе вычислений, на основе информации о предшествующих переходах, собираемой в процессе выполнения программы, т.е. на основе истории переходов. В целом, динамические стратегии обеспечивают более высокую точность предсказаний, чем статические. Идея динамического предсказания переходов предполагает накопление информации об исходе предшествующих команд условного перехода. История переходов фиксируется в форме таблицы, каждый элемент которой состоит из m разрядов. Нужный элемент таблицы определяется с помощью k разрядного кода, который называется шаблоном(Pattern). Поэтому такую таблицу предыстории переходов называют таблицей истории для шаблонов или РНТ от Pattern History Table.
Динамические схемы предсказания переходов обычно описывают в виде автомата Мура, при этом содержимое элементов таблицы РНТ интерпретируется как информация, отображающая текущее состояние автомата. Существует несколько вариантов построения таких автоматов, из числа которых рассмотрим три. Эти автоматы условно обозначим как А1, А2 и А3.
Автомат А1 имеет только два состояния, поэтому каждый элемент РНТ состоит из одного разряда, т.е. m=1. Значение этого разряда отражает исход последнего выполнения команды условного перехода. Если команда завершилась переходом, то в соответствующий элемент РНТ записывается единица, в противном случае – ноль. Очередное предсказание совпадает с итогом предыдущего выполнения команды, т.е., если в РНТ для данной команды записана единица, то делается предсказание о возможном переходе, если записан ноль, то делается предсказание об отсутствии перехода. После обработки очередной команды содержимое элемента таблицы корректируется. Диаграмма состояний автомата А1 имеет следующий вид:
Автомат А1 имеет небольшую память и запоминает значение одного последнего перехода, т.к. m=1.
В двухразрядном автомате А2 элементы РНТ отражают исходы уже двух последних выполненных команд условного перехода и заполняются по схеме регистра сдвига. После обработки очередной команды условного перехода содержимое выделенного для этой команды элемента РНТ сдвигается влево на один разряд, а в освободившейся справа разряд записывается единица, если переход произошел, или ноль, если перехода не было. Если в элементе таблицы присутствует хотя бы одна единица, то при очередном выполнении команды делается предсказание, что переход будет. При нулевом значении элемента РНТ (оба разряда в нуле) считается, что перехода не будет. В результате получается следующая диаграмма состояний автомата А2:
Таким образом, предсказание о невозможности перехода будет сделано только в случае, если при двух последних выполнениях команды перехода не было. Если хотя бы одна из двух последних команд закончилась переходом, то делается предсказание о возможности перехода.
Однако в таком виде двухразрядные автоматы, реализованные на регистре сдвига, используются достаточно редко. Чаще используются автоматы, построенные в виде реверсивного счетчика с насыщением.
Рассмотрим работу такого автомата, который будем обозначать А3.
При поступлении на конвейер команды условного перехода происходит обращение к соответствующему счетчику, находящемуся в РНТ. В зависимости от текущего состояния счетчика делается прогноз, определяющий дальнейший порядок извлечения команд программы. После прохождения на конвейере ступени исполнения, когда становится известным исход команды, содержимое счетчика увеличивается на единицу, если команда завершилась переходом, или уменьшается на единицу, если перехода не было. Счетчик работает в режиме насыщения. Это значит, что добавление единицы сверх максимального числа в счетчике, а также вычитание единицы при нулевом состоянии счетчика уже не производится, т.е. состояния счетчика в этих случаях остаются прежними. Основанием для предсказания служит старший разряд счетчика. Если он содержит единицу, то делается предсказание о возможном переходе, в противном случае предполагается, что перехода не будет.
Проведенные исследования показали, что точности предсказания при m=2 и m=3отличаются незначительно. Поэтому в большинстве известных микропроцессорах используются двухразрядные счетчики (m=2). Алгоритм предсказания на основе двухразрядного счетчика называется алгоритмом Смита и имеет четыре состояния счетчика:
1. состояние 00 – перехода не будет;
2. состояние 01 – перехода не будет;
3. состояние 10 – переход будет;
4. состояние 11 – переход будет.
Диаграмма состояний двухразрядного автомата А3 имеет следующий вид:
Существует несколько стратегий предсказания на основе двухразрядного счетчика, которые отличаются друг от друга тем, какая информация используется в качестве шаблона для доступа к РНТ и какого рода история фиксируется в элементах таблицы.
В качестве шаблонов для доступа к РНТ могут использоваться:
1. адрес команды условного перехода;
2. регистр глобальной истории;
3. регистр локальной истории;
4. комбинация предшествующих вариантов.
Схема, в которой для доступа к РНТ выбран адрес команды условного перехода, т.е. содержимое счетчика команд (СК), позволяет учитывать поведение каждой конкретной команды условного перехода (УП). При многократном выполнении большинства команд УП наблюдается повторяемость исхода: переход либо происходит, либо не происходит, т.е. имеет место бимодальное распределение исходов (две моды). Индексация РНТ с помощью адреса команды УП дает возможность отделить первые исходы от вторых, что позволяет повысить точность предсказания. Каждой команде УП в РНТ соответствует свой реверсивный счетчик состояний, который работает в соответствии с диаграммой состояний автомата А3, т.е. содержимое счетчика увеличивается на единицу, если переход произошел, и уменьшается на единицу в противном случае, причем счетчик работает в режиме насыщения. В качестве шаблона для поиска в РНТ соответствующего данной команде УП реверсивного счетчика, служат младшие k разрядов адреса команды УП. При k разрядном индексе РНТ может содержать до 2k элементов, что позволяет отслеживать поведение до 2k команд УП. Такая стратегия предсказания обеспечивает достаточно высокий процент правильных исходов для тех команд УП, которые в ходе вычислений выполняются многократно, например в циклах. Схема поиска нужного элемента таблицы приведена на рисунке.
Однако в программах, кроме многократно исполняемых команд УП могут встречаться команды, которые выполняются однократно или малое количество раз. Проведенные исследования показали, что исход таких команд УП в значительной степени зависит от поведения предшествующих команд УП, т.е. между исходами команд УП в программе существует некоторая взаимосвязь. Учет такой взаимосвязи дает возможность повысить долю правильных предсказаний. Идея учета взаимосвязи команд УП реализуется схемой с регистром глобальной истории.
Регистр глобальной истории – GHR (Global History Register) представляет собой l – разрядный регистр сдвига.
После выполнения очередной команды УП содержимое регистра сдвигается на один разряд, а в освобождающийся разряд записывается единица, если произошел переход, или ноль, если перехода не было. Таким образом, число в GHR отражает историю выполнения последних l команд УП. Для обращения к РНТ используются k – младших разрядов GHR. Каждой k – разрядной комбинации исходов последних команд УП в таблице РНТ соответствует свой счетчик состояний. Таким образом, счетчик в РНТ определяется комбинацией исходов kпредшествовавших команд УП. Содержимое счетчика состояний используется для предсказания исхода текущей команды УП, после чего содержимое счетчика изменяется (модифицируется) по результату фактического выполнения команды, например, в соответствии с алгоритмом работы автоматаА3.
Регистр локальной истории – LHR (Local History Register) по логике работы аналогичен GHR, но предназначен для фиксации последовательных исходов одной и той же команды УП. В схемах предсказания с LHR используется таблица локальной истории, представляющая собой массив регистров локальной истории, как показано на рисунке:
Каждый счетчик в РНТ фиксирует историю исходов только одной команды УП.
Действие команды условного перехода зависят как от исходов предшествующих выполнений данной команды, так и от исходов выполнения других команд УП. Поэтому в некоторых динамических методах предсказания шаблон для доступа к РНТ формируется путем объединения адреса команды перехода (счетчик команд) и содержимого GHR, что позволяет повысить точность предсказаний. При этом используется одна из двух логических операций: конкатенация (сцепление) и сложение по модулю два.
При конкатенации k – разрядный шаблон для обращения к РНТ образуется путем объединения q младших разрядов от одного источника и k-q младших разрядов от другого источника, в результате чего получается k – разрядный адрес строки РНТ.
Эффективность предсказания на основе подобного шаблона зависит от соотношения количества разрядов q и k-qвзятых от разных источников.
Другой вариант объединения GHR и СК предполагает поразрядное сложение по модулю 2 кодов от указанных источников.
Сформированный таким образом шаблон содержит больше полезной информации для предсказания, чем каждый из источников в отдельности.
Сравнительный анализ рассмотренных 4-ех методов доступа к РНТ показал:
1. с увеличением размера РНТ точность предсказаний возрастает для всех методов;
2. схема с использованием СК, т.е. адреса команды УП, является наименее эффективной;
3. схема с конкатенацией дает наихудшие результаты при малых объемах РНТ, но с увеличением объема РНТ превосходит модель со счетчиком команд;
4. наилучший результат дает схема объединения кодов путем сложения по модулю 2 содержимого GHR и СК.
В реально используемых схемах предсказания размер таблицы РНТ ограничен и лежит в пределах от 256 до 4096 строк, т.е. количества счетчиков состояний. Для выбора определенной строки используется k – разрядный шаблон, обычно значения k лежат в диапазоне от 8 до 12 разрядов. Если обращение к РНТ происходит с помощью 32-ух разрядного счетчика команд, то в качестве шаблона используется k младших разрядов СК. Поэтому две команды УП, k младших разрядов, адреса которых совпадают, будут обращаться к одному и тому же элементу таблицы РНТ и история выполнения одной команды УП будет накладываться на историю выполнения другой команды. Такая ситуация называется эффект наложения (aliasing) и влияет на точность предсказания. Аналогичная ситуация существует и при доступе к РНТ с помощью GHR и LHR. В зависимости от типа программы эффект наложения может приводить к повышению точности предсказания, ее ухудшению или вообще не сказываться на точности предсказаний. Поэтому эффект наложения может быть конструктивным, деструктивным и нейтральным. С увеличением объема таблицы РНТ частота наложения снижается. Проведенные исследования показали, что схема предсказания со счетчиком команд в наименьшей степени подвержена эффекту наложения. Если в качестве шаблона используется GHR или операция конкатенация, то эффект наложения максимальный и обычно отрицательно влияет на точность предсказаний.