Графо-символическое программирование

Технология графосимволического программирования — это технология проектирования и кодирования алгоритмов программного обеспечения, базирующаяся на графическом способе представления программ, преследующую цель полной или частичной автоматизации процессов проектирования, кодирования и тестирования ПО.
Технология графосимволического программирования является графическим языком программирования и позволяет описывать параллельные алгоритмы с помощью графа управления и автоматизированно порождать коды программ.
Концептуальное описание модели
Модель представляется четверкой < D , F , P , G > {displaystyle <D,F,P,G>} , где D {displaystyle D} — множество данных некоторой предметной области, F {displaystyle F} — множество операторов, определенных над данными предметной области, P {displaystyle P} — множество предикатов, действующих над структурами данных предметной области, G = { A , Ψ , Φ , R } {displaystyle G=left{A,{mathit {Psi }},{mathit {Phi }},R ight}} — ориентированный помеченный граф. A = { A 1 , A 2 , . . . , A n } {displaystyle A=left{A_{1},A_{2},...,A_{n} ight}} — множество вершин графа. Каждая вершина A i {displaystyle A_{i}} помечена локальным оператором f i ( D ) ∈ F {displaystyle f_{i}left(D ight)in F} . На графе задано множество дуг управления Ψ = { Ψ 1 i 1 , Ψ 1 i 2 , . . . , Ψ j m } {displaystyle {mathit {Psi }}=left{{mathit {Psi }}_{1i1},{mathit {Psi }}_{1i2},...,{mathit {Psi }}_{jm} ight}} и множество дуг синхронизации Φ = { Φ 1 i 1 , Φ 1 i 2 , . . . , Φ j m } {displaystyle {mathit {Phi }}=left{{mathit {Phi }}_{1i1},{mathit {Phi }}_{1i2},...,{mathit {Phi }}_{jm} ight}} . R {displaystyle R} — отношение над множествами вершин и дуг, определяющее способ их связи. Дуга управления, соединяющая любые две вершины A i {displaystyle A_{i}} и A j {displaystyle A_{j}} , имеет три метки: предикат p i j ( D ) ∈ P {displaystyle p_{ij}(D)in P} , приоритет k ( Φ i j ) ∈ N {displaystyle kleft({mathit {Phi }}_{ij} ight)in N} и тип дуги T ( Φ i j ) ∈ N {displaystyle Tleft({mathit {Phi }}_{ij} ight)in N} . Каждая дуга синхронизации Φ i j {displaystyle {mathit {Phi }}_{ij}} помечена сообщением μ i j ∈ N {displaystyle mu _{ij}in N} .
Тип дуги Ψ i j {displaystyle {mathit {Psi }}_{ij}} определяется как функция T ( Φ i j ) ∈ { 1 , 2 , 3 } {displaystyle Tleft({mathit {Phi }}_{ij} ight)in left{1,2,3 ight}} , значения которой имеют следующую семантику:
- T ( Φ i j ) = 1 {displaystyle Tleft({mathit {Phi }}_{ij} ight)=1} — последовательная дуга (описывает передачу управления на последовательных участках вычислительного процесса);
- T ( Φ i j ) = 2 {displaystyle Tleft({mathit {Phi }}_{ij} ight)=2} — параллельная дуга (обозначает порождение нового параллельного вычислительного процесса);
- T ( Φ i j ) = 3 {displaystyle Tleft({mathit {Phi }}_{ij} ight)=3} — терминирующая дуга (завершает параллельный вычислительный процесс).
Функционирование модели начинается с выполнения оператора f 0 ( D ) {displaystyle f_{0}left(D
ight)} , помечающего начальную вершину A 0 {displaystyle A_{0}} . Развитие вычислительного процесса, описываемого моделью, ассоциируется с переходами из вершины в вершину по дугам управления. При этом переход по дуге управления возможен лишь в случае истинности предиката, которым она помечена. Если несколько предикатов, помечающих исходящие из вершины дуги, одновременно становятся истинными, переход осуществляется по наиболее приоритетной дуге.
Для описания параллелизма вводится понятие параллельной ветви β {displaystyle {mathit {eta }}} — подграфа графа G {displaystyle G} , начинающегося параллельной дугой (тип этой дуги T ( Φ i j ) = 2 {displaystyle Tleft({mathit {Phi }}_{ij} ight)=2} ) и заканчивающегося терминирующей дугой (тип этой дуги T ( Φ i j ) = 3 {displaystyle Tleft({mathit {Phi }}_{ij} ight)=3} ). β = { A β , Ψ β , R β } {displaystyle {mathit {eta }}=left{A_{mathit {eta }},{mathit {Psi }}_{mathit {eta }},R_{mathit {eta }} ight}} , где A β {displaystyle A_{mathit {eta }}} — множество вершин ветви, Ψ β {displaystyle {mathit {Psi }}_{mathit {eta }}} — множество дуг управления ветви, R β {displaystyle R_{mathit {eta }}} — отношение над множествами вершин и дуг ветви, определяющее способ их связи. Дуги, исходящие из вершин параллельной ветви β {displaystyle {mathit {eta }}} , принадлежат также ветви β {displaystyle {mathit {eta }}} . При кодировании алгоритма, описанного с помощью предлагаемой модели, каждая параллельная ветвь порождает отдельный процесс — совокупность подпрограмм, исполняемых последовательно на одном из процессоров параллельной вычислительной системы. Графическая модель обычно содержит несколько параллельных ветвей, каждая из которых образует отдельный процесс. В этом смысле модель параллельных вычислений можно представить как объединение нескольких параллельных ветвей. Таким образом, распараллеливание вычислений возможно только на уровне граф-модели. Вычисления в пределах любого актора выполняются последовательно.
Граф-машина
В технологии ГСП для объектов — агрегатов — используется мониторная схема организации вычислений. В основу способа положено централизованное управление процессом вычислений, осуществляемое специальной программой — граф-машиной.
Граф-машина универсальна для любого алгоритма. Исходной информацией для граф-машины служит описанная выше модель графа управления вычислительным процессом. Анализируя модель, она выполняет в соответствующем порядке акторы и агрегаты, вычисляет значения предикатов и управляет синхронизацией. Для каждой параллельной ветви запускается по одному экземпляру граф-машины, которая представляет собой отдельный процесс в вычислительной системе.
Межмодульный интерфейс параллельного обмена данными
Стандарт хранения и использования данных в ГСП
В технологии ГСП используется стандарт при организации межмодульного информационного интерфейса. Стандарт обеспечивается выполнением семи основных правил:
Способ реализации общей памяти в ГСП
В среде выполнения программы выбирается машина, на которой будет запущен процесс, отвечающий за хранение глобальных переменных ПОП. Учитывая аппаратные особенности и топологию ВС, это может быть узел с наибольшим объемом оперативной памятью или центральный узел, имеющий минимальное время доступа от любого из остальных узлов кластера. Преимущество данного подхода в том, что значительно экономится ресурс памяти на вычислительных узлах, так как на узлах память выделяется только под те переменные, которые используются.
Представленная идея организации хранения и обмена данными между параллельными процессами ориентирован на модель передачи сообщений, в которой каждый процесс работает с локальными данными. Например, стандарт MPI подразумевает, что процессы обмениваются данными только в результате пересылки их в виде сообщений.
Описанный способ обмена данными требует введения понятия диспетчера данных — подпрограммы, выполняющей функции хранения, чтения и модификации данных предметной области.
Диспетчер памяти
Диспетчер данных исполняется в отдельном процессе параллельной программы. В параллельных ветвях граф-модели для чтения или записи некоторого данного осуществляется обращение к диспетчеру памяти с помощью совокупности сообщений. В первом сообщении пересылается запрос на чтение или запись конкретного данного. Каждая переменная из ПОП получает уникальный номер, по которому диспетчер памяти может её идентифицировать. В случае чтения параллельная ветвь переходит к ожиданию ответа от диспетчера данных. При записи во втором сообщении пересылается новое значение переменной. Диспетчер данных циклически принимает и обрабатывает запросы параллельных ветвей.