1. Motivaţia
Yüklə 232,21 Kb.
|
- Bu səhifədəki naviqasiya:
- Sistemele de calcul paralel cu memorie distribuită
- Sistemele Multi-procesor
- Sistemele Multi-computer
- Clustere cu disponibilitate ridicată (High availablity)
- Clustere cu performanţă ridicată (High Performance)
- Clustere destinate calcului pe grid (Grid computing)
- Clustere de echilibrare a încărcării (Load balancing clusters)
- DCalc
- Facilităţi expuse dar fixe (nu pot fi extinse)
- Facilităţi expuse extensibile
- Mediul supervizat (managed mode).
- Dinamism.
|
Cuprins
1. Motivaţia .................................................................................................... 2
3.1. O privire generalizată ........................................................................ 10 3.2. Platforma aleasă ................................................................................. 12 3.3. Structura generală a librăriei .............................................................. 14 3.4. Crearea şi utilizarea algoritmilor ....................................................... 15 3.5. Asambloarele ..................................................................................... 19 3.6. Interfeţele de execuţie ........................................................................ 21 3.7. Cozile de execuţie .............................................................................. 23 3.8. Porţile ................................................................................................. 25 3.9. Planificatorul ...................................................................................... 27 3.10. Dispecerul ........................................................................................ 29
4.1 Framework software ........................................................................... 31 4.2. Descrierea funcţională ....................................................................... 33 4.3. Echilibrarea automată al încărcării .................................................... 36 4.4. Toleranţa la defecte ........................................................................... 38 4.5. Descrierea aplicaţiei Client ................................................................ 40 4.6. Descrierea aplicaţiei Server ............................................................... 46
5.1. Matricea ............................................................................................. 48 5.2. Produsul matricial .............................................................................. 50 5.3 Algoritmii produsului matricial .......................................................... 54 5.4. Descrierea algoritmului selectat ........................................................ 56
6.1. Analiza performanţelor ...................................................................... 59 6.2. Posibilitatea extinderii ulterioare ....................................................... 62
1. Motivaţia Pe parcursul ultimelor decenii tehnica de calcul a evoluat într-un ritm accelerat. Însă, în acelaşi timp au apărut un număr larg de probleme ce se doreau rezolvate utilizând calculatoarele datorită numărului mare de operaţii matematice pe care acestea le pot efectua cu uşurinţă. În timp, aceste probleme au necesitat calculatoare din ce în ce mai performante pentru a putea fi rezolvate în timp cât mai scurt. Această nevoie a condus marile companii producătoare de calculatoare să creeze sisteme multi-procesor şi supercomputerele care au redus mult aceşti timpi. Însă datorită legii lui Moore care prezice un declin în viteza de avansare al puterii de calcul, şi al avansării echipamentului şi tehnologiilor de reţelistică a apărut un alt domeniu ce pretinde să accelereze evaluarea problemelor complexe: sistemele de calcul distribuit. Această lucrare îşi propune implementarea unui astfel de sistem distribuit de calcul cu structură framework care ar putea fi utilizat pentru calculul a unui larg set de probleme ce necesită timpi mari de execuţie. Framework-ul propus în această lucrare va oferi facilităţile necesare programatorului pentru a rezolva acest tip de probleme într-un model flexibil şi în acelaşi timp simplificat. În acelaşi timp se va putea observa că framewok-ul este extrem de flexibil pentru a putea fi utilizat chiar şi în cazuri pentru care nu au fost proiectat iniţial. 2. Paralelismul în tehnica de calcul Calculul paralel înseamnă execuţia simultană pe mai multe procesoare a aceloraşi instrucţiuni cu scopul rezolvării mai rapide a unei probleme, subdivizată şi special adaptată. Ideea de bază este aceea că problemele de rezolvat pot fi uneori împărţite în mai multe probleme mai simple, de natură similară sau identică între ele, care pot fi rezolvate simultan. Rezultatul problemei iniţiale se află apoi cu ajutorul unei anumite coordonări. Un sistem de calcul paralel este un în esenţa un calculator cu mai multe procesoare care lucrează în paralel. Primele astfel de sisteme au fost supercomputerele. Noile procesoare de tip multi-miez (multi-core) utilizate în pe larg în ultimii ani sunt de asemenea sisteme de calcul paralel.
Există multe tipuri de sisteme de calcul paralel; ele se deosebesc prin tipul de interconectare:
Mai jos vom utiliza Taxonomia lui Flynn pentru a clasifica sistemele de calcul paralel (şi serial) între procesoarele componente:
Fig. 2.1 Aceste sisteme au fost şi cele dintâi. În esenţa, procesorul execută o singură instrucţiune în orice moment dat, această instrucţiune lucrând asupra unui singur set de date. Modelul este cel mai simplist şi de aceea a fost primul implementat în tehnică de calcul.
Fig. 2.2 Acest model se aplică dacă procesoarele execută în toate momentele aceeaşi instrucţiune, dar având ca obiect date diferite. Modelul este utilizat în prezent pe scară largă de producătorii de procesoare. Cele mai des întâlnite sunt extensiile MMX şi SSE al procesoarelor Intel. Aceste extensii introduc un set de instrucţiuni paralelizate fiecărui procesor.
Fig. 2.3 Modelul presupune ca toate procesoarele să execute un set de instrucţiuni pe acelaşi set de date. Deşi teoretic a fost definit acesta nu este folosit în tehnică de calcul comercială care are nevoie de mai multe fluxuri de date pentru o rezolvare mai rapidă a problemelor propuse. Modelul MISD presupune o capacitate sporită de evitare a erorilor prin utilizarea a mai multor unităţi de calcul care execută aceeaşi instucţiune pe acelaşi set de date-un lucru util în aplicaţiile militare şi aero-spaţiale.
Fig. 2.4 Modelul presupune că fiecare procesor execută instrucţiuni diferite ce operează pe diferite seturi de date. Acest model este pe larg utilizat în tehnică de calcul actuală pentru că prezintă maxim de avantaje comparativ cu limitările acesteia. Cele mai întâlnite implementări sunt sistemele multi-procesor şi cele multi-miez (multi-core). Acestea însă nu sunt sută la sută paralele pentru că utilizează aceeaşi memorie pe care trebuie să o împartă, şi deci apăr momente în care unele procesoare trebuie să aştepte celelalte să elibereze bus-ul de date.
O altă clasificare a sistemelor de calcul paralele se bazează pe arhitectura memoriei:
Acestea dispun de procesoare multiple care accesează toată memoria disponibilă ca un spaţiu de adrese global (pentru toate procesoarele). Pot fi împărţite în două mari clase, în funcţie de timpul de acces la memorie:
Fig. 2.5 Modelul spune că timpii de acces la toate părţile memoriei sunt egali. Este utilizat pe larg în calculatoarele moderne comerciale datorită complexităţii scăzute în raport cu modelul NUMA. Un plus mare al arhitecturilor UMA este faptul că teoretic pot fi utilizate un număr foarte larg de procesoare conectate în paralel.
Fig. 2.6 Accesul neuniform al memoriei presupune că timpii de acces la memorie nu sunt egali. Complexitatea unui astfel de sistem este extrem de mare. Fiecare nou procesor adăugat în sistem creşte complexitatea acestuia. Din această cauză nu sunt multe implementări comerciale ale acestei tehnologii.
Modelul presupune de asemenea mai multe procesoare, dar fiecare dintre acestea poate accesa doar memoria sa locală. Nu există nici un fel de spaţiu global de adrese pentru toate procesoarele. Avantajul modelului îl reprezintă faptul că nu există nevoia de a împarţi bus-ul sistemului pentru a obţine acces la memoria locală. Sistemele de calcul paralel pot fi de asemenea clasificate după numărul de procesoare din componenţa lor. Sistemele cu mii de asemenea procesoare sunt cunoscute drept massively parallel. Urmează sistemele de calcul paralel la scară mare sau la scară mică. Aceasta depinde şi de viteza procesorului (de exemplu: un sistem de calcul paralel bazat pe un calculator personal va fi considerat "la scară mică"). Sistemele de calcul paralel mai pot fi împărţite şi în sisteme multi-procesor simetrice şi asimetrice, după cum toate procesoarele sunt de acelaşi fel sau nu (de exemplu: dacă doar un procesor poate rula codul sistemului de operare şi celelalte nu au acest privilegiu, atunci sistemul este asimetric). Pentru procesarea paralelă au fost realizate o mare varietate de arhitecturi de calculatoare. Spre exemplu o arhitectura de tip "Ring" are procesoarele legate între ele într-o structură de tip inel. Alte tipuri de arhitecturi paralele: Hypercube, Fat tree, Systolic array s.a. Sistemele Multi-procesor Sistemele multi-procesor au fost primele încercări de a paraleliza evaluarea problemelor complexe de lungă durată. Termenul multiprocesare este des întâlnit în acest context şi descrie utilizarea a 2 sau mai multe procesoare conectate în acelaşi sistem dar care execută instrucţiuni diferite. Această arhitectură este cel mai des întâlnită în proiectarea aşa-numitelor supercomputere. Un supercomputer este un computer complex special, compus din mai multe procesoare care accesează aceeaşi memorie centrală şi care funcţionează concomitent şi coordonat, în cooperaţie strânsă, astfel încât supercomputerul poate atinge o mare performanţă totală de calcul. Numărul de procesoare interconectate ale unui supercomputer depăşeşte la anumite modele chiar şi 100.000. Pentru a menţine costul unui asemenea supercomputer la un nivel rezonabil, există şi arhitecturi de supercomputere care fac uz de procesoare mai ieftine şi mai lente, dar foarte numeroase, grupate în aşa-numite clustere. Printre primele firme care au produs supercomputere pentru piaţă ("comerciale") s-a numărat firma Cray prin anii 1970, numită aşa după fondatorul ei Seymour Cray. Primul sau supercomputer vândut şi instalat oficial a fost celebrul Cray-1, care în anul 1976 a atins viteza de calcul de 130 MegaFLOPS (130 milioane de instrucţiuni cu virgulă mobilă pe secundă). Drept comparaţie, un calculator normal din zilele noastre poate atinge câţiva GigaFLOPS.
O mare importanţă în ziua de azi este acordată sistemelor multi-computer. Aceste sisteme sunt formate din mai multe calculatoare independente unite într-o reţea de comunicaţii. Acestea pot avea o structură identică sau diferită, fapt ce nu impune restricţii asupra modului de operare global al sistemului. Motivele principale pentru care sunt folosite aceste sisteme pe larg în ziua de azi sunt:
În funcţie de gruparea acestor calculatoare, putem distinge sisteme numite cluster. Un cluster presupune că toate calculatoarele componente sunt strâns legate între ele şi dedicate unei singure functionalităţi. În continuare va fi prezentată o clasificare a acestora:
Modelul presupune existenţa a mai multor noduri ce îndeplinesc aceeaşi funcţionalitate. În cazul defectării unui nod din cluster, sistemul nu va fi pus la pământ pentru că vor fi utilizate celelalte noduri din sistem cu aceeaşi funcţionalitate.
Scopul unei astfel de grupări este de a minimiza timpii de răspuns al întregului sistem prin împărţirea încărcării asupra mai multor noduri simultan. Este utilizat în general în aplicaţii de calcul distribuit. Datorită necesităţilor de transfer masiv de date, acest model presupune o reţea bine pusă la punct.
Este un model asemănător cu cel pentru performanţă ridicată dar presupune legături mai slabe între calculatoarele ce fac parte din sistem. Aplicaţiile de bază sunt cele de calcul distribuit în care fiecare nod execută un număr mare de calcule independent de întregul sistem.
Acest sistem este format din noduri obişnuite dar şi din entităţi special destinate controlului de încărcare a întregului sistem. Numărul acelor entităţi de balansare poate fi unul sau mai multe. 3. Librăria DCalcCore 3.1. O privire generalizată În proiectarea software, o librărie este definită ca un set funcţionalităţi implementate şi expuse programatorului într-o formă simplificată gata de a fi integrată în codul „consumator”. Importanţa librăriilor software nu poate fi contestată. Toate limbaje precum C, C++, Pascal încă din primele zile ale vieţii lor au pus la dispoziţia programatorilor un set larg de funcţionalităţi ce erau expuse de librăriile de sistem. Dacă e să urmărim procesul de proiectare şi de implementare al oricărui program vom observa multitudinea de librării care vor fi utilizate de către programatorul în cauză, unele fiind chiar implicit utilizate. Principalul avantaj al unui astfel de concept este modularitatea. Odată creată, librăria poate fi utilizată de către o multitudine de consumatori. În acelaşi timp consumatorii nu trebuie să ştie cum este implementată acea librărie şi au nevoie doar de entităţile expuse (fiind ele funcţii sau clase sau orice alt concept). Pentru a putea fi prezentat framework-ul pentru calcul distribuit DCalc, trebuie să studiem structura librăriei DCalcCore care în esenţa este nucleul acestuia. Librăria expune programatorului un set larg de facilităţi pe care acesta le poate utiliza pentru a-şi crea propriul său framework.
Motivul principal pentru care ele nu pot fi extinse este faptul că sunt destinate unui anumit scop fixat. O extindere nu ar avea un sens într-un astfel de context. Deşi o astfel de decizie poate limita oarecum capacităţile librăriei totuşi este importantă în scopul în care protejează programatorul de o mulţime de erori pe care le poate comite în timp ce extinde acele facilităţi. În acelaşi timp, ţinând acele facilităţi în starea lor actuală (ne-extensibilă) simplifică structura internă a librăriei.
Aceste entităţi reprezintă bază configurabilităţii acestei librării. Extinzând aceste componente programatorul poate să adapteze librăria pentru un număr nelimitat de aplicaţii diferite.
Astfel de componente sunt defapt create pentru programator pe baza componentelor extensibile. Sunt două motive pentru care aceste componente au fost incluse în librărie: a) Rezolvă câteva cazuri pe larg utilizate de către programatori. Nu ar fi avut sens de lăsat fiecare programator să re-implementeze aceleaşi componente. b) Reprezintă un set de exemple. Este mult mai simplu de a scrie o extensie când există exemple deja implementate. 3.2. Platforma aleasă Datorită complexităţilor mari ce intervin în proiectarea şi implementarea framework-urilor, o importanţă deosebită trebuie acordată alegerii platformei de dezvoltare utilizată. Din ce în ce mai des sunt utilizate mediile de dezvoltare orientate obiect. Beneficiile cele mai importante al unui mediu OO sunt evidente în acest caz:
Există un număr mare de platforme OO ce sunt utilizate pe larg în dezvoltarea aplicaţiilor complexe. Aceste platforme se împart în două categorii mari:
Codul este compilat direct în instrucţiuni procesor, programul are acces direct la facilităţile sistemului de operare. O astfel de platformă foarte bine cunoscută este C++.
Codul nu este compilat în instrucţiuni ci într-un cod intermediar. Cele mai cunoscute platforme supervizate sunt Java şi .NET. Deşi C++ este o soluţie fiabilă în cele mai multe cazuri, foarte des dezvoltatorii de framework-uri aleg .NET sau Java. Motivul pentru această alegere este modul în care acestea sunt proiectate. C++, deşi un limbaj / platformă de nivel înalt, este foarte complex de utilizat în sine ceea ce aduce un nou set de probleme care pot fi evitate utilizând platformele .NET sau Java. Printre aceste probleme pe care le rezolvă aceste platforme sunt: 1) Garbage Collector. Procesul automat de eliberare a memoriei ce nu mai este utilizată. În codul C++ această memorie ar trebui să fie eliberată de programator după ce nu mai este întrebuinţată, ceea ce duce adesea la erori la execuţie. În cazul .NET şi Java acesta memorie este detectată automat şi eliberată la nevoie. 2) Mediul supervizat (managed mode). Dacă programele C++ sunt compilate direct în cod procesor, acelea Java sau .NET sunt compilate într-un cod intermediar numit intermediate language (IL). Acest detaliu oferă un număr larg de beneficii care lipsesc în C++ şi alte platforme native. Librăria DCalcCore a fost proiectată utilizând platforma .NET. Motivele mai sus menţionate nu sunt de ajuns pentru a înţelege de ce s-a folosit .NET şi nu Java. În continuare se va încerca expunerea acestor diferenţe cheie ce au jucat rolul decisiv în alegerea acestei platforme: 1) Integritatea. În primul rând s-a ales o platformă supervizată din motivele mai sus menţionate cum ar fi eliberarea automată al memoriei şi un mod mult mai bine protejat de lucru. 2) Portabilitatea. Deşi librăria a fost scrisă utilizând sistemul de operare Microsoft Windows, s-a propus ca aceasta să poată fi utilizată şi pe alte sisteme de operare cum ar fi GNU/Linux sau Solaris. Proiectul cu cod-deschis Mono oferă facilităţile necesare pentru utilizarea acestei librării pe acele sisteme de operare. O întrebare ar putea fi de ce nu s-a ales Java pentru portabilitate? Răspunsul simplificat ar fi: pentru că Java nu oferă un număr de facilităţi care s-au folosit pe larg în arhitectura librăriei. 3) Dinamism. Platforma .NET oferă facilităţi incluse pentru compilarea dinamică a codului scris în limbaj C#. Această compilare dinamică stă la bază librăriei DCalcCore. 3.3. Structura generală a librăriei După cum s-a descris în capitolul 3.1, librăria DCalcCore este împărţită în 3 seturi diferite de entităţi expuse. Mai jos sunt descrise toate componentele de bază ce fac parte din librărie.
|