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

Актуальность работы. Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая все более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, ее значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.

Ядром развития вычислительной техники с момента ее появления остается создание высокопроизводительных вычислительных систем. На протяжении последних десятилетий очень большое внимание уделяется проблемам распараллеливания вычислений. В этой области сосуществуют и активно развиваются два подхода к нахождению и использованию параллелизма вычислительных задач: распараллеливание на уровне процессов (многопроцессорные и массово-параллельные системы) и использование параллельности на уровне отдельных операций внутри одного процессора. В свою очередь распараллеливание на уровне операций может быть реализовано как аппаратными средствами во время исполнения программы (динамический подход), так и транслятором на этапе компиляции программы (статический подход).

Динамическое распараллеливание вычислений наиболее распространено в современных микропроцессорах и продолжает обеспечивать достаточную производительность исполнения вычислительных задач и совместимость программного обеспечения на ряде архитектур. Но дальнейшее увеличение параллельности на уровне операций в архитектурах процессоров может быть ограничено квадратичным усложнением логики проверок в аппаратуре при планировании команд. Поэтому статический подход к реализации пооперационной параллельности в процессе компиляции сейчас активно развивается как альтернатива суперскалярным (с динамическим планированием вычислений) процессорам. Для обозначения такого рода архитектур во второй половине 90-х годов появился термин EPIC (Explicitly Parallel Instruction Computing) [1−3] или архитектура с явно выраженной параллельностью на уровне команд.

В архитектурах с явно выраженной параллельностью эффективное использование машинных ресурсов в большей степени определяется процессом компиляции исходной программы. Другими словами, нахождение максимального параллелизма программы на уровне операций, выражение его в промежуточном представлении и отображение в статически спланированный код — это главные задачи оптимизирующего компилятора, позволяющие получать эффективный результирующий код и обеспечивающие оптимальную загрузку процессора в архитектурах типа EPIC. Развитие методов статического анализа программ является одним из главных резервов, позволяющих находить в программах независимые вычисления и выполнять их в параллельном режиме. Эти методы позволяют оптимизирующему компилятору эффективно применять оптимизирующие преобразования, направленные на максимально эффективное использование аппаратных ресурсов ЕР/С-архитектур в целях получения высокоэффективного кода и увеличения производительности вычислений. Особое внимание в данной работе уделено таким методам статического анализа программ, как внутрипроцедурный анализ потока данных, межпроцедурный анализ потока данных, анализ зависимостей в цикловых регионах программы, анализ предикатных вычислений и его использование для успешного применения оптимизаций. Использование этих методов позволяет добиваться полноценного использования таких архитектурных особенностей ЕР1С-архитектур как широкая команда, предикатный и спекулятивный режимы исполнения инструкций. Следует отметить, что использование методов статического анализа позволяет применять преобразования программы на любом уровне факторизации, начиная от отдельной операции и заканчивая преобразованиями на межпроцедурном уровне.

Цель диссертационной работы.

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

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

• разработка быстрого алгоритма построения формы статического единственного присваивания;

• разработка интегральной структуры данных, удобной для проведения многих преобразований программы;

• разработка эффективного алгоритма перевода программы в предикатную форму;

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

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

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

• реализация указанных алгоритмов в составе оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ».

Предмет исследования составляют алгоритмические аспекты разработки оптимизирующих компиляторов для высокопроизводительных вычислительных систем:

• методы статического анализа программ с точки зрения их эффективности и возможности применения в контексте промышленных оптимизирующих компиляторов;

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

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов, теории абстрактной интерпретации, теории диофантовых уравнений и неравенств, математической логики. Эффективность предложенных методов оценивалась путем вычисления значений ключевых параметров, определяющих эффективность предложенных подходов. Для проведения замеров использовался инструментальный комплекс в составе оптимизирующего компилятора и потактной модели архитектуры «Эльбрус-ЗМ». Замеры производились на пакетах задач Spec92 и Spec95 [7, 8].

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

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

• разработка быстрого алгоритма построения формы статического единственного присваивания;

• разработка интегральной структуры данных, удобной для проведения многих преобразований программы;

• разработка эффективного алгоритма перевода программы в предикатную форму;

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

• улучшение метода анализа зависимостей в цикловых регионах программы, с целью повышения его точности;

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

Практическая ценность результатов работы состоит в том, что на основе предложенных в работе методов была разработана аналитическая часть промышленного оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ» [4−6].

В процессе выполнения диссертационной работы получены следующие практические результаты:

1) Все разработанные алгоритмы реализованы в составе оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ».

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

Апробация.

Результаты работы докладывались на IX Санкт-Петербургской Международной конференции «Региональная информатика-2004 (РИ-2004)» в 2004 г., на Международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, 2004 г.), XXI Научно-технической конференции войсковой части 3 425 (Москва, в/ч 3 425, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО «МЦСТ» и Института Микропроцессорных вычислительных систем РАН.

Публикации.

По теме диссертации опубликованы 8 печатных работ:

• Дроздов А. Ю. Методы анализа программ, предлагаемые для использования в современных оптимизирующих компиляторах // Тезисы докладов XXI научно-технической конференции войсковой части 3 425. — М., в/ч 3 425, 2003.

• Боханко A.C., Дроздов А. Ю. Оптимизация «Расширенное удаление излишних операций чтения из памяти» // Тезисы докладов Международной молодежной научной конференции «XXX Гагаринские чтения», т. 5. — М.: МАТИ, 2004.

• Боханко A.C., Дроздов А. Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная конференция «Региональная Информатика-2004». Тезисы докладов. — СПб.: СПИИ РАН, 2004.

• Дроздов А. Ю., Владиславлев В. Е. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская Международная конференция «Региональная Информатика-2004». Тезисы докладов. — СПб.: СПИИ РАН, 2004.

• Дроздов А. Ю., Новиков C.B. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция «Региональная Информатика-2004». Тезисы докладов. — СПб.: СПИИ РАН, 2004.

• Боханко А. С., Дроздов А. Ю., Корнев P.M. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004 г.

• Дроздов А. Ю., Ровинский Е. В. Технология использования векторных операций для получения оптимального кода // Компьютеры в учебном процессе, № 9, 2004.

• Дроздов А. Ю., Степаненков A.M. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10,2004.

Структура и объем работы.

Диссертация состоит из введения, пяти глав, и заключения. Диссертация содержит 108 страниц, 25 рисунков, 6 таблиц.

Список литературы

насчитывает 93 наименования.

5.9. Выводы.

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

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

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

Предлагаемый подход тестировался на задачах из пакетов 5РЕСлги92 и 5РЕСт195. На входящих в эти пакеты приложениях предложенный метод показал хорошее время работы с минимальными потерями в точности вычисляемой информации.

Использование результатов распространения констант позволяет улучшать производительность на некоторых задачах на 40%. Ниже приведены основные результаты данной главы:

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

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

3) Предложен алгоритм решения задачи межпроцедурной нумерации значений.

Заключение

.

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

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

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

2) Предложена новая структура данных (дерево значений), позволяющая объединить в единое целое информацию о потоке данных и доминировании и показано, как на ее основе применяется широкий класс преобразований потока данных.

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

4) Предложен метод, расширяющий применимость анализа предикатов в программе, переведенной в предикатную форму, на случай произвольного региона. Этот метод позволяет включить в рассмотрение поток данных, входящих в регион через ср-узлы.

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

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

7) Разработано понятие минимального вектора расстояния зависимости и предложен метод его вычисления.

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

9) Разработана реализация решателя систем диофантовых неравенств на основе Симплекс-метода. Показано, что Симплекс-метод имеет преимущество перед методом Фурье по скорости работы на задачах, работающих с многомерными массивами.

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

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

12) Предложен алгоритм решения задачи межпроцедурной нумерации значений.

Все представленные в диссертационной работе алгоритмы и методы, реализованы в составе оптимизирующего компилятора с языков высокого уровня С, С++, ?11 для архитектуры «Эльбрус-ЗМ» и составляют основу аналитической части данного компилятора. Некоторые из предложенных методов внутрипроцедурного анализа программы работают в составе двоичного компилятора для архитектуры «Эльбрус-ЗМ» с кодов Ые1-Х86.