НАУЧНЫЙ РУКОВОДИТЕЛЬ:
Доктор физико-математических наук
Воеводин Владимир Валентинович
ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:
Доктор технических наук
Арушанян Олег Багратович
Доктор физико-математических наук
Ластовецкий Алексей Леонидович
ВЕДУЩАЯ ОРГАНИЗАЦИЯ:
Институт Вычислительной Математики РАН
Защита диссертации состоялась ``4'' июня 1999 г. в 15 часов на заседании диссертационного совета К.053.05.84 при Московском Государственном Университете им. М.В. Ломоносова по адресу:
119899, Москва, Воробьевы горы, НИВЦ МГУ, конференц-зал.
С диссертацией можно ознакомиться в библиотеке НИВЦ МГУ.
Автореферат разослан ``28'' апреля 1999 г.
Ученый секретарь
диссертационного совета,
кандидат физико-математических наук Суворов В.В.
Актуальность темы. В последнее время все более широкое распространение во всем мире получают супер-ЭВМ, а элементы параллелизма понемногу проникают во все типы компьютеров вплоть до персональных. Поэтому задача создания эффективных параллельных программ, а также адаптации для параллельных компьютеров огромного количества уже существующих последовательных приложений становится все более важной.
Если фиксирован метод решения конкретной прикладной проблемы и недоступны эффективные языковые или библиотечные средства ее решения на конкретном параллельном компьютере, то единственным способом достижения максимально возможной производительности является реструктуризация программы, описывающей данный метод. Ее целью должен быть выбор такого порядка вычислений, который сохранял бы эквивалентность получаемых результатов, но был бы при этом наиболее согласован с требованиями архитектуры компьютера. Такая работа обычно возлагается на пользователя, так как штатные компиляторы на реальных программах часто не дают удовлетворительных результатов.
Для помощи пользователям создаются автономные программные системы. В разработку теории, лежащей в основе создания систем статического анализа информационной структуры программ, внесли свой вклад многие ученые во всем мире, такие как А.П. Ершов, В.А. Серебряков, А.А. Летичевский, В.Н. Касьянов, В.В. Воеводин, M. Wolfe, W. Pugh, K. Kennedy, M. 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 C90, CRAY T3D, IBM SP2 и других). Значительное ускорение, полученное на анализировавшихся программах, реально использующихся у нас в стране и за рубежом, подтверждает практическую применимость и эффективность данного подхода.
Апробация работы. Основные положения работы обсуждались на научно-исследовательских семинарах в НИВЦ МГУ и на научно-исследовательском семинаре по автоматизации программирования на факультете ВМиК МГУ.
Результаты диссертации докладывались на Ломоносовских чтениях в МГУ (1995, 1997 годы), на всероссийской научной конференции ``Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов'' (Абрау-Дюрсо, 1998 год), опубликованы в трудах 22-й международной конференции ``Euromicro Conference'' (Prague, 1996) и в трудах первой международной научно-практической конференции по программированию УкрПРОГ'98 (Киев, 1998 год).
Публикации. По теме диссертации опубликовано 6 статей.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы (47 наименований); включает 37 рисунков и 7 таблиц.
Во введении приводится общая характеристика работы и обзор содержания диссертации.
Первая глава работы посвящена обзору существующих методов статического анализа программ и межпроцедурного анализа. Сначала описываются методы анализа арифметических выражений и ациклических участков программ. Эти методы давно и хорошо изучены, однако их сложно реализовывать, они обладают ограниченной применимостью, и с их помощью практически невозможно получить существенное ускорение программ.
Основной ресурс параллелизма в программах приходится на циклические конструкции. На их анализе основывается следующая группа методов: модификация dataflow-анализа, анализ возможных перестановок циклов и анализ пространства итераций циклов. В качестве методов анализа пространства итераций цикла рассматриваются широко известные методы гиперплоскостей, координат, параллелепипедов и пирамид. Эти методы намного более содержательные и широко используются на практике. Основной недостаток всех рассмотренных методов исследования циклов - ориентация только на циклические фрагменты с заранее заданными свойствами и структурой. При этом фрагменты с другой структурой (а их, как показывает статистический анализ, очень много) исключаются из рассмотрения.
В качестве более общего средства для проведения статического анализа структуры программ рассматриваются графовые модели. Рассмотрение ограничивается рамками операционного подхода, который предполагает, что вершинами графа являются некоторые операции программы. Содержание операций, их вычислительная мощность и смысловая нагрузка дуг определяют тип графа. Показывается взаимосвязь и различия операционных и информационных графов, а также схемных моделей и историй реализации. Из всего множества графовых моделей для всей последующей работы выбирается информационная история реализации программ (называемая также графом алгоритма).
Далее в работе вводится формализованное определение графа алгоритма,
введенное в работах В.В. Воеводина и Вл.В. Воеводина, и
фиксируется класс исследуемых программ, называемый линейным классом.
Формулируются условия, при выполнении которых для анализируемой программы
возможно построение параметрического описания графа алгоритма в следующем
виде: для каждого входа каждого оператора указывается конечное множество
троек (DN, DI, F), где DN - линейный многогранник в
пространстве WN внешних переменных программы, значения которых
на момент построения графа неизвестны; DI - линейный многогранник
в пространстве итераций WI, размеры и положение которого могут
зависеть от точек многогранника DN; функция F О Zp линейная
и имеет вид F = Jx+FN + S, где N О Zk - это вектор внешних
переменных программы, J О Zp x n,
F О Zp x k -
целочисленные матрицы, а S О Zp - вектор свободных членов. Областью
определения функции F является многогранник DI, значениями функции
являются точки пространства итераций, причем точка x задает конечную
вершину дуги, соответствующей информационной зависимости, а выражение
Jx+ FN + S - начальную. Для программ, не принадлежащих линейному
классу, возможно построение минимального (в рамках статического подхода)
расширения графа алгоритма.
Далее приводятся формулировки критериев, которые на основании параметрического описания определяют, обладает ли фрагмент программы полезными для анализа и оптимизации структуры фрагмента свойствами (такими как свойство PARDO для циклов, возможность перестановки циклов, возможность распределения циклов и другие).
В следующем разделе приведен обзор существующих методов межпроцедурного анализа. Методы межпроцедурного анализа с точностью до имен массивов не рассматриваются, поскольку они хорошо известны и явно недостаточны для детального анализа программ. Для дополнительного анализа inline-подстановки (подстановки тела процедуры на место вызова) приводятся данные статистического анализа шести достаточно больших реальных программ. Они показывают, что inline-подстановка только листовых процедур (процедур, не содержащих вызовов) приводит к росту размера кода на несколько порядков, что делает его анализ практически не реальным.
Далее вводятся понятия READ/WRITE и IN/OUT областей массивов, которые соответствуют областям массивов, считываемым/обновляемым в анализируемом фрагменте или являющимся входными/выходными для этого фрагмента. Все методы получения READ/WRITE областей делятся на неточные и точные. Неточные методы проще, но, в отличие от точных, описывают только некоторую аппроксимацию необходимой области. Напротив, точные методы могут потребовать много памяти и значительного времени для анализа программ, но описывают области максимально детально. В некоторых случаях могут использоваться комбинированные методы, например, приближенное описание объединения точно описанных областей.
Среди неточных методов рассматриваются: метод ограниченных регулярных секций, метод описания с помощью триплетов, метод простых секций, метод описания в виде выпуклой оболочки, среди точных - подход Бурке-Сайтрона и построение совокупного образа. Для всех методов приводится описание алгоритмов построения пересечения и объединения получаемых областей. Каждый метод иллюстрируется также небольшим примером описания READ/WRITE областей некоторого фрагмента программы. Все описанные методы сравниваются по требуемому для реализации объему памяти и по сложности операций объединения и пересечения получаемых областей.
Далее описывается алгоритм получения IN/OUT областей на основе READ/WRITE областей, который предложили B. Creusillet и F. Irigoin. Этот алгоритм, однако, обладает ограниченной применимостью.
Во второй главе работы описан предложенный алгоритм получения канонической формы параметрического описания графа алгоритма, позволяющий избавиться от избыточности и нерегулярности в его описании. Проводится также исследование математических объектов, на основе которых строится параметрическое описание графа алгоритма после канонизации.
В определение канонической формы параметрического описания графа алгоритма фрагмента входят следующие требования:
После этого имеющиеся в описании области равенства используются для исключения переменных, что позволяет уменьшить размерность рассматриваемой области. Это приводит к упрощению и ускорению всех последующих действий алгоритма. Приводимый в работе метод исключения переменных из равенств, в отличие от обычного метода (домножения коэффицентов ограничения на коэффициент из другого ограничения) позволяет решать задачу определения непустоты области не только в рациональном, но и в целочисленном смысле.
После того как проведены исключения переменных из равенств, описания областей состоят только из неравенств. Для системы линейных неравенств с целочисленными коэффициентами решается задача определения существования целочисленного решения.
Сначала проверяются несложные эвристики, позволяющие решить задачу для областей простого вида. Все проверяемые эвристики связаны с анализом областей, в описание которых входят пары параллельных гиперплоскостей. Такие области исключительно часто встречаются в описаниях графа алгоритма для реальных программ. Проверка эвристик не позволяет решить задачу определения целочисленной непустоты в общем случае, однако она крайне полезна для увеличения эффективности алгоритма при практическом применении.
Если с помощью эвристик задача не решена до конца, то проводятся исключения Фурье-Моцкина. Прямой ход метода позволяет определить рациональную пустоту или непустоту исходной области. Кроме того, если для последней исключаемой при помощи этого метода переменной целочисленной точки нет, то можно утверждать, что и вся область целочисленно пуста, и в таком случае задача определения целочисленной пустоты будет решена до конца. Однако если для последней исключаемой переменной целочисленная точка есть, то это не гарантирует, что исходная область целочисленно непуста.
После этого проводятся исключения Омега-теста, которые позволяют определить целочисленную непустоту в большинстве реальных случаев. Если же и эти исключения не решают задачу, то остается проверить наличие целочисленных точек между границами областей, получающихся при исключениях Омега-теста и исключениях Фурье-Моцкина. Эта проверка осуществляется путем перебора гиперплоскостей, параллельных граням исходной области и получаемых при добавлении целого числа к свободному члену. Перебор гиперплоскостей позволяет даже в самых плохих случаях (исключительно редко встречающихся на практике) гарантировать точное решение задачи определения целочисленной пустоты или непустоты области.
На всех шагах алгоритма производится разбиение области DN в пространстве внешних переменных WN на подобласти, в каждой из которых выполняется или не выполняется проверяемое на данном шаге условие. Работа алгоритма прекращается тогда, когда будут проверены все полученные подобласти области DN. Количество шагов алгоритма конечно, на каждом шаге число подобластей области DN увеличивается не более, чем в два раза, поэтому алгоритм также конечен.
После получения списка целочисленно непустых областей нужно для каждой из них получить неизбыточное описание. Алгоритм проверки избыточности ограничений существенно опирается на то, что область исследуется на пустоту/непустоту в целочисленном смысле. Это позволяет разбить область на две непересекающиеся подобласти, в одной из которых анализируемое ограничение является избыточным, а в другой нет.
Для завершения канонизации описания полученных многогранников нужно гарантировать, что в каждой из целочисленно непустых областей с неизбыточным описанием ни одно ребро не стягивается в точку при изменении значений внешних переменных. Это условие эквивалентно тому, что координаты любой вершины многогранника должны при всех допустимых значениях внешних переменных строго удовлетворять всем ограничениям исследуемой области, не участвующим в образовании данной вершины. При проверке данного условия может производиться новое подразбиение области DN на две, в одной из которых проверяемая вершина принадлежит многограннику, а в другой нет.
В следующем разделе работы исследуются математические свойства канонической формы параметрического описания графа алгоритма. Приводятся алгоритмы, реализующие основные операции над областями DI: пересечение, разность и объединение. Пересечение строится просто как набор всех ограничений исходных областей. Алгоритм для построения разности областей для каждого ограничения вычитаемой области использует разбиение пространства WI на две (в случае ограничения-неравенства) или три (в случае ограничения-равенства) части, базирующееся на том, что в результирующей области важны только целочисленные точки. Объединение областей реализуется через разность.
Далее доказывается ряд теорем, показывающих геометрические свойства областей DI, а также свойства дуг, задаваемых функциями F на этих областях. На основании этих теорем можно получать многие полезные свойства программ. В качестве примера для некоторого класса фрагментов программ формулируются условия, гарантирующие, что эти фрагменты не содержат параллелизма, а значит, должны выполняться строго последовательно.
В третьей главе работы описывается алгоритм проведения межпроцедурного анализа программ, опирающийся на каноническую форму параметрического описания графа алгоритма. Целью межпроцедурного анализа является получение описания входных и выходных данных процедуры с точностью до отдельных элементов массивов. Наличие такого описания позволит проводить статический анализ фрагментов программ, содержащих вызовы процедур.
Для получения описаний областей входных и выходных данных процедуры используется метод, основанный на применении разработанной техники построения параметрического описания графа алгоритма. Суть этого метода заключается в том, чтобы получить описание нужного множества входных или выходных данных в пространстве элементов массива средствами анализа пространства итераций. Очень просто по параметрическому описанию графа алгоритма получить множество точек пространства итераций, потребляющих входные для исследуемого фрагмента данные. Дальнейшая задача состоит в том, чтобы построить отображение полученной области пространства итераций в пространство элементов массива.
Для этого в конец анализируемой процедуры вставляется специально сконструированный фрагмент, который с помощью эквивалентных преобразований текста делается безусловно достижимым из каждой точки исходного кода. Далее при некоторых дополнительных предположениях строится элементарный граф алгоритма. Показывается, что в результате этой процедуры получается точное описание входных данных фрагмента по конкретному входу. После этого остается суммировать полученные области по всем входам. Аналогично решается и задача получения выходных данных фрагмента.
После получения областей входных и выходных данных процедуры необходимо для каждого вызова получить их описание в терминах фактических параметров. Для этого сначала записывается условие того, что элементы массивов, представляющих соответствующие формальный и фактический параметр, ссылаются на одну и ту же ячейку памяти. К этому условию добавляются условия из описаний массивов, в результате чего получается неявное описание исходной области в терминах фактических параметров.
Для получения явного описания области в терминах фактических параметров необходимо получить проекцию области, задаваемой составленной системой, на пространство элементов массива, являющегося фактическим параметром. Для этого из полученной системы исключаются переменные, соответствующие пространству элементов массива, являющегося формальным параметром. Такое исключение делается методом Фурье-Моцкина при условии, что все равенства и неравенства системы линейны.
Тот же самый метод с минимальными модификациями применим и для случая, когда два массива соответствуют друг другу в областях общей памяти или выравниваются при помощи оператора EQUIVALENCE языка Фортран.
Далее в работе проводится исследование возможности выполнения межпроцедурного анализа реальных программ. Сначала рассматривается случай, редко встречающийся на практике, когда в составленной системе неравенств присутствует нелинейность. Часто в подобных случаях удается составить ограничения на внешние переменные, при выполнении которых данная нелинейность пропадает. В этой области пространства внешних переменных межпроцедурный анализ возможен.
Результаты статистического исследования обосновывают применимость описанных алгоритмов межпроцедурного анализа. Даже оценка снизу на число анализируемых вызовов показывает, что для реальных программ в подавляющем большинстве случаев (для всех аргументов более чем 96% проанализированных вызовов) с помощью данного подхода действительно можно описать множества входных и выходных данных.
На основе использования описанных алгоритмов и опыта анализа и оптимизации больших программных комплексов разработана методика проведения межпроцедурного анализа программ. Она предполагает движение по графу вызовов анализируемого проекта от листовых вершин к корневой. На каждом шаге строится описание входных и выходных данных анализируемой программной единицы, затем пересчет их в терминах фактических параметров, после чего и вызывающая процедура становится анализируемой по общей методике. После достижения корневой вершины информация о входных и выходных данных вызываемых процедур может быть передана в обратном направлении - от вызывающих процедур к вызываемым, например, для решения задачи совмещения формальных параметров.
В конце этой главы последовательность действий алгоритма межпроцедурного анализа прослежена на иллюстративном примере.
Четвертая глава посвящена конкретным примерам исследования структуры и оптимизации реальных программ. Показано, как с использованием методов построения и анализа стандартной канонической формы параметрического описания графа алгоритма с использованием алгоритмов межпроцедурного анализа исследовать структуру больших программных комплексов. За счет оптимизации, основанной на результатах такого исследования, удается получить существенное ускорение различных программ на разных типах современных параллельных компьютеров.
Программы LIU_FTC и GCMA - реальные большие программы, первая из которых моделирует устойчивость плазмы в установках управляемого термоядерного синтеза (факультет ВМиК МГУ), а вторая предназначена для моделирования глобальных изменений климата (ИВМ РАН). Их оптимизация производилась для векторно-конвейерного компьютера CRAY Y-MP C90, и именно применение методов межпроцедурного анализа позволило достичь на обеих программах существенного ускорения.
Другая программа, FLO52 из широко известного пакета Perfect Club Benchmarks, представляет собой упрощенный вариант реализации одной из задач вычислительной гидродинамики. Она часто используется в качестве теста для определения реальной производительности параллельных компьютеров. Эта программа изначально была написана для векторно-конвейерного компьютера, поэтому наиболее интересно было попытаться оптимизировать ее для существенно другой архитектуры - массивно-параллельного компьютера CRAY T3D. При этом пришлось решать задачи, характерные для оптимизации программ для компьютеров с распределенной памятью (такие как выбор распределения данных и итераций между процессорами), но и в этом случае без применения межпроцедурного анализа обойтись было бы невозможно. На этой программе также было получено существенное ускорение, и, что может быть еще более важно, показано, что при увеличении размеров сетки, на которой производится вычисление, полученная параллельная программа становится хорошо масштабируемой. Так, если ускорение малого варианта программы (размер вычисляемой области X x Y) наблюдается при увеличении числа процессоров только до 32, то для среднего варианта (область 2X x 2Y) и для большого варианта (область 4X x 4Y) ускорение наблюдается при увеличении числа процессоров до 64 и 128 соответственно.
В заключении формулируются основные результаты работы.
Основные результаты диссертации отражены в следующих работах: