.realizarea Paralelismului Maxim Pt Alg de Prelucrare
CUPRINS
Introducere ………………………………………………………. 4
Cerințe ale prelucrării paralele ………………………….……… 7
Concepte de bază ale prelucrării paralele …………………….. 7
Clasificări ale calculatoarelor paralele ………………………… 15
Realizări hardware ……………………………………………. 22
Modele teoretice de calculatoare paralele …………………….. 24
Trecerea de la algoritmi secvențiali la algoritmi de prelucrare paralelă ………………………………………………………….. 28
Algoritmi pentru înmulțirea matricelor ……………………… 29
Algoritmi de sortare ………………………………………….. 37
Algoritmi pentru colorarea grafurilor ………………………… 43
Analiza performanțelor algoritmilor paraleli ………………… 46
Algoritm de transformare a prelucrărilor secvențiale în prelucrări paralele ………………………………………………………….. 48
Dependențe de date, control și resurse ………………………. 48
Condițiile de paralelism ale lui Bernstein …………………… 51
Algoritm de transformare bazat pe matricea de dependență … 53
Indicatori ai gradului de paralelizare ………………………… 63
Software pentru maxim paralelism …………………………… 65
Descrierea aplicației MParalel ……………………………… 65
Structurile de date folosite …………………………………… 70
Algoritmii utilizați …………………………………………… 72
Execuția aplicației MParalel ………………………………… 76
Concluzii ………………………………………………………… 78
BIBLIOGRAFIE …………………………………………………… 81
ANEXE ……………………………………………………………… 84
BIBLIOGRAFIE
[CHEN90] Gen-Huey Chen, Maw-Sheng Chern, Jin-Hwang Jang, Pipeline arhitectures for dynamic programing algorithms, Parallel Computing, North-Holland, vol. 13, No. 1, January 1990, pp. 111-117.
[DUNN90] Stephen M. Dunn, Peter J. Varman, R. Iyer, Donald J. Haderle, Parallel merging: algorithm and implementation result, Parallel Computing, North-Holland, vol. 15, No. 1-3, September 1990, pp. 165-177.
[EVAN90] D.J. Evans, A parallel sorting – merging algoritm for tightly coupled multiprocessors, Parallel Computing, North-Holland, vol. 14, No. 1, May 1990, pp. 111 – 121.
[GAUD87] J.L. Gaudiot, L.T. Lee, Multiprocessors systems programming in a high-level data-flow language, Parallel Architectures and Languages Europe, Springer – Verlag, June 1987.
[HOCK91] R.W. Hockney, C.R. Jesshop, Calculatoare paralele–arhitectură, programe, algoritmi, Editura Tehnică, București, 1991.
[HUAN90] Jan-Hsiung Huang, Leonard Kleinrock, Optimal parallel merging and sorting algorithms using N1/2 processors without memory contention, Parallel Computing, North-Holland, vol. 14, No. 1, May 1990,
pp. 89 – 97.
[IONE99] Felicia Ionescu, Principiile calculului paralel, Editura Tehnică, București, 1999.
[IVAN98] Laur Ivan, Conor Ryan, Re-Engineering prin descoperirea automată a transformărilor aplicabile pentru paralelizare, Informatica Economică, vol. 2, No. 5, Trim. 1, 1998, pp. 47 – 50.
[KAPE97] Georgios Kapenekas, Modalități de analiză și dezvoltare a programelor în sisteme cu prelucrare paralelă, Informatica Economică, vol. 1, No. 2, Trim. 2, 1997, pp. 67 – 73.
[KIM90] Hyoung Joang Kim, Jang Gyu Lee, A parallel algoritm solving a tridiagonal Toeplitz linear system, Parallel Computing, North-Holland,
vol. 13, No. 3, March 1990, pp. 289 – 294.
[LEVI90] Stewart A. Levin, A fully vectorized quicksort, Parallel Computing, North-Holland, vol. 16, No. 2-3, December 1990, pp. 369 – 373.
[LEWI93] Ted G. Lewis, Foundations of Parallel Programming, IEEE Computer Society Press, Los Alamitos, California, 1993.
[LIN90] Yen-Chun Lin, Ferng-Ching Lin, Parallel sorting with cooperating heaps in a linear array of processors, Parallel Computing, North-Holland, vol. 16, No. 2-3, December 1990, pp. 273 – 278.
[MIRE87] N.N. Mirenkov, Parallel algorithms and static analysis of parallel programs, Parallel Algorithms and Architectures, Springer-Verlag, May 1987, pp. 48 – 59.
[OANC98] Bogdan Oancea, Gheorghe Dodescu, Implementarea paralelismului la nivel de instrucțiune în microprocesoarele superscalare, Informatica Economică, vol. 2, No. 8, Trim.4, 1998, pp. 67 – 75.
[PRAS90] Sushil Prasad, Sojal K. Das, Narsingh Deo, Parallel graph algorithms for hypercube computers, Parallel Computing, North-Holland, vol. 13, No. 2, February 1990, pp. 143 – 158.
[RACE99] Mădălina Aura Răceanu, Parallel Random Access Machine Model, Information Technology – The Proceedings of the Fourth International Symposium on Economic Informatics, Romania, Bucharest, May 6 – 9, 1999, pp. 330 – 335.
[RACO95] Dan Racovițan, Monica Ciaca, Alexandru Vancea, Data dependence and the parallelization of sequential programs, Software Engineering and Applications – The Proceedings of the 2nd International Symposium of Economic Informatics, Romania, Bucharest, May 10 – 13, 1995, pp. 70 – 72.
[RAGH99] Mukund Raghavachari, Anne Rogers, Ace: A Language for Parallel Programming with Customizable Protocols, ACM Transactions on Computer Systems, vol. 17, No. 3, August 1999, pp. 202 – 248.
[SARK91] Vinek Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, Journal of Research and Development, vol. 35,
No. 5-6, September – November 1991, pp. 779 – 805.
[SHYU90] Chii-Huah Shyu, A parallel algorithm for finding a maximum weight clique of an internal graph, Parallel Computing, North-Holland, vol. 13, No. 2, February 1990, pp.
[STEW90] G. W. Stewart, Communications and matrix computations on large message passing systems, Parallel Computing, North-Holland, vol. 16, No. 1, November 1990, pp. 27 – 40.
[THEO90] T. Theoharis, J.J. Modi, Implementation of matrix multiplication on the T – RACK, Parallel Computing, North-Holland, vol. 14, No. 2,
June 1990, pp. 229 – 233.
[TOMP2000] Tim Tompkins, Jon Bates, Utilizare Visual C++ 6.0, Editura Teora, București, 2000.
[TYRT90] Evgenij E. Tyrtyshnikov, New approaches to deriving parallel algorithms, Parallel Computing, North-Holland, vol. 15, No. 1-3, September 1990, pp. 261 – 265.
[ZORO90] Janez Zorovnick, A parallel variant of a heuristical algorithm for graph colouring, Parallel Computing, North-Holland, vol. 13, No. 1, January 1990, pp. 95 – 100.
[WANG90] WANG Chien – Min, WANG Sheng – De, Structured partitioning of concurrent programs for execution on multiprocessors, Parallel Computing, North-Holland, vol. 16, No. 1, December 1990, pp. 41- 57.
[WILL97] Mickey Williams, Bazele Visual C++ 4.0, Editura Teora, București, 1997.
1. Introducere
Lucrarea are ca obiectiv realizarea de software pentru transformarea algoritmilor secvențiali de prelucrare în algoritmi de prelucrare paralelă.
În elaborarea acestei lucrări s-a ținut seama de urmatoarele aspecte:
apariția transputerelor (calculatoare paralele cu performanțe ridicate) capabile să rezolve aplicații cu cerințe de calcul intensive, performanțe care nu se obțin de către calculatoarele secvențiale;
complexitatea foarte mare a unor probleme conduce la obținerea soluției în afara timpului real dacă se folosesc algoritmi secvențiali de prelucrare; paralelismul elimină acest inconvenient.
În acest scop se studiază cerințele prelucrării paralele, algoritmi, principii
de analiză și proiectare a algoritmilor paraleli, condiții de paralelism. Se procedează la realizarea unui algoritm de transformare a programelor secvențiale în programe paralele folosind matricea dependențelor dintre instrucțiuni.
Calculatoarele s-au dezvoltat mult, începând de la sistemele mecanice și electronice cu facilități limitate, până la calculatoarele paralele. În prezent există sisteme cu facilități de prelucrare paralelă. La nivelul programelor există paralelisme, fapt ce conduce la existența oportunității de prelucrare paralelă.
Calculatoarele secvențiale se bazează pe modelul introdus de John von Neumann în anul 1945. Acest model constă dintr-o unitate centrală de procesare (procesorul) și o unitate de memorie, conectate între ele printr-un canal de comunicație pentru transferul datelor. Într-un astfel de calculator, procesorul extrage instrucțiuni și date din memorie, le prelucrează și depune rezultatul înapoi în memorie. Viteza unui calculator secvențial este limitată de doi factori: viteza de execuție a instrucțiunilor procesorului și viteza de transfer a datelor între procesor și memorie.
Soluția pentru obținerea unor viteze de calcul oricât de mari o constituie introducerea paralelismului prin multiplicitatea resurselor: un calculator paralel, compus din unități multiple de procesare și unități multiple de memorie interconectate între ele. Conectarea unui număr mare de procesoare pentru construirea unui calculator paralel reprezintă o soluție eficientă din punct de vedere al costului și permite obținerea unor performanțe pe care un calculator secvențial nu le poate atinge niciodată. De exemplu, în tehnologia curentă este posibilă producerea unui sistem folosind 10000 de procesoare moderne, fiecare cu putere de calcul de 50 MIPS (Millions of Instructions per Second), pentru o performanță totală de 500000 MIPS. Pentru ca un singur procesor să atingă o astfel de putere de calcul, ar trebui să execute o instrucțiune în 0.002 ns (2 ps). Nici un procesor existent nu se apropie de această performanță și nici nu va putea să se apropie. Calculatoarele secvențiale au ajuns la o limită fizică pentru potențialul de calcul (o astfel de limită fiind viteza luminii: 3*108 m/s în vid), ce rezultă din viteza de transmisie a unui semnal prin siliciu, care este de cel mult 3*107 m/s.
Paralelismul este emulat pe mașini secvențiale utilizând o serie de tehnici – multitasking, multithreading – pentru a executa mai multe activități în mod concurent, însă paralelismul în sistemele de calcul a devenit viabil și atractiv datorită scăderii costului componentelor hardware prin integrarea lor VLSI (Very Large Scale Integrated). Dezvoltarea rapidă în tehnologia VLSI și a comunicațiilor a creat situația în care proiectanții hardware construiesc mașini paralele cu mii de noduri de calcul puternice, la un preț relativ scăzut. Complexitatea unor astfel de mașini este cu mai multe ordine de mărime mai mare decât aceea a calculatoarelor uniprocesor.
Calculul paralel – domeniu important în știința calculatoarelor – s-a dezvoltat din necesitatea existenței unor calculatoare cu performanțe ridicate, capabile să rezolve aplicații cu cerințe de calcul intensive, performanțe care nu se obțin de către calculatoarele secvențiale.
Există probleme care necesită o putere de calcul de mii de ori mai mare decât cea oferită de un calculator monoprocesor. Astfel de probleme includ: calculele implicate de studiul curgerii tridimensionale a fluidelor, simularea în timp real a sistemelor complexe, roboți inteligenți, proiectarea asistată de calculator (CAD – Computer Aided Design), grafică. Domeniul inteligenței artificiale constituie o arie care va fi avantajată de procesarea paralelă, în rezolvarea eficientă a multor probleme. Cercetările în domeniul prelucrării paralele sunt motivate prin potențialul de similaritate existent între arhitecturile paralele și rețelele neuronale.
Principalele obstacole împotriva introducerii rapide a calculului paralel sunt marile investiții făcute în software-ul pentru calculatoare secvențiale și dificultățile care apar în programarea multor calculatoare paralele. Cu toate acestea, se consideră că procesarea paralelă este viitorul tehnicii de calcul. Se efectuează cercetări pentru dezvoltarea unor tehnici sofisticate pentru reducerea barierelor software; limbajele de programare paralelă au fost definite și implementate în sensul exprimării în mod cât mai natural a paralelismului unor algoritmi dedicați rezolvării unor probleme specifice; instrumentele pentru dezvoltarea software-ului paralel au fost implementate și sunt experimentate în sistemele pentru procesare paralelă.
Înțelegerea posibilităților de calcul ale mașinilor paralele, ca și modul de utilizare a acestora, este încă în stadiul de început. Se ridică o serie de probleme, cum ar fi: descompunerea aplicațiilor în sute și mii de părți, care să fie executate concurent; alegerea algoritmilor adecvați pentru o anumită arhitectură și a structurilor de date utilizate; coordonarea activității a milioane de elemente de procesare pentru îndeplinirea unei singure sarcini de calcul; comunicarea acestor elemente de procesare.
Lucrarea este structurată pe patru capitole.
Capitolul intitulat “Cerințe ale prelucrării paralele” prezintă conceptele
de bază ale prelucrării paralele, clasificările arhitecturilor paralele, modele teoretice de calculatoare paralele (modele PRAM – Parallel Random Access Machine), precum și o serie de realizări hardware.
Capitolul cu titlul “Trecerea de la algoritmi secvențiali la algoritmi de prelucrare paralelă” dezvoltă comparativ o serie de algoritmi (de calcul, de sortare etc.) secvențiali și paraleli, cu specificarea diferențelor existente între aceștia din punct de vedere al vitezei de calcul și resurselor folosite.
Capitolul “Algoritm de transformare a prelucrărilor secvențiale în prelucrări paralele” abordează construirea unui model de paralelizare a programelor secvențiale ținând seama de dependențele dintre instrucțiuni. În acest sens, se respectă condițiile de paralelism și se urmăresc gradul și tipul de paralelism al programelor.
Capitolul “Software pentru maxim paralelism” descrie aplicația MParalel ce conține un algoritm de paralelizare a programelor C/CPP secvențiale. Aplicația preia fișiere sursă C/CPP secvențiale, le analizează sintactic în scopul identificării instrucțiunilor și operanzilor existenți, iar pe baza dependențelor dintre instrucțiuni realizează transformarea în fișiere paralele ce urmează a fi executate pe un sistem multiprocesor. Aplicația a fost realizată folosind produsul Microsoft Visual C++ 6.0 și mediul de dezvoltare Microsoft Developer Studio.
Lucrarea se încheie cu concluzii și are la bază o bibliografie cu lucrări de specialitate.
În anexele lucrării s-a atașat o parte din codul sursă al aplicației practice.
=== 5_cerinte ===
2. Cerințe ale prelucrării paralele
2.1 Concepte de bază ale prelucrării paralele
Sunt prezentate concepte ale prelucrării paralele: calculator paralel,
granularitatea de calcul, gradul și tipul de paralelism al unui program,
timp de execuție secvențială, timp de execuție paralelă, accelerarea paralelă, eficiența paralelă, costul paralel, costul suplimentar de calcul paralel, proces, thread.
Un calculator paralel ( mașină paralelă ) conține procesoare multiple
capabile să prelucreze informația prin manevrarea concurentă a datelor.
Granularitatea de calcul a programelor paralele este definită ca
fiind dimensiunea relativă a unităților de calcul atribuite procesoarelor. În general, se utilizează termenii de granularitate mică (fine-grain), granularitate medie (medium-grain) și granularitate mare (coarse-grain). Sunt realizabili algoritmi paraleli cu granularitatea cea mai fină, care să utilizeze un număr de procesoare egal cu numărul datelor de intrare, dar acest lucru conduce la cerințe excesive de putere de calcul. De aceea, în practică se atribuie partiții mai mari din mulțimea datelor de intrare fiecărui procesor. Acest lucru face să crească granularitatea programului și să scadă numărul de procesoare necesar pentru implementarea algoritmilor paraleli.
Un calculator paralel este compus fie dintr-un număr mic de procesoare puternice, fie dintr-un număr mare de procesoare mai puțin puternice. Calculatoarele din prima categorie sunt denumite calculatoare cu granularitate mare (grosieră), iar cele din a doua categorie se numesc calculatoare cu granularitate mică (fină).
Un exemplu de calculator paralel cu granularitate mare este Cray Y-MP compus din 8-16 procesoare puternice, fiecare cu o viteză de operare de 10 GFlops (un GFlops este egal cu 109 operații virgulă flotantă pe secundă). În contrast, calculatoarele cum sunt Connection Machine 2 (CM-2) sau MasPar (MP-1) conțin 65536 (64k) procesoare de un bit, respectiv 16384 (16k) procesoare de 4 biți. Între aceste două extreme se plasează o întreagă gamă de calculatoare cu granularitate medie (medium-grain), care conțin sute sau mii de procesoare de putere medie. De exemplu, calculatorul iPSC/860 conține 128 procesoare i860, calculatorul nCUBE-2 dispune de 8192 (8k) procesoare RISC specializate, iar calculatorul Connection Machine 5 (CM-5) conține 16384 (16k) procesoare SPARC.
Pentru implementarea paralelismului este necesară existența atât a unui
suport hardware, cât și software.
Paralelismul hardware este condiționat de arhitectura calculatorului paralel,
care înglobează multiplicitatea resurselor de calcul și a comunicațiilor între aceste resurse.
Paralelismul software se referă la gradul și tipul de paralelism al programului.
Gradul de paralelism (degree of paralelism – DOP) al unui program este
dat de numărul de procesoare utilizate în execuția acestuia. Gradul de paralelism variază în cadrul execuției aceluiași program, funcția de timp a acestuia indicând profilul paralelismului.
Dintre tipurile de paralelism software, paralelismul de date și cel de control
sunt cele mai importante și cel mai frecvent utilizate.
Paralelismul de date ( paralelism structural ) este prezent în acele
programe în care sunt definite structuri de date asupra cărora se execută operații identice. Paralelizarea se realizează prin partiționarea datelor, adică prin divizarea mulțimii de date în submulțimi asignate diferitelor procesoare, care execută operații identice, fiecare asupra submulțimii asignate lui. Programele care exploatează paralelismul de date se numesc programe data-paralele; există și limbaje (denumite limbaje data-paralele) care permit implementarea directă a acestui tip de paralelism.
Paralelismul de control ( paralelism funcțional ) apare atunci când
structurile de date ale programului sunt neregulate, iar operațiile sunt variate și diferite. Paralelizarea se realizează prin partiționarea programului în mai multe sarcini de calcul (thread-uri, procese, instrucțiuni) care sunt executate în paralel pe procesoare diferite ale sistemului. Fiecare procesor execută o sarcină de calcul diferită și comunică cu celelalte procesoare pentru obținerea rezultatului final al aplicației.
Cea mai simplă formă de paralelism de control o reprezintă implementarea pipeline a algoritmilor, în care algoritmul este divizat într-un număr de etape de execuție, fiecare etapă fiind atribuită unui anumit procesor al sistemului. Datele de ieșire ale unei etape de calcul reprezintă date de intrare pentru etapa următoare, la fel ca în execuția pipeline a instrucțiunilor.
O altă formă de paralelism de control o reprezintă implementarea master-slave a algoritmilor. În acest mod de abordare, un proces coordonator (master) creează o listă a sarcinilor de calcul care sunt preluate și executate de o colecție de procese de lucru (slave), care intră în execuție atât timp cât lista creată de procesul master conține sarcini de calcul.
Timpul de execuție secvențială (Ts) este timpul necesar pentru rezolvarea unei probleme pe un calculator secvențial. Acesta este considerat ca fiind numărul de operații de bază sau pași de calcul executați de algoritm. Operații ca adunarea, comparația, interschimbul a două numere sunt operații de bază deoarece necesită același număr de unități de timp pe un calculator secvențial. Un algoritm secvențial este evaluat pe baza timpului de execuție, exprimat ca o funcție de numărul datelor de intrare (dimensiunea intrării) ale acestuia. Timpul de execuție a unui algoritm secvențial se mai numește complexitate secvențială de timp (sequential time complexity).
Timpul de execuție paralelă (Tp) este timpul necesar pentru
rezolvarea unei probleme pe un calculator paralel și reprezintă timpul scurs din momentul de start al execuției, până când ultimul procesor termină execuția.
Timpul de execuție paralelă se estimează prin numărarea a două tipuri de pași:
pași de calcul;
pași de comunicație.
Un pas de calcul este o operație aritmetică sau logică executată de un procesor. Un pas de comunicație este dat de timpul necesar pentru transferul unei date prin intermediul memoriei partajate sau ca mesaj prin rețeaua de interconectare. În modelele teoretice PRAM (Parallel Random-Access Machine), timpii de comunicație sunt ignorați și se iau în considerare doar pașii de calcul. Timpul de execuție a unui algoritm paralel depinde nu numai de dimensiunea intrării (ca în cazul algoritmilor secvențiali), ci și de arhitectura calculatorului paralel și de numărul de procesoare. Timpul de execuție a unui algoritm paralel se mai numește complexitate paralelă de timp (parallel time complexity).
Sunt cazuri în care timpul de execuție (secvențială sau paralelă) ca funcție de dimensiunea intrării are o expresie complicată. Se utilizează în acest sens o expresie mai simplă, cu o comportare cunoscută, care aproximează asimptotic comportarea funcției date. Complexitatea paralelă de timp trebuie să fie mai mică decât complexitatea secvențială de timp pentru soluționarea aceleiași probleme, cel puțin asimptotic.
Accelerarea paralelă ( speedup – S ) este raportul dintre timpul de
execuție în cazul cel mai defavorabil al celui mai rapid algoritm secvențial cunoscut pentru problema dată și timpul de execuție paralelă în cazul cel mai defavorabil:
unde:
Ts este timpul de execuție al celui mai rapid algoritm secvențial cunoscut;
Tp este timpul de execuție paralelă.
Accelerarea nu poate depăși numărul de procesoare. Fie p numărul acestora. Dacă cel mai rapid algoritm secvențial necesită Ts unități de timp pentru rezolvarea unei probleme date, atunci o accelerare egală cu p este obținută dacă fiecare procesor din calculatorul paralel consumă Ts/p unități de timp. O accelerare mai mare decât p este obținută dacă fiecare procesor necesită un timp mai mic decât Ts/p unități de timp. În acest caz, un singur procesor ar putea emula cele p procesoare și ar rezolva problema într-un timp mai mic decât Ts unități de timp. Aceasta este o contradicție cu faptul că Ts este timpul de execuție al celui mai rapid algoritm secvențial, deci problema nu poate fi rezolvată într-un timp mai mic decât Ts pe un singur procesor.
Eficiența paralelă ( efficiency – E ) este dată de raportul dintre
accelerarea paralelă și numărul de procesoare:
unde:
S este accelerarea paralelă;
p este numărul de procesoare.
Dat fiind că în practică accelerarea este mai mică decât numărul de
procesoare p, rezultă că eficiența este mai mică decât 1, având o valoare care depinde de gradul de utilizare a procesoarelor.
Costul paralel ( cost – C ) este dat de suma timpilor consumați de
toate procesoarele pentru rezolvarea problemei:
C = p * Tp,
unde:
p este numărul de procesoare;
Tp este timpul de execuție paralelă.
Costul unui algoritm secvențial este egal cu timpul de execuție al
algoritmului (Ts), deoarece numărul de procesoare este 1.
Un algoritm paralel pentru rezolvarea unei probleme date este optimal din punct de vedere al costului (cost-optimal) dacă costul acestuia este proporțional cu timpul de execuție al celui mai rapid algoritm secvențial cunoscut pentru acea problemă:
p * Tp = k * Ts,
unde:
p este numărul de procesoare;
Tp este timpul de execuție paralelă;
Ts este timpul de execuție secvențială;
k este constantă de proporționalitate.
Rezultă:
Eficiența unui algoritm paralel cost-optimal este constantă în raport cu dimensiunea problemei și cu numărul de procesoare utilizat.
Costul suplimentar de calcul paralel (overhead – To) este acea parte
din costul paralel (C) care nu intervine în cel mai rapid algoritm secvențial de rezolvare a problemei respective:
To = C – Ts
sau
To = p * Tp – Ts,
unde:
p este numărul de procesoare;
Tp este timpul de execuție paralelă;
Ts este timpul de execuție secvențială.
To reprezintă timpul total consumat de toate procesoarele în plus față de timpul necesar celui mai rapid algoritm secvențial.
Definirea costului suplimentar (sau funcția de cost suplimentar) ca diferență între costul paralel și timpul de execuție secvențială are avantajul că înglobează într-o singură expresie toate sursele care contribuie la ineficiența sistemelor paralele (eficiența acestora fiind subunitară).
Sursele majore ale costului suplimentar sunt: încărcarea neechilibrată a procesoarelor, calculele suplimentare, comunicația între procesoare.
Încărcarea neechilibrată a procesoarelor (load imbalance) provine din faptul că, de cele mai multe ori, o problemă nu poate fi imparțită în sarcini de calcul (task – uri) de dimensiuni egale, care să fie atribuite procesoarelor. Atunci când procesoarele au sarcini de calcul diferite, unele procesoare sunt inactive, în timp ce altele sunt în execuție. O altă cauză care produce încărcarea neechilibrată a procesoarelor este necesitatea impusă de un program ca mai multe procesoare să se sincronizeze într-un punct al execuției. Acest lucru face ca procesoarele care sunt gata mai devreme să aștepte până când toate celelalte procesoare ajung în punctul de sincronizare; timpul total cât toate procesoarele sunt în așteptare (inactive) contribuie la costul paralel suplimentar.
Un caz special de încărcare neechilibrată îl constituie prezența într-un algoritm a unei părți neparalelizabile care trebuie să fie executată secvențial, de un singur procesor. O astfel de situație este exprimată de legea lui Amdahl [RACE99] potrivit căreia totalul operațiilor executate secvențial în Ts pași de calcul se descompune într-o parte neparalelizabilă Tseq , iar restul Tpar se execută pe un număr p de procesoare.
Rezultă:
Rezultă expresia legii lui Amdahl:
Dacă se notează cu a = Tseq / Ts fracțiunea neparalelizabilă din sarcina de calcul, atunci accelerarea paralelă (S) este mărginită superior de 1/a, indiferent de numărul de procesoare utilizate. Accelerarea paralelă se mai scrie:
sau
sau
Se observă că S 1/a atunci când p ∞. Legea lui Amdahl stabilește limita superioară a accelerării în cazul în care există o fracțiune neparalelizabilă din sarcina de calcul. Fig. 2.1 prezintă curbele de variație ale accelerării în funcție de numărul de procesoare, având ca parametru fracțiunea a.
Accelerarea
(S)
1024 a = 0
256 a = 0.01
64
16
4 a = 0.1 Număr de
a = 0.9 procesoare
1 (p)
1 4 16 64 256 1024
Fig. 2.1 Accelerarea paralelă în funcție de numărul de procesoare
John Gustafson și Ed Barsis [LEWI93] descoperă o formulă alternativă pentru accelerarea paralelă plecând de la supoziția că timpul de calculare a unei soluții pentru un agoritm data-paralel utilizând p procesoare este normalizat la unitate (Tp = 1). Când programul este rulat pe un procesor, el trebuie să execute partea serială în timpul a*Tp = a, iar partea paralelă în timpul p*(1-a)*Tp = (1-a)*p. Pentru Ts se obține formula: Ts = a + (1-a)*p. Accelerarea paralelă devine S = p – (p – 1)*a. S este proporțională cu p.
Graficul exprimă cele două legi: Amdahl și Gustafson-Barsis.
S(Speedup)
10
Gustafson-Barsis
5
Amdahl
1
a
0.1 0.5 0.9
Fig 2.2 Legile Amdahl și Gustafson-Barsis privind accelerarea paralelă
Legile Amdahl și Gustafson-Barsis prezentate anterior ignoră costul suplimentar de calcul paralel (overhead – To). Formulele de mai jos exprimă cele două legi extinse cu overhead –ul:
Legea Amdahl extinsă are expresia:
Legea Gustafson-Barsis extinsă are expresia:
Există situații în care cel mai rapid algoritm secvențial pentru o problemă dată nu este paralelizabil. Acest lucru obligă la utilizarea unui algoritm mai lent, dar mai ușor de paralelizat.
Dacă Ts este timpul de execuție al celui mai rapid algoritm secvențial pentru o problemă dată, iar Tsl este timpul de execuție al unui algoritm mai lent, dar mai ușor de paralelizat, atunci diferența Tsl – Ts este considerată ca o parte a costului suplimentar de calcul paralel.
Orice problemă nebanală, rezolvată pe mai multe procesoare, necesită comunicație între acestea pentru obținerea rezultatelor finale ale programului. Timpul consumat de procesoare pentru comunicație este cea mai importantă sursă de cost suplimentar. Dacă fiecare din ele p procesoare consumă un timp Tc pentru efectuarea comunicațiilor, atunci costul suplimentar datorat comunicației este p * Tc.
Procesul reprezintă unitatea de bază în programarea calculatoarelor paralele și corespunde operațiilor efectuate de un anumit segment de cod. Procesul este o entitate dinamică; el reprezintă o instanță de execuție a segmentului de cod corespunzător și are propria sa stare și propriile sale date. Paralelismul se obține prin execuția simultană, pe procesoare diferite, a mai multor procese, care comunică și se sincronizează între ele. Procesul primește mesaje pe canale conectate la porturile de intrare, pe care le prelucrează local și transmite mesaje pe canale conectate la porturile de ieșire.
Comunicația între procese este de două feluri: comunicație asincronă punct la punct și comunicație sincronă [KAPE97].
În comunicația asincronă punct la punct, un proces transmite un mesaj către altul prin depunerea acestuia într-un canal, direcționat de la primul proces către cel de-al doilea. Mesajul este depus în canal dacă există spațiu liber în buffer-ul asociat canalului. Un mesaj este eliminat din canal după ce a fost recepționat de proces.
În comunicația sincronă între procese, un proces este transmițător și restul sunt receptori. O comunicație are loc doar dacă toate procesele care participă la comunicație așteaptă comunicare, fenomen numit și rendez-vous. Efectul comunicației este ca toți receptorii să primească simultan mesajul transmis. În continuare toate procesele prelucrează calculele care urmează după rendez-vous.
Thread –ul este un fir de execuție independentă în cadrul unui proces. Procesele tradiționale (de exemplu cele implementate în sistemele de operare UNIX) conțin un singur thread, dar sistemele de operare cu multiprocesare implementează diferite modalități de creare și execuție a thread-urilor multiple (numite pthreads). Fiecare thread reprezintă un flux separat de execuție și este caracterizat prin propria sa stivă și prin stare hardware (registre, flag-uri). Un program poate fi împărțit în mai multe thread-uri, fiecare cu o execuție mai mult sau mai puțin independentă. Aceste thread-uri comunică între ele prin accesul la spațiul de adresă a memoriei procesului, pe care îl partajează.
2.2 Criterii de clasificare a calculatoarelor paralele
Există multe modalități de construire a calculatoarele paralele. Acestea diferă în funcție de mecanismele de control, organizarea spațiului de adresă a memoriei, granularitatea procesoarelor.
După mecanismul de control se pot distinge urmatoarele clase de calculatoare [IONE99]: calculatoare cu flux unic de instrucțiuni și de date (Single Instruction Stream, Single Data Stream – SISD), calculatoare cu fluxuri multiple de instrucțiuni, flux unic de date (Multiple Instruction Stream, Single Data Stream – MISD), calculatoare cu flux unic de instrucțiuni, fluxuri multiple de date (Single Instruction Stream, Multiple Data Stream – SIMD), calculatoare cu fluxuri multiple de instrucțiuni și de date (Multiple Instruction Stream, Multiple Data Stream – MIMD).
Un calculator SISD constă dintr-o singură unitate de procesare (P) care primește un flux de instrucțiuni (FI), de la unitatea de control (C), așa cum se vede în Fig. 2.3. În fiecare pas de calcul, unitatea de control lansează o instrucțiune care operează asupra unei date din fluxul de date (FD) obținut din unitatea de memorie (M).
Unitate de FI Unitate de FD Unitate de
Control (C) Procesare (P) Memorie (M)
Fig. 2.3 Calculator SISD
Un astfel de calculator este un calculator secvențial care respectă modelul de execuție introdus de John von Neumann în perioada anilor 1945. Un algoritm care se execută într-un calculator secvențial este un algoritm secvențial (sau serial).
Algoritmii pentru calculatoarele SISD nu conțin nici o execuție paralelă, datorită faptului că există un singur procesor.
În calculatoarele MISD, N unități de procesare (P), fiecare cu propria lui unitate de control (C), primesc un flux unic de date de la o unitate de memorie (M), așa cum se vede în Fig. 2.4. Există N fluxuri de instrucțiuni (FI) și un singur flux de date (FD). La fiecare pas, asupra unei date primite din memorie, sunt executate operații diferite, de către toate procesoarele simultan, în funcție de instrucțiunea pe care o primește fiecare de la propria unitate de control.
În aceste calculatoare, paralelismul este obținut prin faptul că fiecare unitate de procesare execută operații diferite.
Unitate de FI0 Unitate de
Procesare (P0) Control (C0)
Unitate de FD Unitate de FI1 Unitate de
Memorie (M) Procesare (P1) Control (C1)
Unitate de FIN-1 Unitate de
Procesare (PN-1) Control (CN-1)
Fig. 2.4 Calculator MISD
Un calculator SIMD constă dintr-un număr N de unități de procesare (P), care operează sub controlul unui flux unic de instrucțiuni (FI) lansat de o unitate de control globală (C), ca în Fig. 2.5. Fiecare unitate de procesare posedă o unitate aritmetică-logică, o unitate de control locală și o memorie locală. Procesoarele lucrează sincron: la fiecare pas de calcul, toate procesoarele execută aceeași instrucțiune asupra unei date diferite din fluxuri de date multiple. Calculatoarele SIMD se mai numesc tablouri de procesoare (processors arrays).
Rezolvarea sarcinilor de calcul pe un calculator SIMD presupune comunicația de date și rezultate intermediare între procesoarele componente. Comunicațiile între procesoarele componente ale unui calculator SIMD au loc prin intermediul unei rețele de interconectare sau printr-o memorie partajată și rețea de interconectare.
Calculatoarele SIMD oferă sincronizare automată între procesoare la fiecare ciclu de instrucțiune, de aceea sunt adecvate programelor paralele care necesită sincronizări frecvente și sunt mai puțin eficiente pentru programe paralele care necesită decizii (instrucțiuni condiționale) frecvente. În calculatoarele SIMD, procesoarele nu execută instrucțiuni diferite în același ciclu de execuție. De exemplu, instrucțiunea condițională:
if(b==0) c=a;
else c=a / b;
este executată în doi pași. În primul pas de execuție, toate procesoarele care au b egal cu zero execută instrucțiunea c=a, iar toate celelalte procesoare sunt inactive. În al doilea pas, partea “else” a instrucțiunii este executată de toate procesoarele care au variabila b diferită de zero, iar procesoarele care au fost active în primul pas, devin inactive.
Unitate de FD0
Procesare (P0)
Memorie
Partajată
Unitate de FI Unitate de FD1
Control (C) Procesare (P1) și/sau
Rețea de
interconectare
Unitate de FDN-1
Procesare (PN-1)
Fig. 2.5 Calculator SIMD
Calculatoarele SIMD execută cu cea mai mare eficiență programe care implică operații asupra unor masive de date, programe care sunt cunoscute sub numele de programe data-paralele.
Exemple de calculatoare SIMD: ILLIAC IV, Connection Machines 2, MasPar MP-2.
Calculatoarele MIMD sunt calculatoare paralele în care un procesor execută un program diferit de programul executat de celelalte procesoare. Această clasă de calculatoare este cea mai generală, cea mai puternică și cea mai flexibilă.
Un calculator MIMD constă dintr-un numar N de unități de procesare (P), fiecare cu propria lui unitate de control (C) și memorie locală; fiecare procesor operează sub controlul unui flux de instrucțiuni lansat de unitatea de control proprie, executând operații asupra unui flux de date propriu (Fig. 2.6).
Comunicația între procesoarele unui calculator MIMD se face la fel ca și într-un calculator SIMD printr-o rețea de interconectare sau prin memorie partajată și rețea de interconectare. Procesoarele individuale (elementele de procesare) dintr-un calculator MIMD sunt mai complexe decât cele dintr-un calculator SIMD, deoarece fiecare posedă o unitate de contol proprie. Calculatoarele din această clasă sunt folosite pentru rezolvarea oricărui tip de problemă, inclusiv cele care nu prezintă masive de date regulate și operații identice executate de toate procesoarele în aceleași momente de timp, așa cum este necesar pentru o execuție eficientă în calculatoarele SIMD. Această generalitate și flexibilitate de execuție în calculatoarele MIMD îngreunează sarcina de programare. Dat fiind că procesoarele lucrează asincron, algoritmii implementați sunt algoritmi asincroni, care sunt dificil de proiectat, de implementat, de testat și de evaluat.
Unitate de FI0 Unitate de FD0
Control (C0) Procesare (P0)
Memorie
Partajată
Unitate de FI1 Unitate de FD1
Control (C1) Procesare (P1) și/sau
Rețea de
interconectare
Unitate de FIN-1 Unitate de FDN-1
Control (CN-1) Procesare (PN-1)
Fig. 2.6 Calculator MIMD
O altă dificultate în programarea calculatoarelor MIMD o reprezintă necesitatea ca programatorul să țină seama de caracteristicile hardware ale sistemului. Un programator care scrie un program într-un limbaj de nivel înalt pentru un calculator secvențial, ignoră particularitățile constructive ale mașinii, deoarece acestea sunt preluate de către compilator. Pentru a scrie un program paralel asincron, programatorul trebuie să cunoască bine organizarea hardware a sistemului, dacă dorește să obțină un program eficient. Această dependență a programului de particularitățile constructive ale calculatorului face ca programele paralele sa fie puțin portabile.
După organizarea spațiului de adresă a memoriei se disting arhitecturi cu spațiul de adresă a memoriei partajat și arhitecturi cu transfer de mesaje.
Arhitecturile cu spațiul de adresă a memoriei partajat ( shared –
address – space arhitectures ) asigură suport hardware pentru accesul de citire și scriere a tuturor procesoarelor la o memorie partajată. Procesoarele comunică între ele prin date memorate într-un spațiu unic și partajat de adrese ale memoriei.
Calculatoarele MIMD cu spațiul de adresă a memoriei partajat se numesc multiprocesoare (multiprocessors). Multiprocesoarele mai sunt denumite sisteme puternic cuplate (tightly-coupled systems), datorită gradului ridicat de partajare a resurselor.
Există modele de sisteme cu spațiul de adresă a memoriei partajat: modelul cu acces uniform la memorie (Uniform Memory Access – UMA), modelul cu acces neuniform la memorie (Nonuniform Memory Access – NUMA) și modelul cu acces partajat prin memoria cache (Cache-Only Memory Access – COMA). Aceste modele diferă între ele prin modul în care memoria și resursele periferice sunt partajate și distribuite.
Într-un model cu acces uniform la memorie (UMA), memoria fizică este partajată uniform de toate procesoarele. Toate procesoarele (P) au timp de acces egal la toate cuvintele de memorie partajată (MP) – Fig. 2.7. Deficiența majoră a modelului UMA o constituie faptul că banda de comunicație a rețelei de interconectare trebuie să fie foarte mare pentru a se obține performanțe bune, deoarece în fiecare ciclu instrucțiune, fiecare procesor poate necesita accesul la o locație din memoria partajată, prin intermediul rețelei de interconectare. Timpul de acces la o locație de memorie este mare datorită faptului că datele citite sau scrise în memorie trebuie să traverseze unul sau mai multe etaje în rețeaua de interconectare. Aceste probleme afectează serios performanțele sistemelor cu acces uniform la memorie.
P0 P1 PN-1
Rețea de Interconectare
MP0 MP1 MPM-1
Fig. 2.7 Modelul cu acces uniform la memorie (UMA)
Într-un model cu acces neuniform la memorie (NUMA), timpul de acces variază în funcție de localizarea cuvântului de memorie. În Fig. 2.8 și Fig. 2.9 sunt prezentate două modele cu acces neuniform la memorie.
P0 MPD0 P1 MPD1 PN-1 MPDN-1
Rețea de Interconectare
Fig. 2.8 Model cu acces neuniform la memorie (NUMA):
Sistem cu memorie partajată distribuită (MPD)
P0 ML0 P1 ML1 PN-1 MLN-1
Rețea de Interconectare
MGP0 MGP1 MGPM-1
Fig. 2.9 Model cu acces neuniform la memorie (NUMA):
Sistem cu memorie locală(nepartajată-ML) și memorie globală partajată(MGP)
În modelul cu memorie partajată distribuită (Fig. 2.8), memoria este distribuită fizic procesoarelor sub forma unor module de memorie partajată (MPD), iar mulțimea tuturor acestor module formează un spațiu de adresă unic, accesat de toate procesoarele. În modelul cu memorie locală (nepartajată) și memorie globală partajată (Fig. 2.9), fiecare procesor (P) are atașat un modul de memorie locală (ML), în care sunt memorate programele și datele locale ale fiecarui procesor, iar memoria globală partajată este alcătuită dintr-un număr de module (MGP), în care sunt memorate datele partajate și care sunt accesate de toate procesoarele printr-o rețea de interconectare. Timpul de acces la memorie este neuniform: accesul la modulul de memorie propriu (atașat procesorului) este mai redus decât timpul de acces la modulele de memorie din alte noduri, datorită latenței de traversare a rețelei de interconectare.
În modelul cu acces partajat prin memoria cache (COMA), memoria atașată fiecarui procesor este un modul de memorie cache, iar toate aceste module formează împreună un spațiu global de adrese (Fig. 2.10).
Rețea de Interconectare
D0 D1 DN-1
C0 C1 CN-1
P0 P1 PN-1
Fig. 2.10 Modelul cu acces partajat prin memoria cache
Accesul la un modul de memorie cache (C) nelocal este asistat de un bloc de memorie cu rol de director (D), care menține consistența datelor în cache.
În arhitecturile cu transfer de mesaje ( message – passing
arhitectures), procesoarele (P) sunt conectate între ele printr-o rețea de interconectare. Fiecare procesor are propria lui memorie locală (M), care este accesibilă numai acestuia. Procesoarele interacționează numai prin intermediul mesajelor, transferate prin rețeaua de interconectare. Această arhitectură este o arhitectură cu memorie distribuită și spații multiple de adresă. Fig. 2.11 prezintă organizarea tipică a arhitecturii cu transfer de mesaje.
Rețea de Interconectare
P0 P1 PN-1
M0 M1 MN-1
Fig. 2.11 Arhitectura cu transfer de mesaje
Un calculator MIMD cu transfer de mesaje este denumit multicalculator (multicomputer). Multicalculatoarele mai sunt numite sisteme slab cuplate (loosely – coupled systems) datorită gradului redus de partajare a resurselor.
După modul de organizare a spațiului de adresă a memoriei (spațiu de adresă unic, partajat al memoriei sau spații multiple de adresă), precum și modul de amplasare fizică a memoriei, calculatoarele MIMD sunt împărțite în patru subclase, ca în figura Fig. 2.12:
Calculatoare MIMD
Puternic cuplate Slab cuplate
Multiprocesoare Multicalculatoare
Spațiu unic de adresă a Spații multiple de adresă a
memoriei partajate memoriei și transfer de mesaje
Multiprocesoare Multiprocesoare Multicalc. Multicalc.
cu memorie partajată cu memorie partajată cu memorie cu memorie
centralizată (UMA) distribuită (NUMA) centralizată distribuită
Fig. 2.12 Clasificarea calculatoarelor MIMD
Dintre subclasele descrise, subclasa multicalculatoarelor cu memorie centralizată nu este exemplificată deocamdată printr-un sistem cunoscut.
După granularitatea procesoarelor, calculatoarele se împart în calculatoare cu granularitate grosieră, calculatoare cu granularitate fină și calculatoare cu granularitate medie.
Calculatoarele cu granularitate grosieră (coarse – grain) dispun de procesoare mari și complexe. De exemplu, sistemele Cray 2 și Cray X-MP au câte patru procesoare fiecare, iar sistemele ETA dispun de opt procesoare. Aceste calculatoare au o putere de calcul de 100-1000 milioane operații/sec în virgulă mobilă. Ele sunt folosite pentru descompunerea problemelor în task-uri, care necesită comunicarea între ele numai temporar.
Calculatoarele cu granularitate fină (fine – grain) dispun de un număr mare de procesoare, mici și simple. De exemplu, Connection Machine of Thinking Machines Corporation și STARAN sunt sisteme cu mii de procesoare simple, iar sistemele MPP Goodyear Aerospace și VLIW sunt arhitecturi cu zeci de procesoare. Task – urile ce sunt executate independent în fiecare procesor sunt de dimensiune redusă și comunicația între procesoare domină în total volumul de lucru. Acest lucru face dificilă obținerea eficienței. Pentru o aplicație dată, numărul de procesoare care trebuie utilizate eficient depinde de paralelismul intrinsec dintre aplicație și dimensiunea problemei.
Exemple de calculatoare cu granularitate medie (medium-grain): Encor Computer’s bus – based Multimax, BBN’s Butterfly, Intel’s și PSC hypercube. Aceste sisteme manipulează 15 – 100 MIPS (Millions of Instructions per Second) cu o configurație de 16 – 128 procesoare.
2.3 Realizări hardware
În [HOCK91] este descrisă o serie de arhitecturi paralele: calculatoarele
CRAY X – MP si CRAY – 2, CDC CYBER 205, calculatoarele vectoriale
pipeline, FPS AP – 120B, transputerul T800.
Calculatoarele CRAY X – MP si CRAY – 2 au fost produse de CRAY
Research Inc. la Chippewa Falls, Wisconsin, SUA. Ele au derivat de la CRAY-1, proiectat de la Seymour Cray și instalate prima data la Los Alamos Scientific Laboratory în 1976.
Apariția lui CRAY X – MP, care este versiunea multiprocesor a lui
CRAY– 1, se datorează lui Steve Chen și echipei sale de la Chippewa Falls. În 1982 a fost anunțată o versiune cu 2 CPU, iar în 1984 o versiune cu 4 CPU.
CRAY – 2 a fost dezvoltat de Seymour Cray ca un proiect separat la
Chippewa Falls. El folosește tehnologie mai avansată și un nou mod de răcire.
CDC CYBER 205 a fost construit de Control Data Corporation la Saint
Paul, Minesota, SUA. Mașina a fost anunțată in 1980, iar prima livrare la un utilizator s-a realizat la Oficiul Meteorologic din Brocknell, Marea Britanie în 1981. Până în anul 1985 au fost livrate aproximativ 27 CYBER 205.
În anul 1983 s-a lansat CYBER 205 seria 600, la care s-a înlocuit
memoria principală bipolară cu 4Mw a calculatorului inițial (denumit acum seria 400) cu o memorie MOS statică de 16Mw.
Calculatorul ETA10 care a apărut în 1986 este definit ca 8 calculatoare
CYBER 205 care lucrează cu o memorie comună mare.
În 1984, trei firme japoneze ( Fujitsu, Hitachi si NEC ) au anunțat
calculatoarele vectoriale pipeline, care combină cele mai bune caracteristici ale mașinilor CRAY – 1 și CYBER 205. Toate au unități scalare și vectoriale separate, ca CYBER 205 și registre vectoriale asemeni CRAY – 1. Calculatoarele sunt: Fujitsu VP – 100 și VP – 200 cu performanța maximă de 266 MFlop/sec, respectiv 533 MFlop/sec; Hitachi HITAC S – 810, modelele 10 și 20 cu performanțele de 315 și 630 MFlop/sec; NEC X1 și X2 cu 570, respectiv 1300 MFlop/sec. Deși similare arhitectural, cele 3 calculatoare diferă semnificativ în privința tehnologiilor de răcire.
FPS AP – 120B și derivatele sale – AP 190L, FPS-100, 164, 164/MAX,
264 și FPS 5000 – sunt membrii unei singure familii de calculatoare ce se bazează pe o arhitectură comună: cea a calculatorului FPS-120B. Toate sunt produse de Floating Point Systems Inc.
În anul 1980 s-a extins utilizarea calculatorului AP-120B de la aplicații de
prelucrare a semnalelor la calcule stiințifice generale prin creșterea lungimii cuvântului de la 32 biți la 64 biți, iar a adresei de la 16 la 24 biți. Capacitatea memoriei a fost sporită, la început la 1Mw, apoi la 7.25 Mw. Noua mașină obținută, FPS – 164, a început să fie comercializată în 1981. FPS – 164/MAX este un calculator SIMD deoarece cele 31 CPU ale unei configurații complete lucrează sincron (lock – step) ca urmare a execuției unui flux unic de instrucțiuni.
FPS – 5000 este un calculator MIMD cu memorie partajată, conectat prin
magistrală. Dispune de un procesor de control, până la 3 coprocesoare aritmetice și un procesor de I/E care comunică printr-o magistrală comună cu memoria comună și un calculator gazdă.
Transputerul (INMOS 1985) T800 este un microprocesor pe o capsulă
produs de compania INMOS Lmt. Se distinge de alte procesoare prin accea că a fost proiectat special ca element de bază pentru procesoarele paralele. De aceea, posedă în interiorul circuitului VLSI memorie și linii de comunicație pentru comunicarea cu alte transputere. Este considerat ca o familie de componente VLSI programabile care implementează conceptul de calcul concurent.
Mecanismele pentru facilitarea concurenței includ hardware pentru o
coadă de așteptare pentru procese, cu registre speciale și instrucțiuni microprogramate care permit crearea task-urilor paralele.
Produsele transputer comercializate includ un procesor pe 32 biți cu o
magistrală de adrese/date pe 32 biți multiplexată (T414), un procesor pe 16 biți (T212) și un circuit controler de disc, cu magistrale de date și adrese pe 16 biți și interfața specializată standard. Componentele interne transputerului lucrează concurent; fiecare din cele 4 legături și coprocesorul în VM pot efectua operații utile, în timp ce procesorul execută alte instrucțiuni. Fiecare linie de comunicație are un canal DMA în sistemul de memorie care va reduce lărgimea de bandă la procesor.
Transputerele sunt folosite în multe aplicații și în diverse moduri, acum
existând pe piață mai multe sisteme bazate pe transputere, inclusiv rack – uri cu plăci de dezvoltare cu transputere produse de INMOS.
În [OANC98] sunt descrise sistemele cu procesoare superscalare. Aceste
procesoare sunt capabile să execute mai multe instrucțiuni simultan. Modelul procesoarelor superscalare se bazează pe un flux secvențial de instrucțiuni obișnuite (RISC sau CISC), unitatea de decodificare și planificare având sarcina de a rezolva dependențele între instrucțiuni și de a trimite spre execuție numai acele instrucțiuni care sunt independente. Primele microprocesoare superscalare care au apărut pe piață au fost cele RISC. Microprocesoarele CISC au apărut mai târziu datorită complexității ridicate a acestora.
Pentru a permite executarea în paralel a instrucțiunilor planificate, toate procesoarele superscalare posedă mai multe unități funcționale. Deoarece nu toate unitățile funcționale au aceeași viteză de execuție (o operație în VM durează mai mult decât una în VF), instrucțiunile care la un moment dat sunt în faza de execuție se pot termina în altă ordine decât ordinea secvențială în care ele apar în program. Pentru a menține corectitudinea programului, procesorul trebuie să rezolve problema menținerii secvențialității instrucțiunilor.
2.4 Modele teoretice de calculatoare paralele
Modelele teoretice de calculatoare paralele sunt abstractizări ale modelelor fizice prezentate în subcapitolul 2.2 “Criterii de clasificare a calculatoarelor paralele”. Aceste modele reprezintă un cadru de lucru idealizat în care se ignoră detalii de implementare sau constrângeri fizice. Cel mai utilizat model teoretic de calculator paralel este modelul cu acces aleator (Parallel Random Access Machines – PRAM), care reprezintă extinderea modelului teoretic RAM (Random Access Machines) de calculator secvențial.
Calculatoarele secvențiale convenționale au fost modelate ca mașini cu acces aleator – RAM de către Sheperdson și Sturgis. Modelul RAM constă dintr-o unitate de memorie, o unitate de bandă de intrare cu tipul de acces numai citire (read-only), o unitate de bandă de ieșire cu tipul de acces numai scriere (write-only) și un program ce nu este modificat (Fig. 2.13):
X0 X1 Xn-1 Banda de intrare (read-only)
r0 Acumulator
r1
r2
Program r3
Memorie
Y0 Y1 Banda de ieșire (write-only)
Fig. 2.13 Modelul RAM de calculator secvențial
Banda de intrare conține o secvență de numere întregi; de fiecare dată când se citește o valoare de intrare, banda avansează cu o poziție. Similar, banda de ieșire avansează cu o poziție după fiecare scriere. Memoria constă dintr-un număr nelimitat de registre (r0, r1, r2, …) în care sunt memorate numere întregi. Registrul r0 este registru acumulator în care se efectuează calculele.
Timpul de execuție în cazul cel mai defavorabil a unui program în modelul RAM este o funcție f(n), dată de timpul maxim de execuție a programului asupra tuturor celor n date de intrare. Timpul mediu de execuție a unui program în modelul RAM este dat de timpul mediu de execuție a programului pentru toate cele n date de intrare.
Modelul PRAM (Parallel Random Access Machines) a fost dezvoltat de Fortune și Wyllie, pentru modelarea unui calculator paralel idealizat cu cost suplimentar (overhead) de sincronizare și acces la memorie nul. Modelul PRAM este utilizat pentru analiza performanțelor de calcul paralel: timp de execuție paralelă, accelerare paralelă, eficiență și scalabilitate.
Modelul PRAM cu p procesoare (Pi, 0 ≤ i < p) (Fig. 2.14) prezintă o memorie partajată (MP) centralizată sau distribuită. Procesoarele (numite și elemente de procesare) operează sincron, într-o secvență de cicluri de citire din memorie, calcul, scriere în memorie.
P0
P1 Memorie
Partajată
(MP)
Pp-1
Fig. 2.14 Modelul PRAM cu p procesoare și memorie partajată
Opțiunile de acces concurent al procesoarelor la memoria partajată sunt: citire exclusivă, scriere exclusivă, citire concurentă, scriere concurentă.
Opțiunea citire exclusivă (Exclusive Read – ER) permite ca, într-un ciclu, cel mult un procesor să citească dintr-o anumită locație de memorie.
Opțiunea scriere exclusivă (Exclusive Write – EW) permite ca, într-un ciclu, cel mult un procesor să scrie într-o anumită locație de memorie.
Opțiunea citire concurentă (Concurrent Read – CR) permite ca mai multe procesoare să citească aceeași locație de memorie, în același ciclu.
Opțiune scriere concurentă (Concurrent Write – CW) permite ca mai multe procesoare să scrie în aceeași locație de memorie, în același ciclu.
Variante ale modelului PRAM: EREW-PRAM, CREW-PRAM, ERCW-PRAM, CRCW-PRAM [HUAN90].
Modelul EREW-PRAM este un model PRAM cu citire și scriere exclusivă. Este interzis ca mai mult de un procesor să acceseze, pentru citire sau scriere, simultan, aceeași locație de memorie. Acesta este modelul PRAM cel mai restrictiv.
Modelul CREW-PRAM este un model PRAM cu citire concurentă și scriere exclusivă. În acest model, conflictele de scriere în memoria partajată sunt evitate prin excludere mutuală. Sunt permise accese concurente de citire a mai multor procesoare la aceeași locație de memorie.
Modelul ERCW-PRAM este modelul PRAM cu citire exclusivă și scriere concurentă. Sunt permise accese exclusive de citire și accese concurente de scriere.
Modelul CRCW-PRAM este modelul PRAM cu citire și scriere concurentă. Sunt permise accese concurente de citire și de scriere la aceeași locație de memorie.
Conflictele de scriere concurentă se rezolvă prin urmatoarele moduri: comun, arbitrar, minimal, prioritar.
În cazul modului comun (COMMON – PRAM) operațiile de scriere
memorează aceeași valoare la locația accesată simultan.
În cazul modului arbitrar (ARBITRARY – PRAM) se memorează una din
valori, oricare, iar celelalte valori de scriere sunt ignorate.
În cazul modului minimal (MINIMUM – PRAM) se memorează valoarea scrisă de procesorul cu indexul cel mai mic.
În cazul modului prioritar (PRIORITY – PRAM) se memorează o valoare obținută prin aplicarea unei funcții asociative (de exemplu, însumare) tuturor valorilor cu care se accesează locația de memorie.
Puterea de calcul a acestor modele variază astfel:
EREW-PRAM
CREW-PRAM
COMMON CRCW-PRAM Crește puterea
ARBITRARY CRCW-PRAM
PRIORITY CRCW-PRAM
Modelul EREW-PRAM este cel mai slab. Într-un model CREW-PRAM se execută orice algoritm EREW-PRAM cu același timp de execuție, prin ignorarea facilității de acces concurent de scriere. Într-un model CRCW-PRAM se execută orice algoritm EREW-PRAM cu același timp de execuție, prin ignorarea facilității de acces concurent de citire și scriere.
Modelul PRIORITY-PRAM este cel mai puternic. Orice algoritm proiectat pentru a rezolva o problemă în modelul EREW-PRAM are un timp de execuție mai mare decât un algoritm care rezolvă aceeași problemă într-un model PRIORITY-PRAM. Modelul PRIORITY-PRAM cu p procesoare este simulat printr-un model EREW-PRAM cu p procesoare, cu creșterea timpului de execuție cu un factor egal cu log p.
Modelele PRAM reprezintă idealizarea calculatoarelor paralele, prin presupunerea că toate accesele la memorie și execuția programelor de către procesoare multiple sunt sincronizate fără cost suplimentar.
=== 6_trecere ===
3. Trecerea de la algoritmi secvențiali la
algoritmi de prelucrare paralelă
Pentru descrierea algoritmilor paraleli se folosește un limbaj formal de nivel înalt.
Un algoritm paralel constă din două tipuri de operații: operații secvențiale si paralele. Pentru descrierea operațiilor secvențiale se folosesc instrucțiuni similare celor din limbajul de programare C (de exemplu: for, if…else, while, instrucțiuni de atribuire, de intrare – ieșire, etc.).
Operațiile paralele sunt exprimate prin două tipuri de construcții: par și forall.
Se utilizează par pentru execuția în paralel a mai multor instrucțiuni specificate printr-o listă:
par
{
< lista_instrucțiuni >
} ,
unde fiecare instrucțiune din listă se execută pe un procesor separat.
Pentru execuția în paralel, de către mai multe procesoare, specificate printr-o listă, a unei operații specificată printr-o listă de instrucțiuni, se utilizează forall:
forall <lista_procesoare>
{
< lista_instrucțiuni >
}
Pe baza criteriilor de evaluare a performanțelor algoritmilor paraleli prezentate în capitolul precedent (accelerare paralelă, eficiență, cost), se stabilesc condiții generale pe care aceștia trebuie să le îndeplinească pentru rezolvarea eficientă a problemelor de calcul [IONE99]:
numărul de procesoare trebuie să fie mai mic decât dimensiunea problemei (dimensiunea problemei este dată de dimensiunea intrării);
numărul de procesoare trebuie să fie adaptiv;
timpul de execuție paralelă trebuie să fie cât mai mic;
timpul de execuție paralelă trebuie să fie adaptiv, el depinzând de numărul de procesoare utilizate;
costul trebuie să fie optimal.
3.1 Algoritmi pentru înmulțirea matricelor
Cel mai simplu algoritm secvențial de înmulțire a două matrice
pătratice a și b, cu rezultat matricea c este prezentat în Programul 1.
Programul 1
Algoritm secvențial de înmulțire a două matrice pătratice
ÎNMULȚIRE_MATRICE_1
Condiții inițiale: Matricele a[n][n] și b[n][n] conțin datele.
Rezultat final: Matricea c[n][n] conține rezultatul.
Variabile globale: n, a[n][n], b[n][n], c[n][n].
for( i = 0; i < n; i ++)
for( j = 0; j < n; j ++)
{
c[i][j] = 0;
for( k = 0; k < n; k ++)
c[i][j] += a[i][k] * b[k][j];
}
Algoritmul secvențial conține trei bucle de calcul imbricate, fiecare cu
un număr de n iterații, deci se execută n3 pași de calcul. Timpul de execuție secvențială este de forma Ts = O(n3).
Acest algoritm nu este cel mai rapid algoritm secvențial de înmulțire a
două matrice. Algoritmul lui Strassen are timpul de execuție in O(n2.5).
Într-un algoritm CRCW – PRAM de înmulțire a două matrice pătratice de dimensiune n folosind n3 procesoare se consideră un număr de p = n3 procesoare, în care conflictele de scriere concurentă sunt rezolvate în modul de scriere combinat, folosind operatorul de însumare. Atunci când două sau mai multe procesoare accesează pentru scriere aceeași locație de memorie, în aceea locație se înscrie suma tuturor valorilor.
Matricele a, b și c sunt amplasate în memoria partajată. Cele n3 procesoare sunt aranjate într-un tablou tridimensional, deci fiecare procesor este identificat prin trei indici (Pi,j,k). Fiecare procesor Pi,j,k calculează simultan produsul a[i][k]*b[k][j]. La scrierea concurentă în locația c[i][j], a termenilor a[i][0]*b[0][j], a[i][1]*b[1][j], … , a[i][n-1]*b[n-1][j], de către procesoarele Pi,j,0, Pi,j,1, … , Pi,j,n-1 se memorează suma tuturor acestor valori. Algoritmul este prezentat în Programul 2.
Programul 2
Algoritm CRCW-PRAM de înmulțire a două matrice
pătratice de dimensiune n folosind n3 procesoare
ÎNMULȚIRE_MATRICE_2
Condiții inițiale: Matricele a[n][n] și b[n][n] conțin datele.
Rezultat final: Matricea c[n][n] conține rezultatul.
Variabile globale: n, a[n][n], b[n][n], c[n][n].
forall (0 <= i < n)
{
forall (0 <= j < n)
{
forall (0 <= k < n)
{
c[i][j] = 0;
c[i][j] += a[i][k]*b[k][j];
}
}
}
Inițializarea matricei c, executată de toate procesoarele, înscrie în fiecare
locație a matricei c suma a n valori egale cu zero.
Fiecare procesor execută o singură iterație de calcul, deci timpul de execuție a algoritmului este constant: TpCRCW = O(1).
Accelerarea paralelă este:
S = Ts / TpCRCW
sau
S = O(n3),
unde:
Ts este timpul de execuție secvențială a algoritmului;
TpCRCW este timpul de execuție a algoritmului CRCW-PRAM
(TpCRCW = O(1)).
Eficiența paralelă este:
E = S / p
sau
E = 1,
unde:
S este accelerarea paralelă calculată mai sus;
p este numărul de procesoare utilizate (p = n3).
Costul algoritmului CRCW-PRAM este:
C = p * TpCRCW
sau
C = O(n3),
unde mărimile p și TpCRCW au fost explicate mai sus.
Algoritmul CRCW-PRAM prezintă o accelerare foarte mare (S = O(n3)) și este cost-optimal (costul C este proporțional cu Ts). Acesta performanță a algoritmului este obținută însă cu un număr mare de procesoare (n3), ceea ce face puțin probabilă implementarea lui în practică.
Costul suplimentar de calcul paralel este:
T0 = C – Ts
sau
T0 = n3 – n3 = 0,
unde:
C este costul paralel;
Ts este timpul de execuție secvențială.
Valoarea zero a costului suplimentar este explicată prin faptul că procesoarele sunt încărcate echilibrat, nu există calcule suplimentare, iar timpii de comunicație sunt ignorați.
Într-un algoritm CREW-PRAM de înmulțire a două matrice pătratice de dimensiune n folosind n3 procesoare, spre deosebire de modelul CRCW-PRAM descris anterior, este necesar un spațiu de lucru suplimentar și anume un tablou tridimensional de dimensiune n*n*n, v[n][n][n] amplasat în memoria partajată, în locul matricei c[n][n]. Fiecare locație a tabloului tridimensional corespunde procesorului cu același indice.
În prima parte a algoritmului, fiecare procesor Pi,j,k din cele n3 procesoare calculează produsul a[i][k]*b[k][j] și înscrie rezultatul în locația v[i][j][k].
În a doua parte, trebuie să fie executată reducerea prin însumarea a n elemente ale fiecărui vector din tabloul bidimensional v[i][j]. Acestă operație se poate face în paralel pentru cei n2 vectori, folosind n procesoare Pi,j,0, Pi,j,1, … , Pi,j,n-1 pentru fiecare vector v[i][j]. La sfârșitul reducerii paralele, rezultatul înmulțirii se află în tabloul bidimensional v[n][n][0].
Algoritmul CREW-PRAM de înmulțire este prezentat în Programul 3.
Programul 3
Algoritm CREW-PRAM de înmulțire a două matrice
pătratice de dimensiune n folosind n3 procesoare
ÎNMULȚIRE_MATRICE_3
Condiții inițiale: Matricele a[n][n] și b[n][n] conțin datele.
Rezultat final: Matricea v[n][n][0] conține rezultatul.
Variabile globale: n, a[n][n], b[n][n], v[n][n][0].
forall (0 <= i < n)
{
forall (0 <= j < n)
{
forall (0 <= k < n)
{
v[i][j][k] = a[i][k]*b[k][j];
for(m = 0; m < log n; m++)
if(k modulo 2m+1 == 0)
v[i] [j][k] += v[i][j][k + 2m];
}
}
}
Fiecare procesor execută un pas de calcul pentru aflarea produsului a[i][k]*b[k][j] și log n pași de calcul pentru reducerea paralelă de dimensiunea k a tabloului v[n][n][n] (log n este logaritm în baza 2 din n).
Timpul de execuție paralelă este:
TpCREW = 1 + log n
sau
TpCREW = O(log n).
Se observă că O(1) = TpCRCW < TpCREW < Ts = O(n3).
Accelerarea paralelă este:
S = Ts / TpCREW
sau
S = O(n3 / log n),
unde:
Ts este timpul de execuție secvențială a algoritmului;
TpCREW este timpul de execuție a algoritmului CREW-PRAM folosind n3
procesoare (TpCREW = O(log n)).
Eficiența paralelă este:
E = S / p
sau
E = O(1 / log n),
unde:
S este accelerarea paralelă calculată mai sus;
p este numărul de procesoare utilizate (p = n3).
Costul algoritmului CREW-PRAM folosind n3 procesoare este:
C = p * TpCREW
sau
C = O(n3 * log n ),
unde mărimile p și TpCREW au fost explicate mai sus.
Algoritmul CREW-PRAM de înmulțire a două matrice pătratice nu este cost-optimal deoarece costul C = O(n3 * log n ) nu este proporțional cu Ts = O(n3). În plus, pentru execuție, algoritmul necesită un tablou tridimensional v[n][n][n], deci un spațiu suplimentar de lucru.
Costul suplimentar de calcul paralel este:
T0 = C – Ts
sau
T0 = O(n3 * log n – n3)
sau
T0 = O(n3 * log n),
unde:
C este costul paralel;
Ts este timpul de execuție secvențială.
Înmulțirea matricelor utilizând cele două modele (CRCW-PRAM și CREW-PRAM) este un program data-paralel cu granularitatea cea mai fină și cu un grad de paralelism maxim, O(n3). Programul prezintă caracterul de paralelism structural: datele problemei sunt organizate în structuri regulate (matricele a, b, c) asupra cărora se execută operații identice.
Într-un algoritm CREW-PRAM de înmulțire a două matrice pătratice de dimensiune n folosind n2 procesoare, procesoarele sunt organizate într-un tablou bidimensional și numerotate cu doi indici: Pi,j cu 0 <= i,j < n.
Fiecare procesor Pi,j calculează elementul c[i][j] al matricei rezultat prin calculul a n produse de elemente ale matricelor a și b și însumarea acestor produse.
Algoritmul este prezentat în Programul 4.
Programul 4
Algoritm CREW-PRAM de înmulțire a două matrice
pătratice de dimensiune n folosind n2 procesoare
ÎNMULȚIRE_MATRICE_4
Condiții inițiale: Matricele a[n][n] și b[n][n] conțin datele.
Rezultat final: Matricea c[n][n] conține rezultatul.
Variabile globale: n, a[n][n], b[n][n], c[n][n].
forall (0 <= i < n)
{
forall (0 <= j < n)
{
c[i][j] = 0;
for(k = 0; k < n; k++)
c[i] [j] += a[i][k]*b[k][j];
}
}
Fiecare procesor Pi,j accesează o singură locație, c[i][j], unde depune rezultatul. De aceea modelul suportă scriere exclusivă (EW). Liniile și coloanele matricelor a și b sunt accesate concurent pentru citire (CR).
Fiecare procesor execută o buclă for de n iterații, deci timpul de execuție paralelă este:
TpCREW = O(n).
Se observă că O(log n) = TpCREW(n3) < TpCREW (n2) < Ts = O(n3).
Accelerarea paralelă este:
S = Ts / TpCREW
sau
S = O(n2),
unde:
Ts este timpul de execuție secvențială a algoritmului;
TpCREW este timpul de execuție a algoritmului CREW-PRAM folosind n2
procesoare (TpCREW = O(n)).
Eficiența paralelă este:
E = S / p
sau
E = 1,
unde:
S este accelerarea paralelă calculată mai sus;
p este numărul de procesoare utilizate (p = n2).
Costul algoritmului CREW-PRAM folosind n2 procesoare este:
C = p * TpCREW
sau
C = O(n3),
unde mărimile p și TpCREW au fost explicate mai sus.
Acest algoritm este cost-optimal deoarece costul C = O(n3) este proporțional cu Ts = O(n3).
Costul suplimentar de calcul paralel este:
T0 = C – Ts
sau
T0 = n3 – n3 = 0,
unde:
C este costul paralel;
Ts este timpul de execuție secvențială.
Într-un algoritm de înmulțire a două matrice pătratice de dimensiune n folosind mai puțin de n2 procesoare, matricea c se împarte în p submatrice (p este numărul de procesoare) de dimensiuni cât mai apropiate. Fiecare procesor calculează toate elementele uneia dintre aceste submatrice.
Parționarea matricei c se face în blocuri rectangulare sau pătrate. Procesoarele se organizează într-un tablou bidimensional de dimensiune p1/2 * p1/2 și se numerotează cu doi indici: Pl,m cu 0 <= l, m < p1/2 (Fig. 3.1).
Pentru simplificarea expresiilor se consideră:
p pătrat perfect, q = p1/2;
n divizibil cu q;
s = n / q.
Fig. 3.1 Parționarea în blocuri a matricei c
În Programul 5 este prezentată implementarea algoritmului de înmulțire
a două matrice pătratice de dimensiune n în modelul CREW-PRAM cu un număr p < n2 procesoare, prin pariționarea în blocuri.
Programul 5
Algoritm CREW-PRAM de înmulțire a două matrice
pătratice de dimensiune n folosind p < n2 procesoare
ÎNMULȚIRE_MATRICE_5
Condiții inițiale: Matricele a[n][n] și b[n][n] conțin datele partiționate în
blocuri: q = p1/2, s = n / q.
Rezultat final: Matricea c[n][n] conține rezultatul.
Variabile globale: n, q, s, a[n][n], b[n][n], c[n][n].
forall (0 <= l < q)
{
forall (0 <= m < q)
{
for(i = s*l; i < s*(l + 1); i++)
for(j = s*m; j < s*(m + 1); j++)
{
c[i][j] = 0;
for(k = 0; k < n; k++)
c[i] [j] += a[i][k]*b[k][j];
}
}
}
Fiecare procesor execută trei bucle de calcul imbricate cu s, s și n iterații, deci timpul de execuție paralelă este:
Tp = O(n3 / p).
Accelerarea paralelă este:
S = Ts / Tp
sau
S = O(p),
unde:
Ts este timpul de execuție secvențială a algoritmului;
Tp este timpul de execuție a algoritmului CREW-PRAM folosind mai
puțin de n2 procesoare (Tp = O(n3 / p)).
Eficiența paralelă este:
E = S / p
sau
E = O(1),
unde:
S este accelerarea paralelă calculată mai sus;
p este numărul de procesoare utilizate (p < n2).
Costul algoritmului CREW-PRAM folosind p procesoare este:
C = p * Tp
sau
C = O(n3),
unde mărimile p și Tp au fost explicate mai sus.
Costul suplimentar de calcul paralel este:
T0 = C – Ts
sau
T0 = n3 – n3 = 0,
unde:
C este costul paralel;
Ts este timpul de execuție secvențială.
Algoritmul obținut este cost-optimal și are avantajul că folosește un număr mic și adaptiv de procesoare.
3.2 Algoritmi de sortare
Quicksort este cel mai rapid algoritm secvențial de sortare cunoscut. Este un algoritm de tipul divide – and – conquer care sortează o secvență de elemente prin divizarea recursivă a acesteia în două subsecvențe. Fie secvența de elemente memorată sub forma unui vector A[1…n]. În faza de divizare, o secvență A[q…r] este împărțită în două subsecvențe A[q…s] și A[s+1…r] astfel că fiecare element al primei subsecvențe este egal sau mai mic decât oricare element al celei de-a doua subsecvențe. În faza următoare subsecvențele sunt sortate prin apelul recursiv al acestei funcții de sortare.
Partiționarea unui vector de elemente în doi subvectori astfel încât toate elementele din primul vector să fie mai mici sau egale decât oricare element din cel de-al doilea vector se face prin selectarea unui element x (pivot) din vector. Elementele mai mici sau egale cu x sunt introduse în primul subvector, iar toate elementele mai mari dect x sunt introduse în cel de-al doilea subvector.
Algoritmul secvențial de sortare rapidă este prezentat în Programul 6.
Programul 6
Algoritmul secvențial de sortare rapidă
QUICKSORT(A, q, r)
{
if(q < r)
{
x = A[q]; s = q;
for(i = q + 1; i <= r; i++)
if(A[i] <= x)
{
s += 1;
swap(A[s], A[i]);
}
swap(A[q], A[s]);
QUICKSORT(A, q, s);
QUICKSORT(A, s+1, r);
}
}
Timpul de execuție cu valoarea cea mai redusă se obține dacă se poate împărți fiecare secvență de dimensiune k în două subsecvențe de dimensiune k/2. În acest caz timpul de execuție este dat de relația de recurență:
Ts (n) = 2*Ts(n / 2) + O(n),
a cărei soluție este:
Ts (n) = O(n * log n),
unde log n este logaritm în baza 2 din n.
În Fig. 3.2 este prezentat un exemplu de execuție a algoritmului Quicksort pentru un vector de n = 8 elemente: A={3, 2, 1, 5, 8, 4, 3, 7}.
pivot
Fig. 3.2 Execuția algoritmului Quicksort pentru n = 8 elemente
Un algoritm cost-optimal de sortare rapidă într-un model ARBITRARY CRCW-PRAM presupune execuția în paralel a partiționării vectorilor. În acest model conflictele de scriere în aceeași locație de memorie sunt rezolvate prin selecția arbitrară a unui singur procesor căruia i se permite scrierea, în timp ce toate celelalte operații de scriere sunt ignorate.
Algoritmul paralel de sortare rapidă începe cu construirea unui arbore binar în care nodul rădăcină este primul pivot. Elementele mai mici sau egale decât acest pivot sunt direcționate în subarborele din stânga, iar cele mai mari în subarborele din dreapta. Secvența sortată se obține prin parcurgerea în inordine a acestui arbore.
Algoritmul de construire a arborelui binar de partiționare a vectorului de date este prezentat în Programul 7.
Programul 7
Algoritmul CRCW-PRAM construire a arborelui binar de partiționare a vectorului de date
CONSTRUIRE_ARBORE
Condiții inițiale: Vectorul de sortat este memorat în A[n];
Procesorul Pi are asignat elementul A[i];
Vectorii left[n] și right[n] memorează fiii fiecărui pivot;
Variabila locală pi a fiecărui procesor memorează eticheta
procesorului care deține pivotul.
Rezultatul final: Arborele binar descris de vectorii left și right conține
Elementele sortate care pot fi regăsite printr-o traversare în
inordine a arborelui.
forall(1 <= i <= n)
{
root = i;
parenti = root;
left[i] = right[i] = n + 1;
while(i != root)
if((A[i] <= A[parenti]) && (i < parenti))
{
left[parenti] = i;
if(left[parenti] == i) exit;
else parenti = left[parenti];
}
else
{
right[parenti] = i;
if(right[parenti] == i) exit;
else parenti = right[parenti];
}
}
Algoritmul începe prin scrierea de către toate procesoarele Pi a etichetei i în variabila partajată root. Deoarece operația de scriere concurentă este arbitrară, numai una dintre toate etichetele este înscrisă în variabila root. Valoarea A[root] este folosită ca prim pivot de partiționare și eticheta root este copiată în variabila locală parenti a fiecarui procesor Pi. Procesoarele care au elementele mai mici decât A[parenti] înscriu eticheta proprie în left[parenti], iar cele care au elemente mai mari înscriu eticheta proprie în right[parenti]. Datorită scrierii concurente, numai două dintre valorile etichetelor procesoarelor care doresc să-și înscrie eticheta în vectorii left și right sunt scrise efectiv în locațiile corespunzătoare. Aceste două valori devin etichetele procesoarelor care dețin elementele pivot pentru iterația următoare. Algoritmul continuă până când au fost selectați n pivoți. Un procesor termină execuția atunci când elementul pe care îl deține devine pivot.
În timpul construcției arborelui, câte un nivel al arborelui de sortare este construit într-un timp în O(1). Înălțimea medie a arborelui este în O(log n). Rezultă timpul mediu de construire a arborelui binar în O(log n).
După construirea arborelui binar, algoritmul determină poziția fiecărui element în vectorul sortat. Pentru aceasta se traversează arborele. Fiecare element este amplasat în vectorul A într-un timp în O(1). Un algoritm de traversare în inordine a unui arbore binar pentru calculul poziției fiecărui element într-un model CRCW-PRAM se poate proiecta cu un timp de execuție în O(log n) [IONE99].
Rezultă că se poate obține un timp mediu de execuție pentru algoritmul de sortare rapidă în modelul ARBITRARY CRCW-PRAM Tp = O(log n), folosind n procesoare.
Accelerarea paralelă este:
S = Ts / Tp
sau
S = O(n),
unde:
Ts este timpul de execuție secvențială a algoritmului (Ts = O(n * log n));
Tp este timpul de execuție a algoritmului ARBITRARY CRCW-PRAM
folosind n procesoare (Tp = O(log n)).
Eficiența paralelă este:
E = S / p
sau
E = O(1),
unde:
S este accelerarea paralelă calculată mai sus;
p este numărul de procesoare utilizate (p = n).
Costul algoritmului CREW-PRAM folosind p procesoare este:
C = p * Tp
sau
C = O(n * log n),
unde mărimile p și Tp au fost explicate mai sus.
Costul suplimentar de calcul paralel este:
T0 = C – Ts
sau
T0 = n * log n – n * log n = 0,
unde:
C este costul paralel;
Ts este timpul de execuție secvențială.
Algoritmul de sortare în modelul ARBITRARY CRCW-PRAM este cost-optimal.
În [HUAN90] este descris un algoritm paralel de sortare utilizând n1/2 procesoare pentru sortarea a 2*n elemente. Pentru simplitate se consideră p = n1/2 = 2k procesoare. Algoritmul are două faze.
În prima fază, se asignează fiecărui procesor 2* n1/2 elemente. Fiecare procesor trebuie să sorteze datele asignate lui utilizând algoritmul secvențial optim de sortare – quicksort. La sfârșitul acestei faze vor fi p liste sortate.
În faza a doua, se interclasează recursiv două liste sortate pentru obținerea unei liste sortate mai mari până când se obține lista finală sortată, adică lista ce conține toate elementele inițiale sortate. Această fază este divizată în k pași, k = log p, log p fiind logaritm în baza 2 din p. La începutul celui de-al i – lea pas (i = 1, 2, … ,k), sunt 2k / 2i-1 liste sortate, fiecare cu dimensiunea 2k+i. Numărul de perechi de liste sortate “în așteptarea interclasării” în acest pas este (2k / 2i-1) /2, adică 2k / 2i. Cum sunt în total p = 2k procesoare, numărul de procesoare utilizate pentru interclasarea a fiecăror două liste este deci 2i. În fiecare pas, se interclasează concurent perechi de liste sortate utilizând procesoarele asociate fiecăror două liste sortate. La sfârșitul celor k pași de interclasare va exista o singură listă sortată, deci algoritmul este complet.
Se notează n(i) dimensiunea fiecărei liste ce urmează să fie sortată și p(i) numărul de procesoare utilizate pentru a interclasa două liste în pasul i. Atunci n(i) >= (p(i))2, pentru toți i. Demonstrație: n(i) = 2(k+i) >= 2i+i = (2i)2 = (p(i))2.
Timpul de execuție a primei faze este :
O(2 * n1/2 * log(2 * n1/2))
sau
O((n * log(n1/2)) / n1/2)
sau
O((n * log n) / p),
unde p este numărul de procesoare (p = n1/2 ).
Timpul de execuție a pasului i a fazei a doua este:
O( n(i) / p(i) )
sau
O( 2k+i / 2i )
sau
O( 2k)
sau
O( n/ p ).
Acest timp de execuție este același pentru toți pașii și este independent de pasul i. Sunt k = log p = log n1/2 = ½ * log n pași în faza a doua. Timpul total de execuție a fazei a doua este:
O((n/ p) * k)
sau
O((n * log n) / p).
Ambele faze au același timp de execuție, deci timpul total de execuție paralelă a algoritmului este:
Tp = O((n * log n) / p).
Accelerarea paralelă este:
S = Ts / Tp
sau
S = O(p),
unde:
Ts este timpul de execuție secvențială a algoritmului (Ts = O(n * log n));
Tp este timpul de execuție a algoritmului folosind n1/2 procesoare (Tp = O((n * log n) / p)).
Eficiența paralelă este:
E = S / p
sau
E = O(1),
unde:
S este accelerarea paralelă calculată mai sus;
p este numărul de procesoare utilizate (p = n1/2).
Costul algoritmului CREW-PRAM folosind p procesoare este:
C = p * Tp
sau
C = O(n * log n),
unde mărimile p și Tp au fost explicate mai sus.
Costul suplimentar de calcul paralel este:
T0 = C – Ts
sau
T0 = n * log n – n * log n = 0,
unde:
C este costul paralel;
Ts este timpul de execuție secvențială.
În [EVAN90] sunt prezentate două versiuni de program paralel de sortare pentru multiprocesoare puternic cuplate (tightly coupled multiprocessors). Pseudocodul pentru cele două versiuni este prezentat în ANEXA 1.
Stewart A. Levin [LEVI90] prezintă un algoritm de partiționare vectorizată pentru sortarea rapidă a unui șir de elemente – fully vectorized quicksort algorithm. Algoritmul a fost rulat pe calculatorul paralel Cray X-MP.
Algoritmi pentru colorarea grafurilor
Problema colorării grafurilor (graph coloring) este de a determina dacă
nodurile unui graf dat pot fi colorate cu un număr c de culori, astfel încât să nu existe două noduri adiacente cu aceeași culoare.
Pentru implementarea paralelă a problemei colorării grafului se pleacă de la ipoteza că, pentru un graf cu n noduri și un număr de c culori, trebuie să fie testate toate cele cn combinații posibile de colorare pentru a se afla dacă una sau mai multe din combinațiile posibile îndeplinește condiția dorită.
Cea mai fină granularitate de calcul se obține dacă se utilizează câte un procesor pentru fiecare posibilitate de colorare a grafului. De exemplu, procesorul p(v0, v1, … , vn-1) corespunde colorării nodului i cu culoarea v0, unde 0 <= vi < c. Pentru n noduri ale grafului și un număr c de culori se folosesc cn procesoare.
Pentru testarea unei combinații de colorare se folosește matricea de adiacență a grafului, A[n][n]. Dacă A[j][k] = 1 și vj = vk , această combinație de colorare este invalidă deoarece A[j][k] = 1 înseamnă că nodurile j și k sunt adiacente și vj = vk înseamnă că au aceeași culoare. Rezultatul testării unei combinații este 1, dacă acea combinație este admisibilă, sau 0 în caz contrar.
Pentru calculul numărului total de combinații admisibile se folosește un vector de dimensiune egală cu numărul de combinații totale cn. Fie b acest vector. Inițial fiecare procesor setează cu 1 valoarea corespunzătoare în vectorul b. Dacă un procesor detectează o combinație de colorare invalidă, acesta trece pe 0 elementul corespunzător în vectorul b. Numărul total de combinații admisibile de colorare se obține prin însumarea tuturor valorilor din vectorul b, printr-o operație de reducere paralelă în vectorul b de dimensiune cn.
În Programul 8 este prezentată implementarea algoritmului de colorare a unui graf într-un model CREW-PRAM.
Programul 8
Algoritm CREW-PRAM de colorare a unui graf
COLORARE_GRAF
Condiții inițiale: n numărul de noduri ale grafului;
c numărul de culori;
q = cn;
A[n][n] matricea de adiacență;
b[q] vectorul combinațiilor de colorare;
Rezultat final: b[q] conține posibilitățile valide de colorare;
Variabile globale: n, c, q, A[n][n], b[q]
forall(0 <= i < q)
{
b[i] = 1;
for(j = 0; j < n; j++)
for(k = 0; k < n; k++)
if(A[j][k] && (vj == vk))
b[i] = 0;
/* reducerea paralelă în vectorul b[q] */
for(j = 0; j < log q; j++)
if(i modulo 2j == 0)
b[2*i] += b[2*i + 2j];
}
Timpul de execuție paralelă este în O(n2).
În [ZORO90] este propusă o variantă euristică de coloare a unui graf. Algoritmul începe cu colorarea inițială a grafului (format din n noduri) și o schimbă până se obține o colorare validă sau este depășit numărul de iterații admis. Într-un pas, algoritmul schimbă culoarea cel mult unui nod. Nodul căruia trebuie să-i fie schimbată culoarea este ales între nodurile “rele” – acelea care au cel puțin un vecin colorat cu aceeași culoare. Este aleasă aleator o nouă culoare din setul de c culori utilizat ({1, 2, … ,c}). O colorare a grafului se reprezintă printr-un vector n – dimensional. Fie b acest vector.
Varianta secvențială este prezentată mai jos:
Step1: stabilire colorare inițială
Step2: while ((există un nod rău) && (nu este depășit numărul de pași))
{
2.1 alege nod rău
2.2 colorează nodul ales cu o culoare nouă
}
Step3: if(culoarea este bună)
then graful poate fi colorat cu c culori
else graful nu poate fi colorat cu c culori
În Step1 se generează aleator o colorare a grafului printr-o buclă:
for(i = 0; i <n; i++) b[i] = rand(c) + 1;
În Step2.1 se alege o nouă culoare. Probabilitatea de a alege culoarea i este proporțională cu funcția weight:
weight(i) = 4-S(i),
unde S(i) este numărul vecinilor nodului ales în pasul precedent, colorat cu culoarea i.
Pentru paralelizarea algoritmului s-a simulat o mașină virtuală cu următoarele proprietăți:
sunt suficiente procesoare disponibile(O(n));
fiecare procesor poate accesa memoria pentru scriere;
fiecare procesor poate citi orice locație de memorie;
Varianta paralelă a algoritmului este exprimată prin două procese. Pentru
fiecare nod al grafului se execută procesele:
Proces COLOR_NODE(v: node);
Step1: alege (aleator) colorarea inițială
signal(“gata”); wait
Step2: while (proces SUPRVISOR apare)
2.1 asignează o nouă culoare nodului (depinzând de culoarea nodurilor
vecinilor);
signal(“gata”); wait
/* noua culoare se alege similar algoritmului secvențial */
Proces SUPERVISOR:
Step1: așteaptă toate procesele COLOR_NODE
Step2: if ((există un nod rău) && (nu este depășit numărul de pași))
then signal(“continuă”) către toate procesele COLOR_NODE
else
if(culoarea este bună)
then graful poate fi colorat cu c culori
else graful nu poate fi colorat cu c culori
S-a demonstrat că varianta paralelă a algoritmului de colorare a unui graf găsește o colorare validă într-un pas indiferent de colorarea inițială a grafului.
Analiza performanțelor algoritmilor paraleli
Pentru analiza algoritmilor se folosesc în general trei tipuri de funcții:
funcția exponențială: f(x) = ax, unde x aparține mulțimii numerelor reale R și a > 1;
funcția polinomială: f(x) = xb, unde x aparține lui R și b > 0 (b este gradul polinomului);
funcția logaritmică: f(x) = logbx, unde x aparține lui R și b > 1 (b este baza logaritmului).
Cele mai multe funcții care sunt folosite pentru analiza algoritmilor se pot exprima ca sumă a două sau mai multe funcții.
O funcție f(x) domină o funcție g(x), dacă f(x) crește mai repede decât g(x), deci dacă raportul f(x)/g(x) este o funcție monoton crescătoare de x. Funcția exponențială domină funcția polinomială, iar funcția polinomială domină funcția logaritmică. Relația de dominanță este tranzitivă. Dacă funcția f domină funcția g și funcția g domină funcția h, atunci funcția f domină funcția h. Astfel, funcția exponențială domină funcția logaritmică.
Pentru analiza performanțelor algoritmilor, adică a modului cum crește timpul de execuție atunci când crește dimensiunea intrării, se utilizează limita asimptotică superioară, limita asimptotică inferioară și ordinul exact al funcțiilor.
O funcție g(x) este limita asimptotică superioară a funcției f(x) dacă există c din R+ și x0 din R astfel încât, pentru orice x ≥ x0, există relația f(x) ≤ c*g(x). Se spune că funcția f(x) este în ordinul lui g(x) și se notează f(x) = O(g(x)).
O funcție g(x) este limita asimptotică inferioară a funcției f(x) dacă există c din R+ și x0 din R astfel încât, pentru orice x ≥ x0, există relația f(x) ≥ c*g(x). Se notează f(x) = Ω(g(x)).
O funcție f(x) este în ordinul exact al funcției g(x) dacă există c1 și c2 din R+ și x0 din R astfel încât, pentru orice x ≥ x0, există relația c1*g(x) ≤ f(x) ≤ c2*g(x). Se notează f(x) = Ω(g(x)). Se notează f(x) = Θ(g(x)).
Din definițiile limitelor asimptotice ale funcțiilor rezultă că dacă f(x) = Ω(g(x)) și f(x) = O(g(x)), atunci f(x) = Θ(g(x)).
Timpul de execuție a unui algoritm secvențial se numește complexitate secvențială de timp (sequential time complexity), iar timpul de execuție a unui algoritm paralel se numește complexitate paralelă de timp (parallel time complexity). Complexitatea paralelă de timp trebuie să fie mai mică decât complexitatea secvențială de timp, cel puțin asimptotic.
Un algoritm are o complexitate de timp polinomială dacă există un polinom p(x), astfel încât complexitatea de timp a algoritmului este în O(p(x)), pentru orice dimensiune x a problemei. Mulțimea problemelor care au o complexitate polinomială este numită clasa P (P-class – polynomial class). Mulțimea problemelor rezolvabile prin algoritmi nedeterminiști în timp polinomial este numită clasa NP (NP-class – nondeterministic polynomial class). Sunt algoritmi pentru sortarea a n numere cu timp de execuție polinomial în O(n*logn), sau pentru înmulțirea a două matrice de dimensiune n*n cu timp de execuție polinomial în O(n3). Ambele tipuri de probleme aparțin clasei P. Algoritmii cunoscuți pentru problema comis-voiajorului (traveling salesperson), au timp de execuție exponențial în O(n2 2n). Nu au fost găsiți algoritmi determiniști polinomiali pentru această problemă, deci ea aparține clasei NP.
Clasa P este inclusă în clasa NP, deoarece algoritmii determiniști sunt un caz particular al algoritmilor nedeteminiști. Problemele din clasa P sunt rezolvabile cu calculatorul, în timp ce problemele din clasa NP – P sunt nerezolvabile. O problemă deschisă în știința calculatoarelor este dacă P = NP sau P ≠ NP (Fig. 3.3).
NP: clasa problemelor rezolvabile
prin algorimi nedeterminiști în
NP NPC timp polinomial;
P: clasa problemelor rezolvabile
prin algorimi determiniști în
P timp polinomial
NPC: clasa problemelor complet
nedeterministe
Fig. 3.3 Relațiile dintre clasele NP, P, NPC
Problemele din mulțimea NP – P sunt caracterizate prin timp de execuție exponențial. Clasa NPC (nondeterministic complete class) este clasa problemelor NP complete și are proprietățile:
NPC este inclusă în NP;
NPC ∩ P = Ø.
Cei mai mulți teoreticieni din domeniul științei calculatoarelor cred că P ≠ NP.
=== 7_transformare ===
4. Algoritm de transformare a prelucrărilor
secvențiale în prelucrări paralele
4.1 Dependențe de date, control și resurse
Pentru ca mai multe segmente de program (procese, thread-uri, instrucțiuni) să fie executate concurent este necesar ca fiecare segment să fie independent de toate celelalte segmente.
Pentru exprimarea relațiilor de dependență între unitățile unui program se folosește matricea de dependență a programului (program dependence matrix) sau un graf direcționat, numit graful de dependență al programului (program dependence graph). Liniile și coloanele matricei de dependență corespund segmentelor programului. Un element (i,j) al matricei este 0, dacă segmentele i și j sunt independente, sau 1, dacă execuția segmentului i depinde de execuția segmentului j. În cazul grafului de dependență, nodurile acestuia corespund segmentelor programului, iar arcele direcționate reprezintă relațiile de dependență între segmente.
În acest context, segmentele de program (procese, thread-uri, instrucțiuni) se vor numi task-uri (sarcini de lucru).
Dependențele existente în execuția task-urilor pot fi: dependențe de date, de control și de resurse.
Fiind date task-urile T1 și T2, unde T2 urmează lui T1 în succesiunea programului, dependențele de date între aceste task-uri sunt: dependența prin succesiune, antidependența, dependența prin ieșire, dependența necunoscută.
Task-ul T2 este dependent prin succesiune de task-ul T1, dacă cel puțin o variabilă actualizată de T1 este folosită ca variabilă de intrare de către T2. Dependența prin succesiune (flow dependence) se reprezintă astfel: T1 T2.
Task-ul T2 este antidependent de task-ul T1, dacă o ieșire a lui T2 actualizează o intrare a task-ului T1. T1 | T2 indică antidependența (antidependence) între T1 și T2.
Task-urile T1 și T2 prezintă dependență prin ieșire (output dependence) dacă ele actualizează aceeași variabilă de ieșire. Dependența prin ieșire se reprezintă astfel: T1 0 T2.
Relația de dependență între două task-uri nu poate fi determinată (unknown dependence) dacă ele partajează tablouri de variabile și:
indicele unei variabile dintr-un tablou este el însuși o variabilă indexată;
indicele unei variabile dintr-un tablou nu conține variabila de control a buclei de execuție;
variabilă este apelată de mai multe ori, cu indici care depind în mod diferit de variabila de control a buclei.
Exemplul 4.1
T1: Load R1, A / R1 Memorie(A) /
T2: Add R2, R1 / R2 (R1) + (R2) /
T3: Move R1, R3 / R1 (R3) /
T4: Store B, R1 / Memorie(B) (R1) /
Fig. 4.1 prezintă dependența de date între task-uri pe baza matricei de dependență:
Fig. 4.1 Dependențe de date între task-uri pe baza matricei de dependență
T2 reprezintă o dependență prin succesiune față de T1, deoarece registrul R1 este actualizat de T1, iar T2 folosește ca intrare acest registru. T3 este antiindependent față de T2 datorită registrului R1. T3 este dependent prin ieșire față de T1, deoarece ambele instrucțiuni modifică registrul R1. T2 și T4 sunt independente. Fig. 4.2 prezintă dependența de date între task-uri pe baza grafului de dependență:
T1
T2 T4
T3
Fig. 4.2 Dependențe de date între task-uri pe baza grafului de dependență
Dependențele de control se referă la situațiile în care ordinea de execuție a task-urilor nu poate fi determinată înainte de execuția programului (run-time). De exemplu, instrucțiunea condițională (IF) nu poate fi rezolvată decât în timpul execuției. Sunt cazuri când nu există dependențe între operațiile executate în iterațiile unei bucle. În Exemplul 4.2, iterațiile succesive ale buclei sunt independente din punct de vedere al controlului.
Exemplul 4.2
Independența din punct de vedere al controlului
for( i = 0; i < n; i++)
{
a[i] = b[i];
if( a[i] < 0 ) a[i] = 1;
}
În Exemplul 4.3, iterațiile succesive ale buclei sunt dependente din punct de vedere al controlului. În acest exemplu, fiecare iterație a buclei de execuție depinde de execuția iterației precedente.
Exemplul 4.3
Dependența din punct de vedere al controlului
for( i = 1; i < n; i++)
{
if( a[i – 1] == 0 ) a[i] = 0;
}
Dependența de control inhibă paralelismul segmentelor de cod respective.
Dependențele de resurse se referă la conflictele de utilizare a unor resurse partajate de către mai multe task-uri executate concurent. Exemple de astfel de resurse sunt: registre, zone de memorie, unități de prelucrare numere întregi sau numere flotante. Dacă dependențele se referă la zone de memorie, astfel de conflicte se pot rezolva dacă fiecare task accesează locații de memorie diferite, sau prin serializarea acceselor la memorie folosind mecanisme de sincronizare, cum sunt semafoarele.
Condițiile de paralelism ale lui Bernstein
Bernstein a sintetizat un număr de condiții necesare pentru ca două task-uri să poată fi executate în paralel [IONE99].
Fie Ii mulțimea variabilelor de intrare ale unui task Ti și Oi mulțimea variabilelor de ieșire ale aceluiași task. Variabilele de intrare sunt operanzii extrași din registre sau memorie, iar variabilele de ieșire sunt datele rezultatele care vor fi înscrise în registre sau locații de memorie. Se consideră două task-uri T1 și T2, cu mulțimile variabilelor de intrare I1 și I2 respectiv, și mulțimile variabilelor de ieșire O1 și O2. Aceste două task-uri pot fi execuatate în paralel și se notează T1 || T2, dacă sunt independente, deci nu prezintă nici un conflict în execuție.
Condițiile de execuție paralelă pot fi scrise astfel:
I1 O2 = Ø
I2 O1 = Ø
O1 O2 = Ø.
Aceste condiții se numesc condițiile lui Bernstein. Mulțimea Ii se mai numește domeniul task-ului Ti, iar mulțimea Oi codomeniul (rangul) acestuia. Condițiile lui Bernstein implică faptul că două procese pot fi executate în paralel dacă sunt independente ca succesiune, antiindependente și independente la ieșire.
Execuția paralelă a două task-uri produce același rezultat, indiferent dacă sunt executate secvențial sau în paralel. Acest lucru este posibil numai dacă nici o ieșire a unui task nu este intrare a celuilalt și ele nu scriu (nu modifică) aceleași variabile, în registre sau memorie.
În general, o mulțime de task-uri T1, T2, … , Tk , pot fi executate în paralel dacă condițiile lui Bernstein sunt satisfăcute pentru fiecare pereche de task-uri, adică: T1 || T2 || T3 || …|| Tk , dacă și numai dacă Ti || Tj, pentru orice i diferit de j.
Relația de paralelism este comutativă, adică T1 || T2 implică T2 || T1, dar nu este tranzitivă, adică Ti || Tj și Tj || Tk , nu garantează Ti || Tk . Relația de paralelism este asociativă, adică T1 || (T2 || T3 ) este echivalentă cu ( T1 || T2 ) || T3 pentru că ordinea în care sunt executate task-urile nu introduce diferențe în rezultatul obținut (variabilele de ieșire).
Nerespectarea oricăreia din condițiile lui Bernstein inhibă paralelismul între două task-uri. Pentru n task-uri, nerespectarea uneia sau mai multora din cele 3n(n-1) condiții, inhibă total sau parțial paralelismul între acestea.
Secțiunile de program care depind de condiții din timpul rulării (run-time), ca de exemplu salturile condiționale sau instrucțiunea IF…ELSE, nu pot fi transformate într-o formă paralelă. Dependența de date, de control sau de resurse inhibă execuția paralelă a task-urilor.
Scopul analizei dependențelor între task-urile componente ale unui program este de a identifica posibilitățile de paralelizare a programului. Prin paralelizarea unui program secvențial se înțelege transformarea acestuia într-o formă executabilă în paralel. Paralelizarea unui program secvențial este realizată manual, de către programator, și se numește paralelizare explicită, sau automat, de către compilator, numindu-se paralelizare implicită.
Paralelismul este exploatat la diferite nivele de procesare. În Fig. 4.3, patru nivele de execuție concurentă a programelor prezintă diferite granularități de calcul. Execuția unui program implică o combinație între aceste nivele în funcție de aplicație, algoritm, limbaj de programare și resurse hardware.
Paralelism la nivel de program
Granularitate
mare
Paralelism la nivel de proces
Creșterea Granularitate gradului
medie de
Paralelism la nivel de thread paralelism
Paralelism la nivel de instrucțiune Granularitate
fină
Fig. 4.3 Nivelele de paralelism în execuția programelor
Cu cât granularitatea este mai mică, cu atât gradul de paralelism este mai mare și cerințele de comunicație între unitățile de calcul sunt mai mari.
Paralelismul la nivel de instrucțiune este nivelul de paralelism cu granularitatea cea mai fină, cu dimensiunea tipică a granulei mai mică decât 20 instrucțiuni mașină. Avantajul acestui nivel este gradul ridicat de paralelism. Se bazează pe utilizarea variabilelor partajate și este folosit în arhitecturile cu spațiu de adresă unic al memoriei. Exploatarea paralelismului la nivel de instrucțiune este asistată de un compilator cu paralelizare, care este capabil să detecteze automat paralelismul algoritmului și să translateze codul sursă în cod paralel, recunoscut și executat astfel de către sistemul de operare.
Algoritm de transformare bazat pe matricea de dependență
Analiza la nivel de instrucțiune oferă avantajul unui înalt grad de paralelism. Transformarea bazată pe matricea de dependență folosește avantajul acestui nivel de paralelizare.
Matricea de dependență este o matrice pătratică booleană inferior triunghiulară în care liniile și coloanele reprezintă instrucțiunile programului secvențial ce urmează a fi paralelizat. Intersecția liniei i cu coloana j este 0 sau 1, după cum instrucțiunea Ii este independentă, respectiv depinde de instrucțiunea Ij. Diagonala principală a matricei nu are semnificație din punct de vedere al dependenței între instrucțiuni, deoarece o instrucțiune nu depinde de ea însăși. În Fig. 4.4 este prezentat un exemplu de matrice de dependență.
Fig. 4.4 Exemplu de matrice de dependență între instrucțiuni
Matricea de dependență între instrucțiuni se realizează pe baza unei alte matrice pătratice booleene: matricea de dependență instrucțiuni – operanzi. Programul secvențial ce urmează a fi paralelizat este alcătuit dintr-o suscesiune de instrucțiuni. Operanzii sunt variabile (adrese logice de memorie) declarate de programator și care sunt folosite de aceste instrucțiuni. Sunt instrucțiuni care folosesc unul sau mai mulți operanzi, după cum sunt și instrucțiuni care nu folosesc nici un operand. Intersecția liniei i cu coloana j este 0 sau 1, după cum instrucțiunea Ii este independentă, respectiv depinde de operandul Oj. În Exemplul 4.4 este prezentat un program C++ secvențial.
Exemplul 4.4
Program C++ secvențial
//directive preprocesor
#include “iostream.h”
#include “conio.h”
void main(void)
{
clrscr(); // I1
//declarare variabile
int a; // O1
int b; // O2
int c; // O3
int d; // O4
float e; // O5
//citire date de intrare
cout<<“Numărul a: “; // I2
cin>>a; // I3
cout<<“Numărul b: “; // I4
cin>>b; // I5
cout<<“Numărul c: “; // I6
cin>>c; // I7
cout<<“Numărul d: “; // I8
cin>>d; // I9
a = b++; // I10
c = d – b; // I11
d–; // I12
e = (a + b) * c / (d + c); // I13
//afișare rezultate
cout<<”Numărul e este: “<<e; // I14
getch(); // I15
}
Fig. 4.5 prezintă matricea de dependență instrucțiuni – operanzi a programului C++ secvențial anterior.
Fig. 4.5 Matricea de dependență instrucțiuni – operanzi
Pe baza matricei de dependență instrucțiuni – operanzi se realizează matricea de dependență între instrucțiuni. Acest lucru se realizează în doi pași:
Pas1: pentru fiecare coloană a matricei de dependență instrucțiuni – operanzi
se identifică elementele egale cu 1 și se memorează poziția lor într-un
vector;
Pas2: pentru toate elementele din vectorul creat anterior, și care reprezintă
coloane în matricea de dependență între instrucțiuni (care inițializează
fiecare element cu 0), se parcurg elementele următoare din vector care
vor reprezenta liniile în matrice; la intersecția liniilor cu coloanele se
pune 1;
Pașii 1 și 2 se repetă pentru toate coloanele matricei de dependență instrucțiuni – operanzi.
Algoritmul pentru realizarea matricei de dependență între instrucțiuni este prezentat mai jos, în pseudocod:
pentru orice indice j, 0 <= j < nr_de_operanzi
{
// Pas1
pentru orice indice i, 0 <= i < nr_de_instrucțiuni_executabile
dacă elementul (i, j) al matricei de dependență
instrucțiuni–operanzi este 1
{
se memorează indicele i într-un vector temporar
}
// Sfârșit Pas1
//–––––––––––––––––––––––––––
// Pas2
pentru orice indice i, 0 <= i < (nr_de_ elemente_vector_temporar) – 1
pentru orice indice t, i <= t < nr_de_elemente_vector_temporar
elementul (elementul t al vectorului temporar, elementul i al
vectorului temporar) al
matricei de dependență între instrucțiuni = 1
// Sfârșit Pas2
//–––––––––––––––––––––––––––
}
Pașii 1 și 2 se repetă pentru toate coloanele matricei de dependență instrucțiuni – operanzi.
Matricea de dependență între instrucțiuni este o matrice inferior triunghiulară, acest lucru rezultă din algoritm prin faptul că, în pasul 2, se parcurg, pentru un element al vectorului temporar, toate celelalte elemente care-l urmează pe acesta.
În Fig. 4.6 este prezentată matricea de dependență dintre instrucțiuni realizată pe baza matricei instrucțiuni – operanzi.
Fig. 4.6 Matricea de dependență între instrucțiuni
Paralelizarea programului secvențial se face pe baza matricei de dependență între instrucțiuni. Algoritmul de paralelizare are ca scop realizarea unor secvențe de instrucțiuni (clustere de instrucțiuni), fiecare dintre aceste secvențe fiind formată din instrucțiuni care se execută în paralel. Trecerea de la secvența k la secvența k+1 se face atunci când cele mai rapide instrucțiuni ale secvenței k ce influențează execuția unor instrucțiuni ale secvenței k+1 își termină execuția. Fiecare secvență de instrucțiuni reprezintă un nivel de paralelizare. Algoritmul de paralelizare lucrează prin compararea permanentă a două niveluri consecutive.
Algoritmul se realizează în doi pași:
Pas1: pe primul nivel se trec prima instrucțiune a programului și acele
instrucțiuni care nu depind de aceasta; pe nivelul următor se trec toate
instrucțiunile care depind de prima instrucțiune a programului;
instrucțiunile se preiau din matricea dependență între instrucțiuni;
Pas2: pe un nivel k+1 se trec toate instrucțiunile care depind de instrucțiunile
de pe nivelul k; dacă o astfel de instrucțiune se regăsește pe un nivel
anterior nivelului k+1, ea va fi eliminată de pe acel nivel;
Pasul 2 se repetă până când se ajunge la nivelul frunză – ultimul nivel ce conține instrucțiuni care nu mai influențează execuția altor instrucțiuni.
Rezultatul execuției algoritmului de paralelizare este o succesiune de secvențe: S1,S2, … , Sm, unde Sm este nivelul frunză.
Pentru programul C++ secvențial de Exemplul 4.4, execuția algoritmului este:
Pas1:
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I10, I11, I12, I13, I14, I15
S2:
// de I1 nu depinde nici o instrucțiune
Pas2:
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I10, I11, I12, I13, I14, I15
S2: I10, I13, I11, I12
–––––––––––––––––––––
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I14, I15
S2: I10, I13, I11, I12
S3: I11, I13
–––––––––––––––––––––
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I14, I15
S2: I10, I12
S3: I11, I13
S4: I12, I13
–––––––––––––––––––––
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I14, I15
S2: I10
S3: I11
S4: I12, I13
S5: I13
–––––––––––––––––––––
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I14, I15
S2: I10
S3: I11
S4: I12
S5: I13
S6: I14
–––––––––––––––––––––
S1: I1, I2, I3, I4, I5, I6, I7, I8, I9, I15
S2: I10
S3: I11
S4: I12
S5: I13
S6: I14
Aceasta din urmă este configurația finală se secvențe. S6 este nivelul frunză.
Algoritmul e paralelizare este prezentat mai jos, în pseudocod:
// Pas1:
// pe primul nivel se pun I1 si instructiunile care nu depind de I1;
// memorarea configurației de secvențe se face cu ajutorul unei matrice în care
// liniile reprezintă nivelele de paralelizare; elementele matricei sunt
// instrucțiuni;
primul element al noii matrice este I1
pentru orice indice i, 1<= i < nr_de_instrucțiuni_executabile
dacă elementul (i, 0) al matricei de dependență între instrucțiuni este 0
{
se memorează indicele i într-o matrice, pe prima linie
}
se trece la următorul nivel
// Sfârșit Pas1
//–––––––––––––––––––––––––––––––
//se lucreaza permanent pe doua niveluri consecutive
pentru orice indice i, 1<= i < nr_de_instrucțiuni_executabile
dacă elementul (i, 0) al matricei de dependență între instrucțiuni este 0
{
se memorează indicele i într-o matrice, pe prima linie
}
atât timp cât nu este nod frunză
// Pas2:
// un nivel oarecare
{
pentru orice indice i, 0<= i < nr_de_instrucțiuni_de_pe_nivelul_anterior
{
se selectează instrucțiunea corespunzătoare indicelui;
pentru orice indice j, 0<= j < nr_de_instrucțiuni_executabile
dacă elementul (j+1, instrucțiunea curentă) al matricei de
dependență între instrucțiuni nu este 0
{
dacă (instrucțiunea curentă nu este deja pe nivelul curent)
se memorează instrucțiunea curentă pe nivelul curent;
dacă (instrucțiunea curentă se găsește pe un nivel anterior)
se elimină instrucțiunea curentă de pe acel nivel;
}
}
dacă (nivelul curent este frunză) atunci
se trece la nivelul următor
// Sfârșit Pas2
}
Pasul 2 se repetă până când se atinge nivelul frunză – acel nivel ce conține instrucțiuni care nu mai influențează execuția altor instrucțiuni. Algoritmul realizat în Visual C++ este prezentat în ANEXA 3.
Programele secvențiale conțin instrucțiuni de control care nu pot fi paralelizate. De exemplu, instrucțiunea IF nu se poate evalua decât la momentul execuției (run – time). Matricea de dependență între instrucțiuni trebuie rafinată ținând cont de dependențele de control. În Exemplul 4.5 este prezentat un segment de cod ce conține dependențe de control.
Exemplul 4.5
if(a+b > c) // I1
{
a++; // I2
c = b – a; // I3
cout << c; // I4
d++; // I5
}
else // I6
{
a–; // I7
b = c + a; // I8
cout << b; // I9
d–; // I10
}
Într-o analiză standard, ținând cont doar de dependențele de date, instrucțiunile I5 și I10 apar ca fiind independente de I1 și deci se execută în paralel cu I1. Din punct de vedere al controlului, I5 și I10 nu se execută decât după testarea condiției din instrucțiunea IF. Rafinarea matricei de dependență între instrucțiuni ține cont de acest aspect. O instrucțiune IF va influența execuția blocului aferent ei, indiferent de dependențele de date. Pe ramura ELSE, din punct de vedere doar al dependenței de date, instrucțiunile I7, I8, I9, I10 nu depind de ea. Aceste instrucțiuni depind de evaluarea condiției logice din IF, deci dependență de control.
O problemă în paralelizare o reprezintă buclele (loops). Există cazuri de independență din punct de vedere al controlului în cadrul buclelor (Exemplul 4.2). Paralelizarea unei astfel de structuri repetitive se face prin vectorizare. Exemplul 4.2 vectorizat apare astfel:
A[0…n-1] = B[0…n-1];
if(A[0…n-1] < 1[0…n-1]) A[0…n-1] = 1[0…n-1],
unde: A[0…n-1] = a(i), B[0…n-1] = b(i), 1[0…n-1] = 1(i) =1, 0 <= i < n.
Sunt situații când instrucțiuni din cadrul buclelor nu depind de variabila de ciclare ca în Exemplul 4.6.
Exemplul 4.6
for(i = 0, c = constanta; i < n; i++)
{
a[i] = b[i];
c++; // nu depinde de i
}
Acest exemplu este vectorizat astfel:
A[0…n-1] = B[0…n-1];
C[0…n-1],
unde:
A[0…n-1] = a(i),
B[0…n-1] = b(i),
C[0…n-1] = c(i), c(0) = constanta+1, c(i) = c(i-1)+1, 0 <= i < n.
Există cazuri de dependență din punct de vedere al controlului în cadrul buclelor (Exemplul 4.3). Exemplul 4.3 vectorizat apare astfel:
if(A[0…n-2] == 0[0…n-2]) A[1…n-1] = 0[1…n-1],
unde:
A[0…n-1] = a(i), 0[0…n-1] = 0(i) = 0, 0 <= i < n.
Vectorizarea are avantajul că variabila de ciclare nu intervine în analiza dependențelor de date între instrucțiuni. Pot fi vectorizate doar buclele for simple. Problema se complică în cazul existenței mai multor bucle imbricate. Analiza dependenței iterațiilor unor astfel de bucle, în care sunt utilizați indici multidimensionali, trebuie să determine dacă există dependențe între două referințe indexate ale aceluiași tablou. Analiza completă și exactă a dependenței iterațiilor, pentru cazul general de bucle pe un număr oarecare de niveluri, este rar executată în practică, datorită cerințelor de calcul deosebit de mari, căutându-se soluții aproximative și eficiente pentru anumite situații particulare prin teste de dependență a iterațiilor. Testele de dependență permit determinarea dependenței între două referințe la același tablou într-o buclă imbricată.
În Exemplul 4.7 este prezentat un model de bucle imbricate pe n niveluri, fiecare nivel fiind reprezentat printr-un indice (variabila de control a buclei):
Exemplul 4.7
for(i1 = L1; i1 <= U1; i1++)
for(i2 = L2; i2 <= U2; i2++)
……………..
for(in = Ln; in <= Un; in++)
{
x[f1(i1,…,in)]…[ fm(i1,…,in)] = … // S1
… = x[g1(i1,…,in)]…[ gm(i1,…,in)]; // S2
}
Testele de dependență trebuie să determine dacă există o dependență între instrucțiunile S1 și S2 în aceste bucle de program.
Spațiul Cartezian n – dimensional discret pentru n bucle imbricate se numește spațiul iterațiilor. O iterație este reprezentată ca o coordonată în spațiul iterațiilor. Ordinea lexicografică în spațiul iterațiilor este dată de ordinea de execuție a iterațiilor. În Exemplul 4.8 este clarificată noțiunea de ordine lexicografică în spațiul stărilor.
Exemplul 4.8
for(i = 0; i < 6; i++)
for(j = i; j < 8; j++)
x[i, j] = ……
Următoarea ordine a iterațiilor este o ordine lexicografică:
(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7)
(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7)
(2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7)
(3, 3), (3, 4), (3, 5), (3, 6), (3, 7)
(4, 4), (4, 5), (4, 6), (4, 7)
(5, 5), (5, 6), (5, 7)
Fie α și β doi vectori de n indici întregi cuprinși între rangul inferior și superior al fiecăreia din cele n bucle. Există o dependență de la S1 la S2 dacă și numai dacă există α și β astfel încât α este lexicografic mai mic sau egal cu β și este satisfăcut următorul sistem de ecuații de dependență:
fi(α) = gi(β) pentru orice i, 1 ≤ i ≤ m (*)
Altfel cele două referințe sunt independente. Ecuațiile de dependență (*) sunt expresii liniare de variabilele de indici ai buclelor. Astfel, testele de dependență sunt echivalente problemei ecuațiilor liniare Diophantine, care este o problemă NP – completă. Testele exacte de dependență sunt acele teste care detectează dependențele dacă și numai dacă ele există. În practică nu se execută testele exacte, datorită calculelor excesive implicate pentru adâncimi mari de imbricare a buclelor. În schimb, se caută soluții aproximative, dar cu implementare eficientă, care presupun că orice dependență există, dar ea nu este infirmată. Astfel de teste aproximative nu depistează toate situațiile de independență a buclelor, dar le detectează pe majoritatea dintre ele, iar caracterul conservativ (presupunerea că orice dependență există dacă nu se dovedește contrariul) al acestor teste asigură corectitudinea operațiilor de paralelizare bazate pe condiția de independență a buclelor.
Dacă există o dependență pentru vectorii α și β, atunci vectorul distanță D = (D1,…,Dn) este definit ca β – α, iar vectorul direcție d = (d1,…,dn) al dependenței are următoarele componente:
< dacă α i < βi
di = = dacă α i = βi
> dacă α i > βi
Elementele acestor vectori sunt prezentate întotdeauna de la stânga la dreapta începând de la bucla exterioară către bucla interioară. Pentru bucla imbricată din Exemplul 4.9 sunt calculați vectorii distanță și direcție.
Exemplul 4.9
for(i = L1; i <= U1; i++)
for(j = L2; j <= U2; j++)
for(k = L3; k <= U3; k++)
x[i + 1][j][k – 1] = x[i][j][k] + y;
Vectorii distanță și direcție pentru dependența între iterațiile care acesează tabloul tridimensional x sunt D = (1, 0, -1) și d = (<, =, >).
Vectorii direcție se utilizează pentru determinarea nivelului buclei care poartă dependențe de date (loop – carried dependence). O dependență este purtată de nivelul cel mai exterior al buclei imbricate care nu are “=” în poziția corespunzătoare din vectorul direcție. Dacă o componentă a vectorului direcție este “=”, atunci cele două referințe la tablou se fac în aceeași iterație, pot să existe referințe între cele două referințe, dar acestea sunt dependențe în interiorul iterației, nu între două iterații diferite. De exemplu, vectorul direcție (<, =, >) arată că bucla exterioară i poartă dependențe între iterații. Buclele care poartă dependențe de date nu pot fi paralelizate fără sincronizare. Dependențele purtate de diferite bucle sunt importante și în determinarea posibilității și oportunității de interschimb a buclelor între ele. Vectorii distanță sunt versiuni mai precise ale vectorilor direcție, deoarece specifică și distanța între iterațiile buclelor între două accese la același element al tabloului.
Indicatori ai gradului de paralelizare
Paralelizarea unui program secvențial presupune transformarea acestuia într-un program paralel. Programele secvențiale nu pot fi paralelizate integral datorită dependențelor de control care inhibă paralelismul.
Indicatorii gradului de paralelizare reprezintă măsuri ale paralelismului programelor secvențiale. Aceștia sunt absoluți și relativi. Indicatori absoluți sunt: numărul de instrucțiuni ce pot fi paralelizate, numărul de instrucțiuni ce nu pot fi paralelizate, numărul de secvențe de instrucțiuni paralele. Indicatori relativi sunt: indicele de paralelizare, coeficientul de secvențialitate.
Numărul de instrucțiuni ce pot fi paralelizate (Npar) reprezintă acele instrucțiuni ale programului secvențial care se execută în paralel.
Numărul de instrucțiuni ce nu pot fi paralelizate (Nnpar) reprezintă instrucțiunile de control ce nu se execută în paralel (de exemplu: if, while).
Npar + Nnpar = N,
unde N este numărul de instrucțiuni ale programului secvențial.
Numărul de secvențe de instrucțiuni paralele (Spar) reprezintă numărul de clustere de instrucțiuni ce conțin instrucțiuni ce pot fi paralelizate.
Indicele de paralelizare Ip are expresia:
Ip = Spar / Npar ,
unde:
Spar reprezintă numărul de secvențe de instrucțiuni paralele;
Npar este numărul de instrucțiuni ce pot fi paralelizate.
Ip aparține intervalului [1/ Npar , 1].
Ip este 1/ Npar dacă există un singur cluster de instrucțiuni paralele. Acest lucru provine din faptul că programul secvențial este alcătuit din instrucțiuni total independente între ele. Acesta este un caz ideal, în realitate între instrucțiuni există dependențe de date și control care inhibă paralelismul.
Ip este 1 atunci când numărul de clustere de instrucțiuni paralele este egal cu numărul de instrucțiuni ce pot fi paralelizate, adică fiecare cluster conține o singură instrucțiune. Acesta este rezultatul unei puternice dependențe între instrucțiuni. În acest caz nu este nevoie de execuție pe mai multe procesoare pentru că trecerea la o instrucțiune k nu se face fără terminarea execuției instrucțiunii k -1.
O valoare mică a indicelui Ip indică un grad mare de paralelizare a programului secvențial.
Coeficientul de secvențialitate (Csec) are expresia:
Csec = (Nnpar / Npar ) *100,
unde:
Nnpar reprezintă numărul de instrucțiuni ce nu pot fi paralelizate;
Npar reprezintă numărul de instrucțiuni ce pot fi paralelizate.
Csec aparține intervalului [0, Nnpar]. Extremele intervalului sunt cazuri ideale: Csec este 0 atunci când programul secvențial este paralelizat integral și Csec este Nnpar când programul secvențial conține numai instrucțiuni ce nu pot fi paralelizate. O valoare a lui Csec sub 50% indică un grad bun de paralelizare.
Pentru programul C++ secvențial din Exemplul 4.4, indicatorii gradului de paralelizare au valorile:
numărul de instrucțiuni ce pot fi paralelizate:
Npar = 15
numărul de instrucțiuni ce nu pot fi paralelizate:
Nnpar = 0
numărul de secvențe de instrucțiuni paralele:
Spar = 6
indicele de paralelizare:
Ip = Spar / Npar
sau
Ip = 6 / 15
sau
Ip = 0.4
coeficientul de secvențialitate:
Csec = (Nnpar / Npar ) *100
sau
Csec = 0.
Valoarea Ip = 0.4 indică un grad bun de paralelizare a programului secvențial. Csec = 0 indică faptul că programul C++ secvențial este paralelizat integral. Acesta este un caz ideal, în realitate programele conțin instrucțiuni de control care inhibă paralelismul.
=== 8_MParalel ===
5. Software pentru maxim paralelism
5.1 Descrierea aplicației MParalel
Aplicația MParalel are ca scop transformarea unui fișier sursă C/CPP secvențial în fișier paralel ce urmează să fie executat pe un sistem de calcul multiprocesor; în acest sens, aplicația citește fișiere C/CPP secvențiale, le analizează sintactic, identifică operanzii și instrucțiunile, iar pe baza dependențelor dintre instrucțiuni realizează transformarea fișierelor secvențiale în fișiere paralele.
În Fig. 5.1 este descrisă schema de funcționare a aplicației MParalel:
Fișier sursă C/CPP I/ Aplicația /O Fișier
secvențial MParalel paralel
Fig. 5.1 Schema de funcționare a aplicației MParalel
MParalel primește la intrare un fișier sursă C/CPP secvențial și are ca rezultat versiunea paralelă a acestuia.
Aplicația MParalel a fost realizată utilizând produsul Microsoft Visual C++ 6.0 și mediul de dezvoltare Microsoft Developer Studio, folosind facilitatea AppWizard de creare a proiectelor. MParalel este un proiect bazat pe casete de dialog (dialog box). Aplicația este orientată obiect.
Clasele folosite sunt împărțite astfel:
clasa aplicație – CMParalelApp – definește aplicația ca obiect Windows;
clase GUI (Graphical User Interface) – CMParalelDlg, CInfDlg, CAboutDlg, CAfisareDLG, CDependenteDlg, CMarire, CParDlg, CGrafic, CIndicatori, CExplicatii – sunt responsabile de gestionarea obiectelor grafice (ex: dialog-uri utilizator, controale de tip pushbutton, controale de editare);
clase algoritm – Analizor, CParDlg – implementează algoritmii necesari aplicației.
Ierarhia de clase a aplicației este prezentată în Fig. 5.2:
Aplicația MParalel
Clasa aplicație Clase GUI Clase algoritm
CMParalelApp
Analizor CParDlg
CAboutDlg CAfisareDLG CMarire CIndicatori
CGrafic
CMParalelDlg CInfDlg CDependenteDlg CParDlg Explicatii
Fig. 5.2 Ierarhia de clase a aplicației MParalel
Clasa CMParalelDlg (derivată public din clasa CDialog) este responsabilă de afișarea controlului de tip dialog cu id-ul IDD_MPARALEL_DIALOG. Este fereastra care apare la lansarea aplicației în execuție (Fig. 5.3).
Fig. 5.3 Fereastra care apare la lansarea în execuție a aplicației
Controlul de tip button cu caption-ul “Citește fișier sursă C/CPP” din aceasta fereastra permite afișarea dialog-ului cu id-ul IDD_DIALOG_CITIRE. Controlul de tip button cu caption-ul “Informații” permite afișarea unei ferestre cu informații despre aplicație, fereastră gestionată de clasa CInfDlg (Fig. 5.4).
Fig. 5.4 Fereastra de informații a aplicației
Clasa CAfisareDLG (derivată public din clasa CDialog) este responsabilă de gestionarea casetei de dialog cu id-ul IDD_DIALOG_CITIRE (Fig. 5.5).
Fig. 5.5 Fereastra cu rezultatele analizei fișirului sursa C/CPP secvențial
Această fereastră conține mai multe controale de editare și de tip button.
Controalele de editare sunt folosite pentru:
afișarea conținutului fișierului sursă C/CPP;
afișarea tuturor instrucțiunilor și a tipului acestora;
afișarea declarărilor de variabile din programul sursă;
listarea operanzilor;
afișarea instrucțiunilor executabile și a operanzilor utilizați de fiecare dintre acestea.
Controalele de tip button care apar aici sunt utilizate astfel:
utilizarea controlul cu caption-ul “Analiză fișier sursă secvențial” are ca efect afișările de mai sus în controalele de editare;
controlul cu caption-ul “Analiza dependențelor” permite afișarea dialogului cu id-ul IDD_DIALOG_DEPENDENTE.
Clasa CDependenteDlg (derivată public din clasa CDialog) este responsabilă de gestionarea casetei de dialog cu id-ul IDD_DIALOG_DEPENDENTE. Această fereastră permite vizualizarea matricei de dependențe instrucțiuni – operanzi și a matricei de dependențe între instrucțiuni (Fig. 5.6). Pentru vizualizare sunt folosite controale de editare.
Fig. 5.6 Vizualizarea matricelor de dependență
Clasa CParDlg (derivată public din clasa CDialog) gestionează caseta de dialog cu id-ul IDD_DIALOG_PARALELIZARE. Aici este implementat algoritmul de paralelizare a programelor sursă secvențiale C/CPP (Fig. 5.7).
Fig. 5.7 Fereastra de vizualizare a rezultatelor algoritmului de paralelizare
Clasa CIndicatori (derivată public din clasa CDialog) gestionează dialogul cu id-ul IDD_DIALOG_INDICATORI. Sunt calculați indicatori ai gradului de paralelizare, iar valorile obținute sunt afișate în această fereastră (Fig. 5.8).
Fig. 5.8 Fereastra de vizualizare a indicatorilor
Clasa CGrafic (derivată public din clasa CDialog) este utilizată pentru vizualizarea graficului execuției instrucțiunilor.
Clasa CExplicatii (derivată public din clasa CDialog) este responsabilă de afișarea dialogului cu id-ul IDD_DIALOG_EXPLICATII. Este o casetă de dialog inactivă, rolul ei fiind de a descrie indicatorii folosiți pentru analiza gradului de paralelizare (Fig. 5.9).
Fig. 5.9 Fereastra de descriere a indicatorilor
Clasa Analizor (clasa generică) este responsabilă de analiza sintactică a fișierului sursă C/CPP secvențial. În acest sens, clasa conține metode pentru identificarea instrucțiunilor programului sursă, a tipului acestora, a operanzilor folosiți. Tot aici este realizată matricea de dependență dintre instrucțiuni.
5.2 Structurile de date folosite
Aplicația MParalel este orientată obiect, de aceea structura de date cea mai des utilizată este clasa. Clasele utilizate au la bază clasele MFC (Microsoft Foundation Classes) din Visual C++ 6.0. Clasa Analizor este singura excepție, fiind o clasă generică (nu este derivată din nici o clasă MFC). De exemplu, clasa CMParalelApp este derivată public din clasa MFC CWinApp:
class CMParalelApp : public CWinApp {// …}; ,
clasa CMParalelDlg este derivată din clasa MFC CDialog:
class CMParalelDlg : public CDialog {// …}; ,
iar clasa Analizor nu este derivată: class Analizor {// …}; .
În afara claselor, alte structuri de date folosite sunt: șiruri de caractere, vectori, matrice și structuri. Fișierele sursă secvențiale C/CPP sunt citite într-un buffer de dimensiune mare. Pe acest buffer se face analiza fișierului:
char buffer[DIMENSIUNE1];
Alte structuri de tip buffer sunt folosite pentru afișarea în controalele de editare ale casetelor de dialog. De exemplu:
char instrbuffer[DIMENSIUNE2]; // buffer pentru afișarea
// instrucțiunilor și a tipului acestora,
char declarbuffer[DIMENSIUNE3]; // buffer pentru afișarea
// declarărilor de variabile,
char totioperbuffer[DIMENSIUNE4]; // buffer pentru afișarea
// listei de operanzi,
char operbuffer[DIMENSIUNE5]; // buffer pentru afișarea
// instrucțiunilor și a operanzilor de care depinde fiecare dintre acestea.
Exemple de structură de tip vector:
unsigned short tip_instr[NRINSTR]; // vector ce memorează tipul
// instrucțiunilor din programul sursă,
COLORREF CGrafic::m_Colors[5]={
RGB(255,0,0),
RGB(0,255,0),
RGB(0,0,255),
RGB(255,255,0),
RGB(255,0,255),
}; // vector de elemente de tip COLORREF necesar
// pentru desenarea graficului instrucțiunilor.
Exemple de structură de tip matrice:
char TIP[NRTIPURI][NRTIPURI]; // matrice ce memorează tipul
// instrucțiunii general valabile în programele sursă C/C++,
char operanzi[NROPER][NROPER]; // lista operanzilor din program,
char instructiuni[NRINSTR][NRINSTR]; // lista instrucțiunilor
// programului,
char DEP[NRINSTR][NROPER]; // matricea dependențelor
// instructiuni – operanzi,
char instr_dep[NRINSTR][NRINSTR]; // matricea dependențelor
// dintre instrucțiuni,
char PAR[NRINSTR][NRINSTR]; //matricea instrucțiunilor paralele.
Exemple de structuri:
struct str {
int stanga;
int sus;
int dreapta;
int jos;
int cod;
}; // utilizată pentru identificarea instrucțiunii și a tipului acesteia
// pe grafic.
5.3 Algoritmii utilizați
Clasele Analizor și CParDlg implementează algoritmii de bază ai aplicației MParalel.
Clasa Analizor conține motorul de analiză a fișierelor sursă secvențiale C/CPP și realizează matricea de dependență dintre instrucțiuni instr_dep pe baza matricei de dependență instrucțiuni-operanzi DEP. Definirea clasei Analizor este dată în Exemplul 5.1.
Exemplul 5.1
Definirea clasei Analizor
class Analizor
{
public:
Analizor() // constructor
{
sir = NULL;
poz = 0;
tip = 0;
}
~Analizor() // destructor
{
if(sir) delete[] sir;
}
unsigned short Tip() // functie inline
{
return tip;
}
char* Instr(); // preia urmatoarea instructiune (modifica tip)
int CautaOperanzi(char *instrcur,unsigned short tipinstr);
int ScoateOperanzi(char *instrcur,unsigned short tipinstr);
protected:
unsigned int SareSpatii() // functie inline
{
unsigned long vecheaPoz = poz;
//sare peste spatii, tab si enter
while(sir[poz]==32 || sir[poz] == 9 || sir[poz] == 10 || sir[poz] == 13 )
poz++;
return (unsigned int)(poz-vecheaPoz);
}
//sare sirul care incepe din pozitia curenta
unsigned int SareSir();
public:
void Sir(const char *s) // functie inline
{
if(sir) delete[] sir;
sir = new char[strlen(s)+1]; strcpy(sir,s);
poz = 0; tip = 0;
Curata();
}
protected:
int EsteBloc();
int EsteFunctie();
int EsteIf();
int EsteElse();
int EsteFor();
int EsteWhile();
int EsteDo();
int EsteWhile_de_la_Do();
int EsteDeclar();
int EsteRetDelBreak();
int EsteAtribuire();
int EsteIncrDecr();
int EsteApelFunc();
int EsteDirectiva();
public:
void Curata();
char* sir; //sirul de caractere din care se preiau instructiunile
unsigned long poz; //pozitia curenta in sir
protected:
char* instr; //instructiunea curenta
unsigned short tip; //tipul instructiunii
unsigned long curLine; //indexul in sir al primului element din linia curenta
};
Implementarea clasei Analizor este realizată în ANEXA 2.
Fișierul sursă este memorat într-un buffer de dimensiune mare:
char buffer[DIMENSIUNE].
Analiza fișierului sursă C/CPP secvențial se realizează prin intermediul unei bucle do…while() în care este apelată funcția Instr() până când se ajunge la sfârșitul buffer-ului:
do{
// într-o variabilă de tip char* se preia instrucțiunea curentă din fișier
instrCurr = analizor.Instr();
if(instrCurr) //dacă nu s-a ajuns la sfârșitul buffer-ului
{
// prelucrare instrucțiunea curentă
}
else break; //s-a ajuns la sfârșitul buffer-ului
}while(1);
Apelul funcției Instr() se face în corpul funcției OnAnalizaSursa() din clasa CAfisareDLG:
void CAfisareDLG::OnAnalizaSursa()
{
char *instrCurr; // instrucțiunea curentă
// alte instrucțiuni
Analizor analizor; analizor.Sir(sir);
do{
instrCurr = analizor.Instr();
if(instrCurr)
{ // prelucrare instrucțiunea curentă }
else break;
delete instrCurr;
}while(1);
// alte instrucțiuni
}
Funcția Instr() din clasa Analizor identifică instrucțiunea curentă și tipul acesteia după ce sare peste spațiile albe:
char* Analizor::Instr()
{
SareSpatii(); // sare spațiile albe
if(!EsteBloc())
if(!EsteIf())
if(!EsteFor())
if(!EsteElse())
if(!EsteDo())
if(!EsteWhile_de_la_Do())
if(!EsteWhile())
if(!EsteDirectiva())
if(!EsteFunctie())
if(!EsteDeclar())
if(!EsteRetDelBreak())
if(!EsteIncrDecr())
if(!EsteApelFunc())
if(!EsteAtribuire())
{
// instrucțiuni
}
return instr;
}
Instrucțiunea curentă este apoi prelucrată în vederea identificării operanzilor pe care aceasta îi folosește. Această operație este realizată de funcția ScoateOperanzi(). Aceeași funcție este responsabilă și de realizarea matricei de dependență instrucțiuni-operanzi DEP. Implementarea funcției OnAnalizaSursa() responsabilă de apelul funcțiilor din clasa Analizor este realizată în ANEXA 4.
Pe baza matricei de dependență instrucțiuni-operanzi DEP se realizează matricea de dependență dintre instrucțiuni instr_dep. Algoritmul a fost prezentat în capitolul 4 “Algoritm de transformare a prelucrărilor secvențiale în prelucrări paralele” și este implementat de funcția OnInitDialog() la inițializarea casetei de dialog gestionată de clasa CDependenteDlg. Algoritmul este prezentat în Exemplul 5.2.
Exemplul 5.2
Realizarea matricei de dependență dintre instrucțiuni
BOOL CDependenteDlg::OnInitDialog()
{
// declarări, alte instrucțiuni
for(i=0;i<nr_line;i++)
for(int j=0;j<i;j++) instr_dep[i][j]=0;
int k;
for(int j=0;j<indice;j++)
{
//––––––––––––––––––––––
// Pasul 1
k=0;
for(i=0;i<nr_line;i++)
if(DEP[i][j]==1)
{
tmp[k]=i;
k++;
}
// Sfârșit Pasul 1
//––––––––––––––––––––––
// Pasul 2
for(i=0;i<k-1;i++)
for(int t=i+1;t<k;t++)
instr_dep[tmp[t]][tmp[i]]=1;
// Sfârșit Pasul 2
//––––––––––––––––––––––
} // end for
// alte instrucțiuni
return TRUE;
}
Clasa CParDlg implementează algoritmul de paralelizare a fișierelor sursă C/CPP secvențiale. Algoritmul a fost prezentat în capitolul 4 “Algoritm de transformare a prelucrărilor secvențiale în prelucrări paralele” și este implementat în ANEXA 3.
5.4 Execuția aplicației MParalel
Fișierul mparalel.exe este responsabil de lansarea în execuție a aplicației MParalel. Pentru execuție sunt necesare fișierele mfc42.dll și msvcrt.dll. Acestea sunt biblioteci cu legare dinamică ce includ o mare parte din funcționalitatea aplicației. Cele două fișiere se găsesc în același director cu programul mparalel.exe, respectiv X:\MParalel\Release (X este drive-ul fizic sursă al aplicației – unitate de dischetă, unitate de CD, partiție pe hard-disk).
Pentru oferirea unui aspect deosebit casetelor de dialog, am utilizat controale ActiveX. Codul unui control ActiveX este plasat într-un fișier .OCX sau .DLL. Pentru aplicația MParalel am utilizat controalele ActiveX Microsoft Forms 2.0 Image și Microsoft Forms 2.0 Label al căror cod se găsește în fișierul fm20.dll. Pentru rularea aplicației este necesară înregistrarea acestor controale în sistemul pe care se face execuția. Înregistrarea controalelor se face cu ajutorul programului regsvr32.exe, apelându-l fie prin opțiunea Run din meniul Start, fie din linia de comandă, ca aici:
regsvr32 C:\Windows\System\fm20.dll ,
unde Windows este numele directorului implicit în care au fost plasate fișierele sistemului de operare Windows 95/98. Pentru sistemul de operare Windows NT, calea C:\Windows trebuie înlocuită cu C:\WINNT.
Este posibil ca aceste controale să fie deja instalate în sistem (unele produse Microsoft, ca Microsoft Office, vin cu o serie de controale ActiveX pe care le înregistrează în sistem odată cu instalarea produselor respective). Pentru a verifica acest lucru, se caută fișierul fm20.dll în Registry, utilizând opțiunea Find a meniului Edit din Registry Editor (lansat cu ajutorul programului regedit.exe prin opțiunea Run din meniul Start). Dacă se detectează o intrare în Registry pentru fm20.dll, atunci nu mai este necesară înregistrarea controalelor.
Fișierul fm20.dll se găsește în același director cu programul mparalel.exe. Dacă nu este detectată o intrare în Registry pentru fm20.dll, se copiază acest fișier în C:\Windows\System (sau C:\WINNT\System) și se înregistrează cu regsvr32.exe.
Fișierele de test necesare aplicației se găsesc în directorul X:\MParalel\Test. Fișierele sursă și header ale aplicației sunt în directorul X:\MParalel.
ANEXE
=== 9_concluzii ===
6. Concluzii
Paralelismul are un rol important în rezolvarea problemelor a căror complexitate foarte mare conduce la obținerea soluției în afara timpului real dacă se folosesc algoritmi secvențiali de prelucrare.
Cerințele tot mai mari de viteză de calcul ale aplicațiilor din diferite domenii (studiul curgerii tridimensionale a fluidelor, simularea în timp real a sistemelor complexe, roboți inteligenți etc.) nu mai sunt rezolvate prin utilizarea calculatoarelor secvențiale care au ajuns la o limită fizică pentru potențialul de calcul. Soluția pentru obținerea unor viteze de calcul oricât de mari o constituie introducerea paralelismului prin multiplicitatea resurselor: un calculator paralel, compus din unități multiple de procesare și unități multiple de memorie interconectate între ele.
Conectarea unui număr mare de procesoare pentru construirea unui calculator paralel reprezintă o soluție eficientă din punct de vedere al costului și permite obținerea unor performanțe pe care un calculator secvențial nu le va atinge niciodată.
Introducerea tehnologiei VLSI (Very Large Scale Integration) a reprezentat un pas important în construirea unor calculatoare paralele puternice, la un preț relativ scăzut.
Există multe modalități în care pot fi construite calculatoarele paralele. Acestea diferă în funcție de mecanismele de control, organizarea spațiului de adresă a memoriei, granularitatea procesoarelor.
Pentru implementarea paralelismului este necesară existența atât a unui suport hardware, cât și software.
Paralelismul hardware este condiționat de arhitectura calculatorului paralel, care înglobează multiplicitatea resurselor de calcul și a comunicațiilor între aceste resurse.
Paralelismul software se referă la gradul și tipul de paralelism al programului.
Un calculator paralel poate fi compus dintr-un număr mic de procesoare foarte puternice sau dintr-un număr mare de procesoare mai puțin puternice. Calculatoarele din prima categorie se numesc calculatoare cu granularitate mare, iar cele din a doua categorie sunt denumite calculatoare cu granularitate mică. Între aceste extreme se plasează o întreagă gamă de calculatoare cu granularitate medie, care conțin câteva sute sau mii de procesoare de putere medie.
Procesoarele individuale ale calculatoarelor cu granularitate mare sunt considerabil mai costisitoare decât cele din calculatoarele cu granularitate medie sau mică, datorită faptului că astfel de procesoare nu se construiesc pe scară largă. Calculatoarele cu granularitate medie sunt cele mai ieftine, deoarece ele se construiesc din microprocesoare aflate în producția curentă.
Diferite aplicații de calcul paralel sunt adecvate pentru calculatoare paralele cu diferite valori ale granularității. Unele aplicații cu grad limitat de paralelism nu beneficiază de un număr foarte mare de procesoare disponibile într-un calculator cu granularitate mică și sunt mai potrivite execuției pe calculatoare cu granularitate medie sau mare.
Un algoritm secvențial este evaluat pe baza timpului de execuție, exprimat ca o funcție de numărul datelor de intrare ale acestuia. Timpul de execuție a unui algoritm paralel depinde nu numai de dimensiunea intrării, ci și de arhitectura calculatorului paralel și de numărul de procesoare. De aceea, un algoritm paralel este evaluat numai în contextul arhitecturii calculatorului paralel pentru care a fost proiectat.
Pentru evaluarea unui sistem paralel, aspectele care se analizează sunt: câștigul de viteză de execuție obținut prin execuția paralelă față de cea secvențială, eficiența de utilizare a procesoarelor, costul de execuție paralelă. Aceste aspecte sunt exprimate prin indicatori de performanță a sistemelor paralele: accelerarea paralelă, eficiența paralelă, costul paralel.
Realizarea de software pentru calculatoare paralele este o activitate complexă. Aceasta se datorează faptului că aplicațiile trebuie descompuse în sute și mii de părți care se execută concurent, iar activitatea elementelor de procesare trebuie coordonată pentru îndeplinirea sarcinilor de calcul.
Este dificil de transformat o aplicație realizată pentru execuția pe calculatoare secvențiale într-o aplicație paralelă, din considerente menționate anterior. De aceea, se procedează la reproiectarea aplicației pentru rularea pe calculatoare paralele. Pentru a scrie un program paralel, programatorul trebuie să țină cont de caracteristicile hardware ale sistemului pentru a obține un program eficient. Această dependență de particularitățile constructive ale calculatorului face ca aplicațiile paralele să fie puțin portabile.
Pentru a înlătura dependența hardware, este necesară utilizarea unui mediu de programare adecvat, care să pună la dispoziția programatorului instrumente eficiente de implementare a paralelismului. Multe astfel de instrumente software de dezvoltare se află încă în stadiul de cercetare și testare și numai un număr relativ mic au devenit disponibile comercial.
Există limbaje pentru proiectarea de aplicații paralele, prevăzute cu compilatoare sofisticate capabile să realizeze cod obiect paralel.
Programarea paralelă este de două tipuri: programare paralelă explicită și programare paralelă implicită.
În cadrul programării paralele explicite, programatorul trebuie să prevadă explicit partiționarea programului și a datelor, comunicația între procese, să rezolve dependențele de date și să evite condițiile de blocare.
Programarea paralelă implicită folosind compilatoare cu paralelizare eliberează programatorul de o mare parte din dificultățile programării paralele. Dar compilatoarele cu paralelizare sunt folosite numai pentru programe data-paralele și sunt relativ imature.
Limbajele de programare paralelă de nivel înalt nu rezolvă toate problemele care fac dificilă programarea paralelă, de exemplu nu asigură analiza dependențelor de date și partiționarea sau planificarea algoritmilor paraleli.
Programarea paralelă se află încă în stadiile de început. Numeroase probleme trebuie soluționate pentru ca aceasta să ajungă la fel de “simplă” ca și programarea secvențială.
=== ANEXA 1 ===
ANEXA 1 – algoritm paralel de sortare pentru multiprocesoare puternic cuplate
/////////////////////
//Versiunea 1
/////////////////////
do all processors Pid , 1<= id <= P-1 //P este numarul total de procesoare;
begin
target = [ id * N / P] //N este numarul de elemente ce trebuie sortate;
//Si este subset sortat, 1 <= i <= P;
//L(Si) este marginea inferioara a subsetului Si;
//U(Si) este marginea superioara a subsetului Si;
// α i, j este indexul elementului final al partitiei j din subsetul
//Si, 1 <= j <= P – 1 ;
lower = L(S1)
upper = U(S1)
p = (upper – lower + 1) * id / nprocs
for k = 2 to P do α k, id = binary_search(L(Sk), U(Sk), Sk, S1[pα])
//binary_search(lower_index, upper_index, Si, x) cauta in
//subsetul Si valoarea x si returneaza:
// lower_index – 1, daca x < Si[lower_index]
// upper_index, daca x > Si[upper_index]
// j, daca x >= Si[lower_index…j] si
// x < Si[j+1…upper_index].
diff = (pα – L(S1) + 1) + ∑pk=2 (α k, id – L(Sk) +1) – target
if(abs(diff) <= tolerance) then
α 1, id = pα
terminate returning α k, id , 1 <= k <= P
endif
do
begin
if(diff <= 0) then
lower = pα +1
pα = (lower + upper) / 2
for k = 2 to P do
begin
if(α k, id = L(Sk) – 1) then
α k, id = binary_search(L(Sk), U(Sk), Sk, S1[pα])
else
α k, id = binary_search(α k, id , U(Sk), Sk, S1[pα])
endif
end
else
upper = pα – 1
pα = (lower + upper) / 2
for k = 2 to P do
begin
α k, id = binary_search(L(Sk), α k, id , Sk, S1[pα])
end
endif
diff = (pα – L(S1) + 1) + ∑pk=2 (α k, id – L(Sk) +1) – target
if(abs(diff) <= tolerance) then
α 1, id = pα
terminate returning α k, id , 1 <= k <= P
endif
end
while(lower < upper)
α 1, id = pα
end.
/////////////////////
//Versiunea 2
/////////////////////
do all processors Pid , 1<= id <= P-1
begin
i = 1
target = [ id * N / P]
do
begin
p = [(id – i + 1) |Si| / (P – i + 1)]
for k = i + 1 to P do α k, id = binary_search(L(Sk), U(Sk), Sk, Si[pα]
diff = (∑i-1k=1 |Sk|) + (pα – L(S1) + 1) + ∑pk=i+1 (α k, id – L(Sk) +1) –
– target
if(abs(diff) <= tolerance) then
α i, id = pα
terminate returning α k, id , 1 <= k <= P
endif
lower = L(Si) – 1
upper = U(Si)
do
begin
if(diff < 0) then
lower = pα +1
pα = [(lower + upper) / 2]
for k = i + 1 to P do
begin
if(α k, id = L(Sk) – 1) then
α k, id = binary_search(L(Sk), U(Sk), Sk, Si[pα])
else
α k, id = binary_search(α k, id , U(Sk), Sk, Si[pα])
endif
diff = (∑i-1k=1 |Sk|) + (pα – L(Si) + 1) +
+ ∑pk=i+1 ( α k,id– L(Sk) +1) – target
end
else
upper = pα – 1
if(upper <> L(Si) – 1) then
[pα = (lower + upper) / 2]
for k = i + 1 to P do
begin
if(α k, id <> L(Sk) – 1) then
α k, id = binary_search(L(Sk), α k, id , Sk, Si[pα])
endif
end
diff = (∑i-1k=1 |Sk|) + (pα – L(Si) + 1) +
+ ∑pk=i+1 ( α k,id– L(Sk) +1) – target
else
diff = diff –1
endif
endif
if(abs(diff) <= tolerance) then
α i, id = pα
terminate returning α k, id , 1 <= k <= P
endif
end
while(lower < upper)
α i, id = pα
i = i + 1
end
while(i <> P)
return α k, id , 1 <= k <= P
end.
=== ANEXA 2 ===
ANEXA 2 – implementarea clasei Analizor
// Analizor.cpp: implementation of the Analizor class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "MParalel.h"
#include "Analizor.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
#define FARATIP 0
#define ALTTIP 1
#define IF 2
#define ELSE 3
#define WHILE 4
#define DO 5
#define WHILE_DO 6
#define FOR 7
#define FUNCTIE 8
#define BLOC_INTR 9
#define BLOC_IESI 10
#define DECLAR 11
#define RETURN 12
#define STERGERE 13
#define BREAK 14
#define DIRECTIVA 15
#define ATRIBUIRE 16
#define APELFUNC 17
#define INCR 18
#define DECR 19
#define VIDA 20
char TIP[NRTIPURI][NRTIPURI] ={ "FARA TIP",
"ALT TIP",
"IF",
"ELSE",
"WHILE",
"DO",
"WHILE de la DO", "FOR",
"FUNCTIE",
"INCEPUT BLOC",
"SFARSIT BLOC",
"DECLARARE",
"RETURN",
"DELETE",
"BREAK",
"DIRECTIVA",
"ATRIBUIRE",
"APEL FUNCTIE",
"INCREMENTARE",
"DECREMENTARE",
"VIDA"};
char operanzi[NROPER][NROPER];
int indice;
char operinstrCurr[100];
char instructiuni[NRINSTR][NRINSTR];
unsigned short tip_instr[NRINSTR];
int nr_instr;
char DEP[NRINSTR][NROPER];
int nr_line;
//––––––––––––––––––––––––––––––––––
int Analizor::CautaOperanzi(char *instrcur,unsigned short tipinstr)
{
char ins[200],*p,*buff;
int pozitie,vb;
strcpy(ins,instrcur);
if(tipinstr==DECLAR)
{
p=strtok(ins," ,*");
if(!strcmp(p,"const") || !strcmp(p,"static"))
p=strtok(NULL," ,*");
if(!strcmp(p,"unsigned") || !strcmp(p,"signed"))
{
p=strtok(NULL," ,*");
if(!strcmp(p,"short") || !strcmp(p,"long"))
{
p=strtok(NULL," ,,,*,(,=");
if(!strcmp(p,"int")) p=strtok(NULL," ,,,*,(,=");
}
else p=strtok(NULL," ,,,*,(,=");
}
else
if(!strcmp(p,"short") || !strcmp(p,"long"))
{
p=strtok(NULL," ,,,*,(,=");
if(!strcmp(p,"int") || !strcmp(p,"double"))
p=strtok(NULL," ,,,*,(,=");
}
else p=strtok(NULL," ,,,*,(,=");
while(p)
{
buff=new char[strlen(p)];
strcpy(buff,p);pozitie=0;
while(//buff[pozitie]!='=' &&
buff[pozitie]!='[' &&
buff[pozitie]!=')' &&
buff[pozitie]!='\0') pozitie++;
if(buff[pozitie]!='\0') buff[pozitie]='\0';
if(buff[0]!='\0' &&
strcmp(buff,"new") &&
strcmp(buff,"int") &&
strcmp(buff,"short") &&
strcmp(buff,"char") &&
strcmp(buff,"long") &&
strcmp(buff,"float") &&
strcmp(buff,"double") &&
strcmp(buff,"malloc") &&
strcmp(buff,"sizeof"))
if(buff[0]=='"' && pozitie>1 && buff[pozitie-1]=='"');
else
if(buff[0]=='"' && pozitie==1)
{
p=strtok(NULL," ,,,{,}");
char *tmp=new char[strlen(p)];
strcpy(tmp,p);
vb=0;
if(tmp[0]=='"' || tmp[strlen(p)-1]=='"') vb=1;
while(p!=NULL && vb==0)
{
p=strtok(NULL," ,,,{,}");
tmp=new char[strlen(p)];
strcpy(tmp,p);
if(tmp[0]=='"' || tmp[strlen(p)-1]=='"') vb=1;
}
}
else
if(buff[0]=='"' && pozitie>1 && buff[pozitie-1]!='"')
{
p=strtok(NULL," ,,,{,}");
char *tmp=new char[strlen(p)];
strcpy(tmp,p);
vb=0;
if(tmp[0]=='"' || tmp[strlen(p)-1]=='"') vb=1;
while(p!=NULL && vb==0)
{
p=strtok(NULL," ,,,{,}");
tmp=new char[strlen(p)];
strcpy(tmp,p);
if(tmp[0]=='"' || tmp[strlen(p)-1]=='"') vb=1;
}
}
else
if(buff[0]=='.' || isdigit((int)buff[0]));
else
{
vb=0;
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],buff))
{
vb=1;break;
}
if(!vb)
{
strcpy(operanzi[indice],buff);
indice++;
}
}
p=strtok(NULL," ,,,*,(,{,},+,-,/,<,>,&,=");
}//end while
return 1;
}//end if
if(tipinstr==FOR)
{
p=strtok(ins,"(, ,,,=,+,-,*,<,>,;,),[,]");
p=strtok(NULL,"(, ,,,=,+,-,*,<,>,;,),[,]");
if(!strcmp(p,"unsigned") || !strcmp(p,"signed"))
{
p=strtok(NULL,"(, ,,,=,+,-,*,<,>,;,),[,]");
p=strtok(NULL,"(, ,,,=,+,-,*,<,>,;,),[,]");
}
if(!strcmp(p,"int") ||
!strcmp(p,"char") ||
!strcmp(p,"long"))
p=strtok(NULL,"(, ,,,=,+,-,*,<,>,;,),[,]");
vb=0;
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=1;break;
}
if(!vb)
{
strcpy(operanzi[indice],p);
indice++;
}
return 1;
}//end if
return 0;
}
//––––––––––––––––––––––––––––––––––
void Analizor::Curata()
{
unsigned short intreGh = 0;
unsigned short intreApo = 0;
unsigned long p=0;
unsigned long curent=0;
char *temp = (char *)malloc(strlen(sir));
while(sir[p])
{
if(intreGh || intreApo)
if(sir[p] == '\\')
{
temp[curent++] = sir[p];
p++;
temp[curent++] = sir[p];
if(!sir[p]) break;
p++;
continue;
}
if(sir[p] == '\'')
if(!intreGh)//nu conteaza intre "
intreApo = (intreApo==1) ? 0:1;
if(sir[p] == '"')
if(!intreApo)
intreGh = (intreGh==1) ? 0:1;
if(!intreGh && !intreApo)
{
if(sir[p] == '/')
{
if(sir[++p] == '/')
{
while(sir[++p]!=10 && sir[p]!=13 && sir[p]!='\0');
}
else
if(sir[p] == '*')
{
while(sir[++p]!='\0' && (sir[p]!='*' || sir[p+1]!='/'));
if(sir[p])
{
p+=2;
}
}
else
p–;
}
}
temp[curent++] = sir[p++];
}
temp = (char *)realloc(temp,(curent+1)*sizeof(char));
temp[curent] = '\0';
delete[] sir;
sir = temp;
}
//––––––––––––––––––––––––––––––––––
unsigned int Analizor::SareSir()
{
unsigned int vecheaPoz = poz;
if(sir[poz] == '"')//intre ghilimele
{
while(sir[++poz] && sir[poz] != '"')
if(sir[poz] == '\\') poz ++;
}
else
if(sir[poz] == '\'')//intre '
{
while(sir[++poz] && sir[poz] != '\'')
if(sir[poz] == '\\')
poz ++;
}
else
return 0;
return (unsigned int)(poz-vecheaPoz);
}
//––––––––––––––––––––––––––––––––––
char* Analizor::Instr()
{
unsigned long nr=0;
SareSpatii();
if(poz >= strlen(sir))
{
return NULL;
}
if(!EsteBloc())
if(!EsteIf())
if(!EsteFor())
if(!EsteElse())
if(!EsteDo())
if(!EsteWhile_de_la_Do())
if(!EsteWhile())
if(!EsteDirectiva())
if(!EsteFunctie())
if(!EsteDeclar())
if(!EsteRetDelBreak())
if(!EsteIncrDecr())
if(!EsteApelFunc())
if(!EsteAtribuire())
{
tip = ALTTIP;
while(sir[poz]!=';' && sir[poz]!='\0')
{
nr += SareSir();
nr++;
poz++;
}
instr = (char *)malloc((nr+1)*sizeof(char));
strncpy(instr,sir+poz-nr,nr);
instr[nr] = '\0';
if(sir[poz]==';')
poz++;
}
return instr;
}
//––––––––––––––––––––––––––––––––––
//verifica daca este un inceput/sfarsit de bloc
int Analizor::EsteBloc()
{
if(sir[poz] == '{')//inceput de bloc
{
instr = new char[2];
instr[0] = '{';
instr[1] = '\0';
poz++;
tip = BLOC_INTR;
return 1;
}
if(sir[poz] == '}')//sfarsit de bloc
{
instr = new char[2];
instr[0] = '}';
instr[1] = '\0';
poz++;
tip = BLOC_IESI;
return 1;
}
return 0;
}
//––––––––––––––––––––––––––––––––––
//verfica daca este un if
int Analizor::EsteIf()
{
if(sir[poz] == 'i' && sir[poz+1] == 'f') //posibil if
{
unsigned long vecheaPoz = poz;
poz+=2;
unsigned int curent = SareSpatii()+2;
if(sir[poz] == '(')//este if !
{
unsigned short brackets=1;//nr de paranteze
curent ++;
while(sir[++poz] && brackets)
{
curent += SareSir();//se sare un eventual sir
curent++;
if(sir[poz] == '(')
brackets ++;
else
if(sir[poz] == ')')
brackets –;
}
instr = (char *)malloc((curent+1)*sizeof(char));
strncpy(instr,sir+vecheaPoz,curent);
instr[curent] = '\0';
tip = IF;
return 1;
}
poz = vecheaPoz;
}
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteElse()
{
if(sir[poz]=='e' &&
sir[poz+1]=='l' &&
sir[poz+2]=='s' &&
sir[poz+3]=='e')
{
poz += 4;
instr = new char[5];
strcpy(instr,"else");
tip = ELSE;
return 1;
}
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteFor()
{
if(sir[poz] == 'f' &&
sir[poz+1] == 'o' &&
sir[poz+2] == 'r') //posibil for
{
unsigned long vecheaPoz = poz;
poz+=3;
unsigned int curent = SareSpatii()+3;
if(sir[poz] == '(')//este for !
{
unsigned short brackets=1;//nr de paranteze
curent ++;
while(sir[++poz] && brackets)
{
curent += SareSir();//se sare un eventual sir
curent++;
if(sir[poz] == '(')
brackets ++;
else
if(sir[poz] == ')')
brackets –;
}
instr = (char *)malloc((curent+1)*sizeof(char));
strncpy(instr,sir+vecheaPoz,curent);
instr[curent] = '\0';
tip = FOR;
return 1;
}
poz = vecheaPoz;
}
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteWhile()
{
if(sir[poz] == 'w' &&
sir[poz+1] == 'h' &&
sir[poz+2] == 'i' &&
sir[poz+3] == 'l' &&
sir[poz+4] == 'e') //posibil while
{
unsigned long vecheaPoz = poz;
poz+=5;
unsigned int curent = SareSpatii()+5;
if(sir[poz] == '(')//este while
{
unsigned short brackets=1;//nr de paranteze
curent ++;
while(sir[++poz] && brackets)
{
curent += SareSir();//se sare un eventual sir
curent++;
if(sir[poz] == '(')
brackets ++;
else
if(sir[poz] == ')')
brackets –;
}
instr = (char *)malloc((curent+1)*sizeof(char));
strncpy(instr,sir+vecheaPoz,curent);
instr[curent] = '\0';
poz++;
tip = WHILE;
return 1;
}
poz = vecheaPoz;
}
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteDo()
{
if(sir[poz]=='d' &&
sir[poz+1]=='o' &&
sir[poz+2]=='{')
{
poz += 2;
instr = new char[3];
strcpy(instr,"do");
tip = DO;
return 1;
}
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteDirectiva()
{
if(sir[poz] != '#') return 0;
unsigned long vecheaPoz = poz;
if(poz)
while(–poz && sir[poz] != 10)
{
if(sir[poz] != 32 && sir[poz] != 9)
{
poz = vecheaPoz;
return 0;
}
}
poz = vecheaPoz+1;
while(sir[poz] != 13 && sir[poz]) poz++;
instr = (char *)malloc((poz-vecheaPoz+1)*sizeof(char));
strncpy(instr,sir+vecheaPoz,poz-vecheaPoz);
instr[poz-vecheaPoz] = '\0';
tip = DIRECTIVA;
return 1;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteFunctie()
{
unsigned long vecheaPoz = poz,poztmp=poz;
unsigned int aux=0;
char c = '\0';
while(sir[poz] != ';' && sir[poz] != '{' && sir[poz])
{
SareSir();
c = sir[poz];
poz++;
aux = SareSpatii();
}
if(sir[poz] == '{' && c != '=')
while(sir[poztmp]!='{')
if(sir[poztmp]!='(') poztmp++;
else
{
tip = FUNCTIE;
instr = (char *)malloc((poz – vecheaPoz – aux +1)*sizeof(char));
strncpy(instr,sir+vecheaPoz,poz-vecheaPoz-aux);
instr[poz-vecheaPoz-aux] = '\0';
return 1;
}
poz = vecheaPoz;
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteDeclar()
{
unsigned long vecheapoz=poz;
if(sir[poz]=='c' &&
sir[poz+1]=='o' &&
sir[poz+2]=='n' &&
sir[poz+3]=='s' &&
sir[poz+4]=='t' &&
sir[poz+5]==' ') //este constanta
{
poz+=6;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECLAR;
return 1;
}
if(sir[poz]=='s' &&
sir[poz+1]=='t' &&
sir[poz+2]=='a' &&
sir[poz+3]=='t' &&
sir[poz+4]=='i' &&
sir[poz+5]=='c' &&
sir[poz+6]==' ') //este tip static
{
poz+=7;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECLAR;
return 1;
}
if(sir[poz]=='u' &&
sir[poz+1]=='n' &&
sir[poz+2]=='s' &&
sir[poz+3]=='i' &&
sir[poz+4]=='g' &&
sir[poz+5]=='n' &&
sir[poz+6]=='e' &&
sir[poz+7]=='d' &&
sir[poz+8]==' ') //este unsigned si tip
{
poz+=9;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECLAR;
return 1;
}
if(sir[poz]=='s' &&
sir[poz+1]=='i' &&
sir[poz+2]=='g' &&
sir[poz+3]=='n' &&
sir[poz+4]=='e' &&
sir[poz+5]=='d' &&
sir[poz+6]==' ') //este signed si tip
{
poz+=7;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECLAR;
return 1;
}
if(sir[poz]=='s' &&
sir[poz+1]=='h' &&
sir[poz+2]=='o' &&
sir[poz+3]=='r' &&
sir[poz+4]=='t' &&
(sir[poz+5]==' ') ||(sir[poz+5]=='*')) //este short sau short int
{
poz+=6;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECLAR;
return 1;
}
//testam daca este declaratie de tip char, short, int, long, float, double
if((sir[poz]=='i' && sir[poz+1]=='n' && sir[poz+2]=='t' && (sir[poz+3]==' ' || sir[poz+3]=='*')) ||
(sir[poz]=='c' && sir[poz+1]=='h' && sir[poz+2]=='a' && sir[poz+3]=='r' && (sir[poz+4]==' ' || sir[poz+4]=='*')) ||
(sir[poz]=='l' && sir[poz+1]=='o' && sir[poz+2]=='n' && sir[poz+3]=='g' && (sir[poz+4]==' ' || sir[poz+4]=='*')) ||
(sir[poz]=='s' && sir[poz+1]=='h' && sir[poz+2]=='o' && sir[poz+3]=='r' && sir[poz+4]=='t' && (sir[poz+5]==' ' || sir[poz+5]=='*')) ||
(sir[poz]=='f' && sir[poz+1]=='l' && sir[poz+2]=='o' && sir[poz+3]=='a' && sir[poz+4]=='t' && (sir[poz+5]==' ' || sir[poz+5]=='*')) ||
(sir[poz]=='d' && sir[poz+1]=='o' && sir[poz+2]=='u' && sir[poz+3]=='b' && sir[poz+4]=='l' && sir[poz+5]=='e' && (sir[poz+6]==' ' || sir[poz+6]=='*')))
{
poz+=4;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECLAR;
return 1;
}
return 0;//nu este declarare de variabile
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteAtribuire()
{
unsigned long vecheapoz=poz,poztmp=poz;
while(sir[poz]!=';') poz++;
while(sir[poztmp]!=';')
if(sir[poztmp]=='"')
{
poz=vecheapoz;
return 0;
}
else
if(sir[poztmp]!='=') poztmp++;
else
{
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=ATRIBUIRE;
return 1;
}
poz=vecheapoz;
return 0;//nu este atribuire
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteApelFunc()
{
unsigned long vecheapoz=poz,poztmp=poz;
while(sir[poz]!=';') poz++;
if(sir[poz-1]!=')')
{
poz=vecheapoz;
return 0;//nu este apel de functie
}
while(sir[poztmp]!='(')
if(sir[poztmp]=='=')//este atribuire si nu apel de functie
{
poz=vecheapoz;
return 0;
}
else poztmp++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=APELFUNC;
return 1;
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteIncrDecr()
{
unsigned long vecheapoz=poz;
while(sir[poz]!=';') poz++;
if(sir[vecheapoz]=='+' || sir[poz-1]=='+')
{
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=INCR;
return 1;
}
if(sir[vecheapoz]=='-' || sir[poz-1]=='-')
{
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=DECR;
return 1;
}
poz=vecheapoz;
return 0;//nu este incrementare sau decrementare
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteRetDelBreak()
{
unsigned long vecheapoz=poz;
if(sir[poz]=='r' &&
sir[poz+1]=='e' &&
sir[poz+2]=='t' &&
sir[poz+3]=='u' &&
sir[poz+4]=='r' &&
sir[poz+5]=='n' &&
(sir[poz+6]==' ' || sir[poz+6]=='('))//este return
{
poz+=7;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=RETURN;
return 1;
}
if(sir[poz]=='d' &&
sir[poz+1]=='e' &&
sir[poz+2]=='l' &&
sir[poz+3]=='e' &&
sir[poz+4]=='t' &&
sir[poz+5]=='e' &&
(sir[poz+6]==' ' || sir[poz+6]=='['))//este delete
{
poz+=7;
while(sir[poz]!=';') poz++;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=STERGERE;
return 1;
}
if(sir[poz]=='b' &&
sir[poz+1]=='r' &&
sir[poz+2]=='e' &&
sir[poz+3]=='a' &&
sir[poz+4]=='k' &&
sir[poz+5]==';')//este break
{
poz+=5;
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=BREAK;
return 1;
}
return 0;//nu este return, delete sau break
}
//––––––––––––––––––––––––––––––––––
int Analizor::EsteWhile_de_la_Do()
{
unsigned long vecheapoz = poz,poztmp=poz;
while(sir[poz]!=';') poz++;
if(sir[poztmp] == 'w' &&
sir[poztmp+1] == 'h' &&
sir[poztmp+2] == 'i' &&
sir[poztmp+3] == 'l' &&
sir[poztmp+4] == 'e' &&
sir[poztmp+5] == '(')
if(sir[poz-1]==')')
{
instr=new char[poz-vecheapoz+1];
strncpy(instr,sir+vecheapoz,poz-vecheapoz);
instr[poz-vecheapoz]='\0';
poz++;
tip=WHILE_DO;
return 1;
}
poz=vecheapoz;
return 0;
}
//––––––––––––––––––––––––––––––––––
int Analizor::ScoateOperanzi(char *instrcur,unsigned short tipinstr)
{
char pins[100],*p,vector[15][10];
int indcurr=0,vb,lg;
char *buff,*tmp;
operinstrCurr[0]='\0';
strcpy(pins,instr);
if(tipinstr==APELFUNC)
{
p=strtok(pins,"(,), ,,,&,[,],*,+,-");
p=strtok(NULL,"(,), ,,,&,[,],*,+,-");
while(p)
{
lg=strlen(p);
buff=new char[lg];
strcpy(buff,p);
if(buff[0]=='"' && lg>1 && buff[lg-1]=='"');
else
if(buff[0]=='"' && lg==1)
{
p=strtok(NULL," ,,,(,)");
tmp=new char[strlen(p)];
strcpy(tmp,p);
vb=0;
if(tmp[strlen(p)-1]=='"') vb=1;
while(p!=NULL && vb==0)
{
p=strtok(NULL," ,,,(,)");
tmp=new char[strlen(p)];
strcpy(tmp,p);
if(tmp[strlen(p)-1]=='"') vb=1;
}
}
else
if(buff[0]=='"' && lg>1 && buff[lg-1]!='"')
{
p=strtok(NULL," ,,,(,)");
tmp=new char[strlen(p)];
strcpy(tmp,p);
vb=0;
if(tmp[strlen(p)-1]=='"') vb=1;
while(p!=NULL && vb==0)
{
p=strtok(NULL," ,,,(,)");
tmp=new char[strlen(p)];
strcpy(tmp,p);
if(tmp[strlen(p)-1]=='"') vb=1;
}
}
else
{
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=0;strcpy(vector[indcurr],p);
for(int j=0;j<indcurr;j++)
if(!strcmp(vector[j],p)) {vb=1;break;}
if(!vb)
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," ");
}
indcurr++;
break;
}
} // end if
p=strtok(NULL,"(,), ,,,&,[,],*,+,-");
}//end while
nr_line++;
return 1;
}//end if
if(tipinstr==INCR || tipinstr==DECR)
{
p=strtok(pins,"(,), ,+,-,*");
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
break;
}
nr_line++;
return 1;
}//end if
if(tipinstr==ATRIBUIRE)
{
p=strtok(pins,"=,(,), ,,,*,+,-,/,?,:,[,],&");
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p)) break;
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," ");
p=strtok(NULL,"=,(,), ,,,*,+,-,/,?,:,[,],&");
while(p)
{
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=0;strcpy(vector[indcurr],p);
for(int j=0;j<indcurr;j++)
if(!strcmp(vector[j],p)) {vb=1;break;}
if(!vb)
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," "); }
indcurr++;
break;
}
p=strtok(NULL,"=,(,), ,,,*,+,-,/,?,:,[,],&");
}
nr_line++;
return 1;
}//end if
if(tipinstr==IF || tipinstr==WHILE || tipinstr==WHILE_DO)
{
p=strtok(pins,"(, ,,,|,&,>,<,=,!,*,+,-,/,),[,]");
p=strtok(NULL,"(, ,,,|,&,>,<,=,!,*,+,-,/,),[,]");
while(p)
{
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=0;strcpy(vector[indcurr],p);
for(int j=0;j<indcurr;j++)
if(!strcmp(vector[j],p)) {vb=1;break;}
if(!vb)
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," "); }
indcurr++;
break;
}
p=strtok(NULL,"(, ,,,|,&,>,<,=,!,*,+,-,/,),[,]");
}
nr_line++;
return 1;
}//end if
if(tipinstr==FOR)
{
p=strtok(pins,"(, ,,,<,>,=,+,-,!,*,/,;,),[,]");
p=strtok(NULL,"(, ,,,<,>,=,+,-,!,*,/,;,),[,]");
while(p)
{
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=0;strcpy(vector[indcurr],p);
for(int j=0;j<indcurr;j++)
if(!strcmp(vector[j],p))
{
vb=1;
break;
}
if(!vb)
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," ");
}
indcurr++;
break;
}
p=strtok(NULL,"(, ,,,<,>,=,+,-,!,*,/,;,),[,]");
}
nr_line++;
return 1;
}//end if
if(tipinstr==STERGERE)
{
p=strtok(pins," ,[,]");
p=strtok(NULL," ,[,]");
vb=0;
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=1;break;
}
if(vb)
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," ");
}
return 1;
}//end if
if(tipinstr==RETURN)
{
p=strtok(pins," ,,,(,),[,],+,-,*,/");
p=strtok(NULL," ,,,(,),[,],+,-,*,/");
while(p)
{
vb=0;
for(int i=0;i<indice;i++)
if(!strcmp(operanzi[i],p))
{
vb=1;break;
}
if(vb)
{
DEP[nr_line][i]=1;
strcat(operinstrCurr,p);
strcat(operinstrCurr," ");
}
p=strtok(NULL," ,,,(,),[,],+,-,*,/");
}
nr_line++;
return 1;
}//end if
if(tipinstr==BREAK)
{
return 1;
}//end if
if(tipinstr==BLOC_INTR || tipinstr==BLOC_IESI)
{
return 1;
}//end if
return 0;
}
=== ANEXA 3 ===
ANEXA 3 – implementarea algoritmului de paralelizare
void CParDlg::OnParIntegral()
{
///////////////////////////////////////////////////////////////////
// algoritmul de paralelizare începe aici
//////////////////////////////////////////////////////////////////
char dim[NRINSTR],level=0,k,vb,tmp;
//––––––––––––––––––––––––-
// Pasul 1
//pe primul nivel se pun I1 si instructiunile care nu depind de I1
PAR[level][0]=1;k=1;
for(int i=1;i<nr_line;i++)
if(!instr_dep[i][0])
{
PAR[level][k]=i+1;k++;
}
dim[level]=k;level++;
// Sfârșit Pasul 1
//––––––––––––––––––––––––-
//se lucreaza permanent pe doua niveluri consecutive
k=0;
for(i=1;i<nr_line;i++)
if(instr_dep[i][0])
{
PAR[level][k]=i+1;
k++;
}
while(1) //while
{
// Pasul 2
for(i=0;i<dim[level-1];i++) //for1
{
int c=PAR[level-1][i]-1;
for(int j=c;j<nr_line;j++) //for2
{
vb=0;
if(instr_dep[j+1][c]) //if
{
tmp=j+2;
if(!k)
{
PAR[level][k]=tmp;
k++;
}
else
{
for(int t=0;t<k;t++)
if(tmp==PAR[level][t])
{
vb=1;
break;
}
if (!vb)
{
PAR[level][k]=tmp;
k++;
}
}
if(!vb)
{
for(int w=level-1;w>=0;w–)
{
for(int t=1;t<dim[w];t++)
if(PAR[w][t]==tmp)
{
for(int q=t+1;q<dim[w];q++)
PAR[w][q-1]=PAR[w][q]; dim[w]–;
}
}
}
} //end if
} //end for2
} //end for1
// Sfârșit Pasul 2
if(!k) break; //ieșire din while când se ajunge pe nivelul frunză
dim[level]=k;level++;k=0;
}//end while
/////////////////////////////////////////////////////////////////////////
// algoritmul de paralelizare se termină aici
/////////////////////////////////////////////////////////////////////////
//––––––––––––––––––––––––––––
//////////////////////////////
// alte instrucțiuni
//////////////////////////////
} //terminare corp funcție
=== ANEXA 4 ===
ANEXA 4 – implementarea funcției OnAnalizaSursa()
void CAfisareDLG::OnAnalizaSursa()
{
m_dependente.EnableWindow();
for(int lin=0;lin<NRINSTR;lin++)
for(int col=0;col<NROPER;col++) DEP[lin][col]=0;
char *instrCurr,*pinstr=instrbuffer;
char *antet="INSTRUCTIUNILE PROGRAMULUI TIP INSTRUCTIUNE";
char *linie="============================= =================";
unsigned short temp,lg;
int indicevechi;
strcpy(pinstr,antet);
pinstr+=strlen(antet);
instrbuffer[pinstr-instrbuffer]=_TCHAR(13);
instrbuffer[pinstr-instrbuffer+1]=_TCHAR(10);
pinstr=&instrbuffer[pinstr-instrbuffer+2];
strcpy(pinstr,linie);
pinstr+=strlen(linie);
instrbuffer[pinstr-instrbuffer]=_TCHAR(13);
instrbuffer[pinstr-instrbuffer+1]=_TCHAR(10);
pinstr=&instrbuffer[pinstr-instrbuffer+2];
antet="INSTRUCTIUNI EXECUTABILE OPERANZI";
linie="========================== =========";
char *poper=operbuffer;
strcpy(poper,antet);
poper+=strlen(antet);
operbuffer[poper-operbuffer]=_TCHAR(13);
operbuffer[poper-operbuffer+1]=_TCHAR(10);
poper=&operbuffer[poper-operbuffer+2];
strcpy(poper,linie);
poper+=strlen(linie);
operbuffer[poper-operbuffer]=_TCHAR(13);
operbuffer[poper-operbuffer+1]=_TCHAR(10);
poper=&operbuffer[poper-operbuffer+2];
antet="OPERANZII";
linie="==========";
char *ptotioper=totioperbuffer;
strcpy(ptotioper,antet);
ptotioper+=strlen(antet);
totioperbuffer[ptotioper-totioperbuffer]=_TCHAR(13);
totioperbuffer[ptotioper-totioperbuffer+1]=_TCHAR(10);
ptotioper=&totioperbuffer[ptotioper-totioperbuffer+2];
strcpy(ptotioper,linie);
ptotioper+=strlen(linie);
totioperbuffer[ptotioper-totioperbuffer]=_TCHAR(13);
totioperbuffer[ptotioper-totioperbuffer+1]=_TCHAR(10);
ptotioper=&totioperbuffer[ptotioper-totioperbuffer+2];
antet="DECLARARI";
linie="==========";
char *pdeclar=declarbuffer;
strcpy(pdeclar,antet);
pdeclar+=strlen(antet);
declarbuffer[pdeclar-declarbuffer]=_TCHAR(13);
declarbuffer[pdeclar-declarbuffer+1]=_TCHAR(10);
pdeclar=&declarbuffer[pdeclar-declarbuffer+2];
strcpy(pdeclar,linie);
pdeclar+=strlen(linie);
declarbuffer[pdeclar-declarbuffer]=_TCHAR(13);
declarbuffer[pdeclar-declarbuffer+1]=_TCHAR(10);
pdeclar=&declarbuffer[pdeclar-declarbuffer+2];
Analizor analizor;
analizor.Sir(sir);
indice=0;indicevechi=indice;nr_instr=0;nr_line=0;
/////////////////////////////////////////////////////////////////////
// aici începe bucla de analiză a fișierului
/////////////////////////////////////////////////////////////////////
do{
instrCurr = analizor.Instr();
if(instrCurr)
{
strcpy(pinstr,instrCurr);
pinstr+=strlen(instrCurr);
lg=90-strlen(instrCurr);
char *spatii=new char[lg+1];
for(unsigned short i=0;i<lg;i++) spatii[i]='.';
spatii[lg]='\0';
strcpy(pinstr,spatii);
pinstr+=lg;
delete spatii;
temp=analizor.Tip();
strcpy(pinstr,TIP[temp]);
pinstr+=strlen(TIP[temp]);
instrbuffer[pinstr-instrbuffer]=_TCHAR(13);
instrbuffer[pinstr-instrbuffer+1]=_TCHAR(10);
pinstr=&instrbuffer[pinstr-instrbuffer+2];
static char numefct[100], *pnumefct=numefct;
if(temp==8)
{
strcpy(numefct,instrCurr);
pnumefct=strtok(numefct,", ,");
pnumefct=strtok(NULL,"(");
}
int vb=0;
if(temp==7)
{
char *p,ins[25];
strcpy(ins,instrCurr);
p=strtok(ins,"(, ");
p=strtok(NULL,"(, ");
if(!strcmp(p,"unsigned") ||
!strcmp(p,"int") ||
!strcmp(p,"char") ||
!strcmp(p,"long")) vb=1;
}
if(temp==11 || (temp==7 && vb))
{
strcpy(pdeclar,instrCurr);
pdeclar+=strlen(instrCurr);
declarbuffer[pdeclar-declarbuffer]=_TCHAR(13);
declarbuffer[pdeclar-declarbuffer+1]=_TCHAR(10);
pdeclar=&declarbuffer[pdeclar-declarbuffer+2];
}
if(analizor.CautaOperanzi(instrCurr,temp))
{
for(int i=indicevechi;i<indice;i++)
{
strcpy(ptotioper,"O");ptotioper+=1;
_itoa( i+1,ptotioper,10);ptotioper+=strlen(ptotioper);
strcpy(ptotioper," ");ptotioper+=3;
strcpy(ptotioper,operanzi[i]);
ptotioper+=strlen(operanzi[i]);
totioperbuffer[ptotioper-totioperbuffer]=_TCHAR(13);
totioperbuffer[ptotioper-totioperbuffer+1]=_TCHAR(10);
ptotioper=&totioperbuffer[ptotioper-totioperbuffer+2];
}
indicevechi=indice;
}//end if
if(temp!=8 && !strcmp(pnumefct,"main"))
if(analizor.ScoateOperanzi(instrCurr,temp))
if(operinstrCurr!=NULL)
{
strcpy(instructiuni[nr_instr],instrCurr);
if(temp!=9 && temp!=10)
{
tip_instr[nr_instr]=temp;nr_instr++;
strcpy(poper,"I");poper+=1;
_itoa( nr_instr,poper,10);poper+=strlen(poper);
strcpy(poper," ");poper+=3;
}
strcpy(poper,instrCurr);
poper+=strlen(instrCurr);
lg=70-strlen(instrCurr);
char *spatii=new char[lg+1];
for(unsigned short i=0;i<lg;i++) spatii[i]=' ';
spatii[lg]='\0';
strcpy(poper,spatii);
poper+=lg;
delete spatii;
strcpy(poper,operinstrCurr);
poper+=strlen(operinstrCurr);
operbuffer[poper-operbuffer]=_TCHAR(13);
operbuffer[poper-operbuffer+1]=_TCHAR(10);
poper=&operbuffer[poper-operbuffer+2];
}//end if
}
else break;
delete instrCurr;
}while(1);
////////////////////////////////////////////////////////////////////////////
// aici se termină bucla de analiză a fișierului
////////////////////////////////////////////////////////////////////////////
//afisarea continutului buffer-ului ce contine instructiuni
instrbuffer[pinstr-instrbuffer]='\0';
m_instroperanzi.SetWindowText((LPCTSTR )instrbuffer);
//afisarea continutului buffer-ului ce contine toate declararile
declarbuffer[pdeclar-declarbuffer]='\0';
m_declarari.SetWindowText((LPCTSTR )declarbuffer);
//afisarea continutului buffer-ului ce contine toti operanzii
totioperbuffer[ptotioper-totioperbuffer]='\0';
m_totioperanzii.SetWindowText((LPCTSTR )totioperbuffer);
//afisarea continutului buffer-ului ce contine instructiunile
//si operanzii corespunzatori
operbuffer[poper-operbuffer]='\0';
m_operanzi.SetWindowText((LPCTSTR )operbuffer);
char stat[100],*pstat=stat;
strcpy(pstat,"STATISTICI: ");pstat+=strlen("STATISTICI: ");
_itoa(nr_line,pstat,10);pstat+=strlen(pstat);
strcpy(pstat," instructiuni executabile si ");
pstat+=strlen(" instructiuni executabile si ");
_itoa(indice,pstat,10);pstat+=strlen(pstat);
strcpy(pstat," operanzi");pstat+=strlen(" operanzi");
stat[pstat-stat]='\0';
m_stat.SetWindowText((LPCTSTR )stat);
}
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: .realizarea Paralelismului Maxim Pt Alg de Prelucrare (ID: 130282)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.