Programare grafic-simbolică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 iulie 2022; verificarea necesită 1 editare .

Tehnologia de programare grafic-simbolică este o tehnologie de proiectare și codare a algoritmilor software bazați pe o reprezentare grafică a programelor, cu scopul de a automatiza total sau parțial procesele de proiectare, codare și testare a software -ului .

Tehnologia de programare grafică-simbolică este un limbaj de programare grafică care permite descrierea algoritmilor paraleli folosind un grafic de control și generarea automată a codurilor de program.

Descrierea conceptuală a modelului

Modelul este reprezentat printr-un cvadruplu , unde este un set de date dintr-un anumit domeniu, este un set de operatori definiți asupra datelor dintr-un domeniu, este un set de predicate care acționează asupra structurilor de date ale unui domeniu, este un grafic etichetat. este mulțimea vârfurilor graficului. Fiecare vârf este etichetat cu un operator local . Graficul are un set de arce de control și un set de arce de sincronizare . este o relație peste mulțimi de vârfuri și arce care determină modul în care acestea sunt conectate. Un arc de control care conectează oricare două vârfuri și are trei etichete: predicat , prioritate și tip arc . Fiecare arc de sincronizare este marcat cu un mesaj . $<D,F,P,G>$ $D$ $F$ $P$ $G=\left\{A,{\mathit \Psi},{\mathit \Phi},R\right\}$ $A=\stanga\{A_{1},A_{2},...,A_{n}\dreapta\}$ $A_{i}$ $f_{i}\stânga(D\dreapta)\în F$ ${\mathit \Psi }=\left\{{\mathit \Psi }_{{1i1)),{\mathit \Psi }_{{1i2}},...,{\mathit \Psi }_{{ jm}}\dreapta\}$ ${\mathit \Phi }=\left\{{\mathit \Phi }_{{1i1)),{\mathit \Phi }_{{1i2}},...,{\mathit \Phi }_{{ jm}}\dreapta\}$ $R$ $A_{i}$ $A_{j}$ $p_{{ij}}(D)\în P$ $k\left({\mathit \Phi }_{{ij}}\right)\în N$ $T\stânga({\mathit \Phi }_{{ij}}\dreapta)\în N$ ${\mathit \Phi }_{{ij))$ $\mu _{{ij}}\în N$

Un tip de arc este definit ca o funcție ale cărei valori au următoarea semantică: ${\mathit \Psi }_{{ij))$ $T\left({\mathit \Phi }_{{ij}}\right)\în \left\{1,2,3\right\}$

$T\left({\mathit \Phi }_{{ij}}\right)=1$ - arc secvenţial (descrie transferul controlului în secţiuni succesive ale procesului de calcul);
$T\left({\mathit \Phi }_{{ij}}\right)=2$ - arc paralel (care indică generarea unui nou proces de calcul paralel);
$T\left({\mathit \Phi }_{{ij}}\right)=3$ — arc de terminare (finalizează procesul de calcul paralel).

Funcționarea modelului începe cu execuția unui operator care marchează vârful inițial . Dezvoltarea procesului de calcul descris de model este asociată cu tranzițiile de la vârf la vârf de-a lungul arcelor de control. În acest caz, tranziția de-a lungul arcului de control este posibilă numai dacă predicatul cu care este marcat este adevărat. Dacă mai multe predicate care marchează arcele care ies dintr-un vârf devin adevărate în același timp, tranziția este efectuată de-a lungul arcului cu cea mai mare prioritate. $f_{0}\stânga(D\dreapta)$ $A_0$

Pentru a descrie paralelismul, este introdus conceptul de ramură paralelă — un subgraf al unui grafic care începe cu un arc paralel (tipul acestui arc este ) și se termină cu un arc de sfârșit (tipul acestui arc este ). , unde este mulțimea de vârfuri de ramificație, este mulțimea de arce de control al ramurilor, este relația peste mulțimile de vârfuri de ramificație și arce care determină modul în care sunt conectate. De ramură aparţin şi arcele care emană din vârfurile ramificaţiei paralele . La codificarea algoritmului descris folosind modelul propus, fiecare ramură paralelă generează un proces separat - un set de subrutine executate secvenţial pe unul dintre procesoarele sistemului de calcul paralel. Modelul grafic conține de obicei mai multe ramuri paralele, fiecare dintre acestea formând un proces separat. În acest sens, modelul de calcul paralel poate fi reprezentat ca o unire a mai multor ramuri paralele. Astfel, paralelizarea calculelor este posibilă doar la nivelul modelului grafic. Calculele în cadrul oricărui actor sunt efectuate secvenţial. ${\mathit \beta}$ $G$ $T\left({\mathit \Phi }_{{ij}}\right)=2$ $T\left({\mathit \Phi }_{{ij}}\right)=3$ ${\mathit \beta }=\left\{A_{{{\mathit \beta }}},{\mathit \Psi }_{({\mathit \beta }}},R_{{{\mathit \beta } }}\dreapta\}$ $A_{{{\mathit \beta }}}$ ${\mathit \Psi }_{{{\mathit \beta }}}$ $R_{{{\mathit \beta }}}$ ${\mathit \beta}$ ${\mathit \beta}$

Mașină grafică

În tehnologia GSP pentru obiecte - agregate - este utilizată o schemă de monitorizare pentru organizarea calculelor. Metoda se bazează pe controlul centralizat al procesului de calcul, realizat de un program special - o mașină grafică.
Mașina grafică este universală pentru orice algoritm. Informația inițială pentru mașina-graf este modelul graficului de control al procesului de calcul descris mai sus. Pe măsură ce analizează modelul, execută actorii și agregă în ordinea adecvată, evaluează valorile predicatelor și gestionează sincronizarea. Pentru fiecare ramură paralelă, este lansată o copie a mașinii grafice, care este un proces separat în sistemul de calcul.

Lucrarea mașinii grafice începe cu execuția actorului la nodul rădăcină.
Apoi este construită o listă de arce care provin de la vârful curent. Această listă este scanată de mașina grafică secvenţial, începând cu arcul cu cea mai mare prioritate. Se calculează valoarea predicatului care marchează arcul, iar dacă este adevărată, următorul vârf este procesat. Ca urmare a procesării unui arc paralel într-un proces separat, este lansată o altă mașină grafică care prelucrează ramura paralelă generată de acest arc.
După lansarea tuturor ramurilor paralele, are loc o tranziție către vârf, unde acestea sunt terminate.
Mașina grafică părinte așteaptă ca toate mașinile grafice secundare să finalizeze execuția, cu excepția cazului în care este specificată o condiție alternativă.

Interfață între module pentru schimbul de date în paralel

Standardul de stocare și utilizare a datelor GSP

Tehnologia GSP folosește un standard pentru organizarea unei interfețe de informații inter-module. Standardul este asigurat prin implementarea a șapte reguli de bază:

Se introduce un singur depozit de date pentru întreaga zonă tematică de programare (POP) care este relevant pentru întreaga zonă. O descriere completă a datelor este disponibilă în Dicționarul de date EPP. Orice variabile care nu sunt descrise în dicționarul de date sunt considerate date locale pentru acele obiecte GSP în care sunt utilizate.
În cadrul GSP, descrierea tipurilor de date este plasată central în arhiva tipurilor de date.
Datele care sunt relevante pentru aplicația software generată sunt combinate într-o singură structură universală - clasa TPOData.
În modulele de bază, singurul mecanism de acces la date permis este trecerea parametrilor la o adresă care se referă la o structură de date generică.
Legarea acestor obiecte POP la parametrii formali ai modulelor de bază este implementată în pașapoartele obiectelor POP.
În tehnologia GSP, nu se recomandă utilizarea altor metode de organizare a comunicațiilor între programe în funcție de date.
Datele din POP pot fi partajate sau locale. Memoria pentru datele partajate este alocată în managerul de memorie, iar toate procesoarele au acces la această variabilă. Memoria pentru o variabilă locală este alocată fiecărui procesor și numai acel procesor îi poate citi și modifica valoarea.

Cum este implementată memoria partajată în GSP

Mediul de execuție a programului selectează mașina pe care va fi lansat procesul responsabil cu stocarea variabilelor globale POP. Având în vedere caracteristicile hardware și topologia CS, acesta poate fi nodul cu cea mai mare cantitate de RAM sau nodul central, care are timpul minim de acces de la oricare dintre celelalte noduri din cluster. Avantajul acestei abordări este că resursa de memorie de pe nodurile de calcul este salvată în mod semnificativ, deoarece memoria este alocată pe noduri numai pentru acele variabile care sunt utilizate.

Ideea prezentată de organizare a stocării și schimbului de date între procese paralele este orientată către modelul de transmitere a mesajelor, în care fiecare proces lucrează cu date locale. De exemplu, standardul MPI implică faptul că procesele fac schimb de date numai ca urmare a trimiterii acestora sub formă de mesaje.

Metoda descrisă de schimb de date necesită introducerea conceptului de manager de date - o subrutină care îndeplinește funcțiile de stocare, citire și modificare a datelor de domeniu.

Manager de memorie

Managerul de date este executat într-un proces separat al programului paralel. În ramuri paralele ale modelului grafic, pentru a citi sau scrie unele date, se accesează managerul de memorie folosind un set de mesaje. Primul mesaj trimite o solicitare de citire sau scriere a unei anumite date. Fiecare variabilă din POP primește un număr unic prin care managerul de memorie o poate identifica. În cazul unei citiri, ramura paralelă continuă să aștepte un răspuns din partea managerului de date. La scriere, al doilea mesaj trimite noua valoare a variabilei. Managerul de date round-robin primește și procesează cererile de la filialele paralele.