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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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