Конвейеризация вычислений. Конфликты в конвейере команд

Классификация операционных устройств с магистральной структурой

Магистральные ОПУ классифицируют по виду и количеству магистралей, организации узла РОН, типу ОПБ.

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

По функциональному назначению выделяют:

- магистрали внешних связей, соединяющих ОПУ с памятью и каналами ввода/вывода ВМ;

- внутренние магистрали ОПУ, отвечающие за связь между узлом РОН и операционным блоком.

Количество магистралей внешних связей зависит от архитектуры конкретной ВМ и обычно не превышает двух для внешних связей и трех – для внутренних.

Структура трехмагистрального ОПУ представлена на рис. 2.7, а, соответствующая ему микропрограмма выполнения операции типа «сложение» – на рис. 2.7, б.

Данный вариант характеризуется наибольшим быстродействием: выборка операндов из РОН, выполнение микрооперации суммирования и запись результата в РОН – все эти действия производятся за один такт.

Основной недостаток трехмагистральной организации – большая площадь, занимаемая магистралями на кристалле БИС (от 0,16 до 0,22 от площади кристалла).

а) б)

Рис. 2.7. Трехмагистральное ОПУ: a – структура; б – микропрограмма сложения

Двухмагистральная организация при меньшей площади, покрываемой магистралями (от 0,06 до 0,19 от площади кристалла), требует введения как минимум одного буферного регистра (БР), предназначенного для временного хранения одного из операндов (рис. 2.8, а), при этом операция сложения будет выполняться уже за два такта (рис. 2.8, б):

- Такт 1: загрузка БР одним из операндов;

- Такт 2: выполнение микрооперации в ОПБ над содержимым БР и одного из РОН; запись результата в РОН.

Наконец, организация ОПУ на основе только одной магистрали (рис. 2.9, а) минимизирует расходы площади (от 0,03 до 0,09 от площади кристалла).

а) б)

Рис. 2.8. Двухмагистральное ОПУ: a – структура; б – микропрограмма сложения

а) б)

Рис. 2.9. Одномагистральное ОПУ: a – структура; б – микропрограмма сложения

В одномагистральном ОПУ, вместе с тем, возникает необходимость введения не менее двух буферных регистров БР1, БР2, и длительность операции возрастает до трех тактов (рис.2.9, б):

- Такт 1: загрузка БР1 одним из операндов;

- Такт 2: загрузка БР2 вторым операндом;

- Такт 3: выполнение микрооперации в ОПБ над содержимым БР1 и БР2 и запись результата в один из РОН.

Количество регистров в узле РОН магистрального ОПУ обычно превышает тот минимум, который необходим для реализации универсальной системы операций. Избыток регистров используется:

- для хранения составных частей адреса (индекса, базы);

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

Количество регистров колеблется в среднем от 8 до 16, иногда может достигать 32 – 64. В процессорах с сокращенным набором команд количество РОН доходит до нескольких сотен.

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

Тип операционного блока (ОПБ) определяется способом обработки данных. Различают ОПБ последовательного и параллельного типа.

В последовательном операционном блоке (рис. 2.10) операции выполняются побитно, разряд за разрядом.

Рис. 2.10. Последовательный операционный блок

Бит переноса, возникающий при обработке i-го разряда операндов, подается на вход ОПБ и учитывается при обработке (r+1)-го разряда операндов. Результат побитно заносится в выходной регистр, предыдущее содержимое которого перед этим сдвигается на один разряд. Таким образом, после n циклов в выходном регистре формируется слово результата, где каждый разряд занимает предназначенную для него позицию.

При параллельной организации операционного блока (рис. 2.11) все разряды операндов обрабатываются одновременно.

Рис. 2.11. Параллельный операционный блок

Реализация эффективной системы переносов в рамках «длинного» слова сопряжена с определенными аппаратурными издержками, поэтому на практике часто используют параллельно-последовательную схему ОПБ. В ней слово разбивается на группы по 2, 4 или 8 разрядов, обработка всех разрядов внутри группы осуществляется параллельно, а сами группы обрабатываются последовательно.

Рис. 2.12. Обобщенная схема операционного блока

Обобщенная схема ОПБ приведена на рис. 2.12. В нее входят: дешифратор микрокоманды ДшМК, формирователи кодов ФК₁ и ФК₂, многофункциональный сумматор См, сдвигатель Сдв и формирователь логических условий (ЛУ).

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

Формирователи кодов ФК₁ и ФК₂ служат для формирования прямых и инверсных кодов операндов, поступающих по магистралям А и В. Они реализуют следующий набор микроопераций:

В₀ФК₁: СмЛ:=0; В₀ФК₂: СмП:=0;

В₁А: СмЛ:=А; В₁В: СмП:=В;

В₁ØА: СмЛ:=ØА; В₁ØВ: СмП:=ØВ.

Многофункциональный сумматор выполняет микрооперации арифметического сложения (с учетом переноса C_IN), сложения по модулю два, логического сложения и логического умножения кодов на левом и правом входах:

Сл: См:=СмЛ+СмП+C_IN;

М2: См:=СмЛÅСмП;

И: См:=СмЛÙСмП;

ИЛИ: См:=СмЛÚСмП.

Формирователь логических условий на основе анализа кода на выходе См вы­рабатывает значения ознакомительных сигналов, передаваемых в УУ машины. Осведомительными сигналами могут быть: признак знака S, признак переполне­ния V, признак нулевого значения результата Z и т. п.

Сдвигатель служит для выполнения микроопераций сдвига кода на выхо­де См:

П₁: С:=См;

R₁: С:=R1(SL·См), SR:=См(n);

L₁: С:=L1(См·SR), SL:=См(0).

Микрооперация П₁ обеспечивает передачу результата на магистраль С без сдвига. По ходу микрооперации R₁ результат сдвигается на один разряд вправо, при этом в освобождающийся старший разряд заносится значение с внешнего контакта SL, а вы двигаемый (младший) разряд сумматора посылается на внешний контакт SR.

В микрооперации L₁ результат сдвигается на один разряд влево. Здесь в освобождающийся младший разряд заносится значение с внешнего контакта SR, а выдвигаемый (старший) разряд См передается на внешний контакт SL.

Совершенствование элементной базы уже не приводит к кардинальному росту производительности ЭВМ. Более перспективными в этом плане представляются архитектурные приемы, среди которых один из наиболее значимых – конвейеризация.

Идея конвейера команд была предложена в 1956 году академиком С.А. Лебедевым. Как известно, цикл команды представляет собой последовательность этапов. Возложив реализацию каждого из них на самостоятельное устройство и последовательно соединив такие устройства, мы получим классическую схему конвейера команд. Для иллюстрации воспользуемся примером. Выделим в цикле команды шесть этапов:

1. Выборка команды(ВК). Чтение очередной команды из памяти и занесение ее в регистр команды.

2. Декодирование команды(ДК). Определение кода операции и способов адресации операндов.

3. Вычисление адресов операндов(ВА). Вычисление исполнительных адресов каждого из операндов в соответствии с указанным в команде способом их адресации.

4. Выборка операндов(ВО). Извлечение операндов из памяти. Эта операция не нужна для операндов, находящихся в регистрах.

5. Исполнение команды(ИК). Исполнение указанной операции.

6. Запись результата(ЗР). Занесение результата в память.

Рис. 2.13. Логика работы конвейера команд

На рис. 2.13 показан конвейер с шестью ступенями, соответствующими шести этапам цикла команды. В диаграмме предполагается, что каждая команда обязательно проходит все шесть ступеней, хотя этот случай не совсем типичен. Так, команда загрузки регистра не требует этапа ЗР. Кроме того, здесь принято, что все этапы могут выполняться одновременно. Без конвейеризации выполнение девяти команд заняло бы единицы времени. Использование конвейера позволяет сократить время обработки до 14 единиц.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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