Дипломная работа: Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления
Разработка параллельного ПО является очень трудоемкой задачей из-за сложности определения скрытого параллелелизма, возможности внесения некорректного, нарушающего семантику программы, ложного параллелелизма, и из-за необходимости учитывать большое число факторов, влияющих на конечную производительность программы. Автоматические средства разработки параллельных продуктов и распараллеливания готовых последовательных предоставляют возможность существенно облегчить этот процесс.
Анализ последовательной программы
Одной из первых задач, возлагаемых на автоматический распараллеливатель программ, является анализ исходной последовательной программы с целью сбора максимального количества необходимой для распараллеливания информации об ее структуре. Данные, полученные на этом этапе, в совокупности с результатами работы блока динамического анализа являются основой дальнейшей деятельности системы.
Задача статического анализа исходной программы может быть условно разделена на два этапа:
1) трансляция текста программы в некоторое внутреннее представление и построение структур, отражающих последовательность работы программы и используемые в ней данные;
2) поиск возможных вариантов распараллеливания с выбором оптимального и определение «узких» участков, препятствующих распараллеливанию.
Рассмотрим несколько более подробно 1-й этап, поскольку решение связанных с ним задач является темой данной дипломной работы. Внутреннее представление программы необходимо для возможности ее анализа независимо от исходного последовательного языка, т.е. оно является точным переложением текста программы, записанным в терминах, понятных системе. Кроме того, оно должно быть достаточным для последующей генерации текста параллельной программы на целевом языке. После создания такого представления, необходимо подняться на такой уровень абстракции, который позволит исследовать алгоритм программы с требуемой точки зрения. Иными словами, надо построить структуры данных, содержащих всю программу в приемлемом для последующего анализа виде, расширенные для возможности хранения и обработки результатов работы других блоков распараллеливателя.
1. Система автоматического распараллеливания
Данная дипломная работа является частью проекта разработки системы автоматического распараллеливания программ на языке Fortran77. Система состоит из нескольких функциональных блоков, каждый из которых реализует один или более этапов построения параллельной программы, сохраняющей семантику заданной последовательной программы. Фиксированный интерфейс обмена данными между ними позволяет производить независимую модификацию каждого блока. Таким образом, система может развиваться в сторону дальнейшего увеличения ее интеллектуальности в принятии решений о возможности распараллеливания входной программы и поиска наиболее эффективных вариантов ее преобразования.
1.1 Назначение системы
Представляемая система предназначена для распараллеливания программ, написанных на языке Fortran77. Использование этого языка как основного при разработке научных и инженерных приложений на протяжении многих лет привело к образованию большого числа программ, необходимость в которых сохраняется и сегодня. Автоматическая трансляция накопившегося последовательного кода в параллельный позволит использовать новые архитектурные возможности при существенно меньших по сравнению с повторной реализацией затратах. Формируемый системой отчет о принятых в процессе распараллеливания решениях может служить основой рекомендаций по модификации исходного кода с целью достичь наиболее эффективного результата.
Второй аспект применения – разработка параллельного ПО на основе Fortran77. Достоинство такого подхода заключается в использовании привычного языка программирования и передаче системе распараллеливания обязанностей по оценке эффективности реализации алгоритмов с точки зрения параллельного выполнения.
1.2 Схема работы системы автоматического распараллеливания
На вход системы автоматического распараллеливания (САР) подается текстовый файл с программой на Fortran77. Она должна, во-первых, быть правильной с точки зрения языка, и, во-вторых, удовлетворять накладываемым системой ограничениям.
Первый шаг – разбор текста средствами библиотеки Sage++, в результате которого образуется файл с внутренним представлением исходной программы.
Задача блока INLINE-подстановки процедур САР заключается в модификации структуры исходной программы с целью привести ее к виду, облегчающему дальнейший анализ и повышающему его точность. В результате его работы образуется файл с внутренним представлением программы, состоящей только из главного модуля, в котором все вызовы подпрограмм заменены их телами. Если исходная программа не содержит процедур, пользователь может не использовать этот блок.
Внутреннее представление без вызовов процедур поступает на вход двух блоков. Первый – блок статического анализа. Его задачей является статическое построение расширенного графа потока управления программы и некоторых вспомогательных структур данных.
Блок подготовки программы для динамического анализа также получает внутреннее представление. Его назначение создание версии программы для последующей обработки блоком динамического анализа.
Задача блока динамического анализа дополнение графа управления данными, полученными при выполнении программы в его присутствии. Кроме того, на этом шаге некоторые результаты статического анализа могут быть скорректированы.
Следующий этап – поиск оптимального распределения вычислений и данных между узлами вычислительной сети. Анализ производится на основе информации о возможности распараллеливания тех или иных участков программы, полученной на предыдущих шагах.
Задача учета затрат на доступ к удаленным данным, на перераспределение данных в процессе выполнения программы и т.п. решается осуществлением запросов к блоку оценки времен коммуникаций.
Следующий блок производит модификацию внутреннего представления с целью реализовать выбранный вариант распараллеливания.
Задача блока клонирования процедур заключается в выделении во внутреннем представлении переработанной программы процедур, их оформлении и вставки соответствующих операторов вызова. Пользователь может не использовать функции этого блока, если считает это целесообразным.
Далее на основе результирующего внутреннего представления происходит генерация текста программы на FortranDVM.
1.3 Постановка задачи дипломной работы
Задачей дипломной работы является реализация следующих функций блоков САР:
- Статическое построение расширенного графа потока управления программы и сопровождающих его структур (блок №2);
- Экспорт данных в файлы для блока распределения вычислений и данных (блок №2);
- Чтение из файлов директив FortranDVM, сформированных блоком распределения, и соответствующая им модификация внутреннего представления программы (блок №7).
2. Создание внутреннего представления программы
Для программ, назначение которых заключается в анализе и обработке других программ, основным параметром является текст исходной программы. В отличие от параметров простых типов, такой сложно организованный параметр требует предварительного анализа с целью обеспечить возможность получения из него необходимой для решаемой задачи информации. И поскольку для большинства приложений такого рода доступа к входной программе на уровне символов в текстовом файле недостаточно, возникает задача перевода текста программы в некоторую структуру, отражающую его в виде законченных языковых конструкций – идентификаторов, типов, структур данных, операторов, управляющих конструкций и др. Иными словами, необходимо произвести разбор исходного текста – parsing. Однако в некоторых случаях этого недостаточно и для решения поставленных задач требуется подняться на более высокий уровень абстракции. Следовательно, встает вопрос о создании некоего высокоуровнего представления программы, отражающего специфику конкретной задачи.
2.1 Разбор исходного текста. Система Sage++
Первоочередной задачей на этапе создания внутреннего представления программы, написанной на некотором языке, является разбор исходного текста. В результате такого анализа должна быть доступна информация о порядке выполнения операторов программы с учетом использованных в ней языковых конструкций, нарушающих последовательный характер их выполнения – ветвления, безусловные переходы, циклы, обращения к подпрограммам, операторы прекращения выполнения программы и т.п. Несмотря на то, что для строго типизированных языков программирования анализ операторов объявления может дать полную информацию о константах, переменных и их типах, представляется существенным дополнением наличие таблиц типов и имен. Все перечисленные возможности предоставляет свободно распространяемая библиотека Sage++, разработанная в Иллинойском университете..
“Sage++ является попыткой предложить объектно-ориентированный инструментарий для построения систем обработки программ на языках Fortran77, Fortran90, C и C++. Sage++ предназначен для разработчиков, проводящих исследования в следующих областях: построение распараллеливающих компиляторов, средств анализа производительности и оптимизаторов исходного кода” [2].
Библиотека Sage++ реализована в виде иерархии классов C++, которые позволяют получить доступ к дереву разбора, таблице имен и таблице символов для каждого файла, входящего в исходное приложение. Классы объединены в пять семейств: “Проекты и файлы” – хранят информацию обо всех файлах приложения, “Операторы” – ссылаются на базовые операторы языков, “Выражения” – указывают на выражения, содержащиеся внутри операторов, “Символы” – определенные в программе идентификаторы, “Типы сопоставленные с каждым идентификатором и выражением типы. Библиотека обеспечивает средства как всестороннего изучения исходной программы, так и различной ее модификации – добавление к ней новых файлов, создание и изменение операторов, входящих в файлы, вставка и модификация содержащихся в операторах выражений и др. Рассмотрим основные возможности Sage++, представляющие для нас интерес в рамках первого аспекта.
Перед началом анализа программы необходимо создать и сохранить на диске Sage++-представления каждого входящего в ее состав файла специальной утилитой из пакета Sage++. После этого надо создать текстовый файл проекта со списком имен полученных файлов.
Для получения доступа к данным проекта существует класс SgProject:
SgProject(char *proj_file_name) - конструктор, proj_file_name - имя файла проекта;
int numberOfFiles() количество файлов в проекте;
SgFile &file(int i) i-й файл проекта.
Класс SgFile представляет файл, входящий в исходное приложение:
SgStatement *firstStatement() указатель на первый оператор файла;
SgSymbol *firstSymbol() указатель на первый элемент таблицы имен файла;
SgType *firstType() - указатель на первый элемент таблицы типов файла.
Каждый определенный в файле идентификатор содержится в таблице имен и представляется объектом одного из наследников класса SgSymbol:
int variant() тэг, определяющий класс символа;
int id() - уникальный номер символа в таблице ;
char *identifier() - текстовое представление символа
SgType *type() - тип символа;
SgStatement *declaredInStmt() - оператор объявления;
SgSymbol *next() - указатель на следующий элемент таблицы.
После выяснения тэга подлежащего анализу идентификатора можно при помощи соответствующей ему глобальной функции получить указатель на объект класса-наследника SgSymbol, содержащего специфические для этого идентификатора данные. Примерами таких производных классов могут служить:
SgVariableSymb – переменная программы;
SgConstantSymb - константа;
SgFunctionSymb - процедура, функция или главная программа.
С каждым идентификатором и выражением соотнесен его тип – скалярный или сложный, представленный объектом класса SgType или одного из его наследников:
int variant() - тэг типа, соответствующий либо скалярному типу, либо классу-наследнику;
int id() - уникальный номер типа в таблице типов;
SgType *baseType() - указатель на базовый тип для сложных типов;
SgType *next() – указатель на следующий элемент таблицы типов.
Пример производного от SgType класса SgArrayType, объект которого создается для каждого определенного в программе массива. Основные члены этого класса:
int dimension() - размерность массива;
SgExpression *sizeInDim(int i) - выражение, характеризующее длину по i-му измерению.
Каждый файл программы разбит на операторы, для представления которых используется класс SgStatement и его производные:
int variant() - тэг оператора;
int id() - уникальный номер оператора;
int lineNumber() - номер строки в исходном тексте;
SgExpression *expr(int i) - i-е выражение, входящее в оператор (i = 0,1,2);
SgStatement *lexNext() - следующий в лексическом порядке оператор;
SgStatement *lexPrev() - предыдущий в лексическом порядке оператор;
SgStatement *controlParent() - охватывающий управляющий оператор;
SgStatement *lastNodeOfStmt() – для операторов, не являющихся листом дерева разбора, возвращает указатель на последний оператор поддерева.
Аналогично другим классам Sage++ тэг объекта SgStatement позволяет определить класс-потомок SgStatement, соответствующий рассматриваемому оператору. В каждом из них существуют данные и методы, специфические для представляемого этим классом оператора. Эти классы объединены в несколько семейств:
· заголовочные операторы;
· операторы объявления;
· управляющие операторы;
· исполняемые и другие операторы.
Примеры классов, относящихся к этим семействам.
Заголовочные:
- SgProgHedrStmt – заголовок программы (Fortran);
- SgProcHedrStmt – заголовок подпрограммы (Fortran);
- SgBlockDataStmt – оператор блока данных (Fortran).
Операторы объявления:
- SgVarDeclStmt – оператор объявления переменной;
- SgParameterStmt – оператор объявления констант (Fortran);
- SgImplicitStmt – оператор Implicit (Fortran).
Управляющие:
- SgForStmt – цикл FOR;
- SgIfStmt - оператор ветвления If-Then-Else (Fortran), if (C);
- SgLogIfStmt - оператор логического If (Fortran);
- SgArithIfStmt - оператор арифметического If (Fortran).
Исполняемые и другие:
- SgAssignStmt - оператор присваивания (Fortran);
- SgCallStmt - оператор Call (Fortran);
- SgContinueStmt - оператор Continue;
- SgControlEndStmt - обозначает конец одного из основных блоков (напр. ENDIF);
- SgReturnStmt - оператор Return;
- SgGotoStmt - оператор Goto.
Большинство операторов программы содержат некоторые выражения. Класс SgExpression является базовым для выражений всех видов:
int variant() - тэг вида выражения;
SgExpression *lhs() - левое поддерево выражения;
SgExpression *rhs() - правое поддерево выражения;
В отличие от иерархии классов, порождаемой SgStatement, не вводится подкласс для каждой операции, находящейся в корне дерева разбора выражения. Основные бинарные операции, такие, как стандартные арифметические, идентифицируются только тэгом. Листья дерева могут иметь собственные классы, например:
