Русская Википедия:Графо-символическое программирование
Технология графосимволического программирования — технология проектирования и кодирования алгоритмов программного обеспечения, базирующаяся на графическом способе представления программ, преследующую цель полной или частичной автоматизации процессов проектирования, кодирования и тестирования ПО.
Технология графосимволического программирования является графическим языком программирования и позволяет описывать параллельные алгоритмы с помощью графа управления и автоматизированно порождать коды программ.
Концептуальное описание модели
Модель представляется четверкой <math><D, F, P, G></math>, где <math>D</math> — множество данных некоторой предметной области, <math>F</math> — множество операторов, определенных над данными предметной области, <math>P</math> — множество предикатов, действующих над структурами данных предметной области, <math>G = \left \{ A, \mathit \Psi, \mathit \Phi, R \right \}</math> — ориентированный помеченный граф. <math>A = \left \{A_1, A_2, ..., A_n\right \}</math> — множество вершин графа. Каждая вершина <math>A_i</math> помечена локальным оператором <math>f_i\left (D \right)\in F</math>. На графе задано множество дуг управления <math>\mathit \Psi = \left \{ \mathit \Psi_{1i1}, \mathit \Psi_{1i2}, ..., \mathit \Psi_{jm} \right \}</math> и множество дуг синхронизации <math>\mathit \Phi = \left \{ \mathit \Phi_{1i1}, \mathit \Phi_{1i2}, ..., \mathit \Phi_{jm} \right \}</math>. <math>R</math> — отношение над множествами вершин и дуг, определяющее способ их связи. Дуга управления, соединяющая любые две вершины <math>A_i</math> и <math>A_j</math>, имеет три метки: предикат <math>p_{ij}(D) \in P</math>, приоритет <math>k \left (\mathit \Phi_{ij} \right ) \in N</math> и тип дуги <math>T \left (\mathit \Phi_{ij} \right ) \in N</math>. Каждая дуга синхронизации <math>\mathit \Phi_{ij}</math> помечена сообщением <math>\mu_{ij} \in N</math>.
Тип дуги <math>\mathit \Psi_{ij}</math> определяется как функция <math>T \left (\mathit \Phi_{ij} \right ) \in \left \{1,2,3 \right \}</math>, значения которой имеют следующую семантику:
- <math>T \left (\mathit \Phi_{ij} \right ) = 1</math> — последовательная дуга (описывает передачу управления на последовательных участках вычислительного процесса);
- <math>T \left (\mathit \Phi_{ij} \right ) = 2</math> — параллельная дуга (обозначает порождение нового параллельного вычислительного процесса);
- <math>T \left (\mathit \Phi_{ij} \right ) = 3</math> — терминирующая дуга (завершает параллельный вычислительный процесс).
Функционирование модели начинается с выполнения оператора <math>f_0 \left (D \right )</math>, помечающего начальную вершину <math>A_0</math>. Развитие вычислительного процесса, описываемого моделью, ассоциируется с переходами из вершины в вершину по дугам управления. При этом переход по дуге управления возможен лишь в случае истинности предиката, которым она помечена. Если несколько предикатов, помечающих исходящие из вершины дуги, одновременно становятся истинными, переход осуществляется по наиболее приоритетной дуге.
Для описания параллелизма вводится понятие параллельной ветви <math>\mathit \beta</math> — подграфа графа <math>G</math>, начинающегося параллельной дугой (тип этой дуги <math>T \left (\mathit \Phi_{ij} \right ) = 2</math>) и заканчивающегося терминирующей дугой (тип этой дуги <math>T \left (\mathit \Phi_{ij} \right ) = 3</math>). <math>\mathit \beta= \left \{ A_{\mathit \beta}, \mathit \Psi_{\mathit \beta}, R_{\mathit \beta} \right \}</math>, где <math>A_{\mathit \beta}</math> — множество вершин ветви, <math>\mathit \Psi_{\mathit \beta}</math> — множество дуг управления ветви, <math>R_{\mathit \beta}</math> — отношение над множествами вершин и дуг ветви, определяющее способ их связи. Дуги, исходящие из вершин параллельной ветви <math>\mathit \beta</math>, принадлежат также ветви <math>\mathit \beta</math>. При кодировании алгоритма, описанного с помощью предлагаемой модели, каждая параллельная ветвь порождает отдельный процесс — совокупность подпрограмм, исполняемых последовательно на одном из процессоров параллельной вычислительной системы. Графическая модель обычно содержит несколько параллельных ветвей, каждая из которых образует отдельный процесс. В этом смысле модель параллельных вычислений можно представить как объединение нескольких параллельных ветвей. Таким образом, распараллеливание вычислений возможно только на уровне граф-модели. Вычисления в пределах любого актора выполняются последовательно.
Граф-машина
В технологии ГСП для объектов — агрегатов — используется мониторная схема организации вычислений. В основу способа положено централизованное управление процессом вычислений, осуществляемое специальной программой — граф-машиной.
Граф-машина универсальна для любого алгоритма. Исходной информацией для граф-машины служит описанная выше модель графа управления вычислительным процессом. Анализируя модель, она выполняет в соответствующем порядке акторы и агрегаты, вычисляет значения предикатов и управляет синхронизацией. Для каждой параллельной ветви запускается по одному экземпляру граф-машины, которая представляет собой отдельный процесс в вычислительной системе.
- Работа граф-машины начинается с выполнения актора в корневой вершине.
- Затем строится список дуг, исходящих из текущей вершины. Этот список просматривается граф-машиной последовательно, начиная с самой приоритетной дуги. Вычисляется значение предиката, помечающего дугу, и в случае его истинности происходит переход к обработке следующей вершины. В результате обработки параллельной дуги в отдельном процессе запускается другая граф-машина, обрабатывающая порождаемую данной дугой параллельную ветвь.
- После запуска всех параллельных ветвей происходит переход в вершину, в которой они терминируются.
- Родительская граф-машина ожидает завершения выполнения всех дочерних граф-машин, если не задано альтернативное условие.
Межмодульный интерфейс параллельного обмена данными
Стандарт хранения и использования данных в ГСП
В технологии ГСП используется стандарт при организации межмодульного информационного интерфейса. Стандарт обеспечивается выполнением семи основных правил:
- Вводится единое для всей предметной области программирования (ПОП) хранилище данных, актуальных для всей области. Полное описание данных размещено в словаре данных ПОП. Любые переменные, не описанные в словаре данных, считаются локальными данными для тех объектов ГСП, где они используются.
- В пределах ГСП описание типов данных размещается централизовано в архиве типов данных.
- Данные, актуальные для формируемого программного приложения, объединяются в единую универсальную структуру — класс TPOData.
- В базовых модулях в качестве механизма доступа к данным допускается только передача параметров по адресу, ссылающемуся на универсальную структуру данных.
- Привязка данных объектов ПОП к формальным параметрам базовых модулей реализована в паспортах объектов ПОП.
- В технологии ГСП не рекомендуется использовать иные способы организации межпрограммных связей по данным.
- Данные в ПОП могут быть общими и локальными. Память под общее данное выделяется в менеджере памяти, и все процессоры имеют доступ к этой переменной. Память под локальную переменную выделяется на каждом процессоре, и только этот процессор может читать и изменять её значение.
Способ реализации общей памяти в ГСП
В среде выполнения программы выбирается машина, на которой будет запущен процесс, отвечающий за хранение глобальных переменных ПОП. Учитывая аппаратные особенности и топологию ВС, это может быть узел с наибольшим объемом оперативной памятью или центральный узел, имеющий минимальное время доступа от любого из остальных узлов кластера. Преимущество данного подхода в том, что значительно экономится ресурс памяти на вычислительных узлах, так как на узлах память выделяется только под те переменные, которые используются.
Представленная идея организации хранения и обмена данными между параллельными процессами ориентирован на модель передачи сообщений, в которой каждый процесс работает с локальными данными. Например, стандарт MPI подразумевает, что процессы обмениваются данными только в результате пересылки их в виде сообщений.
Описанный способ обмена данными требует введения понятия диспетчера данных — подпрограммы, выполняющей функции хранения, чтения и модификации данных предметной области.
Диспетчер памяти
Диспетчер данных исполняется в отдельном процессе параллельной программы. В параллельных ветвях граф-модели для чтения или записи некоторого данного осуществляется обращение к диспетчеру памяти с помощью совокупности сообщений. В первом сообщении пересылается запрос на чтение или запись конкретного данного. Каждая переменная из ПОП получает уникальный номер, по которому диспетчер памяти может её идентифицировать. В случае чтения параллельная ветвь переходит к ожиданию ответа от диспетчера данных. При записи во втором сообщении пересылается новое значение переменной. Диспетчер данных циклически принимает и обрабатывает запросы параллельных ветвей.
См. также
