Диссертация на тему "Развитие методов статического анализа программ, используемых в оптимизирующих компиляторах для архитектур с явно выраженной параллельностью", скачать бесплатно автореферат по специальности 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Введение

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 рассматриваются вопросы внутрипроцедурного статического анализа потока данных с учетом предикатных выражений. Рассматривается предикатная форма статического единственного присваивания и предлагается оригинальный алгоритм перевода программы в предикатную форму, основанный на использовании предикатной формы статического единственного присваивания. Заключительная часть этой главы посвящена статическому анализу предикатных выражений, выполняемому на предикатном представлении программы. Предлагается метод, расширяющий применимость этого вида анализа на случай произвольного региона. Этот метод позволяет включить в рассмотрение поток данных, входящих в регион через фузлы.

Название работы	Автор	Дата защиты
Развитие алгоритмов и кодов для расчета транспорта частиц в задачах моделирования переноса излучения	Таланов, Вадим Вадимович	2002
Основы построения программного обеспечения виртуальных тренажеров железнодорожных и автомобильных весов	Круг, Петр Германович	2006
Интерактивный синтез реалистичных изображений больших 3D сцен с применением графических процессоров	Гаранжа, Кирилл Владимирович	2014

Электронная библиотека диссертаций

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