Calcul paralel

Calcul paralel este numită execuția în paralel pe mai multe procesoare a acelorași instrucțiuni, sau și a unor instrucțiuni diferite, cu scopul rezolvării mai rapide a unei probleme, de obicei special adaptată sau subdivizată. 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 a rezultatelor parțiale.

Clasificările sistemelor de calcul paralel

Un sistem de calcul paralel este un computer (calculator) cu mai multe procesoare care lucrează în paralel. Primele astfel de sisteme au fost cele de tip supercomputer, care încă și azi (2011) cunosc o dezvoltare intensă. Noile procesoare de tip multimiez pentru PC-uri sunt de asemenea sisteme de calcul paralel.

Există multe tipuri de sisteme de calcul paralel; ele se deosebesc în primul rând prin tipul de interconectare-

între procesoarele componente (cunoscute drept elemente de procesare, în engleză: processing elements sau PEs), și
între procesoare și memorie.

Taxonomia lui Flynn clasifică sistemele de calcul paralel și scalar după caracteristicile instrucțiunilor și datelor, așa de exemplu:

Single Instruction Multiple Data prescurtat SIMD (o singură instrucțiune / date multiple): dacă toate procesoarele execută în toate momentele aceeași instrucțiune, dar având ca obiect date diferite;
Multiple Instruction Multiple Data prescurtat MIMD (mai multe instrucțiuni / date multiple): dacă fiecare procesor execută la același moment instrucțiuni diferite, cu date diferite.

O altă clasificare a sistemelor de calcul paralel este bazată pe arhitectura memoriei:

Sistemele de calcul paralel cu memorie partajată: dispun de procesoare multiple care toate pot accesa toată memoria disponibilă ca un spațiu de adrese global (pentru toate procesoarele). Acestea pot fi subîmpărțite în două mari clase, în funcție de timpul de acces la memorie:
- Acces uniform al memoriei (Uniform memory access, UMA), în care timpii de acces la toate părțile memoriei sunt egali
- Acces neuniform al memoriei (Non-uniform memory access,NUMA), în care timpii de acces la memorie nu sunt egali.
Sistemele de calcul paralel cu memorie distribuită au de asemenea mai multe procesoare, dar fiecare procesor poate accesa doar memoria sa proprie, numită atunci locală; un spațiu de adrese global pentru toate procesoarele nu există.

Sistemele de calcul paralel pot fi de asemenea clasificate și după numărul de procesoare din componența lor. Sistemele cu mii de asemenea procesoare sunt cunoscute drept massively parallel. Restul sistemelor de calcul paralel sunt numite 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 în sisteme multiprocesor 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 arhitectură de tip „ring" are procesoarele legate între ele într-o structură în inel. Alte tipuri de arhitecturi paralele: Hypercube (hipercub), Fat tree (ramificat), Systolic array (matrice) ș.a.

Teorie și practică

Sistemele de calcul paralel pot fi modelate ca sisteme de calcul cu acces aleator (Parallel Random Acces Machines sau PRAM). Modelul PRAM ignoră costurile interconectării între componentele sistemului. În multe cazuri el este foarte util pentru obținerea de prestații superioare. În realitate însă, interconectarea joacă un rol foarte important.

La rezolvarea unei probleme procesoarele pot comunica între ele sau coopera, sau pot funcționa și independent unele de altele dar sub comanda unui alt procesor, care distribuie subproblemele de rezolvat și colectează rezultatele obținute de fiecare procesor (ferma de procesoare).

Procesoarele dintr-un sistem de calcul paralel pot comunica între ele în mai multe feluri, inclusiv prin memorie partajată, magistrală partajată sau și printr-o rețea interconectată cu o mulțime de topologii posibile, incluzînd rețele de tip star, ring, hypercube etc. Sistemele de calcul paralel bazate pe rețea interconectată trebuie să posede unele protocoale de rutare pentru a permite trecerea mesajelor între nodurile care nu sunt conectate direct. Memoria care stă la dispoziție poate fi:

privată pentru fiecare procesor,
comună între un număr de procesoare, sau
globală, pentru toate procesoarele.

Performanță și costuri

Deoarece un sistem de calcul paralel cu n procesoare nu atinge o viteză de calcul de n ori mai mare decât fiecare procesor în parte, sistemul de calcul paralel, pentru a fi acceptat pe piață, trebuie măcar să fie convenabil la preț.

Pe de altă parte, calculul paralel se folosește la probleme care necesită foarte multe calcule, dar numai dacă acestea pot fi împărțite în sub probleme independente, mai simple, care pot profita de paralelism.

Terminologie în calculul paralel

Unii din termenii folosiți frecvent în calculul paralel sunt:

Task: o secțiune logică independentă dintr-o problemă de rezolvat, programată pe un calculator aproape ca un program de sine stătător.
Sincronizare: coordonarea sarcinilor simultane (task-urilor) pentru a evita dezordinea în recepționarea rezultatelor parțiale, și pentru a asigura corectitudinea rezultatului final.
Speedup, pronunțat /'spi:d'ʌp/ (v. AFI): denumit și parallel speedup, arată de câte ori este mai rapid un algoritm paralel decât algoritmul serial corespunzător.
Scalabilitate: abilitatea unui sistem de calcul paralel de a-și mări viteza totală de calcul atunci când se adaugă procesoare suplimentare. În general nu se atinge o scalabilitate ideală, proporțională cu numărul total de procesoare.

Algoritmi paraleli

Algoritmii paraleli se construiesc reproiectând algoritmii seriali astfel ca să folosească resursele specifice ale sistemului de calcul paralel. Nu toți algoritmii seriali pot fi paralelizați. O analogie exemplificativă: o femeie naște un copil în decursul a nouă luni, dar nouă femei nu pot naște un copil în decurs de o lună. În practică este foarte dificil de obținut o mărire lineară a vitezei de calcul în funcție de numărul de procesoare. Aceasta deoarece cei mai mulți algoritmi sunt prin natura lor secvențiali, vezi Legea lui Amdahl.

Unele probleme pot beneficia de pe urma paralelismului de tip "în secvență" (pipeline ), atunci când sunt adăugate noi procesoare. În acest caz, pentru a subîmpărți problema se folosește abordarea de tip "linie de asamblare". Dacă problema poate fi împărțită în n etape și un rezultat parțial este pasat de la etapă la etapă, atunci pot fi folosite în paralel tot n procesoare, dar cea mai înceată etapă le va frâna pe celelalte, și deci cele n procesoare se vor fi doar rareori folosite la capacitatea lor totală teoretică maximă.

Probleme de calcul paralel

Câteva seturi de probleme de calcul paralel renumite se găsesc la următoarele adrese:

Programare în calcul paralel

Programarea în calcul paralel cuprinde subdivizarea problemei de rezolvat, conceperea și implementarea programelor parțiale corespunzătoare, precum și acordarea între ele a acestor programe parțiale, pentru a beneficia de avantajele sistemelor de calcul paralel. Ea de asemenea se referă și la aplicarea metodelor de programare paralelă (paralelizare) la programele inițial seriale.

Programarea în calcul paralel se axează pe partiționarea întregii probleme de rezolvat în sarcini separate (tasks ), alocarea sarcinilor procesoarelor disponibile și sincronizarea lor pentru a obține rezultate concludente. Acest tip de programare se poate aplica numai problemelor care sunt în general paralelizabile. O problemă poate fi partiționată sau descompusă după domenii, funcțiuni sau după o combinație a celor două.

În programarea paralelă există două tipuri de abordare a problemei:

paralelism implicit, unde sistemul (compilatorul sau alt program) descompune problema și alocă sarcinile fiecărui procesor în mod automat. În acest caz compilatorul ține de compilatoarele de paralelizare automată;
paralelism explicit, unde programatorul trebuie să precizeze explicit în programul său modul cum va fi partiționată problema de rezolvat.

Mulți factori tehnici au impact asupra performanței atinse de programarea paralelă. Astfel, sarcina de echilibrare automată a procesoarelor paralele încearcă să țină toate procesoarele la fel de ocupate, mutând la nevoie sarcinile curente de la procesoarele mai încărcate la cele mai puțin încărcate.

Unii consideră programarea în calcul paralel ca fiind sinonimă cu programarea concurentă. Alții fac deosebire între programarea în calcul paralel, pe de-o parte, care folosește șabloane bine definite și structurate de comunicație între procese și se axează pe execuția în paralel a proceselor, și pe de altă parte programarea concurentă, care de obicei implică definirea de noi șabloane de comunicație între procese care au fost făcute concurente. În ambele cazuri comunicația se face ori prin memoria partajată ori prin schimburi de mesaje corespunzătoare între sarcini.

Programele care lucrează corect într-un sistem cu un singur procesor ar putea să nu funcționeze bine într-un mediu paralel. Aceasta pentru că multiple copii ale aceluiași program pot interfera între ele, de exemplu accesând aceeași zonă de memorie în același moment. De aceea într-un sistem paralel este necesară o programare deosebit de acurată (sincronizare).

Modele de programare în calcul paralel

Articol principal: Modele de programare paralelă.

Un model de programare paralelă este un set de tehnologii software pentru formularea de algoritmi paraleli și adaptarea aplicațiilor la sistemele de calcul paralel existente. Se referă la diverse domenii ale aplicațiilor, limbaje de programare, compilatoare, biblioteci de programe, sisteme de comunicație și sisteme cu I/O paralel. Pentru a realiza o aplicație pe o anumită platformă dată, programatorii trebuie să aleagă un model potrivit de programare paralelă sau o formă de îmbinare a unor modele adecvate.

Implementarea modelelor paralele poate avea loc pe mai multe căi: prin punerea la dispoziție a unor biblioteci de programe specializate, prin extensii de paralelizare ale limbajul de programare ales, sau uneori prin reprogramare totală. Modelul paralel depinde în bună măsură și de caracteristica memoriei accesate de procesoare: partajată, distribuită sau mixtă.

De obicei modelele de programare paralelă sunt apreciate după claritate și simplitate, dar aceste două criterii sunt contradictorii și greu de îndeplinit simultan. Desigur însă că și la calculul paralel este valabil scopul general - mărirea productivității în programare.