Развитие методов статического анализа программ, используемых в оптимизирующих компиляторах для архитектур с явно выраженной параллельностью
- Автор:
Дроздов, Александр Юльевич
- Шифр специальности:
05.13.11
- Научная степень:
Кандидатская
- Год защиты:
2004
- Место защиты:
Москва
- Количество страниц:
108 с.
Стоимость:
700 р.250 руб.
до окончания действия скидки
00
00
00
00
+
Наш сайт выгодно отличается тем что при покупке, кроме PDF версии Вы в подарок получаете работу преобразованную в WORD - документ и это предоставляет качественно другие возможности при работе с документом
Страницы оглавления работы
Введение
1. Методы статического анализа программ
1.1. Основные понятия и определения
1.2. Анализ потока управления
1.2.1. Предикаты и анализ потока управления
1.2.2. Факторизация потока управления
1.2.3. Межпроцедурный анализ потока управления
1.3. Анализ потока данных
1.3.1. Внутри процедурный анализ потока данных
1.3.2. Межпроцедурный анализ потока данных
1.4. Анализ зависимостей в гнездах циклов
1.5. Использование результатов анализа потока данных и потока управления для вычисления отношения зависимости
1.6. Способы представления информации о зависимостях в оптимизирующих компиляторах
1.7. Применение результатов анализа в оптимизациях
1.8. Аппаратные и программные методы ослабления зависимостей
1.9. Постановка задачи
1 Выводы .
2. Внутрппроцедурный анализ потока данных без учета предикатных вычислений
2.1. Эффективный алгоритм построения формы статического единственного присваивания
2.1.1. Алгоритмы построения ффункций
2.1.2. Решение задачи построения ффункций для множества переменных
2.1.3. Групповое построение ффункций в контексте линейного алгоритма
2.1.4. Доказательство корректности и оценка сложности модифицированного алгоритма
2.1.5. Экспериментальные результаты
2.2. Дерево значений новая структура данных, объединяющая информацию о потоке управления и доминировании
2.2.1. Дерево значений
2.2.2. Алгоритм построения дерева значений
2.2.3. Доказательство корректности
2.2.4. Оценка сложности
2.2.5. Результаты тестирования
2.2.6. Оптимизации, использующие дерево значений
2.3. Выводы
3. Внутрнпроцедурный анализ потока данных с учетом предикатных начислений
3.1. Предикатная форма статического единственного присваивания
3.1.1. Описание пути в программе
3.2. Эффективный алгоритм преобразования потока управления в поток данных на основе предикатной формы статического единственного присваивания
3.2.1. Преобразование уфункции в предикатное выражение
3.2.2. Построение предикатного выражения
3.2.3. Хеширование предикатного выражения
3.2.4. Предикатное выражения произвольного пути
3.2.5. Пример работы алгоритма
3.3. Анализ предикатных выражений и его использования для проведения оптимизаций .
3.3.1. Алгоритмы анализа предикатов
3.3.2. Распространение анализа предикатов за пределы ациклических
регионов
3.3.3. Использование результатов анализа предикатов в оптимизирующих компиляторах
3.4. Выводы. .
4. Анализ зависимостей в цикловых регионах программы
4.1. Основные определения .
4.2. Поиск гнезд циклов, для которых возможен анализ
4.3. Поиск индуктивных переменных .
4.4. Поиск инвариантов гнезда циклов
4.5. Сохранение информации об измерениях
4.6. Подготовка данных гнезда циклов. . .
4.7. Подготовка данных для анализа на зависимость двух операций обращения к массиву в цикле . . . .
4.8. Вызов драйвера алгоритма анализа зависимостей .
4.9.Подготовка данных к вызову алгоритма анализа зависимостей
4 Особенности алгоритма анализа зависимостей
4 Минимальное расстояние зависимости .
4 Интерпретация и использование результатов анализа в целях оптимизации
4 Экспериментальные результаты .
4 Выводы .
5. Межироцедурнын анализ потока данных .
5.1. Промежуточное представление
5.2. Пространство имен
5.3. Частичная трансферная функция . .
5.4. Анализ внутри процедуры
5.5. Межпроцсдурный анализ .
5.6. Распространение констант, диапазонов значений переменных и выравниваний объектов
5.7. Межпроцедурный анализ методом нумерации значений
5.8. Экспериментальные результаты
5.9. Выводы
Заключение
Список литературы
Для проведения замеров использовался инструментальный комплекс в составе
оптимизирующего компилятора и потактной модели архитектуры ЭльбрусЗМ. Замеры производились на пакетах задач и 7, 8. Практическая ценность результатов работы состоит в том, что на основе предложенных в работе методов была разработана аналитическая часть промышленного оптимизирующего компилятора для архитектуры Эльбрус3VI . Все разработанные алгоритмы реализованы в составе оптимизирующего компилятора для архитектуры ЭльбрусЗМ. Выявились дальнейшие направления исследований в области развития методов статического анализа программ и их использования в целях оптимизации. Результаты работы докладывались на IX СанктПетербургской Международной конференции Региональная информатика РИ в г. Международной молодежной научной конференции XXX Гагаринские чтения Москва, г. XXI Научнотехнической конференции войсковой части 5 Москва, вч 5, г. ЗАО МЦСТ и Института Микропроцессорных вычислительных систем РАН. Дроздов АЛО. Методы анализа программ, предлагаемые для использования в современных оптимизирующих компиляторах Тезисы докладов XXI научнотехнической конференции войсковой части 5. М., вч 5, . Боханко , Дроздов АЛО. Оптимизация Расширенное удаление излишних операций чтения из памяти Тезисы докладов Международной молодежной научной конференции XXX Гагаринские пения, т. М. МАТИ, . Боханко , Дроздов АЛО. Региональная Информатика. Тезисы докладов. СПб. СПИИ РАН, . Дроздов Л. Ю., Владиславлев В. Е. Эффективный алгоритм межпроцедурного анализа указателей IX СанктПетербургская Международная конференция Региональная Информатика. Тезисы докладов. СПб. СПИИ РАН, . Дроздов Л. Ю., Новиков С. В. Улучшение алгоритмов построения формы статического единственного присваивания IX СанктПетербургская Международная конференция Региональная Информатика. Тезисы докладов. СПб. СПИИ РАН, . Боханко Л. С., Дроздов Л. Ю., Корпев Анализ зависимостей по данным в цикловых регионах программы Компьютеры в учебном процессе, 8, г. Дроздов Л. Ю., Новинский Е. В. Технология использования векторных операций для получения оптимального кода Компьютеры в учебном процессе, 9, . Дроздов Л. Ю., Стеианенков Л. М. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры Компьютеры в учебном процессе, ,. Диссертация состоит из введения, пяти глав, и заключения. Диссертация содержт 8 страниц, рисунков, 6 таблиц. Список литературы насчитывает наименования. Глава 1 содержит краткий обзор существующих методов статического анализа программ, определяются направления для исследования, производится постановка задачи, решению которой посвящена данная диссертационная работа. Глава 2 посвящена вопросам статического внугрипроцедурного анализа программы без учета потока предикатов. В этой главе описывается алгоритм группового для множества переменных, построения формы статического единственного присваивания, дается оценка его сложности и приводятся результаты экспериментов, которые доказывают его эффективность. Далее в этой главе рассматривается новая структура данных дерево значений, позволяющая объединить в единое целое информацию о потоке данных и доминировании. Дается оценка сложности алгоритма построения дерева значений, приводятся результаты экспериментов по замеру памяти, требующейся для его построения. Приводятся примеры оптимизаций, которые реализуются на основе использования этой структуры данных. В Главе 3 рассматриваются вопросы внутрипроцедурного статического анализа потока данных с учетом предикатных выражений. Рассматривается предикатная форма статического единственного присваивания и предлагается оригинальный алгоритм перевода программы в предикатную форму, основанный на использовании предикатной формы статического единственного присваивания. Заключительная часть этой главы посвящена статическому анализу предикатных выражений, выполняемому на предикатном представлении программы. Предлагается метод, расширяющий применимость этого вида анализа на случай произвольного региона. Этот метод позволяет включить в рассмотрение поток данных, входящих в регион через фузлы.
Рекомендуемые диссертации данного раздела
| Название работы | Автор | Дата защиты |
|---|---|---|
| Методы создания и эквивалентных преобразований параллельных программ с учетом информационных зависимостей | Шичкина, Юлия Александровна | 2014 |
| Методы и средства отображения параллельных алгоритмов задач в многопроцессорную вычислительную систему со структурно-процедурной реализацией вычислений | Сластен, Любовь Михайловна | 2005 |
| Исследование и разработка методов декомпиляции программ | Трошина, Екатерина Николаевна | 2009 |