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

9. Конвейерное выполнение оператора А = В + СОчевидно, выполнение команды ADD должно быть приостановлено до техпор, пока не станет доступным поступающий из памяти операнд C.Дополнительной задержки выполнения команды SW не произойдет в случаеприменения цепей обхода для пересылки результата операции АЛУнепосредственно в регистр данных памяти для последующей записи.Для данного простого примера компилятор никак не может улучшитьситуацию, однако в ряде более общих случаев он может реорганизоватьпоследовательность команд так, чтобы избежать приостановок конвейера.

Этатехника, называемая планированием загрузки конвейера (pipeline scheduling) илипланированием потока команд (instruction scheduling), использовалась начиная с60-х годов и стала особой областью интереса в 80-х годах, когда конвейерныемашины получили наибольшее распространение.Пусть, например, имеется последовательность операторов: a = b + c; d = e - f;Как сгенерировать код, не вызывающий остановок конвейера?Предполагается, что задержка загрузки из памяти составляет один такт. Можносгенерировать следующую последовательность команд: (рис.

10):Неоптимизированнаяпоследовательность командОптимизированнаяпоследовательность командLW Rb,bLW Rb,bLW Rc,cLW Rc,cADD Ra,Rb,RcLW Re,eSW a,RaADD Ra,Rb,RcLW Re,eLW Rf,fLW Rf,fSW a,RaSUB Rd,Re,RfSUB Rd,Re,RfSW d,RdSW d,RdРис.10. Пример устранения конфликтов компиляторомВ результате устранены обе блокировки: командой LW Rc,c команды ADDRa,Rb,Rc и командой LW Rf,f команды SUB Rd,Re,Rf. Имеется зависимость междуоперацией АЛУ и операцией записи в память, но структура конвейера допускаетпересылку результата с помощью цепей "обхода".

Заметим, что использованиеразных регистров для первого и второго операторов было достаточно важным дляреализации такого правильного планирования. В частности, если переменная eбыла бы загружена в тот же самый регистр, что b или c, такое планирование небыло бы корректным. В общем случае планирование конвейера может требоватьувеличенного количества регистров. Такое увеличение может оказаться особенносущественным для машин, которые могут выдавать на выполнение несколькокоманд в одном такте.Многие современные компиляторы используют технику планированиякоманд для улучшения производительности конвейера.

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

Для простых конвейеров стратегия планирования наоснове базовых блоков вполне удовлетворительна. Однако когда конвейеризациястановится более интенсивной и действительные задержки конвейера растут,требуются более сложные алгоритмы планирования.К счастью, существуют аппаратные методы, позволяющие изменить порядоквыполнения команд программы так, чтобы минимизировать приостановкиконвейера. Эти методы получили общее название методов динамическойоптимизации (в англоязычной литературе в последнее время часто применяютсятакже термины "out-of-order execution" - неупорядоченное выполнение и "out-oforder issue" - неупорядоченная выдача).Основными средствами динамической оптимизации являются:1.

Размещение схемы обнаружения конфликтов в возможно более низкойточке конвейера команд так, чтобы позволить команде продвигаться поконвейеру до тех пор, пока ей реально не потребуется операнд, являющийсятакже результатом логически более ранней, но еще не завершившейсякоманды. Альтернативным подходом является централизованноеобнаружение конфликтов на одной из ранних ступеней конвейера.2. Буферизация команд, ожидающих разрешения конфликта, и выдачапоследующих, логически не связанных команд, в "обход" буфера.

В этомслучае команды могут выдаваться на выполнение не в том порядке, вкотором они расположены в программе, однако аппаратура обнаружения иустранения конфликтов между логически связанными командамиобеспечивает получение результатов в соответствии с заданной программой.3. Oрганизация коммутирующих магистралей, обеспечивающая засылкурезультата операции непосредственно в буфер, хранящий логическизависимую команду, задержанную из-за конфликта, или непосредственно навход функционального устройства до того, как этот результат будет записанв регистровый файл или в память (short-circuiting, data forwarding, databypassing - методы).4.

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

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

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

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

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

рис. 11).Такие приостановки конвейера из-за конфликтов по управлению должныреализовываться иначе, чем приостановки из-за конфликтов по данным, посколькувыборка команды, следующей за командой условного перехода, должна бытьвыполнена как можно быстрее, как только мы узнаем окончательное направлениекоманды условного перехода.Команды переходаСледующая командаСледующая команда +1Следующая команда +2Следующая команда +3IF ID EX MEM WBIF stall stallIFID EXStall stall stall IFMEM WBIDEXMEM WBstall stall stall IFIDEX MEMstall stall stall IFID EXСледующая команда +4stall stall stallIFIDСледующая команда +5Stall stallstallIFРис.