06. Факторы, снижающие производительность конвейерных структур и методы борьбы с ними

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

■ попыткой нескольких команд одновременно обратиться к одному и тому же ресурсу ВМ (структурный риск);

■ взаимосвязью команд по данным (риск по данным);

■ неоднозначностью при выборке следующей команды в случае команд перехода (риск по управлению).

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

Решение: дублирование ресурса

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

■    «Чтение после записи» (ЧПЗ): команда j читаете до того, как команда i успела записать новое значение х, то есть j ошибочно получит старое значение х вместо нового. ■    «Запись после чтения» (ЗПЧ): команда j записывает новое значение х до того, как команда i успела прочитать х, то есть команда i ошибочно получит новое значение х вместо старого. ■    «Запись после записи» (ЗПЗ): команда; записывает новое значение х прежде чем команда i успела записать в качестве х свое значение, то есть х ошибочно содержит i-e значение х вместо j-го.

Возможен и четвертый случай, когда команда  j читает x прежде команды i. Этот случай не вызывает никаких конфликтов, поскольку как i, так и  j получат верное значение х.

В борьбе с конфликтами по данным выделяют два аспекта: своевременное обнаружение потенциального конфликта и его устранение. Признаком возникновения конфликта по данным между двумя командами i и  j служит невыполнение хотя бы одного из трех условий Бернстейна (Bernstein's Conditions):

Где O(k) — множество ячеек, изменяемых командой k; I(1) — множество ячеек, читаемых командой l; Ø — пустое множество; ∩ — операция пересечения множеств.

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

Для борьбы с конфликтами но данным применяются как программные, так и аппаратные методы.

Программные методы ориентированы на устранение самой возможности конфликтов еще на стадии компиляции программы. Оптимизирующий компилятор пытается создать такой объектный код, чтобы между командами, склонными к конфликтам, находилось достаточное количество нейтральных в этом плане команд. Если такое не удается, то между конфликтующими командами компилятор вставляет необходимое количество команд типа «Нет операции».                      

 Фактическое разрешение конфликтов возлагается на аппаратные методы. Наиболее очевидным решением является остановка команды j на несколько тактов с тем, чтобы команда i успела завершиться или, по крайней мере, миновать ступень конвейера, вызвавшую конфликт. Соответственно задерживаются и команды, следующие в конвейере за  j-й командой. Данную ситуацию называют «пузырьком» в конвейере. Иногда приостанавливают только команду  j, не задерживая следующие за ней команды. Это более эффективный прием, но его реализация усложняет конвейер.

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

Наибольшие проблемы при создании эффективного конвейера обусловлены командами, изменяющими естественный порядок вычислений¹. Простейший конвейер ориентирован на линейные программы. В нем ступень выборки извлекает команды из последовательных ячеек памяти, используя для этого счетчик команд (СК). Адрес очередной команды в линейной программе формируется автомата чески, за счет прибавления к содержимому СК числа, равного длине текущей команды в байтах. Реальные программы практически никогда не бывают линейными. В них обязательно присутствуют команды управления, изменяющие последовательность вычислений: безусловный и условный переход, вызов процедуры» возврат из процедуры и т. п.. Выполнение команд, изменяющих последовательность вычислений, может приводить к приостановке конвейера на несколько тактов, из-за чего производительность процессора снижается.

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

Методы решения проблемы условного перехода

Несмотря на важность аспекта вычисления исполнительного адреса точки перехода, основные усилия проектировщиков ВМ направлены на решение проблемы условных переходов, поскольку именно последние приводят к наибольшим издержкам в работе конвейера. Для устранения или частичного сокращения этих издержек были предложены различные способы, которые условно можно разделить на четыре группы;

■ буферы предвыборки; ■ множественные потоки; ■ задержанный переход; ■ предсказание перехода.

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

Другим решением проблемы переходов служит дублирование начальных ступеней конвейера и создание тем самым двух параллельных потоков команд. В одной из ветвей такого «раздвоенного» конвейера последовательность выборки и выполнения команд соответствует случаю, когда условие перехода не вы полнилось, во второй ветви — случаю выполнения этого условия.

Стратегия задержанного перехода предполагает продолжение выполнения команд, следующих за командой УП, вне зависимости от ее исхода. Естественно, что, то имеет смысл, лишь когда последующие команды являются «полезными», то есть такими, которые все равно должны быть когда-то выполнены, независимо от того, происходит переход или нет, и если команда перехода никак не влияет на результат их выполнения.

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