Лекция 10. Минимализация потерь на выполнение команд перехода.

Минимизация конфликтов по уровню.

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

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

На втором такте происходит дешифрация команды условного перехода и конвеер останавливается. Далее возобновляет свою работу на 5ом такте в момент вычисления целевого адреса. Таким образом команда i могла быть загружена в конвеер в любом случае.

Например, если при каждом выполнении команды условного перехода конвеер приостанавливает выполнение на 3 такта, а количество команд условного перехода состовляет 30% от общего числа команд, то машина достигает половину производительности, которую может достичь при конвеерном выполнении команд. Существует несколько методов по борьбе с конфликтами по управлению: статический и динамический.

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

Во 2-ом случае схема прогнозирует реализацию автоматически.

Статическое:

1)Метод ожидания

2 Метод возврата

3)Мживания перехода

1. Представляет собой простейший способ обработки данных конфликтов и заключается в остановке выполнения всех команд в конвеере с момента дешифрации команд условного перехода до момента вычисления целевого адреса.

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

3. Идея метода заключатся в том, что между моментом загрузки команды условного перехода и собственно переходом по выбранной ветке в конвеер загружаются команды, не связанные с выполнением команды условного перехода.

 

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

В данном случае интервал задержки заполняется независимой командой, находящейся перед командой условного перехода.

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

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

Пример 3 (оптимизированной командой вычитания)

 

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

 

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

Эффективность данного способа зависит от объема памяти и вероятность предсказания может достигать 80%. Для повышения вероятности правильного предсказания используют алгоритмы накапливающие и анализирующие статистику условного перехода по данному адресу и вероятность правильного предсказания повышается до 90-95%.