Новый подход к межпроцедурному анализу программ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Антонов, Александр Сергеевич

• Антонов, Александр Сергеевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Антонов, Александр Сергеевич

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

подстановки

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

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

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

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

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

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

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

Введение

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

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

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

Для помощи пользователям создаются автономные программные системы. В разработку теории, лежащей в основе создания систем статического анализа информационной структуры программ, внесли свой вклад многие ученые во всём мире, такие как А.П. Ершов, В.А. Серебряков, 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 таблиц.

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

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

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

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

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

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

Далее в работе вводится формализованное определение графа алгоритма, введённое в работах В.В. Воеводина и Вл.В. Воеводина, и фиксируется класс исследуемых программ, называемый линейным классом. Формулируются условия, при выполнении которых для анализируемой программы возможно построение параметрического описания графа алгоритма в следующем виде: для каждого входа каждого оператора указывается конечное множество троек (Ду, Дг, -Р), где Ду — линейный многогранник в пространстве Пдг внешних переменных программы, значения которых на момент построения графа неизвестны; Д/ — линейный многогранник в пространстве итераций П/, размеры и положение которого могут зависеть от точек многогранника Д^; функция Р е 2/р линейная и имеет вид Р = Jx + Ф1\Г + где N е — это вектор внешних переменных программы, J е £рХп, Ф е ZpXk — целочисленные матрицы, а 5 £ — вектор свободных членов. Областью определения функции Р является многогранник Д/, значениями функции являются точки пространства итераций, причём точка ж задаёт конечную вершину дуги, соответствующей информационной зависимости, а выражение Зх ФN Б — начальную. Для программ, не принадлежащих линейному классу, возможно построение минимального (в рамках статического подхода) расширения графа алгоритма.

Далее приводятся формулировки критериев, которые на основании параметрического описания определяют, обладает ли фрагмент программы полезными для ана-

лиза и оптимизации структуры фрагмента свойствами (такими как свойство PARDO для циклов, возможность перестановки циклов, возможность распределения циклов и другие).

В следующем разделе приведён обзор существующих методов межпроцедурного анализа. Методы межпроцедурного анализа с точностью до имён массивов не рассматриваются, поскольку они хорошо известны и явно недостаточны для детального анализа программ. Для дополнительного анализа inline-подстановки (подстановки тела процедуры на место вызова) приводятся данные статистического анализа шести достаточно больших реальных программ. Они показывают, что inline-подстановка только листовых процедур (процедур, не содержащих вызовов) приводит к росту размера кода на несколько порядков, что делает его анализ практически не реальным.

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

Среди неточных методов рассматриваются: метод ограниченных регулярных секций, метод описания с помощью триплетов, метод простых секций, метод описания в виде выпуклой оболочки, среди точных — подход Бурке-Сайтрона и построение совокупного образа. Для всех методов приводится описание алгоритмов построения пересечения и объединения получаемых областей. Каждый метод иллюстрируется также небольшим примером описания READ/WRITE областей некоторого фрагмента программы. Все описанные методы сравниваются по требуемому для реализации объёму памяти и по сложности операций объединения и пересечения получаемых областей.

Далее описывается алгоритм получения IN/OUT областей из READ/WRITE областей, который предложили В. Creusillet и F. Irigoin. Этот алгоритм, однако, обладает ограниченной применимостью.

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

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

• никакие из многогранников А/, Д^ не являются целочисленно пустыми, то

есть все они содержат хотя бы одну точку с целочисленными координатами;

• ни одно из ограничений, описывающих многогранники А/, Ддг, не является избыточным;

• ни одно из рёбер многогранников Д/ не может стягиваться в точку ни при каких значениях внешних переменных из соответствующего многогранника

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

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

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

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

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

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

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

На всех шагах алгоритма производится разбиение области Дд/- в пространстве внешних переменных Цдг на подобласти, в каждой из которых выполняется или не выполняется проверяемое на данном шаге условие. Работа алгоритма прекращается тогда, когда будут проверены все полученные подобласти области А^. Количество шагов алгоритма конечно, на каждом шаге число подобластей области Ддг увеличивается не более, чем в два раза, поэтому алгоритм также конечен.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В конце этой главы последовательность действий алгоритма межпроцедурного анализа прослежена на иллюстративном примере.

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

Программы LIU-FTC и GCMA — реальные большие программы, первая из которых моделирует устойчивость плазмы в установках управляемого термоядерного синтеза (факультет ВМиК МГУ), а вторая предназначена для моделирования глобальных изменений климата (ИВМ РАН). Их оптимизация производилась для векторно-конвейерного компьютера CRAY Y-MP С90, и именно применение методов межпроцедурного анализа позволило достичь на обеих программах существенного ускорения.

Другая программа, FL052 из широко известного пакета Perfect Club Benchmarks, представляет собой упрощённый вариант реализации одной из задач вычислительной гидродинамики. Она часто используется в качестве теста для определения реальной производительности параллельных компьютеров. Эта программа изначально была написана для векторно-конвейерного компьютера, поэтому наиболее интересно было попытаться оптимизировать её для существенно другой архитектуры —

массивно-параллельного компьютера CRAY T3D. При этом пришлось решать задачи, характерные для оптимизации программ для компьютеров с распределённой памятью (такие как выбор распределения данных и итераций между процессорами), но и в этом случае без применения межпроцедурного анализа обойтись было бы невозможно. На этой программе также было получено существенное ускорение, и, что может быть ещё более важно, показано, что при увеличении размеров сетки, на которой производится вычисление, полученная параллельная программа становится хорошо масштабируемой. Так, если ускорение малого варианта программы (размер вычисляемой области X х Y) наблюдается при увеличении числа процессоров только до 32, то для среднего варианта (область 2Х х 2Y) и для большого варианта (область 4Х х 4Y) ускорение наблюдается при увеличении числа процессоров до 64 и 128 соответственно.

В заключении формулируются основные результаты работы.

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

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

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

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

Основной вывод этих исследований таков: любое арифметическое выражение без унарного минуса с п операндами может быть вычислено на п/2 процессорах за время порядка log2 п при сложности преобразования в максимально параллельную форму О(п) [7]. Однако надо учитывать, что в этих методах производится перестановка операндов и раскрытие скобок, что может быть неприемлемо с точки зрения точности результатов.

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

Обычно выделяют зависимости по управлению и информационные зависимости: зависимость по потоку (dataflow, истинная), антизависимость, зависимость по входу и по выходу [16]. Графы зависимостей полностью определяют порядок вычислений, так как если от вершины X к вершине Y идёт дуга, то Y может быть выполнена только после X.

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

Можно выделить три направления развития методов анализа циклов [11]: модификация dataflow-анализа, анализ возможных перестановок циклов и анализ пространства итераций цикла.

Модификации методов dataflow-анализа базируются на двух основных идеях: независимом выполнении итераций цикла, между которыми нет информационных зависимостей и способах выявления и использования параллелизма циклов, содержащих рекуррентную зависимость. Для определения факта существования зависимости между итерациями циклов можно использовать многие методы [20, 38, 33, 41]: НОД-тест, неравенство Банерджи, Л-тест, Delta-тест, тест для вхождения одной переменной в каждое ограничение (Single Variable Per Constraint Test), ациклический тест (Acyclic Test), тест на остатки циклов (Simple Loop Residue Test), метод Шо-стака, метод Фурье-Моцкина, Омега-тест и другие.

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

Анализ перестановок циклов очень часто используется на практике [19, 47]. Основная идея в случае тесно вложенных циклических конструкций состоит в том, что находятся зависимости между итерациями циклов, затем возможные перестановки циклов проверяются на отсутствие противоречий с найденными зависимостями. Если противоречий нет, то перестановку производить можно с гарантией эквивалентности результатов. Гнёзда циклов, не являющиеся тесно вложенными, стараются эквивалентными преобразованиями привести к тесно вложенным, после чего производят описанный анализ. Каждый из этих методов можно применять только для гнёзд циклов определённого вида, а кроме того, эти методы ничего не говорят о потенциале исследуемого фрагмента, так как определяют только собственную применимость или неприменимость.

Большими возможностями обладают методы анализа пространства итераций. Пространством итераций гнезда тесновложенных циклов называют [37] множество целочисленных векторов I. координаты которых задаются значениями параметров циклов данного гнезда. Задача распараллеливания при этом сводится к разбиению множества векторов I на подмножества, которые выполняются последовательно друг за другом, но в рамках каждого такого подмножества итерации могут быть выполнены одновременно и независимо. Для решения этой задачи необходимо сначала установить информационные зависимости, а затем в соответствии с ними производить разбиение на подмножества.

Среди методов анализа пространства итераций можно выделить несколько наиболее известных: методы гиперплоскостей, координат, параллелепипедов и пирамид.

Метод гиперплоскостей заключается в том, что пространство итераций размерности п разбивается на гиперплоскости размерности п— 1 так, что все операции,

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

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

Метод параллелепипедов [7] является логическим развитием двух предыдущих методов и заключается в разбиении пространства итераций на гг-мерные параллелепипеды, объём которых определяет результирующее ускорение. В отличие от предыдущих, этот метод применим не только к циклическим гнёздам, но и к одиночным циклам.

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

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

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

Всё множество графовых моделей в рамках операционного подхода можно характеризовать несколькими критериями [11]. Первый из них — это какие именно операции программы ставятся в соответствие вершинам графа. Здесь возможны варианты от отдельных операторов или групп операторов (макрооператоров) программы (схемные модели) до отдельных срабатываний операторов (истории реализации).

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

Второй критерий, которым можно характеризовать графовые модели программ, — какую смысловую нагрузку несут дуги графа. Это может быть либо зависимость по управлению (операционные графы) либо зависимость по данным (информационные графы). Тип информационного графа определяется типом отслеживаемых зави-

симостей.

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

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

Назовём графом алгоритма [8] исследуемой программы ациклический ориентированный граф с множеством вершин V и множеством дуг Р, обладающих следующими свойствами: после выполнения программы отдельному срабатыванию каждого оператора отвечает своя вершина V е V, причём вершины связываются направленной дугой VI —> V] тогда и только тогда, когда результат, вычисленный в вершине используется как аргумент вершиной Vj.

Для того, чтобы ввести параметрическое описание графа алгоритма, зафиксируем сначала класс программ, который будем исследовать [10]. В качестве языка программирования берётся традиционный для подобных исследований Фортран. Предполагается, что все входные для исследуемого фрагмента данные могут принимать любые допустимые значения своего типа. Значения операций присваивания (исключая значения параметров циклов) считаются динамическими характеристиками и не могут быть использованы в рамках статического анализа. Последовательность срабатывания операторов программы определяется графом алгоритма, и нет никаких данных о недостижимости отдельных путей.

Для каждого оператора 6" определим совокупность условий его срабатывания. Для этого возьмем граф управления программы и удалим все дуги, определяющие циклический возврат "назад". Таким образом, получим ациклический граф. Далее, найдем всё множество путей, ведущих из начальной точки программы к выбранному оператору: Р\,..., Р&. Каждый путь Р^ определяет одно из условий срабатывания оператора Б и представляет собой конъюнкцию условий истинности составляющих его альтернативных операторов: = С {к,... Часть альтернативных опера-

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

Затем в каждое условие добавим условия принадлежности оператора Б объемлющим его циклам: по два неравенства на каждый цикл. Полученный набор условий назовём областью срабатывания (областью действия) оператора 5 [10]. Его можно

представить в виде дизъюнктивной нормальной формы:

т ¿=1

где каждое элементарное условие С°г имеет вид (а], г) < (Ц,п)-^-Ь301. Здесь г — вектор параметров циклов, содержащих в, п — вектор внешних переменных фрагмента, а^ и Ц — константные целочисленные векторы, Ь301 — целое число.

Далее, наложим следующие ограничения на исследуемый фрагмент:

• пусть фрагмент состоит только из операторов присваивания, операторов цикла Б О, альтернативных операторов и операторов безусловного перехода, причём все циклы фрагмента заданы только операторами ВО;

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

в стандартной линейной форме (то есть, имеют вид: агц Н-----Ь апгп + £>о + Ь\П\ +

• • • + ЬкПк, где ¿1,..., гп — параметры объемлющих циклов, ах,..., ап, Ьо,..., — целочисленные константы, пх,...,п*. — внешние для данного фрагмента переменные);

• операторы циклов не содержат побочных выходов.

Скажем, что программа, удовлетворяющая этим условиям, принадлежит линейному классу.

Как доказано в [10], для такой программы можно найти описание отвечающего ей графа алгоритма в виде: для каждого входа каждого оператора указывается конечное множество троек (Длг, Д/, .Р), где Дн — линейный многогранник в пространстве Пм внешних переменных программы, значения которых на момент построения графа неизвестны, Д/ — линейный многогранник в пространстве итераций (1/, размеры и положение которого могут зависеть от точек многогранника Д^, функция Р е Zp линейная и имеет вид ^ = Jx + ФИ + Б, где N е Zk — это вектор внешних переменных программы, 3 е ZpXn, Ф е ZpXk — целочисленные матрицы, а 5 е Zp — вектор свободных членов. Областью определения функции -Р1 является многогранник Д/, значениями функции являются точки пространства итераций, причём точка х задаёт конечную вершину дуги, соответствующей информационной зависимости, а выражение Зх + ФИ + 5 — начальную.

Если программа изначально не принадлежит линейному классу, над ней выполняется последовательность преобразований [10, 13], позволяющих в ряде случаев удовлетворить приведённым ограничениям. Это могут быть нормализация циклов и приведение их к строгой вложенности, введение специальной системы координат, согласованной с порядком выполнения операций программы, априорная подстановка переменных, определение глобальных условий достижимости операторов и т. д..

Если же и после таких преобразований программа не принадлежит линейному классу, то выполняется минимальное расширение графа алгоритма. Такое расширение должно обладать следующими свойствами. Во-первых, множество вершин любого реального графа алгоритма должно быть подмножеством множества вершин расширенного графа. Во-вторых, если в каком-нибудь реальном графе есть дуга из вершины г>1 в вершину г>2, то в расширенном графе должен существовать путь, ведущий из в В работе [10] показано, как строить минимальные расширения графа алгоритма для случаев нарушения различных условий принадлежности программы к линейному классу.

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

• Для того, чтобы цикл являлся циклом РагВО (то есть, таким циклом, итерации которого можно выполнять независимо), необходимо и достаточно, чтобы для любой тройки графа алгоритма данного цикла включение Д/ с С? было верным, где

Д/ — многогранник пространства итераций из тройки,

Ч — управляющий параметр анализируемого цикла, /1 — первая компонента вектор-функции Р;

• Для того, чтобы выполнить перестановку двух соседних циклов Ь\ и Ь2 тесно-вложенного гнезда, необходимо и достаточно, чтобы для любой тройки графа алгоритма внешнего цикла включение Д/ с С было верным^где

Д/ — многогранник пространства итераций из тройки,

г2 — управляющий параметр внутреннего цикла, /2 — вторая компонента вектор-функции Р.

• Для того, чтобы выполнить распределение цикла Ь, необходимо и достаточно, чтобы распределяемые части и Т2 находились в разных компонентах сильной связности информационного графа тела Т данного цикла;

• Для того, чтобы выполнить объединение циклов Ь\ и Ь2, необходимо и достаточно, чтобы в информационном графе тела объединенного цикла не было дуг с начальными вершинами, принадлежащими телу Т2 второго цикла, и конечными вершинами, принадлежащими телу Т\ первого цикла;

в = { /2 < г2

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

Исследование возможности проведения некоторых других эквивалентных преобразований приведено также в работе [9]. С использованием подобных критериев можно устанавливать многие полезные свойства программ. Разработаны эффективные алгоритмы, позволяющие проверять указанные условия, и, следовательно, определять характеристики программ.

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

Жёстким ограничением на программы линейного класса является отсутствие среди разрешённых операторов оператора вызова подпрограмм и функций. В работе [8] для разрешения этой проблемы предложено некоторое расширение графа алгоритма при помощи обобщения оператора присваивания, покрывающее, в частности, и некоторые вызовы подпрограмм: выражение F(a>i,... ,а3; ,... ,/Зг) называется оператором присваивания, если перед его выполнением переменные «i,..., ав (входы оператора присваивания) принимают некоторые значения, а в результате его выполнения вычисляются переменные ¡3i,... ,¡3r (выходы оператора присваивания).

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

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

Приводимый здесь обзор базируется на работе [5]. Необходимость выполнения межпроцедурного анализа программ очень часто возникает на практике, в частности при анализе параллельных свойств программ.

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

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

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

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

• определение влияния вызова процедур на контекст вызова [15] и

• определение влияния контекста вызова на исполнение вызываемой подпрограммы.

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

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

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

Одним из первых методов разрешения проблемы межпроцедурного анализа была предложена подстановка тела подпрограммы на место вызова (inline expansion [43]), но она сильно затруднена, если в графе вызовов есть контуры, а также приводит к сильному увеличению размера кода и времени анализа.

Нами было произведено небольшое исследование по оценке размера кода, получаемого при inline-подстановке. Полученные данные показаны в табл. 1. Столбцы таблицы соответствуют исследованным проектам, а строки — тому, на какую глубину вложенности производится inline-подстановка. При этом 0 соответствует исходному тексту, 1 — исходному тексту с подставленными телами листовых процедур и т. д. На пересечении указана оценка количества выполняемых операторов, получаемого для данного проекта при inline-подстановке соответствующего уровня.

В таблице приведены данные по шести проектам из самых разных областей:

• GCMA — программа моделирования долговременных изменений климата;

• ELVEC — тестовая программа для векторных суперкомпьютеров;

Методы межпроцедурного анализа

Inline- Без учёта

подстановка индексных выражений

С учётом индексных выражений

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

Read/Write

1п/(М

Неточные

Точные

На основе Read/Write

Граф алгоритма

Ограниченные Описание Простые Выпуклая регулярные в виде секции оболочка

секции триплетов

Метод Бурке-Сайтрона

Совокупный образ

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

GCMA ELVEC K-SPA MHD LIU-FTC FL052

0 9172 961 11678 1486 25539 1743

1 15754 3540 2509795 4109 4149022 1944

2 77286 6338 3704858 5509 5575598 2539

3 91795 9709 4101261 6082 7571511 3528

4 91795 4221529 6082 7609596

5 91795 8101423 6082 7613489

6 8101423 7613489

7 8101423 7613489

8 8101423 7613489

9 8101423

10 8101423

И 8101423

Таб. 1: Оценка количества выполняемых операторов после применения inline-подстановки

• К-SPA — программа решения систем линейных алгебраических уравнений для блочных разреженных матриц;

• FL052 и MHD — тестовые программы из пакета Perfect Club Benchmarks [34, 22, 32, 40];

• LIU-FTC — программа моделирования устойчивости плазмы в установках управляемого термоядерного синтеза.

Как видно, сюда вошли данные по трём тестовым программам и трём большим реальным вычислительным проектам.

Надо заметить, что в таблице приведена оценка снизу для числа операторов, так как реальное проведение inline-подстановки заведомо потребует преобразований текста, приводящих к добавлению новых операторов. Но даже здесь видно, что для больших реальных программ (таких как K-SPA и LIU-FTC) уже при inline-подстановке даже только листовых процедур размер кода увеличивается на несколько порядков, и представляется нереальным анализировать такие программы на персональном компьютере за приемлемое время.

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

В известных обзорах [15, 44] большое внимание уделялось методам межпроцедурного анализа без учёта индексных переменных. Решаемые этими методами задачи, такие как совмещение параметров процедуры (aliasing), анализируемое с точностью до имён массивов, межпроцедурное распространение констант (constant propagation) и определение входных и выходных параметров процедур с точностью до имён массивов, решаются довольно простыми методами и подробно описаны. Кроме того, такой анализ является весьма грубым и недостаточным для исследования реальных программ, поскольку в большинстве случаев для получения полезных свойств необходимо определение существования зависимости между отдельными элементами массивов. В работе [42] на основе изучения некоторой выборки программ на языке Паскаль делается даже вывод о бесполезности межпроцедурного анализа без учёта индексных переменных для оптимизации реальных программ.

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

Методы межпроцедурного анализа с учётом индексных переменных в последнее время получили дальнейшее развитие во многих работах. Логически межпроцедурный анализ программы можно разделить на две обязательные стадии:

• нахождение входных и выходных данных подпрограммы и

• описание этих данных в терминах фактических параметров (обратная подстановка).

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

В большинстве работ, посвящённых межпроцедурному анализу, рассматриваются только те области, которые соответствуют вырезкам из массивов, используемым или изменяемым в анализируемой подпрограмме (то есть области, описывающие совокупности переменных и элементов массивов, стоящих соответственно в правой или левой части операторов присваивания). Следуя [30], будем называть такие области READ и WRITE областями.

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

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

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

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

Все описываемые далее методы проиллюстрируем на одном примере — зададим с помощью каждого метода WRITE область для фрагмента программы, производящего вычисления для нижнетреугольной части массива и одной из его строк. Этот фрагмент и суммарная WRITE область приведены на рис. 2. На этом рисунке, как и на всех последующих, изображающих аппроксимации этой области, предполагается, что элемент массива А(1, 1) находится в левом верхнем углу, а элементы первой размерности массива располагаются сверху вниз.

PARAMETER (N = 13, К = 7) DIMENSION A(N+1, N+l)

С обращение к нижнетреугольной

С части массива DO I = 1, N DO J = 1, I

A(I, J) = ... END DO END DO

С обращение к строке с номером К DO J = 1, N

А(К, J) = ... END DO

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

Следуя [29], опишем отдельное обращение к элементам массива при помощи трёх векторов: вектора индексных выражений ¿-мерного массива Ф(Л) = (</>i,..., ф^). вектора пар ограничений на управляющие параметры I объемлющих циклов В(А) = (/?i,...,$), где (3j — упорядоченная пара (lbj,ubj) ограничений снизу и сверху на параметр ji-oro цикла, и вектора шагов управляющих параметров циклов Е(-А) = (oi,..., <77). Тогда описатель доступа к массиву Д(-А) представляется в виде тройки

< Ф,В,Е >.

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

Регулярные секции (regular sections) были предложены в работе [26] как простой способ аппроксимации READ и WRITE областей. Они бывают двух основных типов

— ограниченные регулярные секции (restricted regular sections [25]) и описания с помощью триплетов (bounded regular sections [35]).

Ограниченные регулярные секции представляются с помощью вектора индексных выражений массива Ф(Л), в котором каждая компонента фк является либо константным выражением (инвариантом подпрограммы), либо выражением вида а± ij, где ij

— переменная, сопоставляемая j-ому измерению массива (к ^ j), а а — константное выражение (инвариант подпрограммы), либо особым значком который означает всю размерность массива. С помощью такой конструкции можно описать отдельный элемент массива, полные строку, столбец или диагональ, а также их многомерные аналоги.

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

Объединение двух ограниченных регулярных секций получается следующим образом. Если на й-том месте в одной из секций стоит _1_, то на соответствующем месте фк в объединении также будет ±. Если на А:-том месте в обеих секциях стоит

одна и та же константа, то в объединении также будет эта константа. Если на соответствующих местах стоят разные константы, то в объединении будет ±. Если на к-том месте хотя бы в одной из секций стоит выражение а ± ij, то проводится процесс, называемый нормализацией [44], который приводит к тому, что в каждой из секций фк представляется либо значком _L, либо выражением а ± ij, где j < к и (j>j =J_. После этого в объединении будет а ± ij, если эти выражения для обеих секций в точности идентичны, или J_ в противном случае.

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

1. В одном из векторов стоит значок ±.

2. В одном из векторов стоит а ± ij, а в другом выражение, не зависящее от ij.

3. В обоих векторах стоит а + ij или а - ij с одинаковой константой а.

4. В обоих векторах стоит константа а.

Если хотя бы для одной пары элементов векторов ни одно из этих условий не выполняется, то пересечение пусто, иначе непусто.

Для рассматриваемого примера (рис. 2) WRITE область, полученная методом ограниченных регулярных секций, описывается следующим образом:

RRS^A) = (±,±), RRS2(A) = (#,_!_), RRS^(A) = (1,1).

Следовательно, получается описание всего массива А (рис. 3).

В отличие от ограниченных регулярных секций, описание с помощью триплетов (bounded regular sections) не позволяет задавать диагонали, но включает информацию о границах и шагах циклов. Триплет описывается для каждого измерения массива с использованием элементов векторов В (А) и Е(Л) в виде [/6; : ub{ : <Т{\, где lbi,ubi и <Т{ — константы или инвариантные выражения подпрограммы.

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

Для определения пересечения двух секций нужно взять пару триплетов для каждого измерения [lb] : ub] : <т}} и [Щ : ub? : erf] и составить систему равенств и неравенств:

О <к}< (ubj - lb])/*}

о <kf< (чЪ> - Щ)1*1

где kj, kf <£ Z.

Если описываемая такой системой область целочисленно непуста для каждого измерения, то пересечение двух секций непусто. Целочисленную непустоту области можно определять, например, с помощью Омега-теста [41]. В некоторых случаях эту задачу можно решить с помощью простых эвристик.

Для рассматриваемого примера (рис. 2) WRITE область, полученная методом описания с помощью триплетов, описывается следующим образом:

BRS! = ([1 : N : 1], [1 : N : 1]), BRS2 = {K,[l :N: 1]), BRS1U2 = ([1 : JV : 1], [1 : iV : 1]).

Эта область показана на рис. 4.

к* х й X X X X х х шт

т х х X х X X х х шш

т х Ш X X X X X X X **■

т К х Б? х X х X X X шш

к* X х х х X X х х шн

т X х К ш. х х х х шт

т * * * * * № х *

т X X X X х X х х х

т X X х х к X х X к шт

т X X ш х х х X х х тш

т х X X х х х х X х

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

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Антонов, Александр Сергеевич, 1999 год

Литература

[1] А. С. Антонов. Технологические аспекты адаптации последовательных программ для массивно-параллельных компьютеров// В сборнике "Научная адаптация слушателей ВКШ". Изд-во МГУ, 1995. С. 19-38.

[2] А. С. Антонов, Вл. В. Воеводин. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных Супер-ЭВМ// Программирование, 1996 г. №- 4. С. 37-51.

[3] A. S. Antonov, VI. V. Voevodin. Application of the V-Ray Technology for Optimization of the TRFD and FL052 Perfect Club Benchmarks to CRAY Y-MP and CRAY T3D Supercomputers// Proc. of EUROMICRO-96 conference. Prague, Czech Republic, 1996.

[4] А. С. Антонов, Вл. В. Воеводин, В. М. Репин. Алгоритм канонизации описания структуры программ в рамках линейной модели// В сборнике НИВЦ МГУ "Численные методы анализа" (под ред. Н. С. Бахвалова, В. В. Морозова). Изд-во МГУ, 1997. С. 106-119.

[5] А. С. Антонов. Современные методы межпроцедурного анализа программ// Программирование, 1998 г. N° 5 С. 3-14.

[6] А. С. Антонов, Вл. В. Воеводин. Новый подход к построению методов межпроцедурного анализа программ// Материалы международной конференции УкрПРОГ-98. Киев, Украина, 1998. С. 77-84.

[7] В. А. Вальковский и др. Элементы параллельного программирования. (Под ред. В. Е. Котова) М.: "Радио и связь", 1983.

[8] В. В. Воеводин. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.

[9] В. В. Воеводин. Информационная структура алгоритмов// М.: Изд. Моск. унта, 1997. 139 с.

[10] Вл. В. Воеводин. Теория и практика исследования параллелизма последовательных программ// Программирование. 1992. N- 3. С. 38-53.

[11] Вл. В. Воеводин. Статический анализ и вопросы эффективной реализации программ// Вычислительные процессы и системы (Под ред. Г.И. Марчука), М.: "Физматлит", 1993. №9. С. 249-301.

[12] Вл. В. Воеводин Описание входных и выходных данных фрагментов программ// Вестник Московского университета. Серия 15. 1997. N° 1. С. 41-44.

[13] Вл. В. Воеводин Аналитические и инструментальные средства исследования тонкой структуры программ// Диссертация на соискание ученой степени доктора физ.-мат. наук. 1997. 207 с.

[14] Вл. В. Воеводин Легко ли получить обещанный гигафлоп?// Программирование. 1995. №■ 4. С. 13-23.

[15] В. А. Евстигнеев, В. А. Серебряков Методы межпроцедурного анализа (об-зор)Ц Программирование. 1992. N° 3. С. 4-15.

[16] Д. Кук. Высокопроизводительные машины и их компиляторы// Системы параллельной обработки (Пер. с англ. Д. Ивенс) М.: "Мир", 1985. С. 194-216.

[17] Под ред. С. Фернбаха. СуперЭВМ. Аппаратная и программная реализация// М.: "Радио и связь", 1991.

[18] Р. Хокни, К. Джессхоуп. Параллельные вычисления// М.: "Радио и связь", 1986.

[19] J. R. Allen, К. Kennedy. Automatic Loop Interchange/ j SIGPLAN Notices. Vol. 19. №■ 6. pp. 233-246. 1984.

[20] R. Allen, K. Kennedy. Automatic Translation of FORTRAN Programs to Vector Form// ACM Transactions on Programming Languages and Systems. Vol. 9. N- 4. pp. 491-542. October 1987.

[21] V. Balasundaram, K. Kennedy A Technique for Summarizing Data Access and Its Use in Parallelism Enhancing Transformation// In Proceedings of the 1989 ACM SIGPLAN Conference on Programming Language Design and Implementation. Vol. 24. №■ 7. pp. 41-53. Portland, Orgen. June 1989.

[22] W. J. Blume. Success and limitations in automatic parallelization of the Perfect Benchmarks programs// CSRD Tech. Rep. 1992. N- 1249.

[23] W. Blume, R. Doallo, R. Eigenmann, J. Grout, J. Hoeflinger, T. Lawrence, J. Lee, D. Padua, Y. Paek, B. Pottenger, L. Rauchwerger, P. Tu Parallel programming with Polaris// Computer. Vol. 29. №■ 12. pp. 78-82. December 1996.

[24] M. Burke, R. Cytron Interprocedural Dependence Analysis and Parallelisation// ACM SIGPLAN'86 Symposium on Compiler Construction. Vol. 21. №■ 7. pp. 162175. June 1986.

[25] D. Callahan, K. Kennedy Analysis of Interprocedural Side Effects in a Parallel Programming Environment// Journal of Parallel and Distributed Computing. Vol. 5. pp. 517-550. Oktober 1988.

[26] D. Callahan A Global Approach to Detection of Parallelism// PhD thesis. Rice University. Сотр. Sci. Tech. Rep. TR87-50. March 1987.

A. Carle, M. W. Hall, J. Mellor-Crummey, R. Rodriguez FIAT: A Framework for Interprocedural Analysis and Transformation// Rice University. CRPC Tech. Rep. TR95522-S. March 1995.

D. Callahan, K. D. Cooper, R. T. Hood, K. Kennedy, L. Torczon ParaScope: A Parallel Programming Environment/ / The International Journal Supercomputer. Vol. 2. № 4. pp. 84-99. 1988.

S.-E. Choi An Overview of Compiler Techniques for Interprocedural Array Section Analysis// University of Washington. Tech. Rep. 95-11-06. November 1995.

B. Creusillet, F. Irigoin Interprocedural Array Region Analyses// Eighth International Workshop on Languages and Compilers for Parallel Computing, pp.4-1 to 4-15. Colombus (Ohio), USA. August 1995.

B. Creusillet IN and OUT Array Region Analyses// Fifth Workshop on Compilers for Parallel Computers. Malaga, Spain. June 1995.

G .Cybenko, L. Kipp, L. Pointer, D. Kuck. Supercomputer performance evaluation and the Perfect Benchmarks// CSRD Tech. Rep. 1990. № 965.

G. Danzig, B. C. Eaves. Fourier-Motzkin elimination and its dual// Journal of Combinatorial Theory. 1973. A(14). P. 288-297.

C. M. Grassl. Parallel performance of applications on supercomputers// Parallel Computing. 1991. № 17. P.1257-1273.

P. Havlak, K. Kennedy An Implementation of Interprocedural Bounded Regular Section Analysis// IEEE Transactions on Parallel and Distributed Systems. Vol. 2. N- 3. pp. 350-360. July 1991.

F. Irigoin, P. Jouvelot, R. Triolet Semantical Interprocedural Parallelisation: An Overview of the PIPS Project// ACM International Conference on Supercomputing, ICS'91. Cologne, Allemagne. June 1991.

L. Lamport The Parallel Execution of Do Loops// Communications of the ACM. Vol. 17. № 2. pp. 83-93. 1974.

D. E. Maydan, J. L. Hennessy, M. S. Lam. Efficient and Exact Data Dependence Analysis// Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation.

C. D. Polychronopoulos, M. B. Gircar, M. R. Haghighat, C. L. Lee, B. P. Leung,

D. A. Shouten The Structure of Parafrase-2: Advanced Parallelizing Compiler for C and Fortran// Languages and Compilers for Parallel Computing. Pitman Publ. London. 1990.

[40] L. Pointer. Perfect: Performance Evaluation for Cost-Effective Transformations Report 2// CSRD Tech. Rep. 1990. N964.

[41] W. Pugh. A Practical Algorithm for Exact Array Dependence Analysis// Communications of the ACM. Vol. 35, m 8. pp. 102-114. August 1992.

[42] S. Richardson, M. Ganapathi Interprocedural Analysis Useless for Code Optimization// Stanford University. Tech. Rep. CSL-TR-87-342. November 1987.

[43] R. W. Scheifler An Analysis of Inline Substitution for a Structured Programming Language// Communications of the ACM. Vol. 20. N- 9. September 1977.

[44] D. A. Schouten An Overview of Interprocedural Analyses Techniques for High Performance Parallelizing Compilers// Univ. of Illinois at Urbana-Champaign. CSRD Tech. Rep. 1005. May 1990.

[45] P. Tang Exect Side Effects for Interprocedural Dependence Analysis// Australian National University. Tech. Rep. TR-CS-92-15. November 1992.

[46] R. Triolet, F. Irigoin, P. Feautrier Direct Parallelism of Call Statements// In Proceedings of the ACM SIGPLAN'86 Symposium on Compiler Construction. SIG-PLAN Notices. Vol. 21. m 7. pp. 176-185. June 1986.

[47] M. Wolfe Advanced Loop Interchanging// IEEE Proc. of ICCP. pp. 536-543. 1986.