9. Структурные конфликты и способы их минимизации. Конфликты по данным, остановы конвейера и реализация механизма обходов.

При конвейерном выполнении команд возникает ситуация, которая препятствует выполнению команды в заданном порядке. В этих ситуациях работа конвейера приостанавливается до разрешения конфликта. Существует 3 класса конфликтов:

1.Структурный конфликт, который возникает из-за конфликтов по ресурсам.

2.Конфликт по данным – выполнение команды зависит от результата предыдущей.

3.Конфликты по управлению, возникают при выполнении команд условного перехода.

Рассмотрим структурный конфликт. Совмещенный режим выполнения команд требует конвейеризацию операционных устройств и дублирование ресурсов системы для разрешения всех возможных команд в конвейере. Типичным примером является вычислительная система с наличием ОУ, выполняющая свою задачу за несколько тактов конвейера. В этом случае команды и данные не могут поступать на вход устройства. Т.е. происходит структурный конфликт по причине недостаточного дублирования ресурсов (в системе есть один код для записи в память, а двум командам нужно произвести запись в память).

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

1 тип: чтение после записи (RAW);

2 тип: запись после чтения (WAR), j пытается записать данные раньше, чем i их считает.

3 тип: запись после записи (WAW), в результате в ячейке памяти оказываются не те данные.

Для разрешения конфликтов первого типа широко используется принцип обходных путей.

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

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

Методика планирования компилятора для устранения конфликтов по данным.

A=B+C

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

D=E-F

MOV R_b, B MOV R_b, B

MOV R_c, C MOV R_c, C

ADD R_a, R_b, R_c MOV R_e, E

MOV A, R_a ADD R_a, R_b, R_c

MOV R_e, E MOV R_f, F

MOV R_f, F MOV A, R_a

SUB R_d, R_e, R_f SUB R_d, R_e, R_f

MOV D, R_d MOV D, R_d

10. Сокращение потерь на выполнение команд перехода и минимизация конфликтов по управлению.

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

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

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

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

Существует несколько методов по борьбе с конфликтами по управлению: статический и динамический.

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

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

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

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

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

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

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

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

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

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

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

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

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