Научный руководитель: Бучнев А.Ю.
Выпускная квалификационная работа
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Оптимизация управляющего графа программ, имеющих избыточные условные вычисления презентация
Содержание
- 1. Оптимизация управляющего графа программ, имеющих избыточные условные вычисления
- 2. Общие понятия Нумерация значений – разбиение множества
- 3. Проблематика Наличие в программах избыточных условных вычислений,
- 4. Постановка задачи Реализовать отдельную оптимизацию, устраняющую избыточные
- 5. Подход к решению задачи Поиск избыточных условных
- 6. Простейший пример Если в узлах 2, 3,
- 7. Нет Да Нет Да 1. Поиск избыточных
- 8. В данном примере существует единственная подходящая для
- 9. Осуществить обход списка, полученного анализирующим алгоритмом Нет
- 10. Создаём узел 7 — копию узла 4.
- 11. Перенаправляем входящую дугу, по которой значение предиката
- 12. Удаляем дугу, исходящую из узла 7, соответствующую
- 13. Оценка эффективности Ускорение, полученное на пакете тестов spec2000, в среднем составило 0,5%
- 14. Результаты исследования Оптимизация реализована и внедрена в
Общие понятия Нумерация значений – разбиение множества операций промежуточного представления на классы конгруэнтности (эквивалентности); Класс конгруэнтности – подмножество операций, безусловно имеющих одинаковый результат; Гиперблок – непрерывная последовательность инструкций, имеющая
Слайд 1Оптимизация управляющего графа программ, имеющих избыточные условные вычисления
Выполнил: Степнов Денис, 816
гр.
Научный руководитель: Бучнев А.Ю.
Научный руководитель: Бучнев А.Ю.
Слайд 2Общие понятия
Нумерация значений – разбиение множества операций промежуточного представления на классы
конгруэнтности (эквивалентности);
Класс конгруэнтности – подмножество операций, безусловно имеющих одинаковый результат;
Гиперблок – непрерывная последовательность инструкций, имеющая одну точку входа;
CTP – операция подготовки передачи управления;
Станок – регистр, необходимый для выполнения операции CTP.
Класс конгруэнтности – подмножество операций, безусловно имеющих одинаковый результат;
Гиперблок – непрерывная последовательность инструкций, имеющая одну точку входа;
CTP – операция подготовки передачи управления;
Станок – регистр, необходимый для выполнения операции CTP.
Слайд 3Проблематика
Наличие в программах избыточных условных вычислений, вырабатывающих предикат, который используется для
постановки операций под условие;
Наличие безусловно исполняемых и ненужных операций передачи управления;
Потери в производительности, которые могут быть вызваны ограниченным числом станков для подготовок и давлением на кэш инструкций.
Наличие безусловно исполняемых и ненужных операций передачи управления;
Потери в производительности, которые могут быть вызваны ограниченным числом станков для подготовок и давлением на кэш инструкций.
Слайд 4Постановка задачи
Реализовать отдельную оптимизацию, устраняющую избыточные вычисления предикатов
Внедрить оптимизацию в оптимизирующий
компилятор «Эльбрус»
Определить место в линейке оптимизаций
Провести верификацию на стандартных пакетах тестов
Поддержка оптимизации
Провести оценку эффективности на пакете SPEC
Определить место в линейке оптимизаций
Провести верификацию на стандартных пакетах тестов
Поддержка оптимизации
Провести оценку эффективности на пакете SPEC
Слайд 5Подход к решению задачи
Поиск избыточных условных вычислений
Используя результаты анализа «Нумерация значений»,
выявить избыточные условные вычисления;
Применение оптимизации
Дублировать If-узел с избыточным условием по всем входящим в него дугам, по которым оно однозначно определяется, и перенаправить на копии исходящие дуги;
Удалить невыполнимые исходящие дуги из полученных копий If-узла и быть может оригинала (если у него осталась одна входящая дуга по которой условие однозначно определяется), преобразовать If-узлы в Simple-узлы.
Применение оптимизации
Дублировать If-узел с избыточным условием по всем входящим в него дугам, по которым оно однозначно определяется, и перенаправить на копии исходящие дуги;
Удалить невыполнимые исходящие дуги из полученных копий If-узла и быть может оригинала (если у него осталась одна входящая дуга по которой условие однозначно определяется), преобразовать If-узлы в Simple-узлы.
Слайд 6Простейший пример
Если в узлах 2, 3, 4 нет операций, изменяющих переменные
a или b,
то вычисление предиката в узле 4 является избыточным → нужно
создать копию узла 4 (узел 7) и упростить узлы 4 и 7
то вычисление предиката в узле 4 является избыточным → нужно
создать копию узла 4 (узел 7) и упростить узлы 4 и 7
Слайд 7Нет
Да
Нет
Да
1. Поиск избыточных условных вычислений
Осуществить обход по всем возможным парам If-узлов
рассматриваемой процедуры
Осуществить обход по всем исходящим дугам доминатора и входящим дугам доминируемого узла
Один из узлов доминирует над другим
Преемник исходящей дуги доминирует над предшественником входящей дуги & класс конгруэнтности операций, вырабатывающих предикат, совпадает
Занести доминируемый узел, входящую дугу, значение предиката в специальный список
Алгоритм
Слайд 8В данном примере существует единственная подходящая для рассмотрения пара If-узлов:
If-узел 1
доминирует If-узел 4.
Осуществив обход по дугам, можно выявить две входящие в узел 4 дуги, в предшественниках которых значение предиката точно известно.
Однако оптимизацию возможно применить только по одной из входящих в узел 4 дуг, так как переменная «a» переопределяется в узле 2.
Осуществив обход по дугам, можно выявить две входящие в узел 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
Применение перед объединением базовых блоков в гипер-узлы (оптимизация if_conversion)
Проведена верификация на пакетах дневного тестирования при вливе в основную ветку компилятора, а так же на генераторе тестов
Проведена оценка эффективности на пакете тестов spec2000
