Лекция 10. Заключение (Лекции (2015)), страница 4

Эти ограничения должны гарантировать, чтооптимизированная программа будет давать такие же результаты,что и исходная.На планирование кода накладывается следующие три типаограничений:Ограничения управления. Все операции, выполняемыев исходной программе, должны выполняться и воптимизированной программе.Ограничения данных. Операции в оптимизированнойпрограмме должны выдать те же результаты, что исоответствующие операции в исходной программеОграничения ресурсов. Планирование кода не должнотребовать чрезмерного количества ресурсов машины.5610.1 Что было рассказано10.1.24 Планирование кодаЗависимости по даннымОпределение. Две команды называются зависимыми поданным, если изменение порядка их выполнения может привестик изменению результата вычислений, выполняемых программой.Виды зависимостей по данным:Истинная зависимость: чтение после записи.Если команда C1 записывает значение в некоторую ячейкупамяти (или на регистр), а команда C2 считывает этозначение, то команды C1 и C2 зависимы.Антизависимость: запись после чтения.Если команда C1 считывает значение из некоторой ячейкипамяти, а команда C2 записывает в эту ячейку новоезначение, то команды C1 и C2 зависимы.Зависимость по выходу: запись после записи.Если команды C1 и C2 записывают значения в одну и туже ячейку памяти, то команды C1 и C2 зависимы.5710.1 Что было рассказано10.1.24 Планирование кодаАлгоритм планирования с помощью списков включает следующиечетыре шага1.2.Переименование значений, чтобы избежатьантизависимостей.Значения переименовываются таким образом, чтобыкаждое значение имело уникальное имя.

Это нужно длятого, чтобы найти и те расписания, которые были быисключены из-за антизависимостей.Построение графа зависимостей D.Базовый блок обходится снизу вверх. Для каждойоперации строится вершина графа, представляющаязначение, вычисленное этой операцией. Построеннаявершина соединяется дугами с вершинами,использующими это значение.5810.1 Что было рассказано10.1.24 Планирование кодаАлгоритм планирования с помощью списков включает следующиечетыре шага3.Присваивание приоритета каждой операции.Планировщик использует эти приоритеты при выбореопераций. Каждая вершина снабжается несколькимиоценками, используемыми планировщиком дляопределения очередной операции, которая должна бытьзапланирована, и для выбора операций, когда основнаяоценка у них одинакова.

Известно несколько различныхсхем назначения приоритетов. Классическая схемаиспользует в качестве основного приоритетапродолжительность вычисления узла с учетом задержек.4.Итеративный процесс выбора вершин ипланирования их.Алгоритм устанавливает счетчик тактов в 1 и пытаетсязапланировать как можно больше операций. Потомувеличивает счетчик тактов и переходит к планированиюследующего такта. И так далее пока все операции не 59будут запланированы.10.1 Что было рассказано10.1.24 Планирование кодаАлгоритм планирования с помощью списковКогда алгоритм должен выбирать из нескольких готовыхопераций, все зависит от качества алгоритма выбора.

Алгоритмвыбирает операцию с наивысшим приоритетом. Если приоритетыравны требуется рассмотреть дополнительные критерии.Операции обмена с памятью часто имеют неопределенные инепостоянные задержки: этому способствуют промахи кэшей ипрочие особенности работы с памятью. Фактическая задержкапри этом может меняться от 0 до нескольких тысяч тактов. Еслипланировщик исходит из наихудшей возможности, он рискуетполучить достаточно длительные простои процессора, если изнаилучшей, он спровоцирует дополнительные промахи кэша.Наиболее привлекательным представляется алгоритмсбалансированного планирования, когда задержка оцениваетсяв процессе планирования в зависимости от контекста (а также,возможно, характеристик целевого процессора).6010.1 Что было рассказано10.1.24 Планирование кодаГлобальное планирование кодаЗависимости по управлениюКоманда s1 зависит по управлению от команды s2, есливыполнение команды s2 определяет, будет ли выполнятьсякоманда s1.Простые примерыв конструкции if(с) s1; else s2;s1 и s2 зависят по управлению от св конструкции while (с) s;s зависит по управлению от c6110.1 Что было рассказано10.1.24 Планирование кодаГлобальное планирование кодаЭквивалентность по управлениюОпределение.

Если базовый блок В является доминаторомбазового блока В', а блок В' - постдоминатором блока В, то блокиВ и В' называются эквивалентными по управлению,что означает, что блок В выполняется тогда и только тогда, когдавыполняется блок В'.Возможны следующие отношения между блоками: Блоки В1 и В4 эквивалентны по управлению:В1 = Dom(В4) & В4 = Postdom(В1) Блок В1 доминирует над блоком В2, а блок В2 непостдоминирует над блоком В1.B2 Блок В2 не доминирует над блоком В4, аблок В4 постдоминирует над блоком В2. Блоки В2 и В3 не связаны ни отношениемдоминирования, ни отношениемпостдоминирования.B1B3B46210.1 Что было рассказано10.1.24 Планирование кодаВзаимодействие с динамическим планировщикомДинамический планировщик – это, как правило, аппаратныйпланировщик OoO-процессораДинамический планировщик обладает тем преимуществом, чтоон может создавать новые планы в зависимости от условийвремени выполнения, и не рассматривать заблаговременно всевозможные планы.Если целевой процессор оснащен динамическим планировщиком(принадлежит классу OoO), основная функция статическогопланировщика состоит в обеспечении ранней выборки командс большими задержками, чтобы динамический планировщик могзапланировать как можно более раннее выполнение этих команд.Это особенно эффективно в том случае, когда в целевомпроцессоре имеются команды предвыборки данных.В частности, предвыборка данных помогает предотвратитьпромахи кэша, представляющие собой класс непредсказуемыхсобытий, которые могут привести к большим разбросам63производительности программы.10.2 Что не было рассказано10.2.1 Машинно-независимая оптимизацияРаспространение констант (не дистрибутивная, а всего лишьмонотонная структура анализа потока данных)Устранение частичной избыточности (взаимодействие четырехструктур анализа потока данных)Ускорение итераций путем объединения базовых блоков в болеекрупные области (наподобие суперблоков)Анализ указателей – пример межпроцедурного анализаКонтекстно-зависимый и трассо-зависимый анализ потока данныхДополнительные оптимизации циклов:раскрутка цикловвыявление и преобразование индуктивных переменныхОткрытая вставка процедур6410.2 Что не было рассказано10.2.2 Машинно-ориентированная оптимизацияКонвейеризация вычислений при планировании кодаВекторизация циклов (при наличии векторных ФУ)Приватизация данных при параллельном выполнении циклов вразличных потоках над общей памятьюМетоды обеспечения локальности данныхАгрессивные методы глобального планирования кода10.2.3 Динамическая оптимизация в JIT-компиляторахСтруктура JIT-компилятора языка JavaРегистровая Java-машина: Dalvik для ОС Android (Google)JIT-компилятор для C/C++ (LLVM)Некоторые методы динамической оптимизации6510.3 Как будет проходить экзамен10.3.1 Выписка из расписания экзаменов42042142342442542742816.0417.0418.0419.04КККККК20.04КККККККК21.0422.0423.0424.0425.0426.04ЧМЧМЧМ27.04ЧМЧМЧМЧМ28.0429.0430.0401.0502.0503.0504.0505.0520191410131217420421423424425427428Конструирование компиляторовЧисленные методыауд 1056610.3 Как будет проходить экзамен1.2.3.Если студент выполнил все четыре домашних задания, онполучает «отлично», не сдавая экзамена.Если студент выполнил любые три домашних задания, онполучает «хорошо», не сдавая экзамена, но может взятьдополнительный вопрос, чтобы получить «отлично».Чтобы получить билет с вопросом, студент должен ответить напредварительные вопросы (от трех до пяти) по определениям(все эти определения сформулированы в заключительнойлекции).3а.Если студент не сможет ответить на предварительныевопросы, он получит оценку «неудовлетворительно» ибудет сдавать экзамен повторно3б.Если студент ответит на предварительные вопросы, онможет отказаться брать билет и получить оценку«удовлетворительно».3в.Если студент ответит на предварительные вопросы, но несможет ответить на вопрос билета, он получит оценку«удовлетворительно».6710.3 Как будет проходить экзаменВопросы к экзамену (билет будет содержать один вопрос)1.

Внутреннее представление программы, применяемое на оптимизирующихфазах.2. Граф потока управления и его построение.3. Локальная оптимизация методом нумерации значений. Ориентированныйациклический граф.4. Глобальная оптимизация с помощью анализа потока данных. Анализдостигающих определений. Построение множеств входных данных для базовыхблоков.5. Глобальная оптимизация с помощью анализа потока данных. Анализ живыхпеременных.

Построение множеств выходных данных для базовых блоков.6. Глобальная оптимизация с помощью анализа потока данных. Анализдоступных выражений.7. Полурешетки и их свойства. Полурешеточная операция (сбор),полурешеточное отношение частичного порядка и его связь с полурешеточнойоперацией. Диаграммы полурешеток.8. Структура потока данных и ее свойства. Монотонные структуры.Дистрибутивные структуры.9. Обобщенный итеративный алгоритм.

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