Tipuri de paralelism. Prelegeri la disciplina „calculator paralel” - Prelegeri

1.2 Prelucrarea paralelă a datelor

1.2.1 Posibilitate fundamentală de prelucrare paralelă

Aproape toți algoritmii dezvoltați până în prezent sunt secvențiali. De exemplu, la evaluarea expresiei a + b × c, trebuie mai întâi să efectuați înmulțirea și abia apoi să efectuați adunarea. Dacă calculatoarele electronice conțin noduri de adunare și multiplicare care pot funcționa simultan, atunci în acest caz nodul de adunare va fi inactiv în așteptarea ca nodul de multiplicare să-și finalizeze activitatea. Este posibil să se demonstreze afirmația că este posibil să se construiască o mașină care va procesa un anumit algoritm în paralel.

Este posibil să se construiască m procesoare care, atunci când sunt operate simultan, produc rezultatul dorit într-un singur ciclu de ceas al computerului.

Astfel de mașini „multiprocesor” ar putea fi teoretic construite pentru fiecare algoritm specific și aparent „ocoli” natura secvențială a algoritmilor. Cu toate acestea, nu totul este atât de simplu - există o infinitate de algoritmi specifici, astfel încât raționamentul abstract dezvoltat mai sus nu este atât de direct legat de semnificația practică. Dezvoltarea lor ne-a convins de însăși posibilitatea paralelizării, a stat la baza conceptului de paralelism nelimitat și a făcut posibilă luarea în considerare dintr-o perspectivă generală a implementării așa-numitelor medii de calcul - sisteme multiprocesoare configurate dinamic pentru un anumit algoritm.

1.2.2 Modele abstracte de calcul paralel

Modelul de calcul paralel oferă o abordare la nivel înalt pentru caracterizarea și compararea timpilor de execuție a diferitelor programe, în timp ce abstractizează hardware-ul și detaliile de execuție. Primul model de calcul paralel important a fost Parallel Random Access Machine (PRAM), care oferă o abstractizare a unei mașini de memorie partajată (PRAM este o extensie a modelului RAM - Random Access Machine). Modelul BSP (Bulk Synchronous Parallel) combină atât abstracțiile memoriei partajate, cât și cele distribuite. Se presupune că toți procesoarele execută instrucțiunile în mod sincron; în cazul executării aceleiași instrucțiuni, PRAM este o mașină SIMD abstractă (SIMD - Single Instruction stream / Multiple Data stream - un singur flux de instrucțiuni împreună cu un flux de date multiplu), cu toate acestea, procesoarele pot executa instrucțiuni diferite. Principalele comenzi sunt citirea din memorie, scrierea în memorie și operațiile logice și aritmetice obișnuite.

Modelul PRAM este idealizat în sensul că fiecare procesor poate accesa orice celulă de memorie în orice moment (operațiile de scriere efectuate de un procesor sunt vizibile pentru toate celelalte procesoare în ordinea în care au fost efectuate, dar scrierile efectuate de diferite procesoare pot fi vizibile în orice ordine). De exemplu, fiecare procesor din PRAM poate citi date dintr-o celulă de memorie sau poate scrie date în aceeași celulă. Pe mașinile paralele reale, acest lucru, desigur, nu se întâmplă, deoarece modulele de memorie la nivel fizic organizează accesul la aceeași celulă de memorie. Mai mult, timpii de acces la memorie variază pe mașinile reale datorită prezenței cache-urilor și posibilei organizări ierarhice a modulelor de memorie.

Modelul de bază PRAM acceptă citiri și scrieri simultane (în acest context paralele). Sunt cunoscute submodele PRAM care țin cont de reguli pentru a evita situațiile conflictuale atunci când mai multe procesoare accesează simultan memoria partajată.

Teorema lui Brent vă permite să modelați circuite ale elementelor funcționale folosind mașini paralele cu acces aleatoriu (PRAM). Elementele funcționale pot fi fie 4 de bază (efectuarea de operații logice NOT, AND, OR, XOR - negație, logic AND, logic OR și, respectiv, OR exclusiv), mai complexe NAND și NOR (ȘI-NU și SAU-NU), și și orice complexitate.

În cele ce urmează, se presupune că întârzierea (adică timpul de răspuns - timpul după care valorile semnalului dorit apar la ieșirea elementului după ce au fost stabilite valorile la intrări) este aceeași pentru toate elementele funcționale.

Considerăm un circuit de elemente funcționale conectate fără a forma cicluri (presupunem că elementele funcționale au orice număr de intrări, dar exact o ieșire - un element cu mai multe ieșiri poate fi înlocuit cu mai multe elemente cu o singură ieșire). Numărul de intrări determină puterea de intrare a elementului, iar numărul de intrări la care este conectată ieșirea elementului determină puterea de ieșire a acestuia. De obicei, se presupune că puterile de intrare ale tuturor elementelor utilizate sunt mărginite de sus, dar puterile de ieșire pot fi oricare. Mărimea unui circuit se referă la numărul de elemente din acesta; cel mai mare număr de elemente de pe căile de la intrările circuitului la ieșirea elementului se numește adâncimea acestui element (adâncimea circuitului este egală cu cea mai mare dintre adâncimile elementelor sale constitutive).

Figura 1. Simularea unui circuit de dimensiune 15, adâncime 5 cu două procesoare folosind o mașină paralelă cu acces aleatoriu (mașină PRAM)

Figura 1 prezintă rezultatul modelării unui circuit de dimensiune (număr total de procesoare) n=15 cu o adâncime de circuit (număr maxim de elemente la fiecare nivel de adâncime) d=5 cu numărul de procesoare p=2 (elementele simulate simultan sunt combinate în grupuri pe zone dreptunghiulare, iar pentru fiecare grupă este indicată de pasul la care sunt modelate elementele sale; modelarea are loc secvenţial de sus în jos, în ordinea creşterii adâncimii, la fiecare adâncime p piese la un moment dat). Conform teoremei lui Brent, modelarea unei astfel de scheme nu va dura mai mult de ceil(15/2+1)=9 pași.

Lucrarea a fost adăugată pe site-ul site-ului: 2016-06-20

„>Prelegere " xml:lang="en-US" lang="en-US">6

„>Prelucrare paralelă a datelor

„>Paralelismul este capacitatea de a efectua simultan mai multe operații aritmetice, logice sau de serviciu. Mai mult decât atât, operațiile pot fi atât bloc mare, cât și bloc mic.

Procesarea paralelă se poate baza pe mai multe principii:

Paralelism spațial;

Paralelism temporal:

Conducte.
"> Vectorizare.
">Matrice.
">Sistolice.
„>Organizarea structurii de procesare a fluxului de date.
„>Organizarea sistemului pe baza structurii hipercubului.
„>Restructurarea dinamică a structurii aeronavei.

„>Descrierea oricărui algoritm este ierarhică, pe baza proprietății de imbricare. La programare se disting niveluri de imbricare: sarcini, sarcini, subsarcini (procese), macrooperații, operații.

„>1. Forma paralelă a algoritmului

„>Cea mai generală formă de reprezentare a algoritmilor este graficul de control al informației al algoritmului. O formă mai specifică de reprezentare a paralelismului sarcinilor este aparatul de formă tier-parallel (LPF).

">Algoritmul în formă de niveluri paralele este reprezentat sub formă de niveluri, iar nivelul zero include operatori (ramuri) care sunt independenți unul de celălalt.

„>Pe grafic puteți desemna tranziții, adică transferul rezultatelor calculării unei operații primitive de la un nivel la o operație de la nivelul următor. Nivelurile sunt împărțite prin tranziții. Pot exista tranziții „goale” și primitive „vide” operațiuni.

„>La construirea NFP-urilor, ele se bazează pe un set de bază de operații primitive (BNO). Forma paralelă în niveluri este caracterizată de următorii parametri:

„>1. Lungimea graficului (numărul de niveluri)" xml:lang="en-US" lang="en-US">L">.

">2. Latime " xml:lang="en-US" lang="en-US">i"> al-lea nivel - " xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">.

„>3. Lățimea unui grafic paralel-nivel" xml:lang="en-US" lang="en-US">B">= " xml:lang="en-US" lang="en-US">max">(" xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">).

„>4. Lățimea medie a graficului NAP V;vertical-align:sub">cf "> ">.

„>5. Factorul de umplere" xml:lang="en-US" lang="en-US">i">-al-lea nivel " xml:lang="en-US" lang="en-US">k;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> ">.

">6. Coeficientul de dispersie al operațiilor în grafic -" xml:lang="en-US" lang="en-US">Î;vertical-align:super" xml:lang="en-US" lang="en-US">j;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> ">, " xml:lang="en-US" lang="en-US">j„>BNO, unde „>- cantitate " xml:lang="en-US" lang="en-US">j„>al-lea tip de operațiuni în" xml:lang="en-US" lang="en-US">i">-al-lea nivel.

„>7. Numărul minim necesar de calculatoare (de la BNO) pentru a implementa algoritmul reprezentat de acest grafic în YAPF.

„>8. Timpul minim de rezolvare al algoritmului (suma timpilor de răspuns ai calculatoarelor cu cantitatea maximă de calcule pentru fiecare nivel) T;vertical-align:sub" xml:lang="en-US" lang="en-US">min">.

„>9. Conectivitatea algoritmului (numărul de rezultate intermediare care trebuie stocate în timpul implementării algoritmului) C.

„>2. Detectarea automată a concurenței

„>Există două moduri posibile de a construi un algoritm paralel: direct din enunțul problemei sau prin transformarea unui algoritm secvenţial.

„>Metodele de construire a unui algoritm paralel dintr-unul secvenţial se bazează pe identificarea construcţiilor tipice, care apar frecvent în algoritmul secvenţial, care, după anumite reguli, sunt înlocuite cu altele paralele.

„>În ciuda nivelului mai scăzut de paralelism atins la construirea unui algoritm paralel prin conversia dintr-unul secvenţial, această metodă este utilizată pe scară largă, deoarece oferă posibilitatea de a utiliza programe de aplicaţie scumpe dezvoltate şi depanate pentru ODS secvenţial.

„>Într-un program secvenţial, se face o distincţie între procesarea paralelă explicită şi cea ascunsă.

„>Când se analizează un program, se construiește un grafic al fluxului de date. Pentru a detecta paralelismul evident al proceselor, se analizează seturi de variabile de intrare (citire)" xml:lang="en-US" lang="en-US">R„> și variabilele de ieșire (scrise)." xml:lang="en-US" lang="en-US">W„> al fiecărui proces.

„>Procesarea paralelă ascunsă necesită un fel de procedură de transformare pentru un program secvenţial pentru a face posibilă executarea acestuia în paralel. Transformarea ar putea fi după cum urmează:

„>a) reducerea înălțimii arborilor de expresii aritmetice (Fig. 6.3);

">b) transformarea relaţiilor liniare de recurenţă;

">c) înlocuirea operatorilor;

">d) transformarea blocurilor de tranziții și bucle condiționate în formă canonică;

">e) repartizarea ciclurilor.

„>Arhitecturile paralele ating performanțe ridicate dacă conversia paralelismului ține cont de caracteristicile arhitecturii computerului pe care se presupune a fi executat algoritmul.

„>Ca exemplu de luare în considerare a aspectului memoriei, să luăm memoria cu adresare diagonală. Pentru a asigura procesarea paralelă a matricelor, elementele rândurilor și coloanelor acestora trebuie să fie distribuite între dispozitivele de stocare ale procesorului astfel încât să poată fi citit și procesat simultan.În acest caz, matricea este stocată cu shift (Fig. 6.4).

„>Orice algoritm conține secțiuni secvențiale (scalare). S-a dovedit că lungimea acestor secțiuni scalare este factorul determinant la implementarea algoritmului pe un computer paralel.

„>3. Gradul și nivelurile de paralelism

">Grad de paralelism"> (" xml:lang="en-US" lang="en-US">D">) „> aceasta este ordinea numărului de dispozitive de lucru paralele din sistem la implementarea algoritmului de sarcină, cu condiția ca numărul de procesoare (dispozitive de procesare) să nu fie limitat.

">1) Grad scăzut: de la 2 la 10 procesoare.

">2) Grad mediu: de la 10 la 100 de procesoare.

">3) Grad ridicat: de la 100 la 10;vertical-align:super">4 "> procesoare.

">4) Grad ultra-înalt: de la 10;vertical-align:super">4 "> până la 10 ;vertical-align:super">6 "> procesoare.

">Reprezentarea grafică a parametrului" xml:lang="en-US" lang="en-US">D">(" xml:lang="en-US" lang="en-US">t„>) în funcție de timp se numește profil de paralelism al programului. Figura 6.5 prezintă un profil de paralelism tipic.

„>Există o gamă largă de potențial paralelism în programele de aplicație. În programele intensive din punct de vedere computațional, 500 până la 3500 de operații aritmetice pot fi efectuate în paralel în fiecare ciclu, dacă mediul de calcul existent este disponibil pentru aceasta. Cu toate acestea, chiar și un superscalar proiectat corespunzător procesorul poate suporta de la 2 la 5,8 comenzi pe ciclu. Această scădere se datorează în primul rând costurilor de comunicare și de sistem.

Nivelul de paralelism are un impact mai puternic asupra performanței de calcul decât gradul de paralelism.

Sunt luate în considerare nivelurile algoritmice și ale circuitelor de paralelism.

Se disting următoarele niveluri algoritmice de paralelism:

1. Nivel de sarcină:

a) între sarcini;

b) între fazele sarcinii.

2. Nivel software:

a) între părți ale programului;

b) în cadrul ciclurilor.

3. Nivel de comandă (între fazele de execuție a comenzii).

4. Aritmetică și nivel de biți:

„>a) între elementele unei operații vectoriale;

">b) în interiorul circuitelor logice ale ALU.

„>Fiecare dintre niveluri este caracterizat de anumite proprietăți, pe baza cărora au fost dezvoltate structuri speciale de instrumente de calcul. Nivelul de comandă este implementat în orice computere moderne, inclusiv computere personale.

„>Nivelul de paralelism al circuitului este un nivel hardware la care se realizează paralelizarea procesării datelor sau organizarea calculelor paralele.

„>Procesarea paralelă poate fi implementată la următoarele niveluri de circuit:

„>1. La nivelul porților logice și al elementelor de memorie (Fig. 6.6).

„>2. Nivelul circuitelor logice și automatelor simple cu memorie (Fig. 6.7).

„>3. Nivelul registrelor și al circuitelor integrate de memorie (Fig. 6.8).

4. Nivelul microprocesoarelor elementare (Fig. 6.9).

„>5. Nivelul macroprocesoarelor care implementează operații mari (Fig. 6.10).

6. Nivelul computerelor, procesoarelor și programelor (Fig. 6.11).

„>4. Tipuri de paralelism

">4.1. Paralelismul natural și

„>paralelismul mai multor obiecte

În graficul de informații, pot fi identificate subgrafe independente „verticale” care nu folosesc reciproc niciun rezultat intermediar obținut la implementarea operațiilor primitive ale altui subgraf. Acest tip de paralelism se numește paralelism natural al sarcinilor independente.

O problemă are paralelism natural dacă în formularea sa inițială se reduce la o operație pe vectori multidimensionali, matrice multidimensionale sau funcții de rețea (Fig. 6.12).

Paralelismul cu obiecte multiple este un caz special de paralelism natural. Semnificația sa este că sarcina este de a procesa informații despre obiecte diferite, dar similare, procesate folosind același sau aproape același program (Fig. 6.13).

„>Aici, așa-numitele operații integrale ocupă o greutate relativ mică. La paralelizarea mai multor obiecte, situațiile apar mai des decât în cazul general când secțiunile individuale de calcule trebuie efectuate diferit pentru diferite obiecte.

„>4.2. Paralelismul ramurilor independente

Esența paralelismului ramurilor independente este că în programul de rezolvare a unei probleme se pot distinge părți independente, numite ramuri. Dacă calculatorul are hardware-ul corespunzător, ramurile pot fi executate în paralel (Fig. 6.14).

„>Ramura de program Y nu depinde de ramura X dacă:

„> - nu există conexiuni funcționale între ele, adică niciuna dintre variabilele de intrare ale ramurii Y nu este variabila de ieșire a ramurii X sau orice ramură care depinde de X;

"> - nu există nicio legătură între ele prin câmpurile de memorie de lucru;

"> - acestea trebuie executate folosind diferite programe;

„> - sunt independenți în control, adică condiția de executare a ramurii Y nu trebuie să depindă de caracteristicile generate în timpul execuției ramurii X sau de ramura care depinde de aceasta.

„>4.3. Paralelismul operațiilor adiacente sau

">paralelism local

Paralelismul operațiilor adiacente apare atunci când datele de intrare pentru operațiile curente sunt obținute în stadiile anterioare de calcul, iar construcția instrumentelor de calcul face posibilă combinarea execuției mai multor operații care nu sunt interconectate de datele de ieșire și rezultate.

Optimizarea locala a programelor consta in cautarea mai multor instructiuni care trebuie executate in rand si modificarea ordinii unora dintre ele, eventual modificarea numarului de registre si celule de memorie pentru a asigura paralelismul maxim posibil al operatiilor adiacente.

În cele mai multe cazuri, indicatorul conectivității operațiunilor adiacente depinde nu atât de problemă, cât de calitatea optimizării locale.

">5. Modelul problemei

Un model al problemei este construit pentru o analiză comparativă a structurilor calculatoarelor paralele. Prin urmare, ar trebui să fie de natură destul de generală și să descrie numai compoziția formelor de paralelism și a tipurilor de conexiuni.

De regulă, orice model de problemă este construit pe baza unei analize a clasei de probleme modelate. Pe baza rezultatelor analizei, algoritmii sunt convertiți într-o formă paralelă. Algoritmul studiat poate fi reprezentat ca un program format dintr-o succesiune de secțiuni de trei tipuri (Fig. 6.15):

secțiuni scalare (SC);
tronsoane cu paralelism de ramuri independente (BT);
secțiuni vectoriale (VC).

Modelul de sarcină este un set de parametri care caracterizează un program paralel

La construirea unui model al unei sarcini, scopul principal este de a determina timpul relativ al executării acesteia atunci când este implementat de algoritmul studiat.

">Fig. 6.15. Raportul dintre numărul total de calcule pe diferite secțiuni ale algoritmului în modelul problemei

" xml:lang="en-US" lang="en-US">W„>sk

" xml:lang="en-US" lang="en-US">Ww

" xml:lang="en-US" lang="en-US">W„>vk

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">sk

" xml:lang="en-US" lang="en-US">m;vertical-align:sub" xml:lang="en-US" lang="en-US">tu

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">vk

" xml:lang="en-US" lang="en-US">A

" xml:lang="en-US" lang="en-US">В

" xml:lang="en-US" lang="en-US">C

volumul calculelor

lungime relativă

Ministerul Educației și Științei al Federației Ruse

Agenția Federală pentru Educație

Universitatea Tehnică de Stat din Rusia de Sud

(Institutul Politehnic Novocherkassk)

Institutul Shakhty (filiala) SRSTU (NPI)

PRELEȚII DESPRE DISCIPLINA

„CALCULAT PARALEL”

Mine - 2010

Introducere

Noțiuni de bază

1. Probleme generale de rezolvare a „problemelor mari”

1.1 Probleme moderne de știință și tehnologie care necesită supercalculatoare pentru a le rezolva

1.2.2 Modele abstracte de calcul paralel

1.2.3 Metode de prelucrare paralelă a datelor, eroare de calcul

1.3 Conceptul de proces paralel și granule de paralelizare

1.4 Interacțiunea proceselor paralele, sincronizarea proceselor

1.5 Accelerație posibilă în calculul paralel (legea lui Amdahl)

2. Principii de construire a sistemelor de calcul multiprocesor

2.1 Arhitectura sistemelor de calcul multiprocesor

2.2 Distribuția calculelor și datelor în sisteme de calcul multiprocesor cu memorie distribuită

2.3 Clasificarea sistemelor de calcul paralele

2.4 Sisteme de calcul multiprocesor cu memorie distribuită

2.4.1 Supercalculatoare masiv paralele din seria Cry T3

2.4.2 Sisteme cluster de clasă BEOWULF

Concluzie

Bibliografie

Introducere

Chiar și în zorii erei computerelor, pe la jumătatea secolului trecut, designerii de calculatoare electronice au început să se gândească la posibilitatea de a utiliza calculul paralel în computere. La urma urmei, creșterea vitezei doar prin îmbunătățirea componentelor electronice ale unui computer este o metodă destul de costisitoare, care, în plus, se confruntă cu limitări impuse de legile fizice. Astfel, procesarea paralelă a datelor și paralelismul de comandă au fost introduse în proiectarea computerelor, iar acum orice utilizator al unui computer personal, poate fără să știe, lucrează pe un computer paralel.

Una dintre tendințele vizibile în dezvoltarea omenirii este dorința de a modela procesele realității înconjurătoare cât mai strict posibil, atât pentru a îmbunătăți condițiile de viață în prezent, cât și pentru a prezice viitorul cât mai precis posibil. Metodele matematice și tehnicile de modelare digitală în multe cazuri fac posibilă rezolvarea unor astfel de probleme, totuși, în timp, există o serioasă complicație calitativă și cantitativă a tehnologiei de rezolvare a problemelor. În multe cazuri, limitarea este lipsa puterii de calcul a calculatoarelor electronice moderne, dar importanța problemelor în curs de rezolvare a atras resurse financiare uriașe în domeniul creării de calculatoare electronice extrem de complexe.

De ceva timp, creșterea vitezei computerelor cu arhitectura tradițională (numită „von Neumann”) a devenit prohibitiv de costisitoare din cauza limitărilor tehnologice în producția de procesoare, astfel încât dezvoltatorii și-au îndreptat atenția către o altă modalitate de a crește productivitatea - combinarea calculatoarelor electronice în sisteme de calcul multiprocesor. În acest caz, fragmentele de program individuale sunt executate în paralel (și simultan) pe diferite procesoare, schimbând informații prin intermediul unei rețele interne de calculatoare.

Ideea de a combina calculatoare electronice pentru a crește atât productivitatea, cât și fiabilitatea este cunoscută încă de la sfârșitul anilor cincizeci.

Cerințele de a obține performanțe maxime la costuri minime au condus la dezvoltarea sistemelor de calcul multiprocesor; sunt cunoscute sisteme de acest fel care combină puterea de calcul a mii de procesoare individuale. Următoarea etapă este încercările de a uni milioane de computere eterogene de pe planetă într-un singur complex de calcul cu performanțe enorme prin Internet. Astăzi, utilizarea sistemelor de calcul paralele este o direcție strategică în dezvoltarea tehnologiei informatice. Dezvoltarea hardware-ului este susținută în mod necesar de îmbunătățirea componentelor algoritmice și software - tehnologii de programare paralelă.

Metoda de paralelizare a calculelor există de mult timp; organizarea funcționării în comun a multor procesoare independente necesită cercetări teoretice și practice serioase, fără de care o instalare complexă și relativ costisitoare a unui multiprocesor adesea nu numai că nu depășește, dar este inferioară ca performanță față de un calculator tradițional.

Potențialul de paralelizare nu este același pentru problemele de calcul de diferite tipuri - este semnificativ pentru programele științifice care conțin multe bucle și calcule lungi și semnificativ mai puțin pentru problemele de inginerie, care sunt caracterizate prin calcule folosind formule empirice.

Să luăm în considerare două întrebări principale:

1. Sisteme de calcul multiprocesor - (supercalculatoare masiv paralele) Cray T3D(E) cu un număr de procesoare de la 40 la 2176. Acestea sunt supercalculatoare cu memorie distribuită pe procesoare RISC de tip Alpha21164A, cu o topologie de rețea de comunicații - un trei -dimensional torus, un sistem de operare UNIX cu microkernel și traducători pentru limbaje FORTRAN, HPF, C/C++. Modele de programare acceptate: MPI, PVM, HPF.

2. Beowulf clustere de stații de lucru. Clusterele de stații de lucru sunt o colecție de stații de lucru conectate la o rețea locală. Un cluster este un sistem de calcul cu memorie distribuită și control distribuit. Un sistem cluster poate avea performanțe comparabile cu cele ale supercalculatoarelor. Clusterele de stații de lucru sunt de obicei numite clustere Beowulf (cluster Beowulf - după proiectul cu același nume), conectate printr-o rețea locală Ethernet și folosind sistemul de operare Linux.

Noțiuni de bază

Cea mai comună tehnologie de programare pentru sistemele de cluster și computerele paralele cu memorie distribuită este în prezent tehnologia MPI. Principalul mod în care procesele paralele interacționează în astfel de sisteme este prin transmiterea de mesaje unul altuia. Acest lucru se reflectă în numele acestei tehnologii - Message Passing Interface. Standardul MPI definește o interfață care trebuie urmată atât de sistemul de programare de pe fiecare platformă de calcul, cât și de utilizator atunci când își creează programele. MPI acceptă limbajele Fortran și C. Versiunea completă a interfeței conține o descriere a peste 125 de proceduri și funcții.

Interfața MPI acceptă crearea de programe paralele în stilul MIMD (Multiple Instruction Multiple Data), care implică combinarea proceselor cu diferite coduri sursă. Cu toate acestea, scrierea și depanarea unor astfel de programe este foarte dificilă, așa că, în practică, programatorii folosesc mult mai des modelul SPMD (Single Program Multiple Data) de programare paralelă, în cadrul căruia se folosește același cod pentru toate procesele paralele. În zilele noastre, din ce în ce mai multe implementări MPI acceptă lucrul cu așa-numitele „threads”.

Deoarece MPI este o bibliotecă, atunci când compilați un program este necesar să conectați modulele bibliotecii corespunzătoare.

După ce ați primit fișierul executabil, trebuie să îl rulați pe numărul necesar de procesoare. După lansare, același program va fi executat de toate procesele care rulează, rezultatul execuției, în funcție de sistem, va fi scos la terminal sau scris într-un fișier.

Un program MPI este un set de procese care interacționează paralel. Toate procesele sunt generate o singură dată, formând o parte paralelă a programului. În timpul execuției unui program MPI, nu este permisă crearea de procese suplimentare sau distrugerea celor existente (în versiunile ulterioare de MPI a apărut această posibilitate). Fiecare proces operează în propriul spațiu de adrese; nu există variabile sau date partajate în MPI. Principala modalitate de interacțiune între procese este trimiterea de mesaje în mod explicit.

Pentru a localiza interacțiunea proceselor paralele ale programului, puteți crea grupuri de procese, oferindu-le un mediu separat pentru comunicare - un comunicator. Compoziția grupurilor formate este arbitrară. Grupurile pot coincide complet, pot face parte unul din celălalt, nu se intersectează sau se pot intersecta parțial. Procesele pot interacționa numai în cadrul unui anumit comunicator; mesajele trimise în diferiți comunicatori nu se intersectează și nu interferează unele cu altele. Comunicatorii au tipul întreg în limbajul Fortran (în limbajul C, tipul MPI Comm predefinit).

Când pornește un program, se presupune întotdeauna că toate procesele generate funcționează în cadrul unui comunicator cuprinzător. Acest comunicator există întotdeauna și servește pentru interacțiunea între toate procesele care rulează programului MPI. Toate interacțiunile dintre procese au loc în cadrul unui comunicator specific; mesajele transmise în comunicatori diferiți nu interferează unele cu altele.

Procesoare cu set de instrucțiuni reduse (RISC). Arhitectura RISC (Reduced Instruction Set Computer) a procesorului se bazează pe ideea de a crește viteza de funcționare a acestuia prin simplificarea setului de instrucțiuni.

Cercetările au arătat că 33% dintre instrucțiunile dintr-un program tipic sunt transferuri de date, 20% sunt ramuri condiționate și alte 16% sunt operații aritmetice și logice. În marea majoritate a instrucțiunilor, calculul adresei poate fi efectuat rapid, într-un singur ciclu. Moduri de adresare mai complexe sunt utilizate în aproximativ 18% din cazuri. Aproximativ 75% dintre operanzi sunt scalari, adică variabile de număr întreg, real, caracter etc., iar restul sunt tablouri și structuri. 80% dintre variabilele scalare sunt locale, iar 90% dintre variabilele structurale sunt globale. Astfel, majoritatea operanzilor sunt operanzi locali de tipuri scalare. Ele pot fi stocate în registre.

Conform statisticilor, cea mai mare parte a timpului este petrecut procesând instrucțiunile „apel subrutinei” și „întoarcerea subrutinei”. Când sunt compilate, aceste instrucțiuni produc secvențe lungi de instrucțiuni de mașină cu un număr mare de accesări la memorie, așa că, chiar dacă ponderea acestor instrucțiuni este de doar 15%, ele consumă cea mai mare parte a timpului procesorului. Doar aproximativ 1% dintre rutine au mai mult de șase parametri și aproximativ 7% dintre rutine conțin mai mult de șase variabile locale.

În urma studierii acestor statistici, s-a ajuns la concluzia că un program tipic este dominat de operații simple: aritmetice, logice și transferuri de date. Domină și modurile simple de adresare. Majoritatea operanzilor sunt variabile locale scalare. Una dintre cele mai importante resurse pentru creșterea productivității este optimizarea acestor operatori.

Arhitectura RISC se bazează pe următoarele principii și idei. Setul de instrucțiuni ar trebui să fie limitat și să includă doar instrucțiuni simple, al căror timp de execuție după eșantionare și decodare este de un ciclu de ceas sau puțin mai mult. Se utilizează procesarea prin conducte. Instrucțiunile RISC simple pot fi implementate eficient în hardware, în timp ce instrucțiunile complexe pot fi implementate doar în microprogramare. Designul dispozitivului de control în cazul arhitecturii RISC este simplificat, iar acest lucru permite procesorului să funcționeze la viteze mari de ceas. Utilizarea comenzilor simple vă permite să implementați în mod eficient atât procesarea datelor pipeline, cât și execuția comenzilor.

Instrucțiunile complexe durează mai mult pentru a fi executate pe un procesor RISC, dar numărul lor este relativ mic. În procesoarele RISC, un număr mic de instrucțiuni sunt adresate memoriei. Preluarea datelor din RAM necesită mai mult de un ciclu de ceas. Majoritatea instrucțiunilor funcționează cu operanzi localizați în registre. Toate comenzile au un format unificat și o lungime fixă. Acest lucru face ca instrucțiunile de încărcare și decodare să fie mai ușoare și mai rapide, deoarece, de exemplu, codul operațional și câmpul de adresă sunt întotdeauna în aceeași poziție. Variabilele și rezultatele intermediare ale calculelor pot fi stocate în registre. Ținând cont de statisticile de utilizare a variabilelor, majoritatea variabilelor și parametrilor de procedură locali pot fi plasați în registre. Când este apelată o nouă procedură, conținutul registrelor este de obicei mutat în RAM, cu toate acestea, dacă numărul de registre este suficient de mare, este posibil să se evite o mare parte din operațiunile de schimb de memorie care consumă mult timp prin înlocuirea lor cu operațiuni de registre. Datorită arhitecturii simplificate a procesorului RISC, există spațiu pe cip pentru a găzdui un set suplimentar de registre.

În prezent, sistemele de calcul cu arhitectură RISC ocupă poziții de lider pe piața globală de calculatoare pentru stații de lucru și servere. Dezvoltarea arhitecturii RISC este asociată cu dezvoltarea compilatoarelor, care trebuie să profite efectiv de fișierul de registru mare, pipelining etc.

1. Probleme generale de rezolvare a „problemelor mari”

Termenul „probleme mari” se referă de obicei la probleme a căror rezolvare necesită nu numai construirea de modele matematice complexe, ci și efectuarea unui număr imens de calcule, cu multe ordine de mărime mai mari decât cele tipice pentru calculatoarele electronice programabile. Aici, computerele electronice sunt folosite cu resurse adecvate - dimensiunea memoriei RAM și a memoriei externe, viteza liniilor de transmitere a informațiilor etc.

Limita superioară a numărului de calcule pentru „probleme mari” este determinată doar de performanța sistemelor de calcul existente în prezent. Când se „rulează” probleme de calcul în condiții reale, întrebarea nu este „să rezolvi problema deloc”, ci „să o rezolvi într-un timp acceptabil” (ore/zeci de ore).

1.1. Sarcini moderne de știință și tehnologie care necesită

pentru rezolvarea supercalculatoarelor

Destul de des trebuie să se confrunte cu probleme care, deși au o valoare considerabilă pentru societate, nu pot fi rezolvate folosind computere relativ lente de birou sau de acasă. Singura speranță în acest caz se bazează pe computerele de mare viteză, care sunt denumite în mod obișnuit supercomputere. Doar mașinile din această clasă pot face față procesării unor cantități mari de informații. Acestea ar putea fi, de exemplu, date statistice sau rezultate ale observațiilor meteorologice, informații financiare. Uneori viteza de procesare este critică. Exemplele includ prognoza meteo și modelarea schimbărilor climatice. Cu cât este prezis mai devreme un dezastru natural, cu atât este mai mare oportunitatea de a vă pregăti pentru el. O sarcină importantă este modelarea medicamentelor, descifrarea genomului uman, tomografia, inclusiv medicală, și explorarea câmpurilor de petrol și gaze. Sunt multe exemple care pot fi date.

Modelarea proceselor realității înconjurătoare, atât pentru a îmbunătăți condițiile de viață în prezent, cât și pentru a prezice în mod fiabil viitorul, este una dintre tendințele de dezvoltare a omenirii. Metodele matematice și tehnicile de modelare digitală fac în multe cazuri posibilă rezolvarea unor astfel de probleme, totuși, în timp, tehnologia de rezolvare a unor astfel de probleme devine mai complexă. În multe cazuri, limitarea este lipsa puterii de calcul a calculatoarelor electronice moderne.

Mai jos sunt enumerate câteva domenii ale activității umane care necesită putere supercomputer folosind calculul paralel pentru soluția lor:

Previziuni privind vremea, clima și schimbările atmosferice globale

Stiinta Materialelor

Construcția dispozitivelor semiconductoare

Supraconductivitate

Dezvoltare farmaceutică

Genetica umana

Astronomie

Probleme de transport de mare dimensiune

Hidrodinamica și dinamica gazelor

Fuziune termonucleară controlată

Explorări de petrol și gaze

Probleme de calcul în științe oceanice

Recunoașterea și sinteza vorbirii, recunoașterea imaginilor

Una dintre cele mai mari provocări este modelarea sistemului climatic și predicția vremii. În acest caz, ecuațiile de dinamică a continuului și ecuațiile de termodinamică de echilibru sunt rezolvate împreună numeric. Să simuleze desfășurarea proceselor atmosferice pe o perioadă de 100 de ani și un număr de elemente de discretizare de 2,6×106 (o grilă cu un pas de 10 în latitudine și longitudine pe întreaga suprafață a Planetei cu 20 de straturi în înălțime, starea fiecărui element). este descrisă de 10 componente) în orice moment starea atmosferei terestre este descrisă prin numere de 2,6×107. Cu un pas de eșantionare de timp de 10 minute, trebuie determinate 5 × 104 ansambluri pe perioada de timp simulată (adică 1014 valori numerice necesare ale calculelor intermediare). La estimarea numărului de operații de calcul necesare pentru a obține fiecare rezultat intermediar la 102÷103, numărul total de calcule în virgulă mobilă necesare pentru a efectua un experiment numeric cu un model atmosferic global ajunge la 1016÷1017.

Un supercalculator cu o performanță de 1012 op/sec în cazul ideal (încărcare completă și algoritmizare eficientă) va efectua un astfel de experiment în decurs de câteva ore; Pentru a efectua întregul proces de modelare, este necesar să rulați programul de mai multe ori (de zeci/sute de ori).

Problema supercalculaturii este atât de importantă încât multe state supraveghează munca în domeniul tehnologiilor supercalculatoarelor.

Sprijinul statului este direct legat de faptul că independența în producerea și utilizarea tehnologiei informatice este în interesul securității naționale, iar potențialul științific al țării este direct legat și este determinat în mare măsură de nivelul de dezvoltare a tehnologiei informatice și a software-ului.

În scopul obiectivității la comparație, performanța calculatoarelor super-electronice este calculată pe baza execuției unei sarcini de testare cunoscute anterior („benchmark”, din benchmarkul englez). Performanța de vârf este determinată de numărul maxim de operații care pot fi efectuate într-o unitate de timp în absența conexiunilor între dispozitivele funcționale, caracterizează capabilitățile potențiale ale echipamentului și nu depinde de programul care se execută.

Dezavantajul metodei de evaluare a performanței de vârf ca numărul de instrucțiuni executate de un computer pe unitatea de timp (MIPS, Million Instruction Per Second) oferă doar cea mai generală idee despre performanță, deoarece nu ține cont de specificul de programe specifice (este greu de prezis la ce număr și ce instrucțiuni specifice procesorului programul utilizatorului).

Trebuie remarcat faptul că există argumente împotriva utilizării practice pe scară largă a calculului paralel:

Sistemele de calcul paralele sunt prohibitiv de scumpe. Conform legii lui Grosch, confirmată de practică, performanța calculatorului crește proporțional cu pătratul costului său; Ca urmare, este mult mai profitabil să obțineți puterea de calcul necesară achiziționând un procesor puternic decât folosind mai multe procesoare mai lente.

Contra argument. Creșterea vitezei calculatoarelor electronice secvenţiale nu poate continua la nesfârşit; calculatoarele sunt supuse unei învechiri rapide și sunt necesare costuri financiare frecvente pentru achiziționarea de noi modele. Practica creării de sisteme de calcul paralele din clasa Beowulf a arătat în mod clar rentabilitatea acestei căi particulare.

La organizarea paralelismului, pierderile de performanță cresc prea repede. Conform ipotezei lui Marvin Minsky, accelerația de calcul realizată la utilizarea unui sistem paralel este proporțională cu logaritmul binar al numărului de procesoare (la 1000 de procesoare, accelerația posibilă este de numai 10).

Contra argument. Estimarea de accelerare dată este corectă pentru paralelizarea anumitor algoritmi. Cu toate acestea, există un număr mare de probleme, atunci când sunt rezolvate în paralel, se realizează o utilizare aproape de 100% a tuturor procesoarelor disponibile ale unui sistem de calcul paralel.

Calculatoarele seriale se îmbunătățesc constant. Conform binecunoscutei legi a lui Moore, complexitatea microprocesoarelor secvenţiale se dublează la fiecare 18 luni, astfel încât performanţa necesară poate fi atinsă pe computerele secvenţiale „obişnuite”.

Contra argument. O dezvoltare similară este caracteristică sistemelor paralele.

Cu toate acestea, utilizarea paralelismului vă permite să obțineți accelerarea necesară a calculelor fără a aștepta dezvoltarea unor procesoare noi, mai rapide. Eficiența paralelismului depinde puternic de proprietățile caracteristice ale sistemelor paralele. Toate calculatoarele electronice în serie moderne funcționează în conformitate cu circuitul clasic von Neumann; sistemele paralele se disting printr-o varietate semnificativă de arhitectură și efectul maxim din utilizarea paralelismului poate fi obținut prin utilizarea pe deplin a tuturor caracteristicilor hardware-ului (consecința este că transferul de algoritmi și programe paralele între diferite tipuri de sisteme). este dificil și uneori imposibil).

Contra argument. Având în vedere varietatea reală a arhitecturilor sistemelor paralele, există și anumite modalități „stabilite” de a asigura paralelismul. Invarianța software-ului creat este asigurată prin utilizarea instrumentelor software standard pentru suportul calculului paralel (biblioteci software PVM, MPI, DVM etc.). PVM și MPI sunt utilizate în supercalculatoarele Cray-T3.

De-a lungul deceniilor de funcționare a calculatoarelor electronice seriale, s-a acumulat o cantitate imensă de software care se concentrează pe computerele electronice seriale; procesarea lui pentru calculatoare paralele este practic imposibilă.

Contra argument. Dacă aceste programe oferă o soluție pentru sarcinile atribuite, atunci procesarea lor nu este deloc necesară. Totuşi, dacă programele secvenţiale nu permit obţinerea de soluţii la probleme într-un timp acceptabil, sau este nevoie să se rezolve noi probleme, atunci este necesară dezvoltarea unui nou software care poate fi implementat iniţial în execuţie paralelă.

Există o limitare în ceea ce privește accelerarea calculelor cu implementarea paralelă a algoritmului în comparație cu implementarea secvențială.

Contra argument. De fapt, nu există deloc algoritmi fără o (o anumită) cotă de calcule secvențiale. Totuși, aceasta este esența unei proprietăți a algoritmului și nu are nimic de-a face cu posibilitatea rezolvării paralele a problemei în general. Este necesar să învățați cum să aplicați noi algoritmi care sunt mai potriviti pentru rezolvarea problemelor pe sisteme paralele.

Astfel, pentru fiecare considerație critică împotriva utilizării tehnologiilor de calcul paralele, există un contraargument mai mult sau mai puțin semnificativ.

1.2 Prelucrarea paralelă a datelor

1.2.1 Posibilitate fundamentală de prelucrare paralelă

Este posibil să se construiască m procesoare care, atunci când sunt operate simultan, produc rezultatul dorit într-un singur ciclu de ceas al computerului.

1.2.2. Modele abstracte de calcul paralel

Figura 1. Simularea unui circuit de dimensiune 15, adâncime 5 cu două procesoare folosind o mașină paralelă cu acces aleatoriu (mașină PRAM)

1.2.3. Metode de prelucrare paralelă a datelor, eroare de calcul

Sunt posibile următoarele moduri de execuție a părților independente ale programului:

Execuție paralelă – mai multe comenzi de prelucrare a datelor sunt executate în același timp; Acest mod de calcul poate fi realizat nu numai prin prezența mai multor procesoare, ci și prin utilizarea dispozitivelor de procesare prin conducte și vectori.

Calcul distribuit - acest termen este de obicei folosit pentru a indica o metodă de procesare paralelă a datelor, care utilizează mai multe dispozitive de procesare care sunt suficient de îndepărtate unul de celălalt și în care transmisia de date prin liniile de comunicație duce la întârzieri semnificative de timp.

Cu această metodă de organizare a calculelor, prelucrarea datelor este eficientă doar pentru algoritmi paraleli cu intensitate scăzută a fluxurilor de transfer de date interprocesor; Așa funcționează, de exemplu, sistemele de calcul cu mai multe mașini, formate prin combinarea mai multor calculatoare electronice individuale folosind canale de comunicație ale rețelelor de informații locale sau globale.

Formal, această listă poate include și modul multitasking (mod de partajare a timpului), în care un singur procesor este folosit pentru a executa procese; Acest mod este convenabil pentru depanarea aplicațiilor paralele.

Există două moduri de a procesa datele în paralel: paralelism și pipeline.

Paralelismul presupune prezența a p dispozitive identice pentru prelucrarea datelor și a unui algoritm care permite fiecăruia să efectueze o parte independentă a calculelor; la sfârșitul procesării, datele parțiale sunt colectate împreună pentru a obține rezultatul final. În acest caz, vom accelera procesul de p ori. Nu orice algoritm poate fi paralelizat cu succes în acest fel (o condiție naturală pentru paralelizare este calculul părților independente ale datelor de ieșire folosind aceleași - sau similare - proceduri; iterația sau recursivitatea cauzează cele mai mari probleme la paralelizare).

Ideea procesării pipeline este de a izola etapele individuale ale efectuării unei operațiuni generale, iar fiecare etapă, după finalizarea lucrării, trece rezultatul la următoarea, acceptând simultan o nouă porțiune de date de intrare. Fiecare etapă de prelucrare este realizată de propria sa parte a dispozitivului de prelucrare a datelor (etapa transportoare), fiecare etapă realizează o acțiune specifică (micro-operare); procesarea generală a datelor necesită ca aceste părți să se declanșeze secvenţial.

Sistemul transportor la executarea comenzilor imită funcționarea unui transportor al unei fabrici de asamblare, pe care un produs trece secvenţial pe un număr de posturi de lucru; iar la fiecare dintre ele se efectuează o nouă operație asupra produsului. Efectul de accelerare este obținut prin prelucrarea simultană a unui număr de produse la diferite locuri de muncă.

Accelerarea calculelor este realizată prin utilizarea tuturor etapelor conductei pentru procesarea datelor în flux (datele sunt transmise în flux la intrarea conductei și sunt procesate secvenţial în toate etapele). Conductele pot fi dispozitive scalare sau vectoriale (singura diferență este că în acest din urmă caz pot fi utilizați vectori de instrucțiuni). În cazul unei lungimi de transportoare l, timpul de procesare a n operații independente va fi l+n−1 (fiecare treaptă funcționează pe unitatea de timp). Când se utilizează un astfel de dispozitiv, procesarea unei singure porțiuni de date de intrare va necesita l×n timp și numai pentru multe porțiuni vom obține o viteză de calcul apropiată de l.

Din figura 2 se poate observa că performanța E a unui dispozitiv transportor crește asimptotic odată cu creșterea lungimii n a setului de date la intrarea sa, tinzând spre o performanță maximă teoretică de 1/τ

Figura 2. Performanța dispozitivului transportor în funcție de lungimea setului de date de intrare

1.3. Conceptul de proces paralel și granule de paralelizare

Cea mai generală schemă pentru efectuarea calculelor secvențiale și paralele este prezentată în Figura 3 (punctele de timp S și E sunt începutul și, respectiv, sfârșitul sarcinii).

Figura 3. Diagrame de execuție a procesului în timpul calculului secvențial - a), cu paralelizare aproape de ideală - b) și în cazul general al paralelizării - c)

Un proces este un nume dat anumitor secvențe de comenzi care, ca și alte procese, pretind că folosesc procesorul pentru executarea lor; comenzile (instrucțiunile) din cadrul procesului sunt executate secvențial, paralelismul intern nu este luat în considerare.

În Figura 3, liniile subțiri arată acțiunile de creare a proceselor și de schimb de date între ele, liniile groase arată execuția efectivă a proceselor (axa x este timpul). În cazul calculelor secvenţiale se creează un singur proces (Figura 3a) care realizează acţiunile necesare; La executarea algoritmului în paralel, sunt necesare mai multe procese (ramuri paralele ale sarcinii). În cazul ideal, toate procesele sunt create simultan și terminate în același timp (Figura 3b); în cazul general, diagrama procesului este mult mai complicată și reprezintă un fel de grafic (Figura 3c).

Lungimea caracteristică a unui grup de instrucțiuni executate secvențial în fiecare dintre procesele paralele se numește dimensiunea granulei (granule). În orice caz, este indicat să se străduiască „bob grosier” (ideal – diagrama 3b). De obicei, dimensiunea unui granule (granule) este de la zeci până la sute de mii de operații ale mașinii (care este cu ordine de mărime mai mare decât dimensiunea tipică a unui operator Fortran sau C/C++). În funcție de mărimea granulelor, ele vorbesc de paralelism cu granulație fină și granulație grosieră.

Mărimea granulei este, de asemenea, influențată de comoditatea programării - un anumit fragment logic complet al programului este adesea proiectat sub forma unei granule. Este recomandabil să depuneți eforturi pentru încărcarea uniformă a procesoarelor.

Dezvoltarea de programe paralele este o provocare din cauza dificultății de a identifica paralelismul (de obicei ascuns) într-un program (adică identificarea părților algoritmului care se pot executa independent unul de celălalt).

Automatizarea detectării paralelismului în algoritmi nu este ușoară și este puțin probabil să fie rezolvată complet în viitorul apropiat. În același timp, de-a lungul deceniilor de funcționare a tehnologiei informatice, s-a dezvoltat un astfel de număr de algoritmi secvențiali încât nu se poate pune problema paralelizării lor manual.

Chiar și cel mai simplu model de calcul paralel relevă o circumstanță importantă: timpul de schimb de date ar trebui să fie cât mai scurt posibil până la timpul de execuție al secvenței de comenzi care formează granula.

Pentru probleme reale (în mod tradițional), dimensiunea caracteristică a granulului de paralelizare este cu câteva ordine de mărime mai mare decât dimensiunea caracteristică a operatorului unui limbaj de programare tradițional (C/C++ sau Fortran).

1.4. Interacțiunea proceselor paralele, sincronizarea proceselor

Executarea comenzilor programului formează un proces de calcul; în cazul execuției mai multor programe pe memorie comună sau partajată și al schimbului de mesaje între aceste programe, se obișnuiește să vorbim despre un sistem de procese care interacționează concomitent.

Crearea și distrugerea proceselor în sistemele de operare asemănătoare UNIX sunt efectuate de operatori (apeluri de sistem).

Paralelismul este adesea descris în termeni de instrucțiuni macro; în limbile paralele, ramurile paralele sunt pornite folosind operatorul JOIN.

Pentru sistemele de calcul multiprocesor, asigurarea sincronizării proceselor este de o importanță deosebită. De exemplu, momentul declanșării schimbului de date între procesoare nu este a priori convenit în niciun fel și nu poate fi determinat cu acuratețe, deoarece depinde de mulți parametri greu de estimat ai funcționării sistemelor de calcul multiprocesor, în timp ce sincronizarea este pur și simplu necesară pentru a asigura o întâlnire pentru schimbul de informații. În sistemele de calcul multiprocesor cuplate slab, nu se poate spera deloc la o sincronizare absolută a ceasurilor mașinii ale procesoarelor individuale; se poate vorbi doar despre măsurarea intervalelor de timp în sistemul de timp al fiecărui procesor.

Sincronizarea este o modalitate eficientă de a preveni situațiile de „blocare” - o situație în care fiecare dintre procesele care interacționează a primit la dispoziție o parte din resursele de care are nevoie, dar nici el, nici celelalte procese nu au suficiente resurse pentru a finaliza procesarea și, ulterior, a elibera resurse.

Sistemele de programare paralelă utilizează tehnici de sincronizare la nivel înalt. Tehnologia de programare paralelă MPI utilizează o schemă de sincronizare pentru schimbul de informații între procese.

Sincronizarea poate fi susținută și de hardware (de exemplu, sincronizarea barierei în supercomputerul Cray T3, cu ajutorul căruia toate procesele așteaptă un anumit punct din program, după ce se ajunge la care este posibilă munca ulterioară.

1.5. Accelerație posibilă în calculul paralel (legea lui Amdahl)

Este interesant să se estimeze amploarea posibilei creșteri a productivității, ținând cont de caracteristicile calitative ale programului inițial secvenţial în sine.

Figura 4. Schema de derivare a legii lui Amdahl

Legea lui Amdahl (1967) raportează potențiala accelerare a calculelor la paralelizarea cu fracția de operații care sunt efectuate a priori secvenţial. Fie f(0

La transferul algoritmului pe o mașină paralelă, timpul de calcul va fi distribuit după cum urmează:

f×ts – timpul de execuție al unei părți a algoritmului care nu poate fi paralelizată,

· (1-f)×ts/n – timpul petrecut la executarea părții paralelizate a algoritmului.

Timpul t p necesar pentru calculul pe o mașină paralelă cu n procesoare este

t p =f×ts+(1-f)×ts/n .

Accelerarea timpului de calcul cu o proporție mică de operații secvențiale (f<<1) возможно достичь (не более чем в n раз) ускорения вычислений.

În cazul lui f=0,5, este imposibil să se realizeze S>2 cu orice număr de procesoare! Rețineți că aceste restricții sunt de natură fundamentală (nu pot fi ocolite pentru un algoritm dat), dar o estimare practică a fracției f a operațiilor secvențiale este de obicei imposibilă a priori.

Astfel, caracteristicile calitative ale algoritmului însuși impun restricții asupra posibilei accelerații în timpul paralelizării. De exemplu, algoritmii de calcul care folosesc formule secvențiale, care sunt tipice pentru calculele de inginerie, sunt slab paralelizați (partea f este semnificativă), în timp ce, în același timp, algoritmii care pot fi redusi la probleme de programare liniară sunt paralelizați satisfăcător.

Nu este ușor de estimat a priori fracția de operații secvențiale f. Cu toate acestea, se poate încerca să se folosească în mod formal legea lui Amdahl pentru a rezolva problema inversă a determinării f din datele de performanță experimentale; aceasta face posibilă evaluarea cantitativă a eficienței de paralelizare atinsă.

Figura 6. Performanța unui sistem de cluster de calcul folosind procedura de multiplicare a matricei (experiment și calcul folosind formula Amdahl)

Figura 6 prezintă rezultatele unui experiment pe clusterul SCI-MAIN al Centrului de Calcul de Cercetare al Universității de Stat din Moscova cu privire la problema înmulțirii matricei folosind o schemă de bandă (dimensiunea 103 × 103 numere reale cu precizie dublă), datele experimentale se potrivesc cel mai bine (a fost folosită metoda celor mai mici pătrate) corespund formulei Amdahl cu f = 0,051.

Legea lui Amdahl este convenabilă pentru analiza calitativă a problemei paralelizării.

2. Principii de construire a sistemelor de calcul multiprocesor

2.1. Arhitectura sistemelor de calcul multiprocesor

Arhitectura computerelor paralele s-a dezvoltat aproape de la începutul creării și utilizării lor și într-o varietate de direcții. Cele mai generale prevederi conduc la două clase - calculatoare cu memorie partajată și calculatoare cu memorie distribuită. Calculatoarele cu memorie partajată constau din mai multe procesoare care au acces cu prioritate egală la memoria partajată cu un singur spațiu de adresă (Figura 7a).

Figura 7. Calculatoare paralele:

a) cu memorie partajată b) cu memorie distribuită

Un exemplu tipic de astfel de arhitectură sunt computerele din clasa SMP (Symmetric Multi Processors), care includ mai multe procesoare, dar o singură memorie, un set de dispozitive de intrare/ieșire și un sistem de operare. Avantajul computerelor cu memorie partajată este ușurința relativă de a programa sarcini paralele; dezavantajul este scalabilitatea insuficientă. Sistemele SMP reale conțin de obicei nu mai mult de 32 de procesoare; tehnologia NUMA este utilizată pentru a crește și mai mult puterea de calcul a unor astfel de sisteme.

În calculatoarele cu memorie distribuită (sisteme multicomputer), fiecare nod de calcul este un computer cu drepturi depline și include un procesor, memorie, dispozitive de intrare/ieșire, sistem de operare etc. (Figura 7b). Un exemplu tipic al unei astfel de arhitecturi sunt sistemele informatice din clasa MPP (Massively Parallel Processing), în care noduri de calcul omogene sunt combinate folosind un mediu de comunicare. Avantajul calculatoarelor cu memorie distribuită este scalabilitatea (aproape nelimitată); dezavantajul este necesitatea de a folosi software specializat (biblioteci de mesagerie) pentru a face schimb de informații între nodurile de calcul. Pentru sistemele de calcul multiprocesor cu memorie partajată și distribuită, sunt utilizați termenii mașini cuplate strâns și, respectiv, slab cuplate.

După cum sa arătat, performanța canalelor de comunicare influențează foarte mult posibilitatea paralelizării efective, iar acest lucru este important pentru ambele arhitecturi considerate. Cel mai simplu sistem de comunicație este o magistrală comună (Figura 8a), care conectează toate procesoarele și memoria, cu toate acestea, chiar dacă numărul de dispozitive de pe magistrală este mai mare de câteva zeci, performanța magistralei scade catastrofal din cauza influenței reciproce și a concurenței dintre dispozitive pentru proprietatea de monopol asupra magistralei în timpul schimburilor de date.

Figura 8. Sisteme multiprocesor

a) - cu o magistrală comună, b) - cu un comutator matrice

c) - cu comutatoare în cascadă (rețea Omega)

Sunt folosite abordări mai sofisticate pentru a construi sisteme mai puternice. O schemă eficientă de comutare a matricei este (Figura 8b), în care dispozitivele sunt conectate între ele prin comutatoare bidirecționale care permit sau interzic transferul de informații între modulele corespunzătoare. O alternativă este punerea în cascadă a comutatoarelor; de exemplu, conform schemei rețelei Omega (Figura 8c). Mai mult, fiecare comutator poate conecta oricare dintre cele două intrări ale sale la oricare dintre cele două ieșiri; pentru a conecta n procesoare cu n blocuri de memorie în acest caz, sunt necesare n×log2n/2 comutatoare. Dezavantajul schemelor cu comutatoare în cascadă este întârzierea în funcționarea comutatorului.

Pentru sistemele cu memorie distribuită sunt utilizate aproape toate opțiunile de conectare imaginabile (Figura 9), în timp ce parametrul de calitate în ceea ce privește viteza de transmitere a mesajelor este lungimea medie a căii care conectează procesoarele arbitrare; În acest caz, ne referim la calea fizică, deoarece implementarea topologiei logice (prin software) nu prezintă dificultăți.

Figura 9. Opțiuni pentru topologiile de comunicație cu procesor în sistemele de calcul multiprocesor

Cea mai simplă topologie liniară (Figura 9a) corespunde în mod satisfăcător multor algoritmi, care se caracterizează prin conectarea doar a proceselor învecinate între ele (probleme unidimensionale de fizică matematică și cele multidimensionale, reduse la cele unidimensionale); dezavantajul este incapacitatea de a transmite mesaje dacă există o pauză oriunde. Prin înjumătățirea lungimii medii a căii și creșterea fiabilității comunicării (dacă comunicarea este întreruptă, mesajele pot fi transmise în direcția opusă, deși la o viteză mai mică), se realizează conectarea primului nod la ultimul - o topologie „inel” este obţinute (Figura 9b).

Topologia „stea” (Figura 9c) corespunde cel mai bine cu distribuția sarcinii între procese, caracteristică sistemelor „client/server” (nodul master „distribuie” sarcini și „colectează” rezultatele calculelor, în timp ce nodurile slave interacționează cu unul pe altul minim).

Topologia latice (Figura 9d) a fost folosită încă de la începutul anilor 90, la construirea supercomputerului Intel Paragon bazat pe procesoare i860; găsirea căii minime de transmisie a datelor între procesoarele A și B pentru topologia „rețeaua tridimensională” este ilustrată în Figura 10. Topologia „torului bidimensional” (Figura 9e) extinde „rețeaua bidimensională” cu conexiuni suplimentare care reduce lungimea căii medii (desigur, un „tor tridimensional”) și este caracteristic tehnologiei de rețea SCI. Este utilizată o topologie tridimensională „clică” (Figura 9e), caracterizată prin prezența fiecărui procesor care comunică cu fiecare. Figura 9h prezintă o vedere generală a topologiei comunicării complete a tuturor procesoarelor între ele; Această topologie se caracterizează prin cea mai scurtă lungime medie a căii între procesoare, dar este practic imposibil de implementat în hardware cu un număr semnificativ de procesoare din cauza creșterii catastrofale a numărului de conexiuni.

Topologia „hipercubului” (Figura 9i) se caracterizează printr-o lungime medie redusă a căii și apropierea de structurile multor algoritmi de calcul numeric, ceea ce asigură performanțe ridicate. Un hipercub N-dimensional conține 2N procesoare. Un hipercub bidimensional este un pătrat, un hipercub tridimensional formează un cub obișnuit, iar un hipercub cu patru dimensiuni este un cub în interiorul unui cub. Pentru familia de supercalculatoare nCube, un hipercub de dimensiunea maximă 13 conține 8192 de procesoare; în sistemul nCube 3, numărul de procesoare poate ajunge la 65536 (hipercub cu 16 dimensiuni).

Următorii indicatori sunt adesea utilizați ca caracteristici principale ale topologiei rețelei de date:

Figura 10. Găsirea căii minime pentru transmiterea mesajelor între procesoare într-o topologie de rețea tridimensională

Diametrul este definit ca distanța maximă (de obicei cea mai scurtă cale între procesoare) dintre două procesoare din rețea; această valoare caracterizează timpul maxim necesar pentru transferul de date între procesoare (timpul de transfer este, într-o primă aproximare, direct proporțional cu calea). lungime).

Conectivitatea este un indicator care caracterizează prezența diferitelor rute de transfer de date între procesoarele de rețea; un anumit tip de indicator poate fi definit, de exemplu, ca numărul minim de arce care trebuie eliminate pentru a împărți rețeaua de date în două zone deconectate.

Lățimea diviziunii binare este un indicator definit ca numărul minim de arce care trebuie eliminate pentru a împărți o rețea de date în două zone deconectate de aceeași dimensiune.

Costul este definit, de exemplu, ca numărul total de linii de date dintr-un sistem de calcul multiprocesor.

Pare firesc să combinați avantajele sistemelor cu memorie partajată (ușurință relativă de a crea programe paralele) și distribuită (scalabilitate ridicată); Soluția la această problemă a fost crearea de computere cu arhitectură NUMA (Non Uniform Memory Access).

În acest sens, computerele clasice SMP au o arhitectură UMA (Uniform Memory Access). Aceasta utilizează un mecanism (de obicei la nivel hardware - oricare dintre acestea este mai rapid) care permite programelor utilizatorului să trateze toată memoria (fizic) distribuită între procesoare ca un singur spațiu de adrese. Exemple de calculatoare NUMA sunt sistemul Cm, construit în anii șaptezeci și care conține un set de clustere unite printr-o magistrală intercluster și complexul BBN Butterfly care combină 256 de procesoare (1981, BBN Advanced Computers).

2.2. Distribuția calculelor și a datelor în multiprocesoare
sisteme de calcul cu memorie distribuită

Dacă un sistem de calcul multiprocesor conține noduri de calcul cu RAM locală, în plus față de distribuirea părților de calcul între nodurile de calcul individuale, este important să se distribuie rațional datele (de exemplu, blocuri de matrice procesate de dimensiune semnificativă) între nodurile de calcul disponibile. Faptul este că timpul petrecut pentru schimbul de date între nodurile de calcul care prelucrează aceste date și nodurile de calcul care stochează aceste date în RAM-ul lor local poate încetini procesul de calcul cu ordine de mărime.

Este clar că locația unui grup mare de date pe un nod de calcul nu este recomandată din cauza pierderii semnificative inevitabile de timp pentru organizarea transferului de blocuri individuale ale acestor date către nodul de procesare de calcul. Pe de altă parte, o împărțire pur formală a datelor într-un număr de blocuri egal cu numărul nodului de calcul este plină de același lucru.

Distribuția rațională a datelor în RAM locală a unui nod de calcul ar trebui efectuată ținând cont de frecvența de acces al fiecărui nod de calcul la fiecare bloc de date situat pe nodurile de calcul corespunzătoare, încercând în același timp să minimizeze numărul de schimburi, ceea ce necesită determinarea structura informatică fină a algoritmului.

S-ar părea că în cazul general este posibil să se construiască o anumită funcție a complexității (de exemplu, în termeni de timp) a calculelor, ținând cont atât de costurile de resurse ale calculelor în sine, cât și de complexitatea schimburilor pentru un anumit distribuția datelor între nodurile de calcul și minimizarea în continuare a acestei funcții în funcție de parametrul (parametrii) distribuției datelor; În plus, distribuția în sine poate fi modificată. În realitate, construirea unei astfel de funcții este dificilă din cauza necesității de a cuantifica parametrii de timp ai operațiunilor și de a identifica parametri semnificativi de optimizare. Un candidat pentru rolul unei astfel de funcții ar putea fi, de exemplu, legea rețelei a lui Amdahl descrisă mai sus.

Pachetele standard pentru rezolvarea problemelor de algebră liniară folosesc metode de distribuire a datelor între nodurile de calcul, bazate pe analiză teoretică și practică pe termen lung.

2.3. Clasificarea sistemelor de calcul paralele

Clasificarea arhitecturilor sistemelor de calcul are ca scop identificarea atât a factorilor principali care caracterizează fiecare arhitectură, cât și a interrelațiilor dintre structurile de calcul paralele.

SISD (Single Instruction stream / Single Data stream) – un singur flux de comandă și un singur flux de date; Clasa SISD include mașini secvenţiale clasice (tip von Neumann). În astfel de mașini există un singur flux de instrucțiuni (procesate secvențial), fiecare dintre ele inițiind o operație scalară. În această clasă se încadrează și mașinile cu tehnologie de procesare a transportoarelor.

SIMD (Single Instruction stream / Multiple Data stream) – un singur flux de comandă împreună cu un flux de date multiple. În acest caz, un flux de comenzi este păstrat, dar include comenzi vectoriale care efectuează o operație aritmetică pe mai multe date simultan. Operațiile vectoriale pot fi efectuate printr-o matrice de procesoare (ca în mașina ILLIAC IV) sau printr-o metodă pipeline (Cray-1). De fapt, microprocesoarele Pentium VI și Xeon cu setul de instrucțiuni MMX, SSE, SSE2 sunt sisteme SIMD cu un singur cip.

Din țările CSI, sistemele SIMD ar trebui denumite PS-2000 (1972 - 1975) - un sistem computerizat extrem de paralel pentru procesarea informațiilor cu o productivitate de până la 200 de milioane op/s.

MISD (Multiple Instruction stream/Single Data stream) – flux de comandă multiple și flux de date unic. Arhitectura presupune prezența multor procesoare care prelucrează același flux de date; se crede că astfel de mașini nu există.

MIMD (Multiple Instruction stream / Multiple Data stream) - fluxuri multiple de comenzi și date. Clasa MIMD include două tipuri de mașini: controlate de flux de comandă și controlate de flux de date; Dacă computerele de primul tip folosesc execuția tradițională a comenzilor secvenţial în locația lor în program, atunci al doilea tip implică activarea operatorilor, deoarece aceștia sunt pregătiți în prezent.

Clasa presupune prezența mai multor procesoare combinate într-un singur complex, fiecare lucrând cu propriul flux de comenzi și date.

Un exemplu clasic este sistemul Denelcor HEP (Heterogeneous Element Processor); conține până la 16 module de procesor, conectate printr-un comutator în mai multe etape la 128 de module de memorie de date și toate modulele de procesor pot funcționa independent unele de altele cu propriile fluxuri de comandă, iar fiecare modul de procesor poate suporta până la 50 de fluxuri de comandă utilizator.

2.4. Sisteme de calcul multiprocesor cu memorie distribuită

Începând cu ultimul deceniu al secolului al XX-lea, a existat o tendință ca sistemele de memorie distribuită să monopolizeze arhitecturile supercomputerelor, dispozitivele disponibile imediat ce sunt folosite din ce în ce mai mult ca procesoare pe nodurile de calcul. Principalele avantaje ale unor astfel de sisteme sunt scalabilitatea enormă (în funcție de clasa sarcinilor care se rezolvă și de buget, utilizatorul poate comanda un sistem cu un număr de noduri de la câteva zeci la mii); ceea ce a dus la apariția unui nou nume pentru sistemele luate în considerare - computere masiv paralele (sisteme de calcul ale arhitecturii MPP - Massively Parallel Processing).

Primul supercomputer cu procesare masiv paralelă, Connection Machine (CM-1), a fost echipat cu 64.000 de procesoare, fiecare cu propria sa memorie. SM-1 a scanat 16 mii de articole cu știri de ultimă oră în 1/20 de secundă. și a dezvoltat un circuit integrat de procesor cu 4 mii de tranzistori în trei minute. Reprezentanții convexi ai sistemelor MPP sunt supercalculatoare din seria Cry T3.

Cry T3E (1350) este un sistem de calcul multiprocesor fabricat în 2000, cu memorie distribuită construită din procesoare RISC. Topologia rețelei de comunicații este un tor tridimensional. Sistem de operare UNICOS/mk (sistem de operare UNIX cu microkernel). Traducători pentru limbile FORTRAN, HPF, C/C++. Frecvența ceasului 675 MHz. Numărul de procesoare este de la 40 la 2176. Cantitatea maximă de RAM pentru fiecare nod este de 512 MB și viteza maximă este de 2938 Gflop/s. Spre deosebire de predecesorul său, Cry T3D, acest sistem nu necesită un computer front-end.

Sistemul folosește un procesor Alpha21164A, totuși, dacă este necesar, poate fi înlocuit cu ușurință cu un altul, de exemplu, un procesor mai rapid. Fiecare element de procesare conține o unitate centrală de procesare, un modul de memorie și o unitate de comunicații pentru comunicarea cu alte procesoare. Capacitatea canalului de comunicație între procesoare este de 325 MB/s.

Sunt acceptate modelele de programare MPI, PVM, HPF și propria bibliotecă de mesagerie shmem a lui Cray. Performanța obținută prin rezolvarea sistemelor de ecuații algebrice liniare ajunge la 1,12 Tflop/s.

MPP - sistemul este format din noduri de calcul omogene, inclusiv:

Unul, și uneori mai multe procesoare centrale (de obicei arhitectura RISC - Reduced Instruction Set Computing, care se caracterizează printr-un cuvânt lung de comandă pentru specificarea operațiilor, un set redus de instrucțiuni și execuția majorității operațiunilor într-un singur ciclu de procesor),

Memoria locală (accesul direct la memoria altor noduri nu este posibil),

procesor de comunicație (sau adaptor de rețea),

Hard disk-uri (opțional) și/sau alte dispozitive de intrare/ieșire.

La sistem sunt adăugate noduri speciale I/O și noduri de control. Nodurile de calcul sunt conectate printr-un mediu de comunicare (rețea de mare viteză, comutatoare etc.).

Întreținerea sistemelor multiprocesor nu este o sarcină ușoară - cu sute/mii de noduri de calcul, defecțiunea zilnică a câtorva dintre ele este inevitabil; Sistemul de management al resurselor de 5k (complex software și hardware) al unui computer masiv paralel este necesar pentru a gestiona astfel de situații, ocolind o repornire generală catastrofală cu pierderea contextului de executare a sarcinilor în prezent.

2.4.1. Supercalculatoare masiv paralele din seria CRY T3

Fondată în 1972, Cry Research Inc. (acum Cry Inc.), renumit pentru dezvoltarea supercomputerului vectorial Cry 1, în 1993–1995 a lansat modelele Cry T3D/T3E, care implementează pe deplin principiul sistemelor masiv paralele (sisteme de arhitectură MPP). În configurația maximă, aceste computere combină procesoare 32 - 2048 DEC Alpha 21064/150 MHz, 21164/600 MHz, 21164A/675 MHz (în funcție de model), se realizează toate preprocesarea și pregătirea programului (de exemplu, compilare). pe mașina de control (gazdă -calculator).

Dezvoltatorii seriei Cry T3D/T3E au luat calea creării de memorie virtuală partajată. Fiecare procesor poate accesa direct doar memoria locală, dar toate nodurile au un singur spațiu de adrese. Atunci când se încearcă accesarea unei adrese aparținând memoriei locale a altui procesor, se generează o întrerupere hardware specializată și sistemul de operare realizează un transfer de pagină de la un nod la altul, și datorită vitezei extrem de mari a sistemului de comunicații ( rata maximă de transfer de date între două noduri ajunge la 480 MB/s), această abordare este în general justificată. Cu toate acestea, a fost observat un efect de „ping-pong” de reducere bruscă a performanței - dacă variabilele modificate de mai multe procesoare ajung pe o singură pagină, această pagină migrează continuu între noduri. Nodurile de calcul execută programe de utilizator în modul exclusiv (modul cu o singură sarcină).

Designul specific al calculatoarelor din seria Cry T3 este caracterizat de un triplu de numere, de exemplu, 24/16/576 (noduri de control/noduri de sistem de operare/noduri de calcul); Cu topologia „torului tridimensional” utilizată, fiecare nod (indiferent de locația sa) are șase vecini imediati. Atunci când alegeți o rută între două noduri A și B (ale căror coordonate 3D sunt prezentate în Figura 11), routerele de rețea, începând procesul de la vârful inițial A, efectuează mai întâi o compensare de-a lungul coordonatei X până la coordonatele următoarei comunicații nodul și nodul B devin egale; apoi acțiuni similare sunt efectuate de-a lungul coordonatei Y și apoi de-a lungul coordonatei Z (rutare similară din punct de vedere fizic are loc simultan de-a lungul tuturor celor trei coordonate). Deplasările pot fi, de asemenea, negative; dacă una sau mai multe conexiuni eșuează, acestea pot fi ocolite.

O altă caracteristică interesantă a arhitecturii Cry T3 este suportul pentru sincronizarea barierelor - organizarea hardware a tuturor proceselor care așteaptă un anumit punct din program, la atingerea căruia este posibilă munca ulterioară. Calculatoarele din seria T3E au demonstrat performanțe de 1,8 – 2,5 Tflops (pe microprocesoare 2048 Alpha/600 MHz).

O dezvoltare ulterioară a liniei Cry T3 de calculatoare masiv paralele este supercomputerul Cry XT3. Fiecare nod de calcul Cry XT3 include un procesor AMD Opteron, memorie locală (1 - 8 GB) și un canal Hyper Transport care asigură comunicarea prin unitatea de comunicare Cry SeaStar, cu performanțe de vârf (pentru AMD Opteron 2,4 GHz) de la 2,6 teraflopi (548 procesoare). ) , RAM 4,3 TB, topologie 6x12x8) până la 147 teraflopi. Cray XT3 rulează sub sistemul de operare UNICOS/lc, care vă permite să combinați până la 30.000 de noduri de calcul, utilizează compilatoare Fortran 77/90/95 și C/C++, biblioteci de comunicare MPI (Message Passing Interface cu suport pentru standardul MPI 2.0) și ShMem (dezvoltat de Cray Research Inc. biblioteca pentru lucrul cu memorie partajată), biblioteci standard pentru calcule numerice.

În ciuda faptului că a obținut rezultate atât de înalte în domeniul sistemelor MPP, Cry Inc. produce computere vector-pipeline, iar aceste modele pot fi combinate într-un sistem MPP. Performanța fiecărui procesor al computerului Cry SV1 ajunge la 4 Gflops (performanță totală a sistemului de vârf de 32 Gflops), numărul total de procesoare poate ajunge la 1000.

Figura 11. Rețeaua de comunicație „torul tridimensional” al computerului Cray T3E

2.4.2. Sisteme cluster de clasă BEOWULF

Costul prohibitiv al computerelor industriale masiv paralele i-a bântuit pe specialiștii care doreau să folosească sisteme de calcul cu putere comparabilă în cercetarea lor, dar nu au putut să cumpere supercalculatoare industriale. Căutările în această direcție au condus la dezvoltarea clusterelor de calcul (a nu se confunda cu clusterele de baze de date și servere WEB); Baza tehnologică pentru dezvoltarea clusteringului a fost microprocesoarele și tehnologiile de comunicare (de rețea) disponibile pe scară largă și relativ ieftine, care au apărut pe piața publică în anii nouăzeci.

Un cluster de calcul este o colecție de noduri de calcul (de la zeci la zeci de mii) unite printr-o rețea de mare viteză în scopul rezolvării unei singure probleme de calcul. Fiecare nod al unui cluster de calcul este de fapt un computer electronic programabil (adesea un server SMP cu două sau patru procesoare/nucleu) care rulează propriul său sistem de operare (în marea majoritate Linux(*)); Rețeaua de unificare este selectată în funcție de clasa necesară de sarcini de rezolvat și de capacitățile financiare; posibilitatea de acces de la distanță la cluster prin Internet este aproape întotdeauna implementată.

Nodurile de calcul și un computer de control combină de obicei (cel puțin) două rețele (independente) - o rețea de control (servează scopul de a gestiona nodurile de calcul) și o rețea de comunicații (deseori mai productivă) (schimb direct de date între procesele care rulează pe noduri). ); în plus, nodul de control are o ieșire către Internet pentru a accesa resursele unui cluster de utilizatori la distanță, serverul de fișiere îndeplinește funcțiile de stocare a programelor utilizatorului (Figura 12). Administrarea clusterului se realizează de pe computerul de control (sau prin acces la distanță); utilizatorii au dreptul de a accesa (în conformitate cu drepturile atribuite de administrator) la resursele clusterului exclusiv prin computerul de control.

Clusterele Windows de putere semnificativă rămân încă exotice din motive binecunoscute (în ciuda soluțiilor de clasă Windows Compute Cluster Server - WCCS promovate activ de MS).

Unul dintre primele proiecte de cluster a fost proiectul BEOWULF. Proiectul BEOWULF a fost fondat în centrul de cercetare CESDIS (Center of Excellence in Space Data and Information Sciences) creat pe baza organizației NASA GSFC (Goddard Space Flight Center) în 1994 și a început cu asamblarea la GSFC a unui nod cu 16 noduri. cluster (pe procesoare 486DX4/100 MHz, 16 Mb memorie, 3 adaptoare de rețea pe fiecare nod și 3 cabluri Ethernet paralele de 10 Mbit); Sistemul de calcul a fost destinat să desfășoare lucrări la ESS (Proiectul de Științe ale Pământului și Spațiului).

Mai târziu, departamentele NASA au asamblat alte modele de clustere asemănătoare BEOWULF: de exemplu, theHIVE (Highly-parallel Integrated Virtual Environment) de 64 de noduri cu procesor dublu (Pentium Pro/200 MHz, 4 Gb de memorie și 5 switch-uri Fast Ethernet în fiecare) . În cadrul proiectului Beowulf au fost dezvoltate drivere pentru a implementa modul Channel Bonding.

Figura 12. Diagrama mărită a unui cluster de calcul

„Beowulf” este un exemplu tipic de sistem MIMD (Multiple Instruction - Multiple Data), cu mai multe ramuri de program care rulează simultan, schimbând date la anumite intervale. Multe evoluții ulterioare din întreaga lume sunt de fapt clanuri Beowulf.

În 1998, la Laboratorul Național Los Alamos, astrofizicianul Michael Warren și membrii grupului de astrofizică teoretică au construit sistemul de calcul Avalon, care era un cluster Linux pe procesoare DEC Alpha/533 MHz. Inițial, Avalon a constat din 68 de procesoare, apoi a fost extins la 140, fiecare nod avea 256 MB de RAM, un hard disk EIDE de 3,2 Gb și un adaptor de rețea Kingston.

Nodurile sunt conectate folosind patru switch-uri Fast Ethernet și un switch Gigabit Ethernet central cu douăsprezece porturi de la 3Com.

Un exemplu tipic de sistem de calcul în cluster masiv paralel este MVS-1000M (rețea de comunicații - Myrinet 2000, viteză de schimb de informații 120-170 MB/sec, auxiliar - Fast și Gigabit Ethernet) și MVS-15000BC.

Cerința de eficiență maximă în utilizarea resurselor de putere de calcul (atât procesorul, memoria RAM, cât și memoria de disc) ale procesoarelor cluster individuale duce inevitabil la o reducere a „inteligenței” sistemului de operare al nodurilor de calcul la nivelul monitoarelor; pe de altă parte, sunt oferite sisteme de operare cluster distribuite - de exemplu, Amoeba, Chorus, Mach etc.

Serverele bladed (*) sunt produse special pentru a completa hardware-ul clusterelor de calcul - plăci verticale înguste care includ un procesor, RAM (de obicei 256 - 512 MB cu un cache L2 de 128 - 256 KB), memorie pe disc și cipuri de suport de rețea; Aceste carduri sunt instalate în „rack-uri” în format standard 3U, cu o lățime de 19² și o înălțime de 5,25², până la 24 de bucăți fiecare (240 de noduri de calcul per rack cu o înălțime de 180 cm). Pentru a reduce consumul total de energie, pot fi folosite procesoare din seria Transmeta Crusoe TM 5x00 cu tehnologie VLIW, care consumă doar câțiva wați (față de 75 W pentru P4 sau 130 W pentru cristalele de arhitectură IA-64); în același timp, consumul total de energie cu 240 de noduri de calcul nu depășește 1 kW.

Concluzie

Programarea în paralel este o întreagă zonă de probleme conexe, inclusiv suport hardware, analiza structurii algoritmilor pentru a identifica paralelismul și limbaje algoritmice pentru programarea sarcinilor paralele.

Tehnologiile de calcul paralel se dezvoltă în prezent rapid în legătură cu cerințele științei și tehnologiei mondiale.

Destul de des trebuie să se confrunte cu probleme care, deși au o valoare considerabilă pentru societate, nu pot fi rezolvate folosind computere relativ lente de birou sau de acasă. Singura speranță în acest caz se bazează pe computerele de mare viteză, care sunt denumite în mod obișnuit supercomputere. Doar mașinile din această clasă pot face față procesării unor cantități mari de informații. Acestea ar putea fi, de exemplu, date statistice sau rezultate ale observațiilor meteorologice, informații financiare. Uneori viteza de procesare este critică. Aceasta include prognoza meteo și modelarea schimbărilor climatice. Cu cât este prezis mai devreme un dezastru natural, cu atât este mai mare oportunitatea de a vă pregăti pentru el. O sarcină importantă este modelarea medicamentelor, descifrarea genomului uman, explorarea câmpurilor de petrol și gaze și alte sarcini la scară largă, a căror soluție este posibilă cu ajutorul supercomputerelor și sistemelor de cluster.

Problema de astăzi este o lipsă clară de hardware pentru calculul paralel în instituțiile de învățământ și științifice, care nu permite dezvoltarea cuprinzătoare a tehnologiilor relevante; Studiul pur teoretic adesea practicat al unui subiect duce la consecințe negative mai degrabă decât pozitive. Abia acum apar tehnologii care fac posibilă introducerea practicii calculului paralel în majoritatea laboratoarelor educaționale și industriale. Crearea de programe paralele eficiente necesită o analiză mult mai serioasă și mai aprofundată a structurii algoritmilor decât cu programarea secvențială tradițională, iar unele abordări nu pot fi implementate fără o schimbare serioasă a modului de gândire al programatorilor. Alături de analiza teoretică, este necesară o practică constantă în crearea de programe paralele pentru a obține rezultate practic semnificative.

Bibliografie

1. Voevodin V.V., Voevodin Vl.V. Calcul paralel. -SPb.: BHV-Petersburg, 2004. -608 p.

2. Harvey M. Deitel. Introducere în sistemele de operare (tradus din engleză de L.A. Teplitsky, A.B. Khodulev, Vs.S. Shtarkman, editat de Vs.S. Shtarkman). -M.: Mir, 1987 (versiunea electronică, 2004)

3. Gergel V.P., Strongin R.G. Fundamentele calculului paralel pentru sisteme de calcul multiprocesor (manual, ed. 2, actualizat). -N.Novgorod: ed. Universitatea de Stat din Nijni Novgorod poartă numele N.I. Lobachevsky, -2003 (versiunea electronică http://pilger.mgapi.edu/metods/1441/basic_pr.zip).

4. Korneev V.V. Sisteme de calcul. -M.: Helios ARV, -2004, -512 p.

5. Latsis A.O. Cum să construiți și să utilizați un supercomputer. -M.: Bestseller, 2003.

6. Shpakovski G.I. Organizarea calculatoarelor paralele și a procesoarelor superscalare. // Manual indemnizatie. -Minsk: Universitatea de Stat din Belarus, 1996. -296 p. (versiunea electronică http://pilger.mgapi.edu/metods/1441/spakovsk.zip)

7. Shpakovski G.I., Serikova N.V. Programare pentru sisteme multiprocesor în standardul MPI. -Minsk: BSU, 2002. -325 p. (versiunea electronică http://www.cluster.bsu.by/download/book_PDF.pdf, http://pilger.mgapi.edu/metods/1441/pos_mpi.pdf)

De disciplina "Paralelcalculeleîn optică și optoinformatică” în semestrul 10 Forme...

Prelegeri la disciplina „Fundarii teoretice ale controlului automatizat”

Sarcină

... ____________________________ „____”__________________200_ PrelegeriDedisciplina"Baza teoretica... calculele: 1) sistem complet centralizat - algoritm secvenţial clasic 2) sistem complet descentralizat - paralel ...

NOTE DE PRELARE la disciplina „TEHNOLOGII DE REȚEA” (versiunea adăugată) pentru studenții specialității 7

Abstract

Departamentul „Sisteme informaţionale în management” CONSPECT PRELEGIIDedisciplina„TEHNOLOGII DE REȚEA” (versiunea extinsă) pentru... un avantaj foarte important este capacitatea de a efectua paralelcalculele. Când într-un sistem de calcul, sarcina...

Note de curs pe disciplina „sisteme neurocalculatoare” Shebakpol

Abstract

Abstract prelegeriDedisciplina„Sisteme neurocalculatoare” Shebakpolsky M.F. Conținut... despre antrenament, simplitatea modelului paralelcalculele. Nu există niciun motiv să credem... computerele au o inerentă paralel natură calculele se pierde; fiecare operatie...

Procesare paralelă

Procesarea paralelă este un model pentru executarea simultană a unui proces de aplicație de către un grup de procesoare. Există trei moduri de a implementa paralelismul:
-1- Metoda SIMD de lucru cu un flux de comandă și mai multe fluxuri de date, în care toate procesoarele care lucrează sub același program procesează propriile matrice de date sub controlul procesorului principal;
-2- Metoda MIMD de lucru cu fluxuri multiple de comandă și fluxuri de date multiple, în care procesoarele lucrează în funcție de programele lor independent unul de celălalt, comunicând doar ocazional între ele;
-3- Modul MISD de lucru cu mai multe fluxuri de comandă și un flux de date.

În limba engleză: Procesare paralelă

Dicţionar financiar Finam.

Vedeți ce înseamnă „Procesare paralelă” în alte dicționare:

Procesare paralelă- Unul dintre tipurile de prelucrare a informațiilor când mai multe operații pot fi efectuate simultan. Spre deosebire de procesarea conștientă, care are loc de obicei secvenţial, acest tip de procesare are loc fără efort conștient. De exemplu, citind acestea... ...

- (prelucrare paralelă) O metodă de lucru pe un computer în care două sau mai multe părți ale unui program sunt executate nu secvențial, ci în paralel. Strict vorbind, această metodă poate fi folosită numai pe computere care au două sau mai multe... Dicţionar de termeni de afaceri

procesare paralelă- - Subiecte de telecomunicații, concepte de bază EN procesare paralelă...

procesare paralelă- lygiagretusis apdorojimas statusas T sritis automatika atitikmenys: engl. procesare paralelă vok. Parallelverarbeitung rus. procesare paralelă, f pranc. traitement en parallèle, m … Automatikos terminų žodynas

procesare paralelă a informaţiei- un model de procesare a informațiilor în creier, conform căruia informația suferă o serie de transformări în anumite „blocuri funcționale” ale creierului astfel încât la un moment dat să fie procesată simultan (în paralel) în mai multe... ... Mare enciclopedie psihologică

PRELUCRAREA INFORMAȚIILOR PARALELE- Vezi procesarea informațiilor, paralel...

O metodă de procesare paralelă a datelor de către un număr mare de procesoare, implementând metoda MIMD de organizare a paralelismului. În engleză: Massively Parallel Processing Sinonime în engleză: MPP Vezi și: Parallel processing Financial Dictionary Finam... Dicţionar financiar

PRELUCRARE, PARALEL- Prelucrarea informațiilor în care se desfășoară mai mult de o secvență de operațiuni de prelucrare simultan sau în paralel. Procesarea poate implica un nivel extrem de scăzut, componente non-simbolice, cum ar fi cele utilizate în... ... Dicționar explicativ de psihologie

conducte paralele- lygiagretusis konvejerinis apdorojimas statusas T sritis radioelektronika atitikmenys: engl. conducte paralele vok. Parallel Pipelineverarbeitung, f rus. conducte paralele, f pranc. tratament de conducte paralele, m... Radioelektronikos terminų žodynas

prelucrare simultană- prelucrare paralelă - [L.G.Sumenko. Dicționar englez-rus de tehnologia informației. M.: Întreprinderea de stat TsNIIS, 2003.] Subiecte tehnologia informației în general Sinonime procesare paralelă EN procesare simultană ... Ghidul tehnic al traducătorului

Cărți

Prelucrare paralelă a datelor
Prelucrare paralelă a datelor, A. O. Latsis. Tutorialul oferă o imagine de ansamblu sistematică aprofundată a tehnologiilor paralele de procesare a datelor. Atenția principală este acordată tehnologiilor software tradiționale de programare paralelă...

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

MINISTERUL EDUCAȚIEI ȘI ȘTIINȚEI AL REPUBLICII KAZAKHSTAN

Universitatea de Stat din Kazahstanul de Nord poartă numele. M. Kozybaeva

Facultatea de Tehnologia Informaţiei

Departamentul Sisteme Informaţionale

Procesul de procesare paralel

Completat de: Makhkambaeva A.S.

Verificat de: Kasimov I.R.

Petropavlovsk, 2014

Introducere

În sistemele cu un singur procesor, apare așa-numitul pseudo-paralelism - deși în fiecare moment procesorul este ocupat cu procesarea unei sarcini specifice pentru alta, se realizează iluzia executării în paralel a mai multor sarcini. În sistemele multiprocesor, sarcina de a maximiza utilizarea eficientă a fiecărui procesor specific se rezolvă și prin comutarea între procese, dar aici, alături de pseudo-paralelism, există și paralelism real, când procese diferite sunt executate pe procesoare diferite în același timp. .

Ideea paralelizării procesării datelor se bazează pe ideea că majoritatea problemelor pot fi împărțite într-un set de probleme mai mici care pot fi rezolvate simultan. Procesele a căror execuție se suprapune cel puțin parțial în timp sunt numite paralele.

În 1967, Gene Amdahl a formulat legea limitării creșterii productivității la paralelizarea calculelor: „Când o sarcină este împărțită în mai multe părți, timpul total de execuție pe un sistem paralel nu poate fi mai mic decât timpul de execuție al celui mai lung fragment”. Conform acestei legi, accelerarea execuției unui program prin paralelizarea instrucțiunilor acestuia este limitată de timpul necesar executării instrucțiunilor sale secvențiale.

Clasificare Flynn

planificarea accesului la sincronizarea proceselor

Clasificarea se bazează pe două concepte: fluxuri de comandă și fluxuri de date. Un sistem cu N procesoare are N contoare de programe și, prin urmare, N fire de instrucțiuni.

Fluxuri de comandă	Fluxuri de date	Titluri

SISD (Single Instruction, Single Data) este o arhitectură de computer în care un procesor execută un flux de comenzi, operând pe un flux de date. Pentru această clasă, este posibil doar pseudo-paralelismul.

SIMD (Single Instruction, Multiple Data) este o arhitectură de computer care permite paralelismul la nivel de date. Ideea principală a abordării bazate pe paralelismul datelor este că o singură operație este efectuată pe toate elementele matricei de date simultan. Aceste sisteme au de obicei un număr mare de procesoare, de la 1024 la 16384, care pot executa aceeași instrucțiune emisă de o singură unitate de control împotriva datelor diferite. În orice moment, fiecare procesor execută aceeași instrucțiune, dar procesează date diferite. Este implementat un proces de calcul paralel sincron.

MISD (Multiple Instruction, Simple Data) este o arhitectură computerizată în care mai multe module funcționale (două sau mai multe) efectuează diverse operații asupra acelorași date. Calculatoarele tolerante la erori care execută aceleași comenzi în mod redundant pentru a detecta erorile, așa cum sugerează definiția, aparțin acestui tip.

MIMD (Multiple Instruction, Multiple Data) este o arhitectură de computer în care mai multe procesoare independente funcționează ca parte a unui sistem mai mare. Procesarea este împărțită în mai multe fire de execuție (se asigură paralelismul), fiecare cu propria stare hardware a procesorului, în cadrul unui singur proces definit de software sau în mai multe procese.

Dintre sistemele MIMD se pot distinge două subclase: sisteme cu RAM partajată și sisteme cu memorie distribuită. Primul tip de sistem se caracterizează prin faptul că orice procesor are acces direct la orice celulă a acestei RAM partajate. Sistemele de memorie distribuită sunt de obicei o colecție de noduri de computer. Un nod este înțeles ca un procesor independent cu propria RAM locală. În aceste sisteme, orice procesor nu poate accesa în mod arbitrar memoria altui procesor.

OpenMP (Open Multi-Processing) este un standard deschis pentru paralelizarea programelor în C, C++ și Fortran. Descrie un set de comenzi care sunt destinate programării aplicațiilor multithreaded pe sisteme multiprocesor cu memorie partajată. OpenMP implementează calculul paralel folosind multithreading, în care un fir „master” creează un set de fire slave și sarcina este distribuită între ele.

Sarcinile efectuate de fire în paralel, precum și datele necesare pentru îndeplinirea acestor sarcini, sunt descrise folosind directive speciale de preprocesor ale limbajului corespunzător - pragmas. Programul C trebuie să includă fișierul „omp.h”.

Următoarea buclă adaugă tablourile „a” și „b” element cu element. Tot ceea ce este necesar pentru execuția paralelă în acest caz este o singură pragma introdusă imediat înaintea buclei.

#pragma omp paralel pentru

pentru (i=0; i< numPixels; i++)

c[i] = a[i]+b[i];

Acest exemplu folosește „echilibrarea sarcinii”, un termen comun folosit în OpenMP pentru a descrie distribuția sarcinii de lucru între fire. Când echilibrarea sarcinii este utilizată cu o directivă for, așa cum se arată în exemplu, iterațiile buclei sunt distribuite pe mai multe fire, astfel încât fiecare iterație a buclei este executată o singură dată, în paralel de unul sau mai multe fire. OpenMP determină câte fire de execuție trebuie create, precum și cea mai bună modalitate de a crea, sincroniza și distruge firele de execuție. Tot ceea ce este necesar de la programator este să spună OpenMP care anume buclă ar trebui paralelizată.

Echilibrarea sarcinii (distribuirea egală a sarcinii de lucru între fire) este unul dintre cele mai importante atribute ale execuției paralele a unei aplicații. Fără aceasta, unele fire de execuție își pot finaliza munca mult mai devreme decât altele, ceea ce duce la resurse de calcul inactive și pierderi de performanță.

În mod implicit, OpenMP presupune că toate iterațiile buclei durează aceeași perioadă de timp. Ca rezultat, OpenMP distribuie iterațiile buclei aproximativ în mod egal între fire și astfel încât să minimizeze probabilitatea conflictelor de memorie din cauza partajării necorespunzătoare a memoriei.

#pragma omp paralel pentru

pentru (i=2; i< 10; i++)

factorial[i] = i * factorial;

Dacă bucla îndeplinește toate constrângerile și compilatorul paralelizează bucla, nu este garantat să funcționeze corect deoarece poate exista o dependență de date.

Există o dependență de date dacă diferite iterații ale buclei (mai precis, o iterație care rulează pe un fir diferit) citesc sau scriu memoria partajată.

MPI (Message Passing Interface) este o interfață software pentru transmiterea de informații care vă permite să faceți schimb de mesaje între procesele care efectuează aceeași sarcină. MPI se concentrează în primul rând pe sisteme de memorie distribuită. Există implementări pentru limbajele Fortran, C și C++.

În prima versiune a MPI, numărul de procese (ramuri) este setat în momentul lansării programului, adică. Nu există nicio modalitate de a crea ramuri dinamic. În versiunea 2.0 a apărut această caracteristică.

Când o aplicație rulează, toate ramurile sale secundare formează un grup de ramuri (un set ordonat de ramuri). Fiecare grup este asociat cu un „câmp de comunicare” care descrie toți participanții la schimbul de date și datele comune tuturor participanților. Comutatoarele sunt folosite pentru a descrie câmpul de comunicare. Toate operațiunile de schimb de date pot avea loc doar într-un singur câmp de comunicare (acest lucru este asigurat prin verificarea comutatoarelor).

Pentru C, formatul general este

rc = MPI_Xxxxx(parametru, ...);

Rețineți că cazul este important aici. De exemplu, MPI trebuie să fie scris cu majuscule, la fel ca prima literă după liniuță. Toate caracterele ulterioare trebuie să fie cu litere mici. Variabila rc este un cod returnat care are un tip întreg. Dacă are succes, este setat la MPI_SUCCESS. Programul C trebuie să includă fișierul „mpi.h”.

Mesajele MPI constau din două părți principale: datele trimise/primite și informațiile însoțitoare (intrari în plic) care ajută la trimiterea datelor de-a lungul unei anumite rute.

Datele corespund începutului bufferului, numărului, tipului de date. Un buffer este pur și simplu o memorie pe care compilatorul a alocat-o unei variabile (adesea o matrice) din programul dumneavoastră. Buffer start este adresa de unde încep datele. De exemplu, începutul unei matrice în programul dumneavoastră. Număr - numărul de elemente (nu octeți!) de date din mesaj. Tipul de date determină dimensiunea unui singur element.

Informațiile „pe copertă” includ rangul în comunicator - identificatorul procesului în câmpul de comunicare, eticheta - un număr arbitrar care ajută la distingerea mesajelor și comunicatorul însuși, a cărui verificare asigură transmiterea într-un singur câmp de comunicare.

Prelucrare paralelă a datelor

Există mai multe moduri de a separa responsabilitățile între procese:

* delegare („manager-lucrător”);

* rețea peer-to-peer;

* transportor;

* „producător-consumator”.

Fiecare model are propria sa structură de defalcare a muncii, care determină cine este responsabil pentru crearea firelor și în ce condiții sunt create.

În modelul de delegare, un thread („managerul”) creează fire („lucrătorii”) și atribuie câte o sarcină fiecăruia dintre ei. Firul de control trebuie să aștepte până când toate firele și-au finalizat sarcinile. Firul de control deleagă sarcina pe care trebuie să o îndeplinească fiecare fir de lucru prin specificarea unei anumite funcții. Alături de sarcină, firului de lucru i se atribuie și responsabilitatea implementării și obținerii rezultatelor. În plus, în etapa de obținere a rezultatelor, este posibil să se sincronizeze acțiunile cu firul de control (sau altul).

În timp ce în modelul de delegare există un fir de control care deleagă sarcini către firele de lucru, în modelul peer toate firele au aceeași stare de lucru. Deși există un fir de execuție care creează inițial toate firele de execuție necesare pentru a finaliza toate sarcinile, acest fir de execuție este considerat un fir de lucru, dar nu îndeplinește nicio funcție de delegare a sarcinilor. În acest model, nu există un fir centralizat, dar firelor de lucru li se acordă mai multă responsabilitate. Toate firele de execuție de la egal la egal pot procesa cereri din același flux de date de intrare sau fiecare fir de execuție poate avea propriul flux de date de intrare pentru care este responsabil. Este posibil ca firele de lucru să aibă nevoie să comunice și să partajeze resurse.

Modelul transportorului este similar cu o linie de asamblare prin faptul că implică un flux de articole care sunt procesate în etape. La fiecare etapă, un fir separat efectuează unele operații pe un set specific de date de intrare. Când acest corp de date a trecut prin toate etapele, procesarea întregului flux de date de intrare va fi finalizată. Această abordare vă permite să procesați mai multe fluxuri de intrare simultan. Fiecare fir este responsabil pentru producerea rezultatelor intermediare, făcându-le disponibile pentru următoarea etapă (sau următorul thread) din conductă.Ultima etapă (sau thread) generează rezultatele conductei în ansamblu.

În modelul producător-consumator, există un thread de producător care pregătește datele consumate de firul de consum. Datele sunt stocate într-un bloc de memorie partajat între thread-urile producătorului și consumatorului. Firul producător trebuie să pregătească mai întâi datele, pe care le va primi apoi firul de consum. Acest proces necesită sincronizare. Dacă firul de execuție produce date mult mai rapid decât poate consuma firul de execuție, firul de execuție va suprascrie rezultatele pe care le-a primit anterior de mai multe ori înainte ca firul de execuție să aibă timp să le proceseze. Dar dacă firul de execuție consumator primește date mult mai repede decât poate furniza firul de execuție, firul de execuție consumator fie va reprocesa datele pe care le-a procesat deja, fie va încerca să accepte date care nu au fost încă pregătite.

Procese sincrone și asincrone

Procesele sincrone sunt procese cu execuție intermitentă, în care un proces își suspendă execuția până când celălalt se termină. De exemplu, procesul A, părintele, când este executat, creează procesul B, copilul. Procesul A își întrerupe execuția până când se încheie procesul B. Când procesul B se termină, codul său de ieșire este plasat în tabelul de proces. Acest lucru informează procesul A că s-a încheiat procesul B. Procesul A poate continua să se execute și apoi să se termine sau să se termine imediat.

Procesele asincrone rulează independent unele de altele. Aceasta înseamnă că procesul A se va executa până la finalizare, indiferent de procesul B. Poate exista sau nu o relație directă părinte-fiu între procesele asincrone. Dacă procesul A creează procesul B, ambele pot rula independent, dar la un moment dat părintele trebuie să obțină starea de ieșire a procesului copil. Dacă procesele nu sunt direct legate, ele pot avea un părinte comun.

Procesele asincrone pot partaja resurse precum fișiere sau memorie. Acest lucru poate (sau nu) necesita sincronizare sau interacțiune atunci când partajați resurse.

Sincronizarea proceselor înseamnă aducerea mai multor procese la un astfel de curs atunci când anumite etape ale diferitelor procese sunt finalizate într-o anumită ordine sau simultan.

Sincronizarea este necesară în orice cazuri în care procesele paralele trebuie să interacționeze. Pentru organizarea acestuia se folosesc mijloace de comunicare interprocese. Printre instrumentele cele mai frecvent utilizate se numără semnalele și mesajele, semaforele și mutexurile, conductele și memoria partajată.

Comunicarea intraprocesuala

O soluție la problemele de sincronizare a accesului la resursele critice este să dezactivați toate întreruperile imediat după ce un proces intră în secțiunea critică și să le activați chiar înainte de a ieși din ea. Dacă întreruperile sunt dezactivate, atunci comutarea procesului nu are loc, deoarece transferul controlului către planificator poate fi implementat numai folosind întreruperi.

Această abordare are însă o serie de dezavantaje semnificative. Nu există nicio garanție că un proces care are întreruperi dezactivate nu se va bucla în secțiunea sa critică, făcând astfel sistemul complet inoperabil. În plus, această metodă nu este potrivită pentru un sistem multiprocesor, deoarece dezactivarea întreruperilor pe unul dintre procesoare nu afectează în niciun fel execuția proceselor pe alte procesoare ale computerului, iar aceste procesoare au încă acces la resursa partajată.

Un mesaj este o metodă de interacțiune atunci când un proces trimite un mesaj unui al doilea și acel proces îl primește. Dacă mesajul nu ajunge, al doilea proces este blocat (în așteptarea unui mesaj) sau returnează imediat un cod de eroare.

Există o mulțime de probleme asociate cu sistemele de transmitere a mesajelor. De exemplu, mesajul se poate pierde. Pentru a evita pierderea, destinatarul trimite înapoi un mesaj de confirmare. Dacă expeditorul nu primește confirmarea după un timp, el retrimite mesajul din nou.

Acum să ne imaginăm că mesajul a fost primit, dar confirmarea nu a ajuns la expeditor. Expeditorul îl va trimite din nou și va ajunge la destinatar de două ori. Este esențial ca destinatarul să poată distinge o copie a mesajului anterior de cel nou. Acest lucru poate fi rezolvat cu ușurință prin încorporarea numărului mesajului în corpul său.

Un semafor este un obiect care permite nu mai mult de n procese să intre într-o anumită secțiune de cod (de obicei o secțiune critică).

Trei operații sunt posibile cu un semafor:

1) init(n); - inițializarea contorului (numărul trecut la contor este numărul de procese care pot accesa simultan secțiunea critică)

2) așteptați(); - așteptați până când contorul devine mai mare decât 0; după aceea, reduceți contorul cu unul.

3) pleca(); - măriți contorul cu unu.

Înainte ca un proces să acceseze secțiunea critică, este necesar să apelați metoda wait(), după care se garantează că numărul de procese care îl accesează simultan nu depășește n-1. Apoi, procesul poate continua să lucreze și să execute metoda leave() după ce a lucrat cu secțiunea critică, permițând astfel altor procese să știe că „spațiul a devenit liber”.

Dacă numărul de apeluri la metodele wait() și leave() nu se potrivește, atunci sistemul nu va funcționa corect, la fel ca în cazul blocajului procesului - o situație în care mai multe procese sunt într-o stare nesfârșită de așteptare pentru resursele ocupate de aceste procese în sine:

	Procesul 1	Procesul 2
	Vrea să captureze A și B, începe cu A	Vrea să captureze A și B, începe cu B
	Captează resursa A	Captează resursa B
	Așteptând ca resursa B să devină liberă	Așteptând ca resursa A să devină liberă
	Blocare reciprocă

Depanarea blocajelor, ca și alte erori de sincronizare, este complicată de faptul că necesită condiții specifice pentru ca execuția simultană a mai multor procese să apară (în exemplul descris mai sus, dacă procesul 1 ar fi reușit să achiziționeze resursa B înainte de procesul 2, eroarea ar fi nu au avut loc).

Mutexurile sunt cele mai simple semafore binare care pot fi în una dintre cele două stări - marcate sau nemarcate (deschise și, respectiv, închise). Când orice fir care aparține oricărui proces devine proprietarul unui obiect mutex, acesta din urmă este plasat într-o stare neetichetat. Dacă o sarcină eliberează un mutex, starea acestuia devine verificată.

Scopul unui mutex este de a proteja un obiect de a fi accesat de alte fire de execuție, altele decât cel care a dobândit mutexul. În orice moment, doar un fir poate deține un obiect protejat de un mutex. Dacă un alt fir are nevoie de acces la o variabilă protejată de un mutex, atunci acel fir de execuție intră în repaus până când mutex-ul este eliberat.

Test-and-set este o instrucțiune simplă a procesorului (atomic) care nu se întrerupe, care copiază valoarea unei variabile într-un registru și setează o nouă valoare. În timp ce această instrucțiune este în execuție, procesorul nu poate întrerupe execuția acesteia și nu poate trece la executarea unui alt fir. Dacă se utilizează o arhitectură multiprocesor, atunci în timp ce un procesor execută această instrucțiune pe o celulă de memorie, alte procesoare nu pot accesa această celulă.

Algoritmul lui Dekker este prima soluție corectă cunoscută la problema excluderii reciproce în programarea competitivă. Permite două fire de execuție să partajeze o resursă nepartajată fără a provoca conflicte, folosind doar memoria partajată pentru comunicare.

Dacă două procese încearcă să intre în secțiunea critică în același timp, algoritmul va permite doar unuia dintre ele să facă acest lucru, în funcție de a cărui coadă se află în acel moment. Dacă un proces a intrat deja în secțiunea critică, celălalt va aștepta până când primul îl părăsește. Acest lucru este implementat prin utilizarea a două steaguri (indicatori ai „intenției” de a intra în secțiunea critică) și a variabilei turn (care indică rândul procesului care a sosit).

Unul dintre avantajele algoritmului este că nu necesită instrucțiuni speciale Test-and-set și, ca urmare, este ușor de portat în diferite limbaje de programare și arhitecturi de computer. Dezavantajele includ aplicabilitatea acestuia în cazul cu doar două procese și utilizarea așteptării ocupate în loc de suspendarea procesului (folosirea așteptării ocupate implică faptul că procesele ar trebui să petreacă o perioadă minimă de timp în secțiunea critică).

Algoritmul lui Peterson este un algoritm software pentru excluderea reciprocă a firelor de execuție a codului. Deși a fost formulat inițial pentru cazul cu 2 fire, algoritmul poate fi generalizat pentru un număr arbitrar de fire. Algoritmul este numit în mod convențional software, deoarece nu se bazează pe utilizarea comenzilor speciale ale procesorului pentru a dezactiva întreruperile, blocarea magistralei de memorie etc.; numai variabilele generale de memorie și o buclă sunt folosite pentru a aștepta intrarea în secțiunea critică a cod executabil.

Înainte de a începe execuția secțiunii critice, thread-ul trebuie să apeleze o procedură specială (să o numim EnterRegion) cu numărul său ca parametru. Trebuie să aranjeze ca un fir să aștepte ca coada sa să intre în secțiunea critică. După ce a executat secțiunea critică și a părăsit-o, thread-ul apelează o altă procedură (să o numim LeaveRegion), după care alte fire vor putea intra în regiunea critică.

Principiul general al algoritmului lui Peterson pentru 2 fire:

Postat pe http://www.allbest.ru/

Planificarea procesului

Programare - asigurarea accesului secvenţial al proceselor la un singur procesor.

Planificatorul este partea sistemului de operare responsabilă pentru acest lucru.

Algoritm de programare non-preemptive (neprioritar) - nu necesită o întrerupere a temporizatorului hardware, procesul se oprește doar atunci când se blochează sau iese.

Algoritm de planificare preventivă (prioritate) - necesită o întrerupere a cronometrului hardware, procesul rulează doar pentru o perioadă de timp alocată, după care este suspendat de un cronometru pentru a transfera controlul către planificator.

Procesele sunt plasate în cozi prioritare în conformitate cu strategia de programare. Sistemele UNIX/Linux folosesc două strategii de planificare: FIFO (prescurtare de la First In First Out) și RR (prescurtare de la round-robin).

Când se utilizează strategia FIFO, procesele sunt atribuite procesorului în funcție de momentul în care ajung la coadă.

Programarea RR este aceeași cu programarea FIFO, cu o singură excepție: după expirarea intervalului de timp, procesul este plasat la sfârșitul cozii de prioritate, iar următorul proces din linie este atribuit procesorului.

Pentru a se asigura că procesele rulează în paralel, programarea cu prioritate poate fi potrivită. Fiecărui proces i se atribuie o prioritate, iar controlul este transferat procesului cu cea mai mare prioritate. Prioritatea poate fi dinamică sau statică. Prioritatea dinamică poate fi setată după cum urmează: P = 1/T, unde T este partea ultimului cuantum utilizat (dacă se folosește 1/50 din cuantă, atunci prioritatea este 50. Dacă se folosește întregul cuantum, atunci prioritatea este 1).

Procesele sunt adesea grupate în funcție de prioritate și folosesc programarea cu prioritate între grupuri, dar în cadrul grupului folosesc programarea round-robin.

Postat pe Allbest.ur

Documente similare

Structura, specificitatea și arhitectura sistemelor multiprocesor; Clasificare Flynn. Organizarea excluderii reciproce pentru a sincroniza accesul la resursele partajate. Dezactivați întreruperile; semafoare cu drivere de dispozitiv. Grupuri de distribuție a încărcăturii.

lucrare curs, adăugată 06.07.2014

Gestionarea memoriei primare și secundare a computerului. Accesul utilizatorului la diverse resurse partajate de rețea. Sistem de suport pentru interpretul de comandă. Distribuirea resurselor între utilizatori, programe și procese care rulează simultan.

prezentare, adaugat 24.01.2014

Îmbunătățirea parametrilor modulului de memorie. Funcționarea și interacțiunea sistemului de operare cu RAM. Analiza principalelor tipuri și parametri ai RAM. Partea software procesează execuția comenzilor și le plasează în RAM.

lucrare de curs, adăugată 12.02.2009

Principalele funcții și procese ale subsistemului de management al proceselor. Procese de expediere (file). Algoritmi pentru programarea executării firelor. Scopul și tipurile de priorități în sistemele de operare. Funcțiile subsistemului principal de gestionare a memoriei.

prezentare, adaugat 20.12.2013

Modele abstracte și metode de prelucrare paralelă a datelor, erori admisibile de calcul. Conceptul de proces paralel, granulele de sincronizare și paralelizare ale acestora, definiția legii lui Amdahl. Arhitectura sistemelor de calcul multiprocesor.

teză, adăugată 09.09.2010

Scrierea unui program care implementează funcționarea unui sistem multiprocesor cu memorie partajată care procesează cozi de cereri de lungime variabilă. Analiza unei arhitecturi tipice de sistem multiprocesor. Descrierea procedurilor și variabilelor utilizate în program.

lucrare curs, adaugat 21.06.2013

Avantajele sistemelor multiprocesor. Crearea unui program care implementează funcționarea unui sistem multiprocesor cu memorie partajată pentru a procesa un număr diferit de cereri, precum și un număr diferit de procesoare. Modele de calcule pe calculatoare vectoriale și matrice.

lucrare curs, adaugat 21.06.2013

Managementul proceselor este o parte a sistemului de operare care afectează funcționarea computerului. Descriptor de context al procesului și algoritm pentru programarea acestuia. Mijloace de sincronizare și interacțiune a proceselor. Secțiune critică, puncte moarte și fire.

prelegere, adăugată 02/05/2009

Esența și conținutul conceptelor de bază ale sistemelor de operare: procese, memorie, fișiere. Clasificare după diverse criterii și tipuri de procese, direcții de interrelație. Principii de planificare a procesorului. Ordine de gestionare a memoriei non-virtuale.

prezentare, adaugat 24.07.2013

Clasificarea aeronavelor paralele. Sisteme cu memorie partajată și distribuită. Conducte de operare. Performanța unui transportor ideal. Arhitecturi suprascalare. Arhitectura VLIW. Predicția tranziției. Procesoare Matrix. legile lui Amdahl și Gustafson.