Grafsymbolisk programmering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 juli 2022; verifiering kräver 1 redigering .

Grafsymbolisk programmeringsteknologi är en teknik för att designa och koda mjukvarualgoritmer baserade på en grafisk representation av program, med syfte att helt eller delvis automatisera processerna för att designa, koda och testa mjukvara .

Graf -symbolisk programmeringsteknologi är ett grafiskt programmeringsspråk som gör det möjligt att beskriva parallella algoritmer med hjälp av en kontrollgraf och generera programkoder automatiskt.

Konceptuell beskrivning av modellen

Modellen representeras av en fyrdubbling , där är en uppsättning data för ett visst ämnesområde, är en uppsättning operatorer definierade över data för ett ämnesområde, är en uppsättning predikat som verkar på datastrukturer för ett ämnesområde, är en riktad märkt graf. är uppsättningen av grafens hörn. Varje vertex är märkt med en lokal operator . Grafen har en uppsättning kontrollbågar och en uppsättning synkroniseringsbågar . är en relation över uppsättningar av hörn och bågar som bestämmer hur de är sammankopplade. En kontrollbåge som förbinder två hörn och har tre etiketter: predikat , prioritet och bågtyp . Varje synkroniseringsbåge är markerad med ett meddelande . $<D,F,P,G>$ $D$ $F$ $P$ $G=\left\{A,{\mathit \Psi },{\mathit \Phi},R\right\}$ $A=\left\{A_{1},A_{2},...,A_{n}\right\}$ $A_{i}$ $f_{i}\left(D\right)\i F$ ${\mathit \Psi }=\left\{{\mathit \Psi }_{{1i1)),{\mathit \Psi }_{{1i2}},...,{\mathit \Psi }_{{ jm}}\right\}$ ${\mathit \Phi }=\left\{{\mathit \Phi }_{{1i1)),{\mathit \Phi }_{{1i2}},...,{\mathit \Phi }_{{ jm}}\right\}$ $R$ $A_{i}$ $A_{j}$ $p_{{ij}}(D)\i P$ $k\left({\mathit \Phi }_{{ij}}\right)\in N$ $T\left({\mathit \Phi }_{{ij}}\right)\in N$ ${\mathit \Phi }_{{ij}}$ $\mu _{{ij}}\i N$

En bågtyp definieras som en funktion vars värden har följande semantik: ${\mathit \Psi }_{{ij))$ $T\left({\mathit \Phi }_{{ij}}\right)\in \left\{1,2,3\right\}$

$T\left({\mathit \Phi }_{{ij}}\right)=1$ - sekventiell båge (beskriver överföringen av kontroll i på varandra följande delar av beräkningsprocessen);
$T\left({\mathit \Phi }_{{ij))\right)=2$ - parallell båge (som anger genereringen av en ny parallell beräkningsprocess);
$T\left({\mathit \Phi }_{{ij))\right)=3$ — terminating arc (slutför den parallella beräkningsprocessen).

Modellens funktion börjar med exekveringen av en operator som markerar den initiala vertexen . Utvecklingen av den beräkningsprocess som beskrivs av modellen är associerad med övergångar från vertex till vertex längs kontrollbågar. I det här fallet är övergången längs styrbågen endast möjlig om predikatet med vilket det är markerat är sant. Om flera predikat som markerar bågar som utgår från en vertex blir sanna samtidigt, utförs övergången längs den högst prioriterade bågen. $f_{0}\left(D\right)$ $A_0$

För att beskriva parallellitet introduceras konceptet med en parallell gren — en subgraf av en graf som börjar med en parallell båge (typen av denna båge är ) och slutar med en avslutande båge (typen av denna båge är ). , där är uppsättningen av grenhörn, är uppsättningen av grenkontrollbågar, är relationen över uppsättningarna av grenhörn och bågar som bestämmer hur de är anslutna. Bågarna som utgår från grenarnas hörn hör också till grenen . Vid kodning av algoritmen som beskrivs med den föreslagna modellen genererar varje parallell gren en separat process - en uppsättning subrutiner som exekveras sekventiellt på en av processorerna i det parallella beräkningssystemet. Den grafiska modellen innehåller vanligtvis flera parallella grenar, som var och en bildar en separat process. I denna mening kan den parallella beräkningsmodellen representeras som en förening av flera parallella grenar. Således är parallellisering av beräkningar endast möjlig på grafmodellnivå. Beräkningar inom alla aktörer utförs sekventiellt. ${\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 } }}\höger\}$ $A_{{{\mathit \beta }}}$ ${\mathit \Psi }_{{{\mathit \beta }}}$ $R_{{{\mathit \beta }}}$ ${\mathit \beta }$ ${\mathit \beta }$

Graph Machine

I GSP-tekniken för objekt - aggregat - används ett monitorschema för att organisera beräkningar. Metoden bygger på centraliserad styrning av beräkningsprocessen, utförd av ett speciellt program - en grafmaskin.
Grafmaskinen är universell för alla algoritmer. Den initiala informationen för grafmaskinen är modellen för beräkningsprocessstyrningsdiagrammet som beskrivs ovan. När den analyserar modellen, utför den aktörer och aggregerar i lämplig ordning, utvärderar predikatvärden och hanterar timing. För varje parallellgren startas en kopia av grafmaskinen, vilket är en separat process i datorsystemet.

Grafmaskinens arbete börjar med utförandet av skådespelaren vid rotnoden.
Sedan byggs en lista över bågar som kommer från den aktuella vertexen. Denna lista skannas av grafmaskinen sekventiellt, med början med den högsta prioritetsbågen. Värdet på predikatet som markerar bågen beräknas, och om det är sant, bearbetas nästa vertex. Som ett resultat av att bearbeta en parallellbåge i en separat process, startas en annan grafmaskin som bearbetar den parallella grenen som genereras av denna båge.
Efter lanseringen av alla parallella grenar sker en övergång till vertexet, där de avslutas.
Den överordnade grafmaskinen väntar på att alla underordnade grafmaskiner ska slutföra exekvering, såvida inte ett alternativt villkor anges.

Intermodulgränssnitt för parallellt datautbyte

GSP-datalagring och användningsstandard

GSP-tekniken använder en standard för att organisera ett informationsgränssnitt mellan moduler. Standarden säkerställs genom implementeringen av sju grundläggande regler:

Ett enda datalager för hela ämnesområdet programmering (POP) införs som är relevant för hela området. En fullständig beskrivning av data finns i EPP Data Dictionary. Alla variabler som inte beskrivs i dataordboken anses vara lokala data för de GSP-objekt där de används.
Inom GSP placeras beskrivningen av datatyper centralt i arkivet av datatyper.
De data som är relevanta för den genererade mjukvaruapplikationen kombineras till en enda universell struktur - TPOData-klassen.
I basmoduler är den enda tillåtna dataåtkomstmekanismen att skicka parametrar till en adress som refererar till en generisk datastruktur.
Bindning av dessa POP-objekt till de formella parametrarna för basmodulerna implementeras i POP-objektens pass.
Inom GSP-teknik rekommenderas det inte att använda andra metoder för att organisera interprogramkommunikation enligt data.
Data i POP kan delas eller lokalt. Minnet för delade data tilldelas i minneshanteraren och alla processorer har tillgång till denna variabel. Minne för en lokal variabel allokeras på varje processor, och endast den processorn kan läsa och ändra dess värde.

Hur delat minne implementeras i GSP

Programexekveringsmiljön väljer den maskin på vilken processen som ansvarar för att lagra de globala POP-variablerna ska startas. Med tanke på hårdvarufunktionerna och topologin hos CS kan detta vara noden med den största mängden RAM eller den centrala noden, som har den minsta åtkomsttiden från någon av de andra noderna i klustret. Fördelen med detta tillvägagångssätt är att minnesresursen på beräkningsnoder sparas avsevärt, eftersom minne tilldelas på noder endast för de variabler som används.

Den presenterade idén om att organisera datalagring och utbyte mellan parallella processer är inriktad på meddelandeförmedlingsmodellen, där varje process arbetar med lokal data. Till exempel innebär MPI-standarden att processer utbyter data endast som ett resultat av att de skickas i form av meddelanden.

Den beskrivna metoden för datautbyte kräver introduktionen av konceptet en datahanterare - en subrutin som utför funktionerna att lagra, läsa och modifiera domändata.

Minneshanterare

Datahanteraren exekveras i en separat process av parallellprogrammet. I parallella grenar av grafmodellen, för att läsa eller skriva vissa data, nås minneshanteraren med hjälp av en uppsättning meddelanden. Det första meddelandet skickar en begäran om att läsa eller skriva en viss data. Varje variabel från POP får ett unikt nummer med vilket minneshanteraren kan identifiera den. I fallet med en läsning fortsätter den parallella grenen att vänta på ett svar från datahanteraren. När du skriver skickar det andra meddelandet det nya värdet på variabeln. Datahanteraren round-robin tar emot och behandlar förfrågningar från parallella grenar.