Презентация на тему Оптимизация управляющего графа программ, имеющих избыточные условные вычисления

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

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Оптимизация управляющего графа программ, имеющих избыточные условные вычисления

Выполнил: Степнов Денис, 816 гр.
Научный руководитель: Бучнев А.Ю.

Выпускная квалификационная работа


Слайд 2
Текст слайда:

Общие понятия

Нумерация значений – разбиение множества операций промежуточного представления на классы конгруэнтности (эквивалентности);

Класс конгруэнтности – подмножество операций, безусловно имеющих одинаковый результат;

Гиперблок – непрерывная последовательность инструкций, имеющая одну точку входа;

CTP – операция подготовки передачи управления;

Станок – регистр, необходимый для выполнения операции CTP.


Слайд 3
Текст слайда:

Проблематика

Наличие в программах избыточных условных вычислений, вырабатывающих предикат, который используется для постановки операций под условие;

Наличие безусловно исполняемых и ненужных операций передачи управления;

Потери в производительности, которые могут быть вызваны ограниченным числом станков для подготовок и давлением на кэш инструкций.


Слайд 4
Текст слайда:

Постановка задачи

Реализовать отдельную оптимизацию, устраняющую избыточные вычисления предикатов

Внедрить оптимизацию в оптимизирующий компилятор «Эльбрус»
Определить место в линейке оптимизаций
Провести верификацию на стандартных пакетах тестов
Поддержка оптимизации

Провести оценку эффективности на пакете SPEC


Слайд 5
Текст слайда:

Подход к решению задачи

Поиск избыточных условных вычислений
Используя результаты анализа «Нумерация значений», выявить избыточные условные вычисления;

Применение оптимизации
Дублировать If-узел с избыточным условием по всем входящим в него дугам, по которым оно однозначно определяется, и перенаправить на копии исходящие дуги;
Удалить невыполнимые исходящие дуги из полученных копий If-узла и быть может оригинала (если у него осталась одна входящая дуга по которой условие однозначно определяется), преобразовать If-узлы в Simple-узлы.


Слайд 6
Текст слайда:

Простейший пример

Если в узлах 2, 3, 4 нет операций, изменяющих переменные a или b,
то вычисление предиката в узле 4 является избыточным → нужно
создать копию узла 4 (узел 7) и упростить узлы 4 и 7


Слайд 7
Текст слайда:

Нет

Да

Нет

Да

1. Поиск избыточных условных вычислений

Осуществить обход по всем возможным парам If-узлов рассматриваемой процедуры

Осуществить обход по всем исходящим дугам доминатора и входящим дугам доминируемого узла

Один из узлов доминирует над другим

Преемник исходящей дуги доминирует над предшественником входящей дуги & класс конгруэнтности операций, вырабатывающих предикат, совпадает

Занести доминируемый узел, входящую дугу, значение предиката в специальный список

Алгоритм


Слайд 8
Текст слайда:

В данном примере существует единственная подходящая для рассмотрения пара If-узлов:
If-узел 1 доминирует If-узел 4.
Осуществив обход по дугам, можно выявить две входящие в узел 4 дуги, в предшественниках которых значение предиката точно известно.
Однако оптимизацию возможно применить только по одной из входящих в узел 4 дуг, так как переменная «a» переопределяется в узле 2.

1. Поиск избыточных условных вычислений

Пример


Слайд 9
Текст слайда:

Осуществить обход списка, полученного анализирующим алгоритмом

Нет

Да

В узел входит более одной дуги

Удалить лишнюю исходящую дугу и вычисление предиката

Дублировать узел со всеми исходящими дугами

Удалить у копии лишнюю исходящую дугу и вычисление предиката

Перенаправить на копию дугу, содержащуюся в списке

2. Применение оптимизации

Алгоритм


Слайд 10
Текст слайда:

Создаём узел 7 — копию узла 4. При копировании узла CFG-графа средствами компилятора «Эльбрус» (функция graph_GetNodeCopy), автоматически копируются исходящие из него дуги. Входящие дуги не копируются.

2. Применение оптимизации

Пример


Слайд 11
Текст слайда:

Перенаправляем входящую дугу, по которой значение предиката точно известно, на скопированный узел.

2. Применение оптимизации

Пример


Слайд 12
Текст слайда:

Удаляем дугу, исходящую из узла 7, соответствующую отрицательному значению предиката. Удаляем вычисление предиката и преобразовываем узел 7 из If-узла в Simple-узел.

2. Применение оптимизации

Пример


Слайд 13
Текст слайда:

Оценка эффективности

Ускорение, полученное на пакете тестов spec2000, в среднем составило 0,5%


Слайд 14
Текст слайда:

Результаты исследования

Оптимизация реализована и внедрена в линейку оптимизирующего компилятора «Эльбрус»:
Применение на 3-м уровне оптимизации
Применение перед объединением базовых блоков в гипер-узлы (оптимизация if_conversion)
Проведена верификация на пакетах дневного тестирования при вливе в основную ветку компилятора, а так же на генераторе тестов
Проведена оценка эффективности на пакете тестов spec2000


Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика