ТЕХНОЛОГИЯ ВИЗУАЛЬНОГО МОДЕЛИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ. ЯЗЫК PGRAPH

Полный текст

ВВЕДЕНИЕ Современное программное обеспечение (ПО) характеризуется сложностью выполняемых функций и значительностью объемов исполняемых кодов. При этом к программам предъявляются высокие требования к качеству и надежности ее кодов. Использование графических методов программирования позволяет повысить производительность труда программиста, сократить время разработки параллельных вычислительных процессов, а также повысить их надежность. Визуальные средства разработки алгоритмов используют для создания программ графические элементы (диаграммы и схемы). Технология графосимволического программирования (ГСП), созданная на кафедре программных систем Самарского национально-исследовательского университета, является одним из способов наглядного представления алгоритмов программы в виде графа управления и в большей степени соответствует образному способу мышления человека. 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕХНОЛОГИИ ГСП Технология ГСП предоставляет возможности проектирования и создания алгоритмов программ с использованием графической нотации. Данная технология разрабатывалась для автоматизации процессов проектирования, кодирования и тестирования программного обеспечения. В основу рассматриваемой технологии легла традиционная модель объекта с дискретными состояниями, когда можно выделить конечное число состояний для любого объекта программирования. Тогда вычислительный процесс можно описать переходами объекта из одного состояния в другое. 1.1. Моделирование последовательных алгоритмов В технологии ГСП понятие алгоритма связывается с совокупностью вычислимых функций (модулей, операций). Тогда программу алгоритма A можно интерпретировать как некоторую результирующую вычислимую функцию: , где in(D) - множество входных данных функции f, out(D) - множество выходных данных функции f. В [2] изложена концепция описания алгоритма для вычислительной модели, названной машиной Колмогорова. В машине Колмогорова на каждом шаге работы алгоритма реализуется переработка текущего состояния структур данных D в новое состояние D* с помощью некоторой локальной функции D*=fk(D). Процесс переработки D0=D в D1=f1(D0), D1 в D2=f2(D1)=f1(f2(D)) и т.д. продолжается до тех пор, пока не появится сигнал о получении решения. В ГСП тоже реализуется преобразование структур данных с помощью вычислимых функций, но по другим правилам. Граф состояний G - ориентированный помеченный граф, вершины этого графа - состояния, а дуги определяют переходы системы из состояния в состояние [1]. Формально состояние - это достижение объектом O (моделью алгоритма) определенной конкретизации структур данных, требующее выполнения соответствующих действий над данными предметной области с помощью некоторой вычислимой функции Ak. Поэтому каждая вершина графа помечается локальной вычислимой функцией Ak. При этом следует помнить, что состояние графа Sj - это некое понятие («концепт»), связанное с абстрагированием объекта O, а вычислимая функция Ak, «приписанная» состоянию, - функциональное действие, которое необходимо выполнить при переходе объекта в это состояние. Для реализации событийного управления на графе состояний G вводится множество логических функций (предикатов) P={P1 , P2 ,…, Pl }. Здесь Pi(D){0,1} в зависимости от значений данных D. Дугам графа G поставим в соответствие функции-предикаты. Событие, реализующее переход Si Sj на графе состояний G, инициируется, если модель объекта O на текущем шаге работы алгоритма находится в состоянии Si и соответствующий предикат Pij(D) (помечающий данный переход) истинен. Ориентированный помеченный граф наглядно представляет пути развития вычислительного процесса. Фактически граф G является строгим описанием графа управления программы. Модель алгоритма в технологии графосимволического алгоритма можно описать следующим образом: M=<D,F,P,G>, где D - данные некоторой предметной области, F - множество вычислимых функций, P - множество предикатов, действующих над структурами данных, G - граф состояний объекта O [1]. С помощью данной четверки M можно описать любой алгоритм программы. При этом алгоритм программы представляется в визуальной форме, в виде графа управления. Кроме того, происходит декомпозиционное расслоение основных компонент описания алгоритма. Так структура алгоритма представляется графом управления G, логические выражения, определяющие управления, собраны в едином хранилище - множестве предикатов P. Технология ГСП допускает построение иерархически вложенных алгоритмических моделей, уровень вложенности граф-моделей не ограничен. Рисунок 1 содержит описание модели алгоритма решения задачи о ханойских башнях. Текст программы на языке C++ в соответствии с графическими нотациями, представленными на рисунке, генерируется автоматически [3]. Предложенный стиль визуального программирования языка PGRAPH имеет много общего с другими языками визуального программирования. С одной стороны, графические нотации языка PGRAPH часто воспринимаются как разновидность автоматного программирования, например, Switch-технологии Шалыто А.А. [4]. С другой стороны, язык PGRAPH имеет схожие черты с языками, использующими блок-схемы: ДРАКОН [5]. В определенном смысле PGRAPH можно считать алгоритмическим языком моделирования, реализующим процесс проектирования ПО, и тогда он похож на язык UML [6] за тем исключением, что на языке PGRAPH после завершения описания модели алгоритма всегда автоматически порождается код программы. Используемый в ГСП математический формализм - граф управления (ГУ) - служит хорошей основой для решения ряда задач повышения качества разрабатываемых моделей алгоритмов: структурного тестирования графа управления, структурной оптимизации ГУ, построения схем маршрутов вычислительных процессов, классификации используемых данных по признаку вход/выход и т.д. Но удивительной особенностью данной технологии является возможность разработки модели алгоритма без использования его готового облика. В технологии ГСП для разработки алгоритма достаточно иметь лишь идею решения задачи, а алгоритм строится шаг за шагом в процессе прорисовки графа управления. 1.2. Моделирование параллельных алгоритмов Параллельная программа содержит несколько вычислительных процессов, поэтому для описания модели параллельного алгоритма в технологии ГСП необходимо ввести новые элементы. Следует обозначить начало и конец параллельных процессов, а также определить условия их запуска и завершения [7]. Для этих целей вводится понятие дуг различного типа. Рассматриваемая технология допускает для описания параллельного алгоритма использование следующих типов дуг: последовательная, параллельная (обозначение начала параллельного процесса) и терминирующая (обозначение завершения параллельного процесса). Для формального описания типов дуг Ψij используется функция, принимающая три значения T(Ψij) {1,2,3} (1 - последовательная дуга, 2- параллельная дуга, 3 - терминирующая). Каждый отдельный вычислительный процесс начинается параллельной дугой и заканчивается терминирующей. В технологии ГСП для описания такого процесса вводится понятие параллельной ветви b, являющейся подграфом графа G. Параллельную ветвь алгоритма можно формально определить следующим образом: b = <Ab, Ψb , Rb>, где Ab - множество вершин ветви, Ψb - множество дуг управления ветви, Rb - отношение над множествами вершин и дуг ветви, определяющее способ их связи. Дуга, которая обозначает вход в параллельный процесс называется параллельной дугой и помечается «кружком». Дуга, обозначающая выход из параллельной ветви, называется терминирующей и помечается перечеркиванием. Допускается вложенность параллельных ветвей. Ветви, породившиеся в одной вершине некоторой ветви, должны терминироваться также в одной вершине этой же ветви. Можно создать неограниченное количество параллельных ветвей. Число параллельных ветвей программы фиксируется при создании алгоритма. Модель параллельного алгоритма можно представить как совокупность всех параллельных ветвей: где - параллельные ветви графа G. Функционирование модели начинается с запуска единственной ветви, называемой мастер-ветвью. На рисунке 2 представлен пример параллельной программы, предназначенной для решения системы обыкновенных дифференциальных уравнений (ОДУ) больших размерностей методом Рунге-Кутты. Данный модуль входит в более общую программу расчета движения космической тросовой системы (КТС) [8]. Применение КТС открывает новые возможности в использовании космического пространства: создание искусственной тяжести, транспортные операции в космосе, возвращение полезных грузов с орбиты, запуск малых спутников с базового космического аппарата (КА), использование геомагнитного поля Земли для орбитальных маневров - вот далеко не полный перечень возможностей КТС [9]. Несмотря на свою внешнюю простоту, задача высокоточного расчета движения КТС имеет свои сложности. Трос может иметь длину 30 километров и более. Для достижения приемлемой точности расчетов необходимо разбивать трос на значительное количество участков (100000 и более). На одном процессоре (для последовательного алгоритма) потребуется слишком много машинного времени. Однако исходную задачу можно разбить на p частных задач, меньших размерностей, и решать их на высокопроизводительной кластерной вычислительной системе, что достигается за счет разбиения всего троса на p участков. В то же время, особенности решаемой задачи не позволяют использовать классические схемы организации параллельных вычислений, часто используемые численные решения дифференциальных уравнений [10]. Дело в том, что для определения сил натяжения для каждой точки троса требуется знать положение соседних с ней точек, что не позволяет организовать независимое решение частных систем ОДУ на каждом процессоре. Каждая частная задача должна получать и передавать информацию о положении точек, смежных с соседним участком троса (каждый участок обсчитывается на собственном процессоре). В методе Рунге-Кутты изменение фазовых координат для уравнения рассчитывается по формуле . (1) Здесь X - матрица фазовых координат для каждой точки КТС; F(X,t) - правые части ОДУ движения тросовой системы; K1 ,K2 ,K3 ,K4 - матрицы коэффициентов формулы (1). Использование метода Рунге-Кутты применительно для КТС не позволяет производить вычисления коэффициентов Ki независимо друг от друга. И, как следствие, возникает такая странная 4-х фазная (пульсирующая) модель организации параллельных вычислений, представленная на рис. 2. В каждой фазе независимо друг от друга вычисляются коэффициенты K1,K2,K3,K4. При этом при переходе от фазы к фазе передаются каждому процессору положения точек, смежных с каждым участком троса. Последняя фаза вычисляет новое положение всех точек троса. Рис. 2. Пример параллельной программы 2. МОДЕЛЬ СИНХРОНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ При выполнении параллельных вычислений требуется синхронизация работы модулей программы, выполняемых разными процессорами. Задача синхронизации - это задача, в рамках которой требуется согласовать выполнение нескольких процессов. Данная задача решается с использованием различных механизмов [11]. В технологии ГСП применяется комбинированный способ, использующий одновременно механизмы передачи сообщений и принципы мониторной синхронизации. Определим почтовый ящик Lpost как список сообщений, с помощью которых вершины модели информируют друг друга о своем состоянии: , где μi,j - сообщение, посылаемое от вершины Аi вершине Aj. Возможность передачи сообщения от одной вершины граф-модели к другой вершине изображается графически дугой синхронизации Ψij, проведенной из вершины-источника сообщения в вершину-получателя сообщения. Вершина Аk посылает сообщения другим вершинам, записывая сообщения в список Lpost. Наличие сообщения μi,j в списке Lpost говорит о том, что оператор вершины Аi завершил работу и хочет сообщить об этом вершине Аj. Каждой вершине ставится в соответствие семафорный предикат , представляющий собой правильно построенную формулу относительно булевых переменных , связанных логическими связками типа &,˅. Булевы переменные определяются следующим образом: Семафорный предикат разрешает или запрещает запуск соответствующей вершины, в которую входит дуга синхронизации. Если , то запуск оператора вершины Аj разрешается, иначе вычисления приостанавливаются до того момента, когда станет равным 1. Проиллюстрируем применение рассмотренных методов на реальном примере. Рассмотрим модель асинхронного потенциального RS-триггера, построенного на элементах И-НЕ (рис. 3) [7]. Рис. 3. Принципиальная схема RS-триггера на элементах И-НЕ Логика работы RS-триггера во времени может быть описана следующей системой функций: (2) Поскольку триггеры в основном применяются в цифровых устройствах, они, как правило, работают в дискретном времени, и, как следствие, значения их выходных сигналов анализируются только в определенные моменты времени. Пусть S=x11(t), R=x22(t), x12(t)=y2(t), x21(t)=y1(t), Ǫ=y1(t+1), Ǭ=y2(t+1). На рисунке 4 представлена параллельная модель алгоритма RS-триггера. Параллельные ветви данной модели совместно используют переменные y1 и y2 (вершина 3.0 использует переменную y2 для чтения, а вершина 4.1 - для записи). Дуги синхронизации, на рисунке 4 - пунктирные «стрелки», позволяют разрешить конфликт совместного использования данных. ЗАКЛЮЧЕНИЕ Визуальное программирование является удобным способом написания параллельных программ. В статье рассмотрены основные аспекты создания параллельных программ в рамках технологии ГСП. В теоретическом плане для организации параллельных вычислений последовательная алгоритмическая модель расширена дополнительными компонентами. Для описания параллельной программы введено понятия типа дуг и изменен алгоритм управления вычислительными процессами, для этого используются средства организации синхронизации параллельных вычислений. Разработка и запись параллельного алгоритма в графическом виде значительно облегчает понимание такого алгоритма. Графический способ записи программы в технологии ГСП предоставляет пользователям возможности анализа структуры и производительности параллельной программы, а так же корректности применяемых механизмов синхронизации вычислений. Рис. 1. Пример последовательной программы Рис. 4. Параллельная модель RS-триггера

Об авторах

Александр Николаевич Коварцев

Самарский национальный исследовательский университет имени академика С.П. Королёва

Email: kovr_ssau@mail.ru
доктор технических наук, профессор, заведующий кафедрой программных систем

Виктор Викторович Жидченко

Самарский национальный исследовательский университет имени академика С.П. Королёва

Email: vzhidchenko@yandex.ru
кандидат технических наук, доцент кафедры программных систем

Дарья Александровна Попова-Коварцева

Самарский национальный исследовательский университет имени академика С.П. Королёва

Email: dakkovr@mail.ru
кандидат технических наук, доцент кафедры программных систем

Александра Николаевна Даниленко

Самарский национальный исследовательский университет имени академика С.П. Королёва

Email: danilenko.al@gmail.com
кандидат технических наук, доцент кафедры программных систем

Список литературы

Дополнительные файлы