Под оптимизацией понимают последовательность
Существует много различных классификаций оптимизирующих преобразований. Здесь мы рассмотрим классификации по уровню представления программы и по размеру участка экономии.
В зависимости от уровня представления программы различают следующие виды оптимизации:
С точки зрения эффективности наиболее предпочтительной является машинно-зависимая оптимизация, поскольку именно с ее помощью можно учесть особенности конкретной вычислительной среды, однако машинно-зависимый оптимизатор непереносим. С другой стороны, преобразование программы на уровне исходного языка позволяет получить более эффективную программу, допускающую дальнейшее развитие и сопровождение. Наконец, машинно-независимая оптимизация на уровне промежуточного представления является компромиссом между этими двумя крайними случаями.
Другим важным для качества оптимизации соображением является также размер участка экономии, то есть того фрагмента программы, в рамках которого производится оптимизирующее преобразование. Чем больше участок экономии, тем больше информации о
Как правило, эффект оптимизации достигается применением серии разнородных оптимизирующих преобразований. Здесь мы рассмотрим возможные зависимости между ними и их влияние на результаты друг друга.
С одной стороны интуитивно понятно, что конкретное оптимизирующее преобразование применимо не к произвольной программе (например, никакое оптимизирующее преобразование не применимо к оптимальной программе). С другой стороны, последовательность оптимизирующих преобразований, применяемых к программе, можно трактовать как серию изолированных преобразований, применяемых к разным программам (а именно, к исходно программе, к программе после первого преобразования, к программе после второго преобразования и т.д.). Отсюда возникают следующие возможные зависимости между оптимизирующими преобразованиями.
T1 и T2 называются независимыми, если применение одного из них к программе не влияет на применимость другого.T1 повторно по отношению к преобразованию T2 , если для произвольной программы p из применимости к ней T2 следует применимость его к T1 (p) .T1 тупиково по отношению к преобразованию T2 , если для произвольной программы p T2 неприменимо к T1 (p) .
Проведение оптимизирующего преобразования обычно осуществляется в несколько стадий. Рассмотрим каждую из них на конкретном примере.
else. Задачу фрагментации решает анализ потока управления. Заметим, что различные оптимизирующие преобразования требуют выделения различных фрагментов исходной программы, так что количество задач фрагментации достаточно велико. Некоторые алгоритмы фрагментации подробнее рассмотрены в лекции 12.a после первого присваивания фрагмента не используется в случае ложности условия p(x) . Задачи такого рода решаются с применением анализа потоков данных. Примеры задач then -часть условного оператора. Таким образом, в случае ложности условия p(x) программа выполняет на один оператор меньше.
Одним из самых простых видов оптимизаций является так называемая покадровая оптимизация, которая обычно применяется на уровне машинно-зависимого представления программы.
Суть покадровой оптимизации - поиск сравнительно короткой последовательности инструкций, удовлетворяющей определенным контекстным условиям, и замена такой последовательности на более эффективную.
Для реализации этого подхода используют понятие "окна" (или "кадра", frame), которое передвигается по программе. В каждый момент времени содержимое кадра исследуется на предмет соответствия тому или иному образцу и в случае совпадения производится преобразование.
На слайде приведен пример работы покадрового оптимизатора. В данном случае были распознаны следующие образцы:
Результат применения покадровой оптимизации является программа, показанная на слайде справа.
Для описания способов решения задач оптимизации, нам потребуются следующие обозначения.
Ориентированным графом назовем пару конечных множеств (V, E) , называемых соответственно множествами вершин и дуг, при этом множество дуг представляет собой совокупность пар вершин.
Для произвольной дуги e=(v, w) вершину v назовем началом дуги e (обозначение beg(e) ), вершину w - концом дуги e (обозначение end(e) ).
Для произвольной вершины v обозначим через in(v) множество входящих дуг, через out(v) - множество выходящих дуг.
Программу для оптимизации удобно представлять в виде размеченного графа потока управления.
Граф потока управления - это ориентированный граф, в котором выделены две вершины start и stop, и удовлетворяющий следующим требованиям:
start не входит ни одна дуга.stop не выходит ни одна дуга.start .stop .Введем далее в рассмотрение некоторое конечное множество, которое мы будем называть алфавитом операторов $$\Omega$$ и назовем разметкой графа потока управления произвольное отображение $$\sigma$$ множества вершин графа в множество операторов.
Пара $$(G, \sigma)$$, где G - граф потока управления, а $$\sigma$$ - его разметка, и является представлением программы для оптимизации. От дополнительных свойств элементов множества операторов зависит характер оптимизаций, которые можно выразить, используя данное представление.
Заметим, что построение такого представления программы уже включает в себя широко известное оптимизирующее преобразование - удаление недостижимого кода, то есть той части программы, на которую никогда не передается управление.
На слайде приведен пример программы (слева) и ее представления в виде размеченного графа управления (справа). В качестве алфавита операторов выступает множество, состоящее из изображений элементарных операторов данной программы, то есть множество
{'g=a', 'm=b', 'a<b', 'm', 's=g', 'g=m', 'g=b', 'm=a', 'm=s%m'}
Далее мы рассмотрим несколько полезных вариантов определения множества операторов, применимых для формализации основных оптимизирующих преобразований.
Данный способ описания программы применяется тогда, когда необходимо описать преобразования потока управления, которые не требуют
Алфавит операторов в этом случае содержит выделенный пустой оператор ( $$emptyset $$ ). Будем требовать, чтобы разметка графа потока управления сопоставляла пустой оператор только тем вершинам, для которых число исходящих дуг не превосходит единицы. Два слова в алфавите операторов объявляются эквивалентными в том и только том случае, когда они равны с точностью до вхождения пустых операторов.
Для определения p слово w(p) в алфавите операторов получается последовательным выписыванием символов, которыми помечены вершины p .
Будем говорить, что две программы $$(G_1, \sigma_1) $$ и $$(G_2, \sigma_2) $$ эквивалентны, тогда и только тогда, когда существует такое отображение m между вершинами G1 и G2, что для произвольной вершины v графа G1 и произвольного пути p , начинающегося в ней, найдется путь p' в графе G2, начинающийся в вершине m(v) , для которого слова w(p) и w(p') эквивалентны.
На слайде приведен пример преобразования потока управления к форме, эквивалентной в описанном выше смысле (а именно, преобразование m .
Нетрудно заметить, что данное отображение необратимо, и, следовательно, определяемое им отношение несимметрично. Таким образом, введенное нами отношение, строго говоря, не является отношением эквивалентности. Это несоответствие может быть устранено, однако для наших целей этого не потребуется.
Следующей удобной формой представления программ для оптимизации является представление с использованием def-use chains .
Помимо алфавита операторов введем в рассмотрение алфавиты входов I и выходов O и определим для каждого оператора $$\omega$$ множество его входов $$input(\omega)$$ и выходов $$output(\omega)$$. При этом будем требовать, чтобы множества входов и выходов для разных операторов не пересекались.
Рассмотрим теперь отображение DU , которое каждому выходу сопоставляет некоторое подмножество множества входов. Тогда для каждого оператора определяются множества $$def(\omega)$$ и $$use(\omega)$$, которые есть соответственно множества его выходов и множество тех выходов других операторов, образы которых при отображении DU содержат хотя бы один вход оператора $$\omega$$
Неформально говоря, данное представление позволяет отследить потоки данных в программе без учета того, как именно эти данные преобразуются. Множества входов и выходов соответствуют интуитивному представлению об аргументах и результатах операторов, а отображение DU просто описывает, как используются выработанные операторами результаты.
Рассмотрим представление программы, приведенной в разделе "Представление программы", с использованием def-use chains.
Здесь входы операторов обозначены с помощью кружков, расположенных слева он операторов, выходы - с помощью кружков, расположенных справа. Пунктирные стрелки ведут из выходов одних операторов к входам других и обозначают образы при отображении DU.
Построение данного представления опирается на решение одной из задач из области
Далее мы рассмотрим примеры оптимизирующих преобразований и те представления, которые необходимо использовать для их проведения.
Удаление пустого оператора - это одно их наиболее простых и распространенных оптимизирующих преобразований, которое реализуется практически во всех, даже не оптимизирующих, компиляторах. Для его формализации требуется представление программы в виде графа потока управления с пустым оператором.
Данное преобразование заключается в том, что вершина графа, помеченная пустым оператором, удаляется вместе с входящими и исходящими дугами, а в оставшийся граф добавляются дуги, соединяющие предшественников удаленного оператора с его потомком (если он есть). Напомним, что в выбранном нами представлении у вершины графа, помеченной пустым оператором, может быть не более одного потомка.
Несмотря на кажущуюся простоту данного преобразования, им покрывается большое количество частных случаев. В качестве примеров его применения справа на иллюстрации приведены удаление перехода на следующую инструкцию и удаление перехода на переход.
Данное преобразование легко реализуется, если программа представлена с помощью def-use chains. Преобразование заключается в удалении такого оператора, у которого не используются его выходы.
Пример применения такого преобразования приведен на иллюстрации.
Данное преобразование повторно по отношению к самому себе, поскольку удаление одного оператора приводит к тому, что операторы, вырабатывающие для него данные, также могут оказаться неиспользуемыми.
Данное преобразование применяется к сильно связным подграфам графа управления (т.е. подграфам, состоящим из взаимно достижимых вершин). Таким образом, для его проведения необходима фрагментация программы на уровне
Если такой подграф выделен, то для него определяется множество входных вершин, то есть таких его вершин, в которые существует путь из вершины start, лежащий целиком за пределами этого подграфа. На иллюстрации входные вершины подграфа S обозначены темными кружками и символами e1, …, ek .
Чистка цикла вверх заключается в том, что вершина, лежащая в сильно связном подграфе, заменяется на несколько копий вне его, каждая из которых непосредственно предшествует
Легко видеть, что данное преобразование также повторно по отношению к самому себе.
Данное преобразование также легко реализуется в представлении с использованием def-use chains и в каком-то смысле является симметричным предыдущему.
Теперь вершина изнутри сильно связного подграфа заменяется на несколько копий, каждая из которых является непосредственным преемником выходных вершин подграфа. Выходной вершиной называется такая вершина, среди непосредственных преемников которой есть вершина, не принадлежащая данному подграфу.
Легко видеть, что преобразование корректно только в том случае, когда ни одна вершина подграфа не достижима из тех вершин, которые используют результаты оператора, которым помечена выносимая вершина.
Данное преобразование также повторно по отношению к самому себе.
Далее мы перейдем к описанию преобразований, для которых недостаточно рассмотренных выше способов представления программы.
Объединение циклов производится с целью сокращения накладных расходов на организацию цикла.
Контекстные условия корректности этого преобразования следующие:
Заметим, что условие одинаковости переменной циклов не является самым точным. Более правильно было бы сказать, что должно быть осуществимо такое переименование переменных, при котором переменные цикла становятся одинаковыми.
Раскрутка циклов заключается в дублировании тела цикла и сокращении числа итераций. Кроме того, необходимо позаботиться, чтобы все вхождения переменной цикла в тело были заменены выражениями, вычисляющими требуемые значения с учетом измененных значений переменной цикла.
В современных машинных архитектурах используется конвейерный принцип - некоторый участок кода загружается во внутреннюю память процессора заранее в предположении, что его все равно придется исполнять. В ситуации, когда осуществляется переход за границы этой предварительно загруженной области осуществляется так называемый сброс конвейера, что сопровождается существенной временной задержкой. Понятно, что источником таких сбросов являются условные и безусловные переходы, в частности, переходы на начало циклов. Раскрутка предпринимается с целью увеличить протяженность линейных участков для того, чтобы предотвратить сброс конвейера при организации очередной итерации.
Пример этого преобразования приведен на иллюстрации. Как видно, в общем случае помимо раскрученного цикла необходима организация дополнительного цикла, осуществляющего довычисления для остатка итераций.
Данное преобразование особенно эффективно при применении к вычислениям внутри тел циклов, хотя это не является его необходимым контекстным условием.
Основная идея понижения силы операций - это замена (в частных случаях) использования более дорогих операций более дешевыми (умножения - сложением или сдвигом, возведения в степень - умножением и т.д.) Обычно используются следующие тождества:
Два последних тождества и дают возможность применения преобразования к циклам. На иллюстрации приведен пример такого преобразования. В данном случае умножение внутри тела цикла было заменено сложением.
Упрощение выражений представляет собой целый класс оптимизирующих преобразований. Наиболее часто встречающимися среди них являются константные вычисления и упрощения с использованием алгебраических тождеств. Понижение силы операций также может быть рассмотрено как преобразование из серии упрощения выражений.
Пример константных вычислений показан на иллюстрации.
Экономия общих подвыражений заключается в том, что среди всех вычисляемых на участке экономии выражений выделяются эквивалентные, и затем их вхождения заменяются на вхождение новой переменной, хранящей заранее вычисленное значение этого общего выражения.
Поскольку выделение одних подвыражений закрывает возможность выделить другие, данное преобразование является неоднозначным.
На иллюстрации показаны примеры применения этого преобразования. Во втором случае видна неоднозначность при выделении подвыражений: выражения b+c и c+d не могут быть выделены одновременно. Поскольку подвыражение b+c используется чаще, именно оно и было выделено.
Продемонстрируем теперь на примере зависимость качества оптимизации от размера участка экономии.
Фрагмент исходной программы показан в левой части иллюстрации. В правой части изображены возможные остаточные программы при локальной, квазилокальной и глобальной оптимизациях.
При локальной оптимизации произведено только понижение силы операций (умножение заменено на сдвиг).
При квазилокальной оптимизации помимо этого может быть упрощено выражение в then -части условного оператора. Для этого, однако, участок экономии должен включать в себя конструкцию ветвления.
Наконец, при глобальной оптимизации и при соответствующих свойствах функции f (ее значение должно полностью определяться значениями параметров и она не должна иметь побочных эффектов) исходный фрагмент может быть сокращен до вида, указанного на иллюстрации.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.