Конфликты в конвейере команд

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

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

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

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

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

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

«Чтение после записи» (ЧПЗ): команда;' читает х до того, как команда i успела записать новое значение х, то есть; ошибочно получит старое значение х вмес­то нового.

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

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

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

Рис. 9.4. Конфликты по данным: а — «Чтение после записи»; б — «Запись после чтения»;

в — «Запись после записи»

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

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

■ для ЧПЗ:;

Ш для ЗПЧ:;

для ЗПЗ: Щ

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

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

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

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

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

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

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

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

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

Вторая причина нарушения ритмичности работы конвейера имеет отношение только к командам условного перехода. Для пояснения сути проблемы воспользу­емся ранее приведенной условной программой рис. 9.3), несколько изменив по­становку задачи (рис. 9.5).

Рис. 9.5. Влияние условного перехода на работу конвейера команд

Пусть команда 3 — это условный переход к команде 15. До завершения коман­ды 3 невозможно определить, какая из команд (4-я или 15-я) должна выполняться следующей, поэтому конвейер просто загружает следующую команду в последо­вательности (команду 4) и продолжает свою работ}'. В варианте, показанном на рис. 9.3, переход не произошел и получена максимально возможная производи­тельность. На рис. 9.5 переход имеет место, о чем неизвестно до 7-го шага. В этой точке конвейер должен быть очищен от ненужных команд, вьшолняыТШхся до дан­ного момента. Лишь на шаге 8 на конвейер поступае т нужная к о манда 15, из -за чего в течение тактов от 9 до 12 не будет завершена ни одна другая команда. Это и есть издержки из-за невозможности предвидения исхода команды условного перехода. Как видно, они либо существенно больше, чем для прочих команд перехода (если переход происходит), либо отсутствуют вовсе (если переход не происходит).

Для сокращения задержек, обусловленных выборкой команды из точки пере­хода, применяются несколько подходов:

■ вычисление исполнительного адреса перехода на ступени декодирования ко­манды;

* использование буфера адресов перехода;

Ш использование кэш-памяти для хранения команд, расположенных в точке пе­рехода;

Ш использование буфера цикла.

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

Буфер адресов перехода (ВТВ, Branch Target Buffer) представляет собой кэш­
память небольшой емкости, в которой хранятся исполнительные адреса точек пе­
рехода нескольких последних команд, для которых переход имел место. В роли
тегов выступают адреса соответствующих команд. Перед выборкой очередной ко­
манды ее адрес (содержимое счетчика команд) сравнивается с адресами команд,
представленных в ВТВ. Для команды, найденной в буфере адресов перехода, ис­
полнительный адрес точки перехода не вычисляется, а берется из ВТВ, благодаря
чему выборка команды из точки перехода может быть начата на один такт раньше.
Команда, ссылка на которую в ВТВ отсутствует, обрабатывается стандартным
образом. Если это команда перехода, то полученный при ее выполнении исполни­
тельный адрес точки перехода заносится в ВТВ, при условии, что команда завер­
шилась переходом. При замещении информации в ВТВ обычно применяется ал­
горитм LRU. -.

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

Кэш-память команд, расположенных в точке перехода (BTIC, Branch Target Instruction Cache), — это усовершенствованный вариант ВТВ, где в кэш-память помимо исполнительного адреса команды в точке перехода записывается также и код этой команды. За счет увеличения емкости кэш-памяти BTIC позволяет при повторном выполнении команды перехода исключить не только этап вычисления исполнительного адреса точки перехода, но и этап выборки расположенной там команды. Преимущества данного подхода в наибольшей степени проявляются при многократном исполнении одних и тех же команд перехода, главным образом при реализации программных циклов.

Буфер цикла представляет собой маленькую быстродействующую память, вхо­дящую в состав первой ступени конвейера, где производится выборка команд. В буфере сохраняются коды п последних команд в той последовательности, в ко­торой они выбирались. Когда имеет место переход, аппаратура сначала проверяет, нет ли нужной команды в буфере, и если это так, то команда извлекается из буфера. Стратегия наиболее эффективна при реализации циклов и итераций, чем и объяс­няется название буфера. Если буфер достаточно велик, чтобы охватить все тело цикла, выборку команд из памяти достаточно выполнить только один раз в первой итерации, поскольку необходимые для последующих итераций команды уже на­ходятся в буфере.

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

Среди ВМ, где реализован буфер цикла, можно упомянуть некоторые вычис­лительные машины фирмы CDC (Star 100,6600,7600) и суперЭВМ CRAY-1. Спе­циализированная версия буфера цикла имеется и в микропроцессоре Motoro­la 68010, где он используется для особых циклов, включающих в себя команду «Уменьшение и переход по условию».

Дата добавления: 2014-01-07