Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

В дипломной работе рассматриваются задачи, связанные с технологией автоматического распараллеливания программ.

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

Вторая часть содержит описание проекта разработки системы автоматического распараллеливания программ на языке Fortran77, частью которого является данная дипломная работа.

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

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

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

• Введение 4
• 1. Система автоматического распараллеливания. 11
• 1.1 Назначение системы. 11
• 1.2 Схема работы системы автоматического распараллеливания. 12
• 1.3 Постановка задачи дипломной работы. 14
• 2. Создание внутреннего представления программы. 15
• 2.1 Разбор исходного текста. Система Sage++. 15
• 2.2 Внутреннее представление программы высокого уровня. 19
• 2.3 Расширенный граф управления. Вспомогательные структуры. 20
• 3. Построение расширенного графа управления. 24
• 3.1 Ограничения на входную программу. 24
• 3.2 Описание классов. 24
• 3.3 Алгоритмы. 30
• Заключение. 35
• Библиография. 36
• Приложение. 37

Введение

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

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

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

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

Параллельное программирование привносит дополнительный уровень сложности: если мы станем программировать на низком уровне, не только резко увеличится количество инструкций по сравнению с последовательной программой, но и придется подробно распределять задания между, возможно, тысячами процессоров, и координировать миллионы межпроцессорных обменов. Таким образом, модульность можно назвать одним из основных требований к параллельному ПО. Поскольку большинство существующих алгоритмов ориентировано на однопроцессорные системы, очевидна необходимость при разработке новых алгоритмов учитывать особенности одновременного выполнения многих операций: параллельность - неотъемлемое требование к алгоритмам, реализуемым в параллельном ПО. Постоянное увеличение количества процессоров в параллельных компьютерах приводит нас к выводу, что программы, рассчитанные на фиксированное число CPU, равно как и программы, предназначенные для выполнения на одном компьютере, нельзя считать приемлемыми. Следовательно, мы можем к списку требований добавить расширяемость - “эластичность” к увеличению числа процессоров, на которых выполняется программа. Если все параллельные вычислительные системы классифицировать по способу организации доступа к памяти, то можно выделить две группы: системы с общей памятью - каждый процессор (вычислительный узел) имеет непосредственный доступ к запоминающему устройству, и системы с распределенной памятью - каждый узел имеет отдельное ЗУ. Во 2-м случае обмены данными требуют достаточно высоких накладных расходов, и если для мультипроцессорных компьютеров доступ к данным другого процессора может потребовать в 10 - 1000 раз больше времени, чем к своим, то для сетевых распределенных систем порядок может быть намного выше. В связи с этим, к параллельным алгоритмам и программам предъявляется также требование локальности - оптимальное с точки зрения расходов на межпроцессорные коммуникации распределение данных.

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

Модель Message Passing, вероятно, является сегодня наиболее распространенной. В этой модели программа также создает набор задач, каждая из которых содержит локальные данные, и идентифицируется уникальным именем. Задачи могут передавать и принимать сообщения для\от именованной задачи. Таким образом, рассматриваемая модель представляет собой лишь сокращенную версию модели задача/канал - отличие только в механизме передачи данных. Однако на практике большинство message-passing систем при старте программы создают фиксированное количество одинаковых задач и не позволяют создавать или уничтожать задачи во время выполнения. Т.е. эти системы фактически реализуют модель SPMD - “одна-программа-много-данных”, в которой все задачи выполняют одну и ту же последовательную программу над разными данными.

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

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

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

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

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

расширенный граф управления;

список циклов программы;

таблица символов программы.

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

Типы блоков:

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

Цикл. Представляет циклы программы.

Ветвление. Соответствует условным операторам программы.

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

Отношение между двумя блоками может двух типов:

1) второй блок выполняется сразу после первого;

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

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

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

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

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

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

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

- 1-я ссылка вправо

- 2-я ссылка вправо

- ссылка вниз

- ссылка вверх

- 1-я ссылка влево

- 2-я ссылка влево

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

уникальный номер;

тип блока;

уровень, характеризующий глубину вложенности;

флаг возможности параллельного исполнения;

количество каждой из возможных вычислительных операций;

ссылки на 1-й и последний операторы блока.

Специфические данные:

для циклов - уникальный номер цикла;

для ветвлений - вероятность перехода по каждой из ветвей.

Количество операций определяется следующим образом:

1) линейный блок - общее их количество во всех входящих в него операторов;

2) блок цикла - сумма операций во всех входящих в его тело блоков;

3) блок ветвления - сумма слагаемых вида: число операций в i-й ветви * вероятность перехода по ней;

4) блок слияния не имеет операций;

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

Приведем схему фрагмента некоторой программы и соответствующий ей граф.

ЛИН1

DO 1 … (1)

ЛИН2

DO 1 … (2)

IF … THEN

ЛИН3

ELSE

ЛИН4

ENDIF

1 CONTINUE

DO 2 … (3)

ЛИН5

2 CONTINUE

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

Уникальный номер цикла. Служит для связи с расширенным графом.

Уровень вложенности - соответствует аналогичному полю из графа.

Ссылка на идентификатор счетчика цикла.

Начальное, конечное выражения счетчика, шаг цикла.

Количество итераций (витков) цикла.

Списки переменных и элементов массивов, используемых на чтение и на модификацию.

Список редукционных переменных.

Ссылки на оператор заголовка цикла и на оператор его завершения.

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

Тэг вида идентификатора - переменная или массив.

Тип идентификатора.

Строка имени.

Размерность и длина по каждому измерению - для массива.

Ссылка на соответствующий элемент таблицы имен низкоуровнего представления.

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

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

Первое требование к входной программе заключается в ее корректности с точки зрения синтаксиса и семантики Fortran77. Заключенные в ней ошибки, не определенные на этапе разбора текста средствами Sage++, могут привести к непредсказуемым результатам.

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

в программе не должны присутствовать операторы прекращения выполнения;

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

Другим существенным требованием является запрет на использование COMMON-областей.

Ограничения, накладываемые в данной дипломной работе:

выражения в заголовках циклов (начальное, конечное, шаг) могут быть только линейными относительно некоторой переменной, т.е. иметь вид C1*V+C0, где C1 и C0 - константы, V - переменная;

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

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

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

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

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

Рассмотрим назначение классов 1-го набора и их наиболее важные члены.

1) Класс cSourceProgramSg - представляет исходную последовательную программу. Обработка входной программы должна начинаться с создания объекта этого класса.

cSourceProgramSg (char *projfile) - конструктор класса, projfile - имя файла проекта Sage++; в этом конструкторе происходит открытие проекта, разбор входящего в него файла исходной программы, создание незаполненных графа, списка циклов и таблицы символов.

SgStatement *FirstSt () - 1-й оператор программы.

SgStatement *LastSt () - последний оператор программы.

cProgramGraphSg *PrgGraph () - граф программы.

cLoopListSg *LpList () - список циклов.

cSymbolTabSg *SymTab () - таблица символов.

void PrepareConsts () - замена в теле программы обращений к константам на их значения.

void PrepareLoops () - конвертация циклов программы к виду DO-ENDDO.

void BuildLoopList () - построение списка циклов.

void BuildProgGraph () - построение графа программы.

void PrintLoopList (ostream&) - вывод в поток списка циклов для просмотра.

void PrintProgGraph (ostream&) - вывод графа.

void PrintSymbolTab (ostream&) - вывод таблицы имен.

void ExportData (char*) - экспорт данных в файлы.

void ImportData (char*) - импорт данных из файлов;

void Unparse (char*) - генерация результирующего текста в файле, имя которого определяется параметром метода.

При экспорте данных в файлы образуются следующие файлы:

filename.gr - узлы графа;

filename.gri - индексный файл;

filename.lp - список циклов;

filename.st - таблица символов, где filename - параметр метода ExportData(char*).

2) Класс cProgramGraphSg - представляет расширенный граф программы.

cProgramGraphSg (cSymbolTabSg*, cLoopListSg*) - конструктор класса, создает пустой граф управления. Параметры - таблица символов и список циклов, на которые будет ссылаться граф.

cLoopListSg *LpList () - список циклов, используемый графом.

cSymbolTabSg *SymTab () - таблица имен, используемая графом.

cProgramGraphNodeSg *CurNode () - текущий узел.

int IsStart () - является ли текущий узел начальным.

int GoStart (), GoDown (), GoUp (), GoLeft1 (), GoLeft2 (),

GoRight1 (), GoRight2 (), GoId (long int) - переместить указатель на текущий узел соответственно на 1-й узел, вниз, вверх, влево по 1-й ссылке, влево по 2-й ссылке, вправо по 1-й ссылке, вправо по 2-й ссылке, на узел с заданным номером. Возвращает 1 при удачном переходе, 0 в противном случае..

void CountOpers () - подсчет числа операций для каждого узла графа.

void ExportData (ofstream&, ofstream&) - экспорт графа и индексной информации в потоки.

void ImportData (ifstream&) - импорт данных от блока распределения вычислений, подлежащих вставке в граф;

void Build (SgStatement*, SgStatement*, int, int) - построение графа.

void Unparse () - произвести вставку добавленных в граф данных во внутреннее представление Sage++;

3) Класс cProgramGraphNodeSg - представляет узел графа управления.

cProgramGraphNodeSg () - конструктор класса, создает новый узел.

SgStatement *poSt1, *poSt2, *poSt3 - принимают значения после построения графа.

Для линейного участка: poSt1 - 1-й оператор блока, poSt2 - последний оператор.

Для цикла: poSt1 - оператор заголовка цикла, poSt2 - оператор, завершающий цикл (ENDDO)

Для ветвления: poSt1 - IF, poSt2 - ELSE, poSt3 - ENDIF.

int Level - уровень вложенности, внешнему уровню соответствует 0.

int IsParal - признак возможности распараллеливания.

long int LoopId - для элементов типа “цикл” содержит номер соответствующего цикла из списка.

float Ver1, Ver2 - для элементов типа “ветвление” вероятность перехода соответственно по 1-й и 2-й ветви.

float Opers[df_OPERS_COUNT] - массив, в каждом элементе которого содержится количество соответствующих индексу элемента операций в блоке. Например, Opers[0] - число сложений, Opers[1] - вычитаний.

long int Id () - уникальный номер узла.

int NodeType () - тэг типа узла.

long int ExportData (ofstream&) - экспорт узла в файловый поток, возвращает количество записанных байт.

void ImportData (ifstream&) - импорт данных из файлового потока.

void Unparse () - произвести вставку добавленных в узел данных во внутреннее представление Sage++.

4) Класс cLoopListSg - представляет список циклов программы.

cLoopListSg (cSymbolTabSg*) - конструктор класса, создает пустой список циклов, параметр - таблица символов, на которую будет ссылаться список.

cSymbolTabSg *SymTab () - таблица символов, используемая списком.

cLoopListNodeSg *CurNode () - указатель на текущий элемент списка.

int GoStart (), GoEnd (), GoRight (), GoLeft (), GoId (long int) - переместить указатель на текущий узел соответственно на 1-й узел, последний узел, влево, вправо, на узел с заданным номером. Возвращает 1 при удачном переходе, 0 в противном случае.

void Analyse () - произвести необходимый анализ элементов списка.

void Build (SgStatement*, SgStatement*, int) - построить список.

void ExportData (ofstream&) - экспорт списка в файловый поток.

5) Класс cLoopListNodeSg - представляет элемент списка циклов.

cLoopListNodeSg () - конструктор класса, создает новый элемент.

long int Id () - номер элемента.

SgStatement *poSt1, *poSt2 - ссылки соответственно на оператор заголовка цикла и на оператор завершения цикла.

cSymbolSg *poCounterSym - ссылка на переменную-счетчик цикла.

cExpressionSg *poStartExpr, *poEndExpr, *poStepExpr - начальное, конечное выражения счетчика и выражение шага цикла.

long int IterNum - количество итераций цикла.

int Level - уровень вложенности.

int IoOp, GotoOp - флаги наличия в теле цикла операторов ввода\вывода и операторов перехода за тело цикла.

cVarListElemSg *LVar[df_MAX_LRVAR_COUNT], *RVar[df_MAX_LRVAR_COUNT] - списки обращений к переменным и элементам массивов на модификацию и на чтение соответственно.

sReduct RedVar[df_MAX_REDVAR_COUNT] - список редукционных переменных, содержащихся в теле цикла.

void AnalyseHead (cSymbolTabSg *) - произвести анализ заголовка цикла.

void AnalyseBodyVars (cSymbolTabSg*) - произвести анализ обращений к переменным и элементам массивов в теле цикла.

void AnalyseRedVars (cSymbolTabSg*) - произвести поиск редукционных переменных в теле цикла.

void AnalyseIoOp () - определить присутствие в теле цикла операций ввода\вывода.

void AnalyseGotoOp () - определить присутствие в теле цикла операторов перехода за тело цикла.

long int ExportData (ofstream&) - экспорт элемента в файловый поток, возвращает количество записанных байт.

6) Класс cSymbolTabSg - представляет таблицу символов. Реализована в виде двунаправленного списка элементов класса cSymbolSg.

cSymbolTabSg () - конструктор класса, создает пустую таблицу.

cSymbolSg *FirstSym () - указатель на 1-й элемент списка.

void ExportData (ofstream&) - экспорт таблицы в файловый поток.

7 ) Класс cSymbolSg - представляет элемент таблицы символов.

cSymbolSg () - конструктор класса, создает новый элемент.

long int Id () - уникальный номер элемента.

SgSymbol *poSgSym - ссылка на соответствующий элемент таблицы символов Sage++.

int Variant () - тэг вида элемента: переменная или массив.

int Type - код типа.

char *Name - строка имени.

int Dim () - размерность (для массива).

int DimLen (int i) - длина по i-му измерению (для массива).

cSymbolSg *LinkRight () - следующий в списке элемент.

cSymbolSg *LinkLeft () - предыдущий в списке элемент.

long int ExportData (ofstream&) - экспорт элемента в файловый поток.

int operator == (cSymbolSg&), operator != (cSymbolSg&)

8) Класс cExpressionSg - представляет выражение. Текущая реализация класса позволяет хранить только выражения вида c1*V+c0, где c1,c0 - константы, V - переменная.

cExpressionSg (SgExpression*, cSymbolTabSg*) - конструктор класса, параметрами являются подлежащее разбору выражение, представленное объектом Sage++, и таблица символов, которая будет дополнена входящим в состав выражения идентификатором.

int Variant () - тэг вида выражения.

cSymbolSg *poVariable - ссылка на переменную выражения.

int IntC0 (), IntC1 () - значения констант, приведенные к типу int.

float RealC0 (), RealC1 () - аналогично, float.

double DoubleC0 (), DoubleC1 () - аналогично, double.

long int ExportData (ofstream&) - экспорт выражения в файловый поток.

int operator == (cExpressionSg&), operator != (cExpressionSg&)

9) Класс cArrayRefSg - представляет ссылку на элемент массива.

cArrayRefSg (SgArrayRefExp*, cSymbolTabSg*) - конструктор класса, параметрами являются подлежащая разбору ссылка на элемент массива, представленная объектом Sage++, и таблица символов, в которую будут добавлены входящие в ссылку переменные и имя массива.

SgArrayRefExp *poSgArrRef - исходный объект Sage++.

cSymbolSg *poSym - идентификатор массива.

int SubscrNum - количество индексных выражений в ссылке.

cExpressionSg* SubscrList [df_MAX_DIM] - массив индексных выражений.

long int ExportData (ofstream&) - экспорт в файловый поток.

int operator == (cArrayRefSg&)

int operator != (cArrayRefSg&)

10) Класс cVarListElemSg - представляет элемент списка обращений к переменным и массивам.

cVarListElemSg (SgVarRefExp*, cSymbolTabSg*), cVarListElemSg (SgArrayRefExp*, cSymbolTabSg*) - конструкторы класса, 1-й для разбора обращения к переменной, параметрами являются ссылка на переменную, представленная объектом Sage++, и таблица символов, в которую будут добавлены идентификаторы; 2-й для разбора ссылки на массив, параметры имеют тот же смысл.

int Variant () - тэг вида элемента (ссылка на переменную или на массив).

cSymbolSg *poSym - идентификатор переменной для ссылки 1-го вида.

cArrayRefSg *poArr - ссылка на массив для 2-го вида.

long int ExportData (ofstream&) - экспорт в файловый поток.

int operator == (cVarListElemSg&)

int operator != (cVarListElemSg&).

Для каждого из описанных классов существует его аналог во втором наборе, имеющий такое же имя за исключением постфикса “Sg”. В классах-аналогах отсутствуют методы для построения структур и конструкторы разбора. Корректная инициализация объектов этих классов производится только за счет введенных методов импорта из файлового потока. В классе cProgramGraphNode добавлены члены-данные для хранения директив FortranDVM, формирование которых осуществляет блок распределения вычислений и данных, и методы для их вставки, а также реализован экспорт этих комментариев в файл.

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

На самом внешнем уровне программы построения и экспорта всех структур находится функция main(). Ее основное содержание заключается в следующих строках:

cSourceProgramSg TestProg(projfile);

TestProg.PrepareAll();

TestProg.BuildAll();

TestProg.PrintAll(cout);

TestProg.ExportData(trgfile);

В первую очередь создается объект класса cSourceProgramSg, параметром конструктора которого является имя файла-проекта Sage++. Далее вызываются методы этого класса:

PrepareAll() - предварительная обработка Sage++ представления исходного приложения;

BuildAll() - построение всех структур;

PrintAll(cout) - вывод в поток cout построенных структур для просмотра;

ExportData(trgfile) - экспорт данных в файлы.

void cSourceProgramSg::PrepareAll()

Вызывает методы того же класса:

PrepareConsts(); - подготовка констант.

PrepareLoops(); - подготовка циклов.

void cSourceProgramSg::PrepareConsts()

Осуществляет замену обращений к константам их значениями. Алгоритм:

Просмотр таблицы имен Sage++ и составление списка объявленных констант и их значений.

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

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

При таком алгоритме, например, выражение 2*N+M+t, где N=100, M=5, будет заменено выражением 205+t.

void cSourceProgramSg::PrepareLoops().

Приводит все циклы программы к виду DO-ENDDO. Просматривает операторы программы. Для найденных циклов применяет метод Sage++, выполняющий такое преобразование.

void cSourceProgram::BuildAll().

BuildLoopList(); - построение списка циклов.

BuildProgGraph(); - построение графа.

void cSourceProgram::BuildLoopList().

LpList()->Build(FirstSt(), LastSt(), 0); - построение списка циклов.

LpList()->Analyse(); - анализ построенного списка.

void cLoopListSg::Build(SgStatement *first_line, SgStatement *last_line, int cur_lev).

Этот метод производит последовательный просмотр операторов в промежутке от first_line до last_line включительно с обеих сторон. При обнаружении оператора-заголовка цикла, осуществляется добавление к списку циклов нового элемента, в качестве его уровня вложенности принимается значение cur_lev. Затем метод вызывает себя со следующими параметрами: следующий оператор после обнаруженного заголовка цикла - first_line, оператор завершения найденного цикла - last_line, cur_lev+1 - для cur_lev в новом вызове. После возвращения из рекурсивного вызова просмотр продолжается с оператора завершения найденного цикла. Метод добавления нового элемента к списку цикла устроен так, что текущий указатель списка перемещается на вновь добавленный.

void cLoopListSg::Analyse().

Для каждого элемента списка:

AnalyseHead(SymTab()); - анализ заголовка.

AnalyseBodyVars(SymTab()); - анализ обращений к переменным и массивам в теле.

AnalyseRedVars(SymTab()); - поиск редукционных переменных.

AnalyseIoOp(); - поиск операторов ввода\вывода.

AnalyseGotoOp(); - анализ операторов перехода.

void cLoopListSg::AnalyseRedVars(cSymbolTabSg*).

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

перем = {перем} {операция} {выражение}, или (1)

перем =min/max({выражение} {перем}), или (2)

IF ({перем}.GT.{выражение})

{перем}={выражение} (3)

{операция}="+"|"*" (4)

где {выражение} не содержит {перем}, а также {перем} нигде больше не используется в данном цикле. Условие (3) есть другая реализация условия (2). Также необходимо обнаруживать редукционные переменные в выражениях вида:

{перем}={выражение}{операция}{перем}{операция}{выражение} (5), где выполняются те же условия, что и в (1)-(4), но при этом {операция} стоящая по обе стороны {перем} одинакова и если {операция} ="+", то {выражения} не содержат операций умножения и деления.

void cSourceProgramSg::BuildProgGraph().

PrgGraph()->Build(FirstSt(), LastSt(), 0, sy_DIR_RIGHT1); - построение графа.

PrgGraph()->Analyse(); - анализ построенного графа.

void cProgramGraphSg::Analyse().

CountOpers();

void cProgramGraphSg::Build (SgStatement *first_line, SgStatement *last_line, int cur_lev, int cur_dir).

Для идентификации каждого из возможных направлений добавления новых элементов определены константы:

sy_DIR_RIGHT1, sy_DIR_RIGHT2, sy_DIR_DOWN

Добавление нового звена в некотором направлении осуществляется при помощи методов cProgramGraphSg::AddNewRight1 ();

cProgramGraphSg::AddNewRight2 ();

cProgramGraphSg::AddNewRightFull (); - специальное добавление для блока слияния;

cProgramGraphSg::AddNewDown ();

При этом текущий указатель графа перемещается на новый блок.

Поскольку в графе отсутствует заглавное звено, первый узел графа строится особым образом независимо от указанного направления.

Алгоритм работы метода (рекурсивный):

Перемещение текущего указателя списка циклов на первый элемент.

Запомнить номер текущего элемента графа в переменной node1.

Начать цикл прохода с first_line.

switch

Если текущий оператор - заголовок цикла

Если перед этим прошли какое-то количество операторов, т.е. надо добавить линейный блок, определяем направление добавления следующим образом:

Если еще ничего не добавляли и cur_dir == sy_DIR_DOWN

Добавить вниз.

Иначе

Если ничего не добавляли и cur_dir == sy_DIR_RIGHT2

Добавить вправо2.

Иначе

Добавить вправо1.

{такой анализ связан с тем, что когда мы добавляем 1-е звено в данном вызове метода, мы должны учитывать переданное направление; в остальных случаях добавление блоков на одном уровне происходит вправо1}

Запомнить номер текущего (только что добавленного) элемента в node1.

Заполнить блок информацией.

{теперь надо добавить блок для найденного цикла}

Определить направление аналогично и добавить.

Заполнить блок информацией.

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

Вызвать рекурсивно Build с телом найденного цикла, cur_lev+1, sy_DIR_DOWN.

Установить указатель текущего оператора на конец цикла (ENDDO).

Если текущий оператор - заголовок ветвления

Проверка на необходимость добавления линейного блока - аналогично.

Добавить блок развилки в нужном направлении - аналогично.

Запомнить номер текущего блока (развилка) в переменной node2.

Заполнить блок информацией.

Добавить слияние.

Запомнить номер текущего блока (слияние) в переменной node3.

Вернуться влево (на развилку).

Вызвать Build с телом 1-й ветви, cur_lev, sy_DIR_RIGHT1.

Перейти на блок node2.

Вызвать Build с телом 2-й ветви, cur_lev, sy_DIR_RIGHT2.

Перейти на блок node3 (далее надо добавлять после слияния).

Установить указатель текущего оператора на конец ветвления (ENDIF).

Если текущий оператор - логический IF

Аналогично, только второй ветви нет.

Если текущий оператор - IF-ELSEIF

Аналогично, только ELSEIF обрабатывается как новый IF-THEN.

Конец switch

Если текущий оператор == last_line

Закончить цикл просмотра

Проверка на наличие линейного участка - аналогично.

Перейти на блок node1 (тот, на котором были перед вызовом).

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

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

экспорт этих структур в файлы;

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

дополнение внутреннего представления программы директивами FortranDVM, сформированными блоком распределения вычислений и данных.

Общий объем разработанного программного кода - около 4500 строк на языке C++.

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

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