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


Предсказание переходов

Предсказание переходов в настоящее время рассматривается как один из более эффективных способов борьбы с конфликтами по управлению. Для устранения таких конфликтов еще до момента выполнения команды условного перехода или сразу же после ее поступления на конвейер делается предположение о наиболее вероятном исходе такой команды, т.е. делается предсказание о том, произойдет или не произойдет переход. Все последующие команды подаются на конвейер в соответствии со сделанным предсказанием. При ошибочном предсказании конвейер необходимо вернуть в состояние, с которого началась загрузка ненужных команд. Для этого необходимо очистить начальные ступени конвейера и приступить к загрузке, начиная с команды, которой передается управление. Подобная перезагрузка конвейера по эффекту эквивалентна приостановке конвейера, что ведет к снижению производительности процессора. Поэтому цена ошибки предсказания перехода может оказаться достаточно высокой, но при правильных предсказаниях крупен и выигрыш, поскольку конвейер в этом случае работает ритмично без остановок и задержек. При правильном предсказании выигрыш в производительности будет тем больше, чем выше точность предсказания. Точность предсказания обычно оценивают как процентное отношение числа правильных предсказаний к их общему количеству. Для того чтобы снижение производительности конвейера по причине конфликтов по управлению не превысило 10%, точность предсказания переходов должна быть выше 97,7%.

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

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

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

1. Переход происходит всегда (ПВ);

2. Переход никогда не происходит (ПН);

3. Предсказание определяется по результатам профилирования;

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

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

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

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

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

Проведенные исследования путем имитационного моделирования с помощью тестовых программ показали, что точность предсказания первого способа ПВ лежит в диапазоне от 55% до 76%, а второго – менее 50%. Поэтому при прочих равных условий предпочтение следует отдать стратегии ПВ.

Несмотря на невысокую точность предсказаний обе стратегии нашли применение в реальных микропроцессорах. Например, способ ПВ использовался в микропроцессорах i 486 фирмы Intel, а способ ПН был реализован в микропроцессорах М68020 и МС88000 ЭВМ VAX 11/780 фирмы DEC.

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

Четвертый способ предсказания на основе кода операции команды перехода предполагает, что для одних команд переход произойдет всегда, а для других команд – никогда. Поэтому все команды условного перехода делят на две группы, командам одной группы назначается стратегия ПВ, а другой – ПН. Распределение команд на группы можно проводить либо по результатам профилирования, либо по кодам команд. Например, стратегию ПВ можно назначить командам перехода по условиям: меньше нуля, равно, больше или равно, а всем остальным командам – стратегию ПН. Этот способ имеет примерно такую же точность предсказания, что и третий, т.е. примерно 75%.

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

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

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