Аналитическое предсказание времени исполнения программ и основанные на нем методы оптимизации

• Автор: Макошенко, Денис Валентинович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Новосибирск
• Количество страниц: 122 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. ОЦЕНКА ВРЕМЕНИ ИСПОЛНЕНИЯ ПРОГРАММЫ

1Л. Основные понятия и определения.

1.2. Модель памяти вычислительной системы

1.3. Модель времени вычислений.

Выводы по главе 1

2. РАСКРАСКА ГРАФА НЕСОВМЕСТИМОСТИ

2.1. Задача оптимального распределения физических регистров

2.2. Алгоритм ЧейтинаБриггса раскраски графа несовместимости и его модификация.

2.3. Древовидный алгоритм раскраски графа несовместимости

2.4. Жадный алгоритм раскраски рафа несовместимости.
2.5. Параметрический древовидный алгоритм раскраски графа несовместимости.
2.6. Особенности реализации и оценка сложности параметрического алгоритма раскраски
Выводы по главе 2
3. ПОНИЖЕНИЕ ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА НЕСОМЕСТИМОСТИ С ПОМОЩЬЮ РЕГИСТРОВЫХ СБРОСОВ
3.1. Частичный сброс виртуального регистра и его свойства
3.2. Условие распределения физических регистров
3.3. Достаточное условие распределения регистров.
3.4. Дерево вариантов всех комбинаций частичных сбросов для линейного участка.
3.5. Выбор оптимальной комбинации частичных сбросов с помощью дерева вариантов
3.6. Параметрический алгоритм нахождения оптимальной комбинации частичных сбросов
Выводы по главе 3
4. ВЫБОР КОМБИНАЦИИ ПРЕОБРАЗОВАНИЙ ДЛЯ МИНИМИЗАЦИИ ВРЕМЕНИ ИСПОЛНЕНИЯ ПРОГРАММЫ
4.1. Проблема выбора комбинации преобразований.
4.2. Граф зависимостей возможных преобразований
4.3. Дерево перебора всех возможных комбинаций элементарных преобразований
4.4. Выбор оптимальной комбинации преобразований.
4.5. Параметрический алгоритм минимизации времени исполнения цикла программы.
Выводы по главе 4.
5. РАСПАРАЛЛЕЛИВАНИЕ ПАРАМЕТРИЧЕСКИХ АЛГОРИТМОВ ДЛЯ СОКРАЩЕНИЯ ВРЕМЕНИ КОМПИЛЯЦИИ
5.1. Оценка целесообразности распараллеливания обхода поддеревьев из семейств Тс0, ТД1Д2 и Та0
5.2. Анализ распараллеливаемое построения поддеревьев из семейств Тс0.
5.3. Анализ распараллеливаемое построения поддеревьев из семейств Т, Э2
5.4. Анализ распараллеливаемое построения поддеревьев из семейств ТаЫ.
Выводы по главе 5.
ЗАКЛЮЧЕНИЕ
Литература


В диссертационной работе использовались различные методы и математические инструменты, такие как: теория графов, теория алгоритмов, элементы теории множеств, теория преобразования и оптимизации программ и др. Древовидный параметрический алгоритм раскраски графа несовместимости процедуры для оптимизации быстродействия кода в рамках лимита времени компиляции. Древовидный параметрический алгоритм выбора оптимального множества сбросов для понижения хроматического числа 1рафа несовместимости линейного участка для оптимизации быстродействия кода в рамках лимита времени компиляции. Древовидный параметрический алгоритм выбора оптимальной комбинации преобразований линейного участка для оптимизации быстродействия кода в рамках лимита времени компиляции. Предложены новые алгоритмы, позволяющие оптимальнее использовать иерархию памяти путем более эффективного распределения регистров. Построена графовая модель программы, описывающая зависимости между возможными преобразованиями. В частности, алгоритмы распределения регистров и выбора оптимальной комбинации преобразований имеют параметр, позволяющий минимизировать время исполнения программы, не превышая лимита времени компиляции. Результаты диссертации могут быть использованы при разработке оптимизирующих компиляторов нового поколения, которые предоставят программисту возможность делать выбор между качеством оптимизации программы и временем, затрачиваемым на оптимизацию. Также предложенные методы оптимизации являются хорошо распараллеливаемыми, что позволяет значительно сократить время оптимизации программы за счет использования современных многоядерных архитектур. Результаты диссертации внедрены в официальный курс лекций "Оптимизирующие компиляторы" и используются при обучении студентов кафедры микропроцессорных технологий факультета РТК Московского физико-техническо1Т> институ та современным методам программирования и оптимизации для различных вычислительных архитектур. Интеллектуальные и многопроцессорные системы ИМС-, Международная научно-техническая конференция, Дивноморское, Россия, - сентября . IEEE EAST-WEST DESIGN & TEST SYMPOSIUM MOSCOW, RUSSIA, September -, . Современные проблемы фундаментальных и прикладных наук, -я научная конференция МФТИ, Долгопрудный, - ноября, . Автоматическое распараллеливание программ», семинар кафедры алгебры и дискретной математики мехмата Южного федерального университета, сентября . Основные результаты диссертации опубликованы в семи работах, среди них четыре статьи, из которых две опубликованы в журналах перечня ВАК [], [], одна - в зарубежном журнале [8], одна - в сборнике научных трудов [] и три публикации - в сборниках тезисов докладов конференций [9], [0], []. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации - 2 стр. Список литературы содержит 9 наименований. Во введении обоснована актуальность проводимых исследований, сформулирована цель диссертационной работы, показана новизна и практическая значимость результатов, указаны положения, выносимые на защиту, и кратко аннотировано содержание глав. В главе 1 рассматривается задача аппроксимации времени исполнения программы. Дан обзор существующих методов, указаны их преимущества и недостатки. Вводятся модель памяти вычислительной системы, модель программы и модель времени вычислений. Показывается, что эти три модели являются аппаратом, необходимым для решения задачи аппроксимации времени выполнения программы во время ее компиляции. В разделе 1. В разделе 1. Раздел 1. Обсуждаются достоинства и недостатки предложенного метода. В главе 2 рассматривается задача раскраски графа несовместимости, которая возникает на первом шаге процесса распределения регистров. Предложен обзор существующих методов для решения этой задачи. В разделе 2. Раздел 2. Чейтином и развитые Бриггсом и другими. Раздел 2. В разделе 2. В разделе 2. Раздел 2. Глава 3 посвящена новым алгоритмам, понижающим хроматическое число графа, использующегося для назначения переменных на физические регистры. Раздел 3.