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

 

Конфликты по управлению возникают при конвейеризации команд условных переходов. По статистике до 15%-20% всех команд в программе - это команды условных переходов. Конфликт проявляется в том, что адрес условного перехода определяется только в конце выполнения команды, в то время, как конвейер уже должен быть заполнен командами из какой-то одной ветви. Если не обрабатывать конфликт, то производительность конвейера может снижаться в 2 и большее число раз. Способы борьбы с конфликтами по управлению можно разделить на 2 группы: статические и динамические. К статическим методам можно отнести: 1) Возврат, т.е. статическое прогнозирование перехода как всегда выполняемого, либо – всегда не выполняемого с последующей очисткой конвейера в случае неправильного прогноза и возвратом к нужной команде. 2) Разворачивание циклов. Поскольку многие условные переходы связаны с определением условия выхода из цикла, то в случае, когда число шагов цикла заранее известно и невелико, можно «развернуть» цикл, то есть продублировать тело цикла столько раз, сколько необходимо, отказавшись от проверки условия вообще. Это приведет к увеличению кода программы, но избавит от конфликта по управлению. 3) Задержанные переходы (использование «слотов задержки»). Под слотами задержки понимают участки программы, которые будут занесены в конвейер и успеют выполниться до выяснения адреса перехода в условной команде. Идея их использования состоит в том, чтобы заполнять слоты задержки «полезными» или «невредными» командами, то есть такими, которые либо не зависят от условия, либо – не приведут к нарушению логики программы, даже если их выполнение окажется лишним. (Рис. 3.8) 4) Предсказание переходов на основе профиля программы. Профилирование (profiling) предусматривает составление прогноза о выполнении тех или иных переходов на основе статистических наблюдений за программой по результатам ее многократного прогона. К динамическим методам можно отнести: Приостановку конвейера до выяснения адреса перехода. Реализацию команд условного перехода в процессоре таким образом, чтобы адрес перехода выяснялся на начальных этапах выполнения команды. Динамическое предсказание ветвлений в процессоре (branching predict). Динамическое предсказание ветвлений в процессорах осуществляется с помощью буферов предсказания перехода (БПП – Branch Predicting Buffer – BPB). Чаще всего в них используется счетчик прогнозов, который представляет собой обычный n-разрядный двоичный счетчик. При каждом выполненном переходе счетчик прогнозов для данного перехода увеличивается, а при невыполненном – уменьшается на единицу. Если текущее значение счетчика > 2n-1, то переход прогнозируется как выполняемый, иначе – как невыполняемый. На практике ограничиваются либо 1-битным, либо 2-битными счетчиками, которые при этом обеспечивают вероятность правильного прогноза соответственно до 70% и 85%. Для еще большего ускорения предсказания используют буфер целевых адресов переходов (Branch Target Buffer – BTB), представляющий собой ассоциативную кэш –память, в которой в качестве тегов используются адреса команд ветвления в текущей части программы, а в ячейках содержатся счетчики прогнозов и целевые адреса перехода при условии его выполнения. Процессор при выборке команды проверяет, не хранится ли ее адрес в BTB, считывает счетчик прогнозов и в зависимости от его значения принимает решение о выборке команд по следующему адресу.