Прогнозирование переходов
В случае наличия команд перехода результат предварительного исполнения команд часто должен быть аннулирован, необходимо обработать другую группу команд. Вот почему рекомендуется уменьшать число команд перехода не только при программировании на любом языке программирования! Для увеличения вероятности правильной выборки команд используется блок предсказания переходов (БПП).
БПП появились, начиная с PENTIUM.
Различают два способа прогнозирования переходов: статическое и динамическое. Статическое прогнозирование выполняется, если команда перехода встретилась в программе в первый раз, динамическое – при повторном выполнении команды перехода (цикл, вызов процедуры). Для PENTIUM статическое предсказание для команд безусловного перехода – переход будет, для команд условного перехода – перехода не будет. Для старших версий PENTIUM команды условного перехода делятся на ссылки вперед и назад. Прогнозируется, что ссылка вперед будет, назад – нет. Подумайте, почему выбрана именно такая стратегия предсказания!
Примеры[2]:
s= i=0;
m1:
s+= x[i];
i++;
if (i<10)goto m1;
Для PENTIUM данный переход при первом исполнении цикла будет спрогнозирован неверно, для PENTIUM 11 верно.
Динамическое прогнозирование использует БПП. БПП включает в себя 512 строчный буфер, в каждой строке которого записывается информация об одной команде перехода. Для PENTIUM в строке записывается адрес команды перехода, адрес, куда надо перейти и 2 флага по одному биту.
Для каждой команды перехода, для которой нет еще информации в буфере, она записывается в одну строку, прогноз на переход строится в соответствии со статистическим прогнозом. Если прогнозируется наличие перехода, один из флагов устанавливается в 1. Если фактически перехода нет, этот бит сбрасывается.
При повторном выполнении команды перехода прогнозируется наличие перехода, если хотя бы один флаг установлен. Если фактически переход есть, то второй флаг устанавливается в 1, если нет – единичный флаг сбрасывается. Прогнозируется отсутствие перехода, если оба бита нулевые. Таким образом, если был переход дважды или более, то случайное отсутствие перехода не влияет на правильность прогноза. Наиболее неблагоприятный вариант – чередование наличия и отсутствия перехода.
Начиная с PENTIUM PRO, и для всех последующих процессоров, задается 4 адреса для каждой команды перехода и 4 флага, что позволяет точно предсказывать переход, если период не более 4, например, для фрагмента кода
if (a == 5) a = 7; else a = 5;
который выполняется в цикле, всегда будет предсказан верный переход, начиная с третьего выполнения. (период равен 2).
Несмотря на мощность БПП, ошибки все же возможны. Для исключения таких ошибок используется так называемое спекулятивное выполнение. Выполняются обе ветви программы. Как только адрес перехода будет вычислен, результаты для неверной ветви аннулируются. Это не совсем безобидный способ - один канал занят выполнением ненужных команд.
