А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 184
Текст из файла (страница 184)
Можно уменьшить количество используемых регистров, 903 10.5. Программная конвейеризация генерируя менее компактный код. Минимальное количество используемых регистров о, для каждой переменной о достигается при устойчивом состоянии из Т х Г,СМ„о„команд. Здесь Г.СМ„означает наименьшее общее крагнное (1еааг сопппоп тц!йр!е) всех в„, где индекс о пробегает по всем приватизируемым пеРеменным (т.е. нас интеРесУет наименьшее целое число, котоРое кРатно всем йои). К сожалению, наименьшее общее кратное может оказаться достаточно большим даже при малых значениях о„. 10.5.11 Условные инструкции Если доступны предикатные команды, то можно преобразовать команды, зависяшие от управления, в предикатные.
Предикатные команды могут быть программно конвейеризованы так же, как и любые другие операции. Однако если в теле цикла содержится большое количество потока управления, зависящего от данных, то более подходящими могут оказаться методы планирования, описанные в разделе 10.4.
Если машина не оснащена предикатными командами, то для обработки небольших потоков управления, зависящих от данных, можно воспользоваться описываемой ниже концепцией иерархического приведения ()йегагс!йса! гег(цсгюп). (!одобно алгоритму 1О.!1 при иерархическом приведении управляющие конструкции в цикле планируются изнутри наружу, начиная с наиболее глубоко вложенных структур.
При планировании каждая конструкция приводится к единому узлу, представляюгцему все ограничения, накладываемые на планирование ее компонентов со стороны других частей программы. Такой узел затем можно планировать так, как если бы это был простой узел в окружаюшей управляюшей конструкции. Процесс планирования завершается, когда к единственному узлу приводится вся программа. В случае условных инструкций с ветвями "г(геп" и "е!зе" каждая из ветвей планируется независимо.
1. Ограничения всей условной инструкции консервативно рассматриваются как объединение ограничений каждой из ветвей. 2. В качестве использования ресурсов берется максимальное из использований ресурсов в ветвях. 3. Ограничения предшествования представляют собой объединение соответствуюших ограничений в каждой из ветвей, получаемое путем воображаемого выполнения обеих ветвей. Такой узел затем планируется, как и любой другой. Генерируются два множества кода, соответствующие двум ветвям. Любой код, спланированный параллельно 904 Глава !О.
Параллелизм на уровне команд с условной инструкцией, дублируется в обеих ветвях. Если перекрываются множественные условные инструкции, то для каждой комбинации выполняемых параллельно ветвей должен генерироваться отдельный код. 10.5.12 Аппаратная поддержка программной конвейеризации Для минимизации размера программно конвейеризованного кода была предложена специализированная аппаратная поддержка. Примером может служить блок сиен(иющихся регистров (го!айну гея!з1ег 6!е) в архитектуре 1[апппп. В этом блоке имеется базовый регистр (Ьазе герз1ег), который добавляется к номеру регистра, указанному в коде, для получения фактического регистра, к которому выполняется обращение. Различныс итерации цикла могут использовать различные регистры, просто изменяя содержимое базового регистра на границе каждой итерации.
Кроме того, в архитектуре 1[ап(ит имеется мощная поддержка предикатных команд. Предикаты могут использоваться не только для превращения зависимостей управления в зависимости данных, но и для избежания генерации пролога и эпилога. Тело программно конвейеризованного цикла содержит расширенный набор команд, выполняемых в прологе и эпилоге. Мы можем просто генерировать код для устойчивого состояния и использовать предикаты для получения эффекта пролога и эпилога. При том что аппаратная поддержка повышает плотность программно конвейеризованного кода, следует отдавать себе отчет в цене такой поддержки. Поскольку программная конвейеризация — метод, предназначенный для компактных глубоко вложенных циклов, конвейеризованные циклы и так получаются небольшими.
Специализированная поддержка программной конвейеризации обеспечиваем ся, в основном, в машинах, предназначенных для выполнения большого количества программно конвейеризованных циклов и в ситуациях, когда очень важно минимизировать размер кода. 10.5.13 Упражнения к разделу 10.5 Упражнение 10.5.1. В примере 10.20 было показано, как установить относительные границы тактов, на которые планируются узлы б и с.
Вычислите эти границы для каждой из пяти остальных пар узлов 1) для произвольного Т; 2) для Т = 3; 3) для Т = 4. Упражнение 10.5.2. На рис. 10.31 показано тело цикла. Адреса, такие как а ( й9), предназначены для указания ячеек памяти. Здесь а — константа, а В9 — регистр, подсчитывающий итерации в цикле. Можно считать, что разные итерации обращаются к разным ячейкам памяти, поскольку В9 имеет разные значения. Вос- 905 !0.5. Программная конвейеризация пользуйтесь моделью машины из примера 10.12 и спланируйте цикл на рис. 10.31 следующими способами.
а) Оставьте каждую итерацию как можно более компактной (т.е. добавьте по одной команде "нет операции" после каждой арифметической операции) и дважды разверните цикл. Спланируйте вторую итерацию так, чтобы она начиналась как можно в более ранний момент времени без нарушения ограничения, заключающегося в том, что в любой момент времени машина может выполнять одну загрузку, одно сохранение, одну арифметическую операцию и одно ветвление.
б) Повторите предыдущее задание, но с тройной разверткой цикла. Снова начинайте итерации в наиболее ранний момент времени, когда это позволяют сделать машинные ограничения. ! в) Постройте полностью конвейеризованный код с учетом машинных ограничений. В этом задании вы можете при необходимости вводить команды "нет операции", но вы должны каждые два такта начинать новую итерацию. Рис. !0.3!. Машинный код к упражнению !0.5.2 Упражнение 10.5.3. Некоторый цикл требует 5 загрузок, 7 сохранений и 8 арифметических операций.
Чему равен минимальный интервал между запусками итераций при программной конвейеризации этого цикла на машине, которая выполняет каждую операцию за один такт и обладает количеством ресурсов, достаточным для выполнения за один такт а) 3 загрузок, 4 сохранений и 5 арифметических операций; б) 3 загрузок, 3 сохранений и 3 арифметических операций.
1 Упражнение 10.5.4. Используя модель машины из примера 10.12, найдите минимальный интервал между запусками итераций и единый план итераций для следующею цикла: 1) 1: 10 2) ЯТ 3) 1!) 4) А)э!) 5) ЯТ б) ЯОВ 7) ЯТ 8) ВХ Р1, а(В9) Ь(В9), В1 К2, с(В9) КЗ, К1, В2 с(В9), КЗ К4, В1, К2 Ь(В9), В4 В9, 7 906 Глава ! О. Параллелизм на уровне команд йок (х = 1; з < и; з++) ( А[з) = В[з-1) + 1; в[ ) = л['-1) + г; Не забывайте, что подсчет итераций выполняется при помощи автоматического увеличения значения регистра, так что никакие отдельные операции для этого не требуются. 1 Упражнение 10.5.5. Докажите, что в частном случае, когда все операции требуют только по одной единице одного ресурса, алгоритм 10.!9 всегда в состоянии построить оптимальный план, соответствующий нижней границе. 1 Упражнение 10.5.6. Предположим, что у нас есть циклический граф зависимости данных с узлами а, 6„с и и'.
Ребра от а к 6 и от с к д имеют метки (О, 1), а ребра от б к с и от и' к а — метки [1,1). Других ребер в графе нет. а) Изобразите этот циклический граф зависимости данных. б) Вычислите таблицу наидлиннейших простых путей между узлами. в) Найдите длину наидлиннейших простых путей, если интервал между запусками итераций Т равен 2. г) Повторите предыдущее задание для значения Т = 3. д) Каковыми будут ограничения на относительные моменты планирования команд, представленных узлами а, б, с и ~7, в случае Т = 3? 1 Упражнение 10.5.7. Разработайте алгоритм со временем работы О [пз) для поиска длины самого длинного простого пути в графе с и узлами в предположении, что не существует циклов положительной длины. Указание: адаптируйте алгоритм Флойда [Р[оуб) для кратчайших путей [см., например, А.
'Ч. АЬо апд 7. П. Б1!шап, Роипг?анют о~'Сотршег Бс1епсе, Сотрпгег 5с[епсе Ргезз, й[ечг Уог[с, 1992). !! Упражнение 10.5.8. Предположим, что у нас есть машина с тремя типами команд, которые называются А, В и С. Все команды выполняются за один такт, и на каждом такте машина может выполнить по одной команде каждого типа. Предположим, что цикл состоит из шести команд, по две каждого типа. В таком случае можно выполнить цикл путем программной конвейеризации с интервалом между запусками итераций, равным двум. Однако некоторые последовательности шести команд требуют вставки задержки в один такт, а некоторые — в два такта.
Сколько из 90 возможных последовательностей двух А, двух В и двух С не требуют задержек? Сколько требуют одной задержки? Указание: существует симметрия среди трех типов команд, так что две последовательности, которые могут 907 10.6. Резюме к главе 1О быть преобразованы одна в другую путем перестановки имен А, В и С, должны требовать одного и того же количества задержек. Например, последовательность АВВСАС в этом смысле такая же, как и ВССАВА. 10.6 Резюме к главе 10 + Вопросы архитектуры. Оптимизированное планирование кода позволяет использовать возможности современных компьютерных архитектур. Такис машины зачастую допускают конвейерное выполнение, когда одновременно несколько команд находятся на разных стадиях выполнения. Некоторые машины позволяют также одновременно начинать выполнение нескольких команд.
+ Зависимости через данные. При планировании команд мы должны учитывать влияние команд на каждую ячейку памяти и на регистры. Истинные зависимости через данные проявляются, когда одна команда должна читать ячейку памяти после того, как другая запишет в нее информацию. Антизависимость заключается в записи после чтения, а зависимость через выход осуществляется, когда две команды записывают данные в одну и ту же ячейку памяти. + Устранение зависимостей.
Используя дополнительные ячейки для хранения данных, можно устранить антизависимости и зависимости через выход. Не могут быть устранены только истинные зависимости, которые должны учитываться при планировании кода. + Графы зависимости данных для базовых блоков. Такие графы представляют временные ограничения между командами базового блока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
