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

о

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА Научно-исследовательский вычислительный центр

На правах рукописи УДК 681.3.06

АНТОНОВ Александр Сергеевич

НОВЫЙ ПОДХОД К МЕЖПРОЦЕДУРНОМУ АНАЛИЗУ ПРОГРАММ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Диссертация на соискание ученой степени кандидата физико-математических наук

Москва, 1999

Содержание

Введение 6

Общая характеристика работы ............................................6

Содержание работы..........................................................8

1 Существующие методы описания и исследования структуры программ 16

1 Подходы к исследованию структуры программ..........................16

2 Граф алгоритма и его использование при анализе программ............19

3 Обзор существующих методов межпроцедурного анализа программ . 22

3.1 Основные положения ................................................23

3.2 Неточные методы получения READ и WRITE областей .... 28

3.3 Точные методы получения READ и WRITE областей..........32

3.4 Сравнение методов получения READ и WRITE областей ... 34

3.5 Получение IN и OUT областей из READ и WRITE областей . 35

2 Каноническая форма параметрического описания графа алгоритма 36

1 Описание задачи ..................................36

2 Описание алгоритма канонизации...................................37

2.1 Нормализация........................................................37

2.2 Исключение переменных из равенств..............................38

2.3 Эвристические методы..............................................40

2.4 Исключения Фурье-Моцкина........................................42

2.5 Исключения Омега-теста............................................43

2.6 Перебор гиперплоскостей............................................45

2.7 Получение неизбыточного описания................................45

2.8 Гарантия сохранности формы многогранников ..................46

3 Операции над областями....................................................47

4 Геометрические свойства областей ........................................48

5 Свойства дуг графа алгоритма на канонических областях..............53

6 Определение свойств программ на основе канонической формы параметрического описания графа алгоритма..................................55

3 Межпроцедурный анализ программ на основе канонической формы параметрического описания графа алгоритма 59

1 Получение IN и OUT областей с помощью графа алгоритма............59

2 Описание входных и выходных данных процедуры в терминах фактических параметров (обратная подстановка)...................61

3 Анализ данных, использующих общую память .....................63

4 Исследование возможности проведения межпроцедурного анализа ... 64

5 Методика проведения анализа больших программных комплексов . . 67

6 Пример применения техники межпроцедурного анализа................69

4 Практическое применение описанных методов 72

1 Немного о компьютерах CRAY Y-MP С90 и CRAY T3D................72

2 Оптимизация программы LIU-FTC для одного векторно-конвейерного процессора CRAY Y-MP С90......................................73

2.1 Общая характеристика и структура программы ................73

2.2 Анализ и оптимизация программы ................................73

2.3 Результаты оптимизации............................................76

3 Оптимизация программы GCMA для компьютеров CRAY Y-MP С90 76

3.1 Общая характеристика и структура программы ................76

3.2 Анализ и оптимизация программы ................................77

3.3 Оставшиеся узкие места программы..............................82

3.4 Результаты оптимизации............................................82

4 Анализ и получение параллельной версии FL052 ........................82

4.1 Общая характеристика и структура FL052 ......................83

4.2 Потенциал параллелизма программы..............................84

4.3 Какое распределение данных использовать?......................86

4.4 Как распределять итерации циклов? ..............................88

4.5 Согласование распределений данных и итераций................89

4.6 Оптимизация работы программы на каждом процессоре .... 91

4.7 Результаты оптимизации FL052 ..................................92

Заключение 94

Литература 95

Список рисунков

1 Дерево методов межпроцедурного анализа................................24

2 Фрагмент программы и вычисляемая область массива..................27

3 Область, полученная методом ограниченных регулярных секций ... 28

4 Область, полученная методом описания с помощью триплетов .... 30

5 Область, полученная методом простых секций............................31

6 Область, заданная минимальной выпуклой оболочкой ..................32

7 Проектирование методами Фурье-Моцкина и Омега-теста..............44

8 Определение избыточности ограничения..................................46

9 Пересечение, разность и объединение двух областей....................47

10 Разность двух областей (ограничение-равенство)........................47

11 Разность двух областей (ограничение-неравенство)......................48

12 Свойства областей............................................................49

13 Порядок проекций вершин..................................................51

14 Пример последовательно выполняемого фрагмента программы .... 57

15 Области в пространстве итераций..........................................57

16 Вспомогательный фрагмент программы ..................................60

17 Обратная подстановка........................................................61

18 Анализ директивы EQUIVALENCE........................................63

19 Анализ данных в COMMON-блоках........................................64

20 Исследование условий линейности функции Трд..........................65

21 Методика проведения анализа программ..................................68

22 Пример применения техники межпроцедурного анализа................70

23 Фрагмент графа вызовов программы LIU-FTC ..........................74

24 Фрагмент подпрограммы F33C..............................................74

25 Фрагмент подпрограммы NNL..............................................75

26 Структура фрагмента подпрограммы TAULW............................77

27 Фрагмент подпрограммы RADFLW........................................78

28 Фрагмент подпрограммы GAUSPH........................................79

29 Схлопывание циклов..........................................................81

30 Граф вызовов программы FL052 ..........................................84

31 Циклический профиль подпрограммы EFLUX............................85

32 Тривиальное распределение итераций...........................86

33 Координатное распределение итераций....................................87

34 Структура подпрограммы PSMOO........................................87

35 Возможные схемы распределения итераций ..............................89

36 Схемы параллельного взаимодействия ....................................90

37 Полученное ускорение........................................................93

Список таблиц

1 Оценка количества выполняемых операторов после применения шНпе-

подстановки ...................................................................25

2 Результаты сбора статистики....................... 66

3 Результат внесения циклов внутрь подпрограмм........................80

4 Результаты оптимизации подпрограмм программы С СМ Л..............83

5 Времена выполнения вариантов РБМОО, с. (средний вариант)..........90

6 Времена выполнения подпрограмм, с. (средний вариант)................92

7 Времена выполнения вариантов И|052, с..................................92

Введение

Общая характеристика работы

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

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

Для помощи пользователям создаются автономные программные системы. В разработку теории, лежащей в основе создания систем статического анализа информационной структуры программ, внесли свой вклад многие ученые во всём мире, такие как А.П. Ершов, В.А. Серебряков, A.A. Летичевский, В.Н. Касьянов, В.В. Воеводин, М. Wolfe, W. Pugh, К. Kennedy, М. Lam, F. Irigoin, P. Tang, A. Schouten, L. Lamport, D. Kuck, P. Feautrier, U. Banerjee и другие.

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

Более общий подход к анализу структуры программ реализован в системе V-Ray System, разрабатываемой в лаборатории Параллельных информационных технологий НИВЦ МГУ и использующей в качестве основы для анализа программ параметрическое описание графа алгоритма (информационной истории реализации программ). В работах В.В. Воеводина и Вл.В. Воеводина сформулированы и доказаны условия существования информационной зависимости в программах, являющиеся не только достаточными, но и необходимыми. Эти критерии применимы к широкому классу программ, называемому линейным классом.

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

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

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

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

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

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

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

На основе предложенных алгоритмов разработана новая методика исследования структуры больших программных комплексов. Она служит основой при построении инструментальных систем для изучения и визуализации информационной структуры программ. Одна из таких систем разрабатывается в лаборатории Параллельных информационных технологий НИВЦ МГУ и называется V-Ray System.

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

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

Практическая значимость. Разработанный и описанный в диссертации метод канонизации параметрического представления графа алгоритма позволяет получить его точное и неизбыточное описание. Он ориентирован на практическое применение и спроектирован так, что сначала проверяются простые, но эффективные достаточные условия, работающие в большинстве реальных ситуаций, и лишь затем проводятся действия, требующие больших затрат по времени. Алгоритм канонизации на данный момент реализован в виде набора подпрограмм в рамках проекта по разработке системы анализа информационной структуры программ V-Ray System.

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

Полученные результаты широко применяются при анализе и оптимизации реальных приложений для различных современных параллельных компьютеров и суперЭВМ (CRAY Y-MP С90, CRAY T3D, IBM SP2 и других). Значительное ускорение, полученное на анализировавшихся программах, реально использующихся у нас в стране и за рубежом, подтверждает практическую применимость и эффективность данного подхода.

Апробация работы. Основные положения работы обсуждались на научно-исследовательских семинарах в НИВЦ МГУ и на научно-исследовательском семинаре по автоматизации программирования на факультете ВМиК МГУ.

Результаты диссертации докладывались на Ломоносовских чтениях в МГУ (в 1995 и 1997 годах), на всероссийской научной конференции "Фундаментальные и прикладные аспекты разработки больших распределённых программных комплексов" (Абрау-Дюрсо, 1998 год), опубликованы в трудах 22-й международной конференции "Euromicro Conference" (Prague, 1996) и в трудах первой международной научно-практической конференции по программированию УкрПРОГ'98 (Киев, 1998 год).

Публикации. По теме диссертации опубликовано 6 статей.

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка литературы (47 наименований); включает 37 рисунков и 7 таблиц.

Содержание работы

Во введении приводится общая характеристика работы и обзор содержания диссертации.

Первая глава работы посвящена обзору существующих методов статического анализа программ и межпроцедурного анализа. Сначала описываются методы ана-

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

Основной ресурс параллелизма в программах приходится на циклические конструкции. На их анализе основывается следующая группа методов: модификация с^аАо^/'-анализа, анализ возможных перестановок циклов и анализ пространства итераций циклов. В качестве методов анализа пространства итераций цикла рассматриваются широко известные методы гиперплоскостей, координат, параллелепипедов и пирамид. Эти методы намного более содержательные и широко используются на практике. Основной недостаток всех рассмотренных методов исследования циклов — ориентация только на циклические фрагменты с заранее заданными свойствами и структурой. При этом фрагменты с другой структурой (а их, как показывает статистический анализ, очень много) исключаются из рассмотрения.

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

Далее в работе вводится формализованное определение графа алгоритма, введённое в работах В.В. Воеводина и Вл.�