Тема 7_2010 Конвейерная организация. Конфликты (Лекции (ещё одни)), страница 4

11. Приостановка конвейера при выполнении команды условного переходаНапример, если конвейер будет приостановлен на три такта на каждойкоманде условного перехода, то это может существенно отразиться напроизводительности машины. При частоте команд условного перехода впрограммах, равной 30% и идеальном CPI, равным 1, машина с приостановкамиусловных переходов достигает примерно только половины ускорения, получаемогоза счет конвейерной организации. Таким образом, снижение потерь от условныхпереходов становится критическим вопросом.Число тактов, теряемых при приостановках из-за условных переходов, можетбыть уменьшено двумя способами:1.

Обнаружением является ли условный переход выполняемым илиневыполняемым на более ранних ступенях конвейера.2. Более ранним вычислением значения счетчика команд длявыполняемого перехода (т.е. вычислением целевого адреса перехода).Реализация этих условий требует модернизации исходной схемы конвейера,приведенного на рис.11.

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

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

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

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

Поведение конвейеравыглядит так, как будто ничего необычного не происходит. Однако если условныйпереход на самом деле выполняется, то необходимо просто очистить конвейер откоманд, выбранных вслед за командой условного перехода и заново повторитьвыборку команд (рис. 12).Невыполняемый условный переход IF ID EX MEM WBКоманда i+1IF ID EX MEM WBКоманда i+2IF IDКоманда i+3IFКоманда i+4EX MEM WBIDIF IDВыполняемый условный переходКоманда i+1EX MEM WBEX MEM WBIF ID EX MEM WBIF ID EX MEM WBКоманда i+2stall IFIDКоманда i+3Stall IFКоманда i+4stallEX MEM WBID EXMEM WBIFEX MEMIDРис. 12. Диаграмма работы модернизированного конвейераАльтернативная схема прогнозирует переход как выполняемый.Как только команда условного перехода декодирована и вычислен целевойадрес перехода, предполагаем, что переход выполняемый, и осуществляем выборкукоманд и их выполнение, начиная с целевого адреса.

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

В задержанном переходе такт выполнения сзадержкой перехода длиною n есть:Команды c 1 по n находятся в слотах (временных интервалах) задержанногоперехода. Задача программного обеспечения заключается в том, чтобы сделатькоманды, следующие за командой перехода, действительными и полезными.Аппаратура гарантирует реальное выполнение этих команд перед выполнениемсобственно перехода. Здесь используются несколько приемов оптимизации.На рис. 13,а показаны три случая, при которых может планироватьсязадержанный переход.

В верхней части рисунка для каждого случая показанаисходная последовательность команд, а в нижней части - последовательностькоманд, полученная в результате планирования. В случае (а) слот задержкизаполняется независимой командой, находящейся перед командой условногоперехода. Это наилучший выбор. Стратегии (b) и (c) используются, еслиприменение стратегии (a) невозможно.Рис. 13,а. Требования к переставляемым командам при планированиизадержанного переходаВ последовательностях команд для случаев (b) и (c) использованиесодержимого регистра R1 в качестве условия перехода препятствует перемещениюкоманды ADD (которая записывает результат в регистр R1) за команду перехода. Вслучае (b) слот задержки заполняется командой, находящейся по целевому адресукоманды перехода.

Обычно такую команду приходится копировать, поскольку кней возможны обращения и из других частей программы. Стратегии (b) отдаетсяпредпочтение, когда с высокой вероятностью переход является выполняемым,например, если это переход на начало цикла.Наконец, слот задержки может заполняться командой, находящейся междукомандой невыполняемого перехода и командой, находящейся по целевому адресу,как в случае (c). Чтобы подобная оптимизация была законной, необходимо, чтобыможно было все-таки выполнить команду SUB, если переход пойдет не попрогнозируемому направлению. При этом предполагаем, что команда SUBвыполнит ненужную работу, но вся программа при этом будет выполнятьсякорректно. Это, например, может быть в случае, если регистр R4 используетсятолько для временного хранения промежуточных результатов вычислений, когдапереход выполняется не по прогнозируемому направлению.В таблице на рис.

13,б указываются различные ограничения для всехприведенных выше схем планирования условных переходов, а также ситуации, вкоторых они дают выигрыш. Компилятор должен соблюдать требования приподборе подходящей команды для заполнения слота задержки. Если такойкоманды не находится, слот задержки должен заполняться пустой операцией.РассматриваемыйслучайКогда увеличиваетсяпроизводительностьТребования(a)Команда условного перехода недолжна зависеть отпереставляемой командыВсегда(b)Выполнение переставляемойкоманды должно бытькорректным, даже если переходне выполняетсяМожет потребоватьсякопирование командыКогда переход выполняется.

Можетувеличивать размер программы вслучае копирования команды(c)Выполнение переставляемойкоманды должно бытькорректным, даже если переходвыполняетсяКогда переход не выполняетсяРис.13, бПланирование задержанных переходов осложняется:1. наличием ограничений на команды, размещение которых планируется вслотах задержки и2. необходимостью предсказывать во время компиляции, будет ли условныйпереход выполняемым или нет.Имеются небольшие дополнительные затраты аппаратуры на реализациюзадержанных переходов. Из-за задержанного эффекта условных переходов, длякорректного восстановления состояния в случае появления прерывания нужнынесколько счетчиков команд (один плюс длина задержки).7.

Проблемы реализации точного прерывания в конвейереОбработка прерываний в конвейерной машине оказывается более сложнойиз-за того, что совмещенное выполнение команд затрудняет определениевозможности безопасного изменения состояния машины произвольной командой.В конвейерной машине команда выполняется по этапам, и ее завершениеосуществляется через несколько тактов после выдачи для выполнения. Еще впроцессе выполнения отдельных этапов команда может изменить состояниемашины. Тем временем возникшее прерывание может вынудить машину прерватьвыполнение еще не завершенных команд.Как и в не конвейерных машинах двумя основными проблемами приреализации прерываний являются:(1) прерывания, которые возникают в процессе выполнения некоторой команды;(2) механизм возврата из прерывания для продолжения выполнения программы.Например, для нашего простейшего конвейера прерывание по отсутствиюстраницы виртуальной памяти при выборке данных не может произойти до этапавыборки из памяти (MEM).

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