Практикум «Оптимизирующие компиляторы» (на примере GCC) (1157417), страница 10
Текст из файла (страница 10)
В цикле производятся попыткипостроенияреалистичногорасписаниякоманд.Расписаниедляминимально возможного ИИИ считается окончательным. Обычно этоталгоритм не гарантирует нахождение наилучшего решения.Практикум «оптимизирующие компиляторы»В ряде случаев используются другие алгоритмы, например углубленноеконвейерно-проникающее планирование потока команд [16] – алгоритмEPS (Enhanced Pipeline Scheduling) К.
Эбчоглу [31], оперирующий сациклическим графом базового блока.Алгоритм EPS не похож на алгоритмы программной конвейеризации,основанные на модульном планировании и выделении ядра. Алгоритмиспользуеторигинальныйподходкпрограммнойконвейеризации,основанный на перемещении кода с условием сохранения структуры телацикла [31]. Алгоритм очень похож на схему распараллеливания циклов,применяемую в суперскалярных процессорах. Основным недостаткомэтого алгоритма, ограничивающего его применение в некоторых условиях,являетсяориентированностьнанеограниченныересурсыМПинеограниченный скалярный параллелизм.
Алгоритм EPS состоит из двухэтапов:1)глобальноеперемещениекодаспереименованиемиподстановкой вперёд; 2) конвейеризация тела цикла.1. Глобальное перемещение кода с переименованием и подстановкойвперёд используется для перемещения операции, которая находится послеусловногооператора,вперёдэтогооператорадляукороченияантизависимостей. Переименования превращает операцию x = y op z в двеоперации: x' = y op z; x=x'. Первое присвоение определяет переменную,которая используется только для операции копирования x=x', поэтому еёможно вынести вперёд условного оператора.
Например, код:if (a>0) x=y+z;с помощью этого метода превращается в:x0=y+z;Вынесенныйif (a>0) x=x0;вперёдусловногооператораоператорназываетсяспекулятивно исполняемым – потому что его исполнение необходимотолько в случае истинности условия условного оператора. СпекулятивноеПрактикум «оптимизирующие компиляторы»исполнение широко используется в разных методах оптимизации кода длямикропроцессоров, поддерживающих скалярный параллелизм [40].Для оператора присвоения var=expr подстановкой вперёд называетсяизменение использования var в следующих за присвоением операторах наexpr.
Последнее полезно если в результате подстановки вперёд операторысмогут исполняться параллельно. Обе операции проиллюстрированы наследующем рисунке:m=t*aa'=b+ca=b+ca=a'd=2*am=t*aa'=b+cm=t*aa=a'd'=2*a'd=2*a(a)(b)(c)Рисунок 16. Пример подстановки вперёд и переименования переменных.Нарисунке(а)изображёнграфзависимостейподаннымдопреобразования, на (b) – граф зависимостей после переименования a=b+c,на (c) – после подстановки вперёд a'. Дополнительно подстановка вперёдможет разрушать прямые зависимости, мешающие перемещению кода.Зависимость S1δS2 может быть разрушена подстановкой вперёд, если S1 –операция копирования, или S1 и S2 имеют в качестве операндов константы.Последовательность операторовS1: x = z + 4; S2: y = x + 2; с S1δS2заменяется последовательностьюS1: x = z + 4; S2: y = z + 6;где S1 и S2 могут исполняться параллельно.Приконвейеризациициклаоператорыперемещаютсяпротивдугзависимостей по управлению.
Алгоритм конвейеризации содержит в себедве фазы, которые итеративно повторяются пока операторы ещё имеютвозможность перемещения, или при генерации расписания команд циклаПрактикум «оптимизирующие компиляторы»начинают циклически повторяться инструкции последней генерированнойкоманды. Во время первой фазы операторы тела цикла перемещаютсявперёд на сколько это позволяют зависимости по данным и управлению.Первые инструкции тела цикла, исполняющиеся параллельно, называются«границей» – операторы цикла перемещаются вперёд любым образом, ноне вперёд границы — она ограничивает перемещение кода. Во времядругой фазы инструкции, стоящие «на границе» дублируются иперемещаются. Операторы дублируются при перемещении через верхнюю«границу» цикла, потому что каждый из них имеет двух потомков поуправлению. Операторы, выносящиеся вперёд границы, формируютпролог цикла.
Дублирующие операторы добавляются к этому же телуциклу в конец, и обозначаются как код из следующей итерации. Этоталгоритмиспользуетсяитеративно,покаоператорыбудутиметьвозможность перемещения или процесс генерации расписания инструкцийне зациклится. Например, для алгоритма цифровой фильтрацииfor(i=0;i<N;i++) s+=coef[i]*data[i];после проведения глобальной оптимизации код имеет вид:Выполнить N раз: { s=s+(*coef)*(*data); data++; coef++; }Обозначим операции тела цикла как Snm, где n – номер операции, m –номер итерации, m может не обозначаться, если номер итерации можетбыть любым. Обозначим как операцию S1: *coef; S2: *data; S3:(*coef)*(*data); S4: s+(*coef)*(*data); S5: coef++; S6: data++. Этапыформирования программного конвейера проиллюстрируем с помощьютаблицы, в каждой строке которой помещены операции, исполняющиесяпараллельно.
Строка, выделенная рамкой, обозначает границу. Вышеграницы формируется пролог цикла. Рассмотрим формирование конвейерадля приведённого примера на рисунке ниже:Практикум «оптимизирующие компиляторы»Таблица 6. Схема формирования программного конвейера алгоритмом EPS.Этап 1Этап 2Этап 3КонвейерТакт 1S11 S51 S21 S61S11 S51 S21 S61S11 S51 S21 S61S11 S51 S21 S61Такт 2S31S12 S52 S22 S62 S31S12 S52 S22 S62 S31S12 S52 S22 S62 S3111333321Такт 3S4S4S1 S5 S2 S6 S3 S4S13 S53 S23 S63 S32 S41Такт 4S33 S42Такт 5S43Справа в столбике «конвейер» показан конечный вид цикла, тело циклазатемнено. Выше тела сформирован пролог, ниже – эпилог. Интервалинициации итераций равен 1 (длина цикла в командах), время исполненияитерации составляет 3 такта, экономии времени составляет 200% отначального значения.В случае, если конвейеризируется гнездо циклов, более вложенный циклпредставляетсякакоднакомплекснаякоманда.Далеесучетомзависимостей между итерациями происходит конвейеризация внешнегоцикла.
Естественно, эта операция имеет смысл только в том случае, еслиархитектура процессора имеет достаточно длинное командное слово –необходим резерв скалярного параллелизма для конвейеризации телацикла.Практикум «оптимизирующие компиляторы»Кодогенератор (backend compiler)Кодогенератор является одной из трёх основных частей компилятора, ипоследним принимает участие в генерации объектного кода. На модулекодогенератора лежит ответственность за генерацию (суб)оптимальногокода для данной процессорной архитектуры из оптимизированногомодулем глобальной оптимизации внутреннего представления программы.Особенностью кодогенератора является его зависимость от архитектурыпроцессора и парадигмы генерации кода для него.Структурно, кодогенератор может состоять из нескольких основных идостаточно большого количества дополнительных модулей, необходимыхдля поддержки кодогенерации для конкретного процессора.Перечислим основные модули кодогенератора:1.
модуль выбора инструкций – сопоставляет операторам исходнойпрограммы инструкции физического процессора;2. модуль определения класса регистров – определяет, в каком типерегистров должна обрабатываться переменная;3. модульраспределениярегистров–привязываетфактическиобрабатываемые переменные к физическим регистрам процессора;4. модуль генерации расписания команд – генерирует упорядоченнуюпоследовательностьинструкций процессора для последующеговыполнения.В случае, если компилятор является перенацеливаемым – то есть, способенгенерироватьархитектурыобъектный–коддополнительносогласноимеетсяимеющемусябазаданных,информацию об архитектуре процессора и его системе команд.описаниюсодержащаяПрактикум «оптимизирующие компиляторы»Перед рассмотрением методики генерации кода, рассмотрим краткоописание архитектуры микропроцессора в том виде, в котором оноиспользуется в перенацеливаемых компиляторах.Описание архитектуры микропроцессораМикропроцессор описывается с помощью специального высокоуровневогоязыка описания архитектуры (Architecture Description Language) - ЯОА.Так как стандартов на ЯОА не существует, и каждый разработчикперенацеливаемого компилятора или системы совместной разработкиаппаратного и программного обеспечения обычно имеет свой собственныйЯОА.ЯОА делятся на 3 типа: структурные, бихеовиоральные и смешанные.1.
Структурные ЯОА: описание производится на структурном уровне ввиде устройств (сумматор, и т.д.) и соединений между ними.Примеры языков: MIMOLA (компилятор MSSQ и RECORD), XASM(симулятор BUILDABONG);2. Бихевиоральные ЯОА: описывается функционирование процессора.Обычно бихевиоральное описание состоит из описания ресурсов(регистров, памяти) и возможных преобразований содержимого этихресурсов (фактически система инструкций процессора).
Примерыязыков: nML (IMEC, Cadence скорее для симуляторов, ассемблеров идизассемблеров), ISDL (проект SPAM), FlexWare, LISA, Expression;3. Смешанные ЯОА: имеющие черты как структурного, так ибихевиоральногоЯОА.Примерыархитектура TriMedia), HMDES.языков:PRMDL(Philips,Практикум «оптимизирующие компиляторы»Описание конвейера в GCCДля повышения производительности современные микропроцессорымогут выполнять несколько различных инструкций одновременно, чтодостигается за счет использования нескольких функциональных устройстви конвейеризации исполнения в функциональных устройствах.
Очевидно,что инструкция может быть запущена на исполнение, если выполнены дваусловия: входные данные для инструкции готовы к использованию и естьсвободныефункциональныеустройствадляееисполнения.Следовательно, в процессе исполнения могут возникнуть два типазадержек: задержки по готовности данных (data delay) и задержки позанятости ресурсов (resource delay).В оптимизирующих компиляторах специальный модуль – планировщикинструкций - отвечает за уменьшение задержек по занятости ресурсов иготовностиданных.Этадостигается,восновном,засчетпереупорядочивания инструкций, хотя могут быть использованы и другиеметоды. В состав планировщика инструкций входит важный компонент –распознаватель конфликтов в конвейере (pipeline hazard recognizer),отвечающий за определение возникающих ресурсных задержек.Распознаватель конфликтовВ настоящее время даже в рамках одной архитектуры существуетмножествомодификацийпроцессоров.Становитсяневозможнымнаписание распознавателя конфликтов в конвейере для каждого из них.Ситуация еще более усложняется в перенацеливаемых компиляторах длямножества архитектур и множества конкретных процессоров.
Поэтому всовременный компилятор интегрировано описание модели конвейерацелевогопроцессораконфликтов.и,какправило,генераторраспознавателяПрактикум «оптимизирующие компиляторы»Сначала в GCC распознаватель конфликтов управлялся таблицамизанятости функциональных устройств, сгенерированными с помощьюфайлов описания процессора. Таблицы были самым простым методомописания процессора, но значительно огрубляли описание, и чем болеесложным становилось описание процессора, тем более медленнымстановился распознаватель конфликтов, основанный на использованиитаблиц.
С дальнейшим усложнением описания процессора скоростьработы распознавателя конфликтов стала существенной проблемой.Модель распознавателя конфликтов и описание конвейераМодель конвейера основана на использовании описания всех комбинацийрезервированияфункциональныхинструкциями,срезервированияфактическиустройствпомощьютаблицпредставляет(ФУ),использующихсярезервирования.собойТаблицапоследовательностьзанятий функциональных устройств в дискретные моменты времени,прошедшие со времени начала исполнения инструкции в процессоре –фактически описывается, в какой такт от начала инструкции занимаетсянекоторое функциональное устройство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
