Аналитическое предсказание времени исполнения программ и основанные на нем методы оптимизации тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Макошенко, Денис Валентинович

• Макошенко, Денис Валентинович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Макошенко, Денис Валентинович

ВВЕДЕНИЕ.

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

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. Оценка целесообразности распараллеливания обхода поддеревьев из семейств ТС(Б), ТД)1,В2) и Та(0).

5.2. Анализ распараллеливаемости построения поддеревьев из семейств Тс(0).

5.3. Анализ распараллеливаемости построения поддеревьев из семейств Т5(01, Б2).

5.4. Анализ распараллеливаемости построения поддеревьев из семейств Та(1Ч).

Выводы по главе 5.

Введение диссертации (часть автореферата) на тему «Аналитическое предсказание времени исполнения программ и основанные на нем методы оптимизации»

Актуальность темы

Современные научные исследования [46], разработка оборонных технологий [34], растущая функциональность мобильных устройств [28] требуют все более высокой производительности программного обеспечения.

Помимо аппаратной составляющей наибольший вклад в повышение производительности дают операционная система [61], [17], [75], [1] и оптимизирующий компилятор [89], [90], [66], [32], [3], [50]. Причем, согласно измерениям, приведенным на www.spec.org [77], компилятор вносит значительно больший вклад в производительность программы, чем операционная система.

Следует отметить, что постоянное повышение производительности вычислительных архитектур, как правило, влечет за собой усложнение этих архитектур и, как следствие, усложнение их эффективного использования. Для эффективного исполнения на конкретной вычислительной архитектуре программа должна быть оптимизирована с учетом особенностей этой архитектуры. Обычно это достигается либо ручной оптимизацией текста программы на ассемблере, либо использованием компилятора с языка высокого уровня, автоматически оптимизирующего программу под выбранную архитектуру. Последний способ более распространен, поскольку он значительно сокращает время разработки программного продукта и не требует от программистов детальных знаний о целевой архитектуре.

Процесс повышения производительности программы компилятором может быть представлен как некая комбинация преобразований, выбранная из заданного набора [6]. Одной из задач построения оптимизирующего компилятора является задача выбора для каждой оптимизируемой программы такой комбинации преобразований из имеющегося набора, чтобы после ее применения результирующая программа наиболее эффективно использовала аппаратные ресурсы архитектуры. Сложность задачи обусловлена двумя факторами:

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

• Преобразования могут зависеть друг от друга: без применения одного преобразования невозможно применение другого; наоборот, применение какого-то преобразования может блокировать применение другого преобразования; наконец, примененные по отдельности, преобразования могут приводить к понижению оптимальности кода, в V то время как их комбинация может улучшать его оптимальность. Пример, иллюстрирующий данную проблему, может быть найден в г

97].

Широко используемые компиляторы, например, gcc [41], MSVS[64], Intel compiler [49], проводят комбинации преобразований, которые жестко подчиняются опциям, специфицированным в командной строке. Для некоторых конкретных оптимизируемых программ такие жестко 1 зафиксированные комбинации преобразований могут привести к неоптимальному коду. Разработчики компиляторов зачастую выбирают некоторый пакет программ, например [77], на котором путем ручного подбора достигается хорошее взаимодействие преобразований.

Различными авторами исследовался метод перебора различных сочетаний параметров командной строки компилятора [29], [39] и машинное обучение [2], [79], которые влияют на выбор проводимых преобразований. Однако, задачу можно считать нерешенной для промышленных компиляторов.

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

Большое подмножество преобразований, проводимых компилятором, решают задачи, которые являются ТчГР-полными [20], [81]. Поэтому, зачастую, при разработке компилятора оптимальные алгоритмы заменяются эвристическими, чтобы сократить время компиляции до приемлемого.

Возможность контролировать эвристики, управляющие качеством преобразований, дает пользователю компилятора свободу в вопросе выбора, что в данный момент является более важным: время компиляции программы или качество проведенной оптимизации. Современные компиляторы дают возможность контролировать набор проводимых преобразований, но не оптимальность каждого конкретного преобразования [42], [82].

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

Цель и задачи работы

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

Целью данной диссертации является повышение эффективности использования системы процессор+память.

Достижение цели связано с решением следующих задач:

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

2. Разработка семейства алгоритмов оптимизации распределения регистров, позволяющих с помощью выбора значения параметра оптимизировать быстродействие кода, не превышая лимита времени компиляции.

3. Разработка семейства алгоритмов выбора оптимальной комбинации преобразований программы, позволяющих с помощью выбора значения параметра оптимизировать быстродействие кода, не превышая лимита времени компиляции.

Методы исследования

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

Результаты выносимые на защиту

Древовидный параметрический алгоритм раскраски графа несовместимости процедуры для оптимизации быстродействия кода в рамках лимита времени компиляции.

Древовидный параметрический алгоритм выбора оптимального множества сбросов для понижения хроматического числа графа несовместимости линейного участка для оптимизации быстродействия кода в рамках лимита времени компиляции.

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

Научная новизна

Предложены новые алгоритмы, позволяющие оптимальнее использовать иерархию памяти путем более эффективного распределения регистров.

Построена графовая модель программы, описывающая зависимости между возможными преобразованиями.

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

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

Практическая ценность

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

Результаты диссертации внедрены в официальный курс лекций "Оптимизирующие компиляторы" и используются при обучении студентов кафедры микропроцессорных технологий факультета РТК Московского физико-технического института современным методам программирования и оптимизации для различных вычислительных архитектур.

Апробация работы

Основные положения диссертации обсуждались на следующих конференциях и семинарах:

1. Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция, Дивноморское, Россия, 22-27 сентября 2003.

2. IEEE EAST-WEST DESIGN & TEST SYMPOSIUM 2009 MOSCOW, RUSSIA, September 18-21, 2009.

3. Современные проблемы фундаментальных и прикладных наук, 52-я научная конференция МФТИ, Долгопрудный, 27-28 ноября, 2009.

4. «Автоматическое распараллеливание программ», семинар кафедры алгебры и дискретной математики мехмата Южного федерального университета, 12 сентября 2005.

Публикации

Основные результаты диссертации опубликованы в семи работах, среди них четыре статьи, из которых две опубликованы в журналах перечня ВАК [97], [98], одна - в зарубежном журнале [108], одна - в сборнике научных трудов [99] и три публикации - в сборниках тезисов докладов конференций [109], [100], [78].

Структура диссертации

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации - 122 стр. Список литературы содержит 109 наименований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Макошенко, Денис Валентинович

ЗАКЛЮЧЕНИЕ