WikiSort.ru - Программирование

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

Технология графосимволического программирования является графическим языком программирования и позволяет описывать параллельные алгоритмы с помощью графа управления и автоматизированно порождать коды программ.

Концептуальное описание модели

Модель представляется четверкой ${\displaystyle <D,F,P,G>}$ , где ${\displaystyle D}$  — множество данных некоторой предметной области, ${\displaystyle F}$  — множество операторов, определенных над данными предметной области, ${\displaystyle P}$  — множество предикатов, действующих над структурами данных предметной области, ${\displaystyle G=\left\{A,{\mathit {\Psi }},{\mathit {\Phi }},R\right\}}$  — ориентированный помеченный граф. ${\displaystyle A=\left\{A_{1},A_{2},...,A_{n}\right\}}$  — множество вершин графа. Каждая вершина ${\displaystyle A_{i}}$ помечена локальным оператором ${\displaystyle f_{i}\left(D\right)\in F}$ . На графе задано множество дуг управления ${\displaystyle {\mathit {\Psi }}=\left\{{\mathit {\Psi }}_{1i1},{\mathit {\Psi }}_{1i2},...,{\mathit {\Psi }}_{jm}\right\}}$ и множество дуг синхронизации ${\displaystyle {\mathit {\Phi }}=\left\{{\mathit {\Phi }}_{1i1},{\mathit {\Phi }}_{1i2},...,{\mathit {\Phi }}_{jm}\right\}}$ . ${\displaystyle R}$  — отношение над множествами вершин и дуг, определяющее способ их связи. Дуга управления, соединяющая любые две вершины ${\displaystyle A_{i}}$ и ${\displaystyle A_{j}}$ , имеет три метки: предикат ${\displaystyle p_{ij}(D)\in P}$ , приоритет ${\displaystyle k\left({\mathit {\Phi }}_{ij}\right)\in N}$ и тип дуги ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)\in N}$ . Каждая дуга синхронизации ${\displaystyle {\mathit {\Phi }}_{ij}}$ помечена сообщением ${\displaystyle \mu _{ij}\in N}$ .

Тип дуги ${\displaystyle {\mathit {\Psi }}_{ij}}$ определяется как функция ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)\in \left\{1,2,3\right\}}$ , значения которой имеют следующую семантику:

• ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)=1}$  — последовательная дуга (описывает передачу управления на последовательных участках вычислительного процесса);
• ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)=2}$  — параллельная дуга (обозначает порождение нового параллельного вычислительного процесса);
• ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)=3}$  — терминирующая дуга (завершает параллельный вычислительный процесс).

Функционирование модели начинается с выполнения оператора ${\displaystyle f_{0}\left(D\right)}$ , помечающего начальную вершину ${\displaystyle A_{0}}$ . Развитие вычислительного процесса, описываемого моделью, ассоциируется с переходами из вершины в вершину по дугам управления. При этом переход по дуге управления возможен лишь в случае истинности предиката, которым она помечена. Если несколько предикатов, помечающих исходящие из вершины дуги, одновременно становятся истинными, переход осуществляется по наиболее приоритетной дуге.

Для описания параллелизма вводится понятие параллельной ветви ${\displaystyle {\mathit {\beta }}}$  — подграфа графа ${\displaystyle G}$ , начинающегося параллельной дугой (тип этой дуги ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)=2}$ ) и заканчивающегося терминирующей дугой (тип этой дуги ${\displaystyle T\left({\mathit {\Phi }}_{ij}\right)=3}$ ). ${\displaystyle {\mathit {\beta }}=\left\{A_{\mathit {\beta }},{\mathit {\Psi }}_{\mathit {\beta }},R_{\mathit {\beta }}\right\}}$ , где ${\displaystyle A_{\mathit {\beta }}}$  — множество вершин ветви, ${\displaystyle {\mathit {\Psi }}_{\mathit {\beta }}}$  — множество дуг управления ветви, ${\displaystyle R_{\mathit {\beta }}}$  — отношение над множествами вершин и дуг ветви, определяющее способ их связи. Дуги, исходящие из вершин параллельной ветви ${\displaystyle {\mathit {\beta }}}$ , принадлежат также ветви ${\displaystyle {\mathit {\beta }}}$ . При кодировании алгоритма, описанного с помощью предлагаемой модели, каждая параллельная ветвь порождает отдельный процесс — совокупность подпрограмм, исполняемых последовательно на одном из процессоров параллельной вычислительной системы. Графическая модель обычно содержит несколько параллельных ветвей, каждая из которых образует отдельный процесс. В этом смысле модель параллельных вычислений можно представить как объединение нескольких параллельных ветвей. Таким образом, распараллеливание вычислений возможно только на уровне граф-модели. Вычисления в пределах любого актора выполняются последовательно.

Граф-машина

В технологии ГСП для объектов — агрегатов — используется мониторная схема организации вычислений. В основу способа положено централизованное управление процессом вычислений, осуществляемое специальной программой — граф-машиной.
Граф-машина универсальна для любого алгоритма. Исходной информацией для граф-машины служит описанная выше модель графа управления вычислительным процессом. Анализируя модель, она выполняет в соответствующем порядке акторы и агрегаты, вычисляет значения предикатов и управляет синхронизацией. Для каждой параллельной ветви запускается по одному экземпляру граф-машины, которая представляет собой отдельный процесс в вычислительной системе.

1. Работа граф-машины начинается с выполнения актора в корневой вершине.
2. Затем строится список дуг, исходящих из текущей вершины. Этот список просматривается граф-машиной последовательно, начиная с самой приоритетной дуги. Вычисляется значение предиката, помечающего дугу, и в случае его истинности происходит переход к обработке следующей вершины. В результате обработки параллельной дуги в отдельном процессе запускается другая граф-машина, обрабатывающая порождаемую данной дугой параллельную ветвь.
3. После запуска всех параллельных ветвей происходит переход в вершину, в которой они терминируются.
4. Родительская граф-машина ожидает завершения выполнения всех дочерних граф-машин, если не задано альтернативное условие.

Межмодульный интерфейс параллельного обмена данными

См. также

• APL

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