Содержание к диссертации
Введение 4
1. Методы статического анализа программ .. 9
Основные понятия и определения 9
Анализ потока управления 10
Предикаты и анализ потока управления
Факторизация потока управления
Межпроцедурный анализ потока управления
1.3. Анализ потока данных 11
Внутрипроцедурный анализ потока данных
Межпроцедурный анализ потока данных
Анализ зависимостей в гнездах циклов 15
Использование результатов анализа потока данных и потока управления для вычисления отношения зависимости 17
Способы представления информации о зависимостях в оптимизирующих компиляторах 17
Применение результатов анализа в оптимизациях 18
Аппаратные и программные методы ослабления зависимостей 18
Постановка задачи 19
1.10. Выводы .20
2. Внутрипроцедурный анализ потока данных без учета
предикатных вычислений .21
2.1. Эффективный алгоритм построения формы статического
единственного присваивания 21
Алгоритмы построения ф-функций
Решение задачи построения ф-функций для множества переменных
Групповое построение ф-функций в контексте линейного алгоритма
Доказательство корректности и оценка сложности модифицированного алгоритма
Экспериментальные результаты
2.2. Дерево значений: новая структура данных, объединяющая
информацию о потоке управления и доминировании 32
Дерево значений
Алгоритм построения дерева значений
Доказательство корректности
Оценка сложности
Результаты тестирования
Оптимизации, использующие дерево значений
2.3. Выводы 39
.. 1__
3. Внутрипроцедурный анализ потока данных с учетом
предикатных вычислений .... ..40
3.1. Предикатная форма статического единственного присваивания 40
3.1.1. Описание пути в программе
3.2. Эффективный алгоритм преобразования потока управления в
поток данных на основе предикатной формы статического
единственного присваивания 46
Преобразование у-функции в предикатное выражение
Построение предикатного выражения
Хеширование предикатного выражения
Предикатное выражения произвольного пути
Пример работы алгоритма
3.3. Анализ предикатных выражений и его использования для
проведения оптимизаций ... 55
Алгоритмы анализа предикатов
Распространение анализа предикатов за пределы ациклических регионов
Использование результатов анализа предикатов в оптимизирующих компиляторах
3.4. Выводы ..... 62
4. Анализ зависимостей в цикловых регионах программы 63
Основные определения ... 63
Поиск гнезд циклов, для которых возможен анализ 64
Поиск индуктивных переменных .64
Поиск инвариантов гнезда циклов 66
Сохранение информации об измерениях 66
Подготовка данных гнезда циклов. . ... 67
Подготовка данных для анализа на зависимость двух операций обращения к массиву в цикле ... 68
Вызов драйвера алгоритма анализа зависимостей .. ... 68 4.9.Подготовка данных к вызову алгоритма анализа зависимостей 69
Особенности алгоритма анализа зависимостей 71
Минимальное расстояние зависимости .... .72
Интерпретация и использование результатов анализа в целях оптимизации 72
Экспериментальные результаты .72
Выводы 74
5. Межпроцедурный анализ потока данных . 75
Промежуточное представление .... 76
Пространство имен. . .... 77
Частичная трансферная функция . . 78
Анализ внутри процедуры 79
Межпроцедурный анализ ... 84
Распространение констант, диапазонов значений переменных и выравниваний объектов 91
Межпроцедурный анализ методом нумерации значений 92
Экспериментальные результаты 96
Выводы 99
Заключение 100
Список литературы 102
Список иллюстраций 107
Список таблиц 108
Введение к работе
Актуальность работы. Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая все более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, ее значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.
Ядром развития вычислительной техники с момента ее появления остается создание высокопроизводительных вычислительных систем. На протяжении последних десятилетий очень большое внимание уделяется проблемам распараллеливания вычислений. В этой области сосуществуют и активно развиваются два подхода к нахождению и использованию параллелизма вычислительных задач: распараллеливание на уровне процессов (многопроцессорные и массово-параллельные системы) и использование параллельности на уровне отдельных операций внутри одного процессора. В свою очередь распараллеливание на уровне операций может быть реализовано как аппаратными средствами во время исполнения программы (динамический подход), так и транслятором на этапе компиляции программы (статический подход).
Динамическое распараллеливание вычислений наиболее распространено в современных микропроцессорах и продолжает обеспечивать достаточную производительность исполнения вычислительных задач и совместимость программного обеспечения на ряде архитектур. Но дальнейшее увеличение параллельности на уровне операций в архитектурах процессоров может быть ограничено квадратичным усложнением логики проверок в аппаратуре при планировании команд. Поэтому статический подход к реализации пооперационной параллельности в процессе компиляции сейчас активно развивается как альтернатива суперскалярным (с динамическим планированием вычислений) процессорам. Для обозначения такого рода архитектур во второй половине 90-х годов появился термин EPIC (Explicitly Parallel Instruction Computing) [1-3] или архитектура с явно выраженной параллельностью на уровне команд.
В архитектурах с явно выраженной параллельностью эффективное использование машинных ресурсов в большей степени определяется процессом компиляции исходной программы. Другими словами, нахождение максимального параллелизма программы на уровне операций, выражение его в промежуточном представлении и отображение в статически спланированный код - это главные задачи оптимизирующего компилятора, позволяющие получать эффективный результирующий код и обеспечивающие оптимальную загрузку процессора в архитектурах типа EPIC. Развитие методов статического анализа программ является одним из главных резервов, позволяющих находить в программах независимые вычисления и выполнять их в параллельном режиме. Эти методы позволяют оптимизирующему компилятору эффективно применять оптимизирующие преобразования, направленные на максимально эффективное использование аппаратных ресурсов ЕР/С-архитектур в целях получения высокоэффективного кода и увеличения производительности вычислений. Особое внимание в данной работе
уделено таким методам статического анализа программ, как внутрипроцедурный анализ потока данных, межпроцедурный анализ потока данных, анализ зависимостей в цикловых регионах программы, анализ предикатных вычислений и его использование для успешного применения оптимизаций. Использование этих методов позволяет добиваться полноценного использования таких архитектурных особенностей ЕР1С-архитектур как широкая команда, предикатный и спекулятивный режимы исполнения инструкций. Следует отметить, что использование методов статического анализа позволяет применять преобразования программы на любом уровне факторизации, начиная от отдельной операции и заканчивая преобразованиями на межпроцедурном уровне.
Цель диссертационной работы
Целью диссертационной работы является исследование проблем и подходов к практическому решению задач статического анализа потока данных, статического анализа зависимостей и использованию результатов этих анализов в целях оптимизации программ для архитектур с явным параллелизмом. Для достижения поставленной цели в работе выполняются следующие этапы:
исследование современного уровня развития методов статического анализа программ и возможностей их использования в промышленных оптимизирующих компиляторах;
разработка быстрого алгоритма построения формы статического единственного присваивания;
разработка интегральной структуры данных, удобной для проведения многих преобразований программы;
разработка эффективного алгоритма перевода программы в предикатную форму;
улучшение метода анализа предикатных выражений и усиление эффективности применения оптимизаций, работающих на основе предикатного анализа;
улучшение метода анализа зависимостей в цикловых регионах программы, с целью повышения его точности и расширения области применимости;
развитие метода межпроцедурного анализа потока данных, позволяющего расширить область применимости межпроцедурного анализа с высокой степенью детализации результатов на приложения большого объема;
реализация указанных алгоритмов в составе оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ».
Предмет исследования составляют алгоритмические аспекты разработки оптимизирующих компиляторов для высокопроизводительных вычислительных систем:
методы статического анализа программ с точки зрения их эффективности и возможности применения в контексте промышленных оптимизирующих компиляторов;
оценка влияния использования методов статического анализа программ на эффективность проведения оптимизирующих преобразований программ, на конечную производительность и эффективность результирующего кода.
Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов, теории абстрактной интерпретации, теории диофантовых уравнений и неравенств, математической логики. Эффективность предложенных методов оценивалась путем вычисления значений ключевых параметров, определяющих эффективность предложенных подходов. Для проведения замеров использовался инструментальный комплекс в составе
оптимизирующего компилятора и потактной модели архитектуры «Эльбрус-ЗМ». Замеры производились на пакетах задач Spec92 и Spec95 [7, 8].
Научная новизна
Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, по преимуществу, составляют:
разработка быстрого алгоритма построения формы статического единственного присваивания;
разработка интегральной структуры данных, удобной для проведения многих преобразований программы;
разработка эффективного алгоритма перевода программы в предикатную форму;
улучшение метода анализа предикатных выражений и усиление эффективности применения оптимизаций, работающих на основе предикатного анализа;
улучшение метода анализа зависимостей в цикловых регионах программы, с
целью повышения его точности;
разработка единого метода решения задач межпроцедурного анализа потока
данных, в том числе задачу межпроцедурной нумерации значений.
Практическая ценность результатов работы состоит в том, что на основе предложенных в работе методов была разработана аналитическая часть промышленного оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ» [4-6].
В процессе выполнения диссертационной работы получены следующие практические результаты:
Все разработанные алгоритмы реализованы в составе оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ».
Выявились дальнейшие направления исследований в области развития методов статического анализа программ и их использования в целях оптимизации.
Апробация
Результаты работы докладывались на IX Санкт-Петербургской Международной конференции «Региональная информатика-2004 (РИ-2004)» в 2004 г., на Международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, 2004 г.), XXI Научно-технической конференции войсковой части 03425 (Москва, в/ч 03425, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО "МЦСТ" и Института Микропроцессорных вычислительных систем РАН.
Публикации
По теме диссертации опубликованы 8 печатных работ:
Дроздов А.Ю. Методы анализа программ, предлагаемые для использования в современных оптимизирующих компиляторах // Тезисы докладов XXI научно-технической конференции войсковой части 03425. - М.:, в/ч 03425, 2003.
Боханко А.С., Дроздов А.Ю. Оптимизация «Расширенное удаление излишних операций чтения из памяти» // Тезисы докладов Международной молодежной научной конференции «XXX Гагаринские чтения», т. 5. - М.: МАТИ, 2004.
Боханко А.С., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная
конференция "Региональная Информатика-2004". Тезисы докладов. - СПб.: СПИИ РАН, 2004.
Дроздов А.Ю., Владиславлев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская Международная конференция "Региональная Информатика-2004". Тезисы докладов. - СПб.: СПИИ РАН, 2004.
Дроздов А.Ю., Новиков СВ. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция "Региональная Информатика-2004". Тезисы докладов. - СПб.: СПИИ РАН, 2004.
Боханко А.С., Дроздов А.Ю., Корпев P.M. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004 г.
Дроздов А.Ю., Ровинский Е.В. Технология использования векторных операций для получения оптимального кода // Компьютеры в учебном процессе, № 9, 2004.
Дроздов А.Ю., Степаненков A.M. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10,2004.
Структура и объем работы
Диссертация состоит из введения, пяти глав, и заключения. Диссертация содержит 108 страниц, 25 рисунков, 6 таблиц. Список литературы насчитывает 93 наименования.
Краткое содержание работы
