Graphical Symbolic Programming

Graph-symbolic programming technology is a technology for designing and coding software algorithms, based on the graphical way of presenting programs, with the goal of fully or partially automating software design, coding and testing processes.

The technology of graph- symbolic programming is a graphic programming language and allows you to describe parallel algorithms using a control graph and automatically generate program codes.

Content

Conceptual Model Description

The model is represented by four $<D,F,P,G>$ ${\ displaystyle <D, F, P, G>}$ where $D$ ${\ displaystyle D}$ - a lot of data of a certain subject area, $F$ ${\ displaystyle F}$ - many operators defined over the data of the subject area, $P$ ${\ displaystyle P}$ - a lot of predicates acting on data structures of the subject area, $G=\left\{A,{\mathit {\Psi }},{\mathit {\Phi }},R\right\}$ ${\ displaystyle G = \ left \ {A, {\ mathit {\ Psi}}, {\ mathit {\ Phi}}, R \ right \}}$ - oriented labeled graph. $A=\left\{A_{1},A_{2},...,A_{n}\right\}$ ${\ displaystyle A = \ left \ {A_ {1}, A_ {2}, ..., A_ {n} \ right \}}$ - many vertices of the graph. Every vertex $A_{i}$ ${\ displaystyle A_ {i}}$ marked with a local operator $f_{i}\left(D\right)\in F$ ${\ displaystyle f_ {i} \ left (D \ right) \ in F}$ . The graph contains many control arcs ${\mathit {\Psi }}=\left\{{\mathit {\Psi }}_{1i1},{\mathit {\Psi }}_{1i2},...,{\mathit {\Psi }}_{jm}\right\}$ ${\ displaystyle {\ mathit {\ Psi}} = \ left \ {{\ mathit {\ Psi}} _ {1i1}, {\ mathit {\ Psi}} _ {1i2}, ..., {\ mathit { \ Psi}} _ {jm} \ right \}}$ and many arcs of synchronization ${\mathit {\Phi }}=\left\{{\mathit {\Phi }}_{1i1},{\mathit {\Phi }}_{1i2},...,{\mathit {\Phi }}_{jm}\right\}$ ${\ displaystyle {\ mathit {\ Phi}} = \ left \ {{\ mathit {\ Phi}} _ {1i1}, {\ mathit {\ Phi}} _ {1i2}, ..., {\ mathit { \ Phi}} _ {jm} \ right \}}$ . $R$ ${\ displaystyle R}$ - the relation over the sets of vertices and arcs that determines the way they are connected. Control arc connecting any two vertices $A_{i}$ ${\ displaystyle A_ {i}}$ and $A_{j}$ ${\ displaystyle A_ {j}}$ has three labels: predicate $p_{ij}(D)\in P$ ${\ displaystyle p_ {ij} (D) \ in P}$ , a priority $k\left({\mathit {\Phi }}_{ij}\right)\in N$ ${\ displaystyle k \ left ({\ mathit {\ Phi}} _ {ij} \ right) \ in N}$ and type of arc $T\left({\mathit {\Phi }}_{ij}\right)\in N$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) \ in N}$ . Each arc of synchronization ${\mathit {\Phi }}_{ij}$ ${\ displaystyle {\ mathit {\ Phi}} _ {ij}}$ marked with message $\mu _{ij}\in N$ ${\ displaystyle \ mu _ {ij} \ in N}$ .

Arc Type ${\mathit {\Psi }}_{ij}$ ${\ displaystyle {\ mathit {\ Psi}} _ {ij}}$ defined as a function $T\left({\mathit {\Phi }}_{ij}\right)\in \left\{1,2,3\right\}$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) \ in \ left \ {1,2,3 \ right \}}$ whose values have the following semantics:

$T\left({\mathit {\Phi }}_{ij}\right)=1$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) = 1}$ - sequential arc (describes the transfer of control in successive sections of the computing process);
$T\left({\mathit {\Phi }}_{ij}\right)=2$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) = 2}$ - parallel arc (denotes the generation of a new parallel computing process);
$T\left({\mathit {\Phi }}_{ij}\right)=3$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) = 3}$ - terminating arc (completes the parallel computing process).

The functioning of the model begins with the execution of the operator $f_{0}\left(D\right)$ ${\ displaystyle f_ {0} \ left (D \ right)}$ marking the start vertex $A_{0}$ ${\ displaystyle A_ {0}}$ . The development of the computational process described by the model is associated with transitions from vertex to vertex along control arcs. Moreover, the transition along the control arc is possible only if the predicate with which it is marked is true. If several predicates marking outgoing from the vertex of an arc become true at the same time, the transition is performed along the most priority arc.

To describe parallelism, the concept of a parallel branch is introduced. ${\mathit {\beta }}$ ${\ displaystyle {\ mathit {\ beta}}}$ - graph subgraph $G$ ${\ displaystyle G}$ starting with a parallel arc (type of this arc $T\left({\mathit {\Phi }}_{ij}\right)=2$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) = 2}$ ) and ending with a terminating arc (type of this arc $T\left({\mathit {\Phi }}_{ij}\right)=3$ ${\ displaystyle T \ left ({\ mathit {\ Phi}} _ {ij} \ right) = 3}$ ) ${\mathit {\beta }}=\left\{A_{\mathit {\beta }},{\mathit {\Psi }}_{\mathit {\beta }},R_{\mathit {\beta }}\right\}$ {\ displaystyle {\ mathit {\ beta}} = \ left \ {A _ {\ mathit {\ beta}}, {\ mathit {\ Psi}} _ {\ mathit {\ beta}}, R _ {\ mathit {\ beta}} \ right \}} where $A_{\mathit {\beta }}$ ${\ displaystyle A _ {\ mathit {\ beta}}}$ - many vertices of the branch, ${\mathit {\Psi }}_{\mathit {\beta }}$ ${\ displaystyle {\ mathit {\ Psi}} _ {\ mathit {\ beta}}}$ - many branch control arcs, $R_{\mathit {\beta }}$ ${\ displaystyle R _ {\ mathit {\ beta}}}$ - the relation over the sets of vertices and arcs of the branch, which determines the way they are connected. Arcs emanating from the vertices of a parallel branch ${\mathit {\beta }}$ ${\ displaystyle {\ mathit {\ beta}}}$ also belong to the branch ${\mathit {\beta }}$ ${\ displaystyle {\ mathit {\ beta}}}$ . When coding the algorithm described using the proposed model, each parallel branch generates a separate process - a set of subprograms executed sequentially on one of the processors of the parallel computing system. A graphical model usually contains several parallel branches, each of which forms a separate process. In this sense, the parallel computing model can be represented as the union of several parallel branches. Thus, parallelization of calculations is possible only at the level of the graph model. Calculations within any actor are performed sequentially.

Count Machine

In GSP technology for objects - aggregates - a monitor scheme for organizing calculations is used. The method is based on centralized control of the computation process carried out by a special program - a graph machine.
A graph machine is universal for any algorithm. The source information for the graph machine is the model of the graph for controlling the computational process described above. By analyzing the model, it performs actors and aggregates in the appropriate order, calculates predicate values, and manages synchronization. For each parallel branch, one instance of the graph machine is launched, which is a separate process in the computing system.

The work of the graph machine begins with the execution of the actor at the root vertex.
Then a list of arcs starting from the current vertex is constructed. This list is scanned by the graph machine sequentially, starting with the highest priority arc. The value of the predicate marking the arc is calculated, and if it is true, the transition to processing the next vertex occurs. As a result of processing a parallel arc in a separate process, another graph-machine starts, processing the parallel branch generated by this arc.
After starting all parallel branches, a transition to the vertex at which they are terminated occurs.
The parent graph machine expects all child graph machines to complete execution unless an alternative condition is specified.

Intermodular Parallel Communication Interface

Standard for data storage and use in SHGs

In GSP technology, a standard is used when organizing an intermodular information interface. The standard is ensured by the implementation of seven basic rules:

A single repository of data relevant to the entire field is introduced for the entire subject area of programming (POP). A full description of the data is available in the EPP data dictionary. Any variables not described in the data dictionary are considered local data for those SHG objects where they are used.
Within the GSP, the description of data types is centralized in the data type archive.
The data relevant to the generated software application are combined into a single universal structure - the TPOData class.
In basic modules, as a mechanism for accessing data, only parameters can be transmitted to an address that refers to a universal data structure.
The binding of these EPP objects to the formal parameters of the base modules is implemented in the passports of EPP objects.
In SHG technology, it is not recommended to use other methods of organizing inter-program communications according to data.
Data in EPP can be general and local. Memory for shared data is allocated in the memory manager, and all processors have access to this variable. Memory for a local variable is allocated on each processor, and only this processor can read and change its value.

Shared Memory Implementation Method in SHGs

In the program runtime, a machine is selected on which the process will be launched, which is responsible for storing global EPP variables. Given the hardware features and the topology of the aircraft, this may be the node with the largest amount of RAM or a central node that has the minimum access time from any of the other nodes in the cluster. The advantage of this approach is that the memory resource on computational nodes is significantly saved, since on the nodes memory is allocated only for those variables that are used.

The presented idea of organizing the storage and exchange of data between parallel processes is focused on the messaging model in which each process works with local data. For example, the MPI standard implies that processes exchange data only as a result of sending them in the form of messages.

The described method of data exchange requires the introduction of the concept of a data manager — a subprogram that performs the functions of storing, reading, and modifying data in a domain.

Memory manager

The data manager is executed in a separate process of the parallel program. In parallel branches of the graph model for reading or writing some data, the memory manager is accessed using a set of messages. In the first message, a request is sent to read or write a specific data. Each variable from POP receives a unique number by which the memory manager can identify it. In the case of reading, the parallel branch goes on to wait for a response from the data manager. When recording in the second message, the new value of the variable is sent. The data manager cyclically receives and processes requests for parallel branches.