Modele de programare paralelă

Ce este calculul paralel?

Calcul paralel: utilizarea de mai multe procesoare sau computere care lucrează împreună pe o sarcină comună.

• Fiecare procesor functioneaza pe sectiunea sa de problema
• Procesoarele pot face schimb de informatii

Paralelismul – utilizat mai ales pana in urma cu cativa ani la calcul de inalta performanta; in ultimii ani, datorita limitarilor fizice care nu permit cresterea continua a frecventei microprocesoarelor paralelismul este utilizat tot mai intense in arhitectura.

Limitele de calcul paralel

-Vitezele de transmisie - viteza unui calculator de serie este direct dependentă de modul rapid de date se pot deplasa prin hardware. Limitele absolute sunt viteza luminii (30 cm / nanosecunde) și limita de transmitere din sârmă de cupru (9 cm / nanosecunde). Viteze crescânde necesita creșterea proximitatea elemente de prelucrare.

-Limitele miniaturizarea - tehnologie de procesor este de a permite un număr tot mai mare de tranzistori să fie plasat pe un cip. Cu toate acestea, chiar cu componente moleculare sau atomice-nivel, o limită va fi atinsă cu privire la modul componentele mici pot fi.

- Limitari economice - este tot mai scump de a face un singur procesor mai rapid. Folosind un număr mai mare de procesoare de mărfuri moderat rapide pentru a atinge aceeasi performanta(sau mai bune) este mai putin costisitoare.

- Arhitecturi informatice actuale sunt din ce în ce bazându-se pe nivelul de paralelism hardware pentru îmbunătățirea performanței: Unități de execuție multiple:

• Instructiuni Pipelined
• Multi-core

Există trei motivații pentru utilizarea procesorului paralel:

• pentru a atinge performanța cerută relativă la timpul de execuție;
• pentru că este o arhitectură disponibilă;
• pentru că problema care se pune se pretează la calculul paralel.

Cei trei factori principali care au favorizat introducerea pe scară largă a procesării paralele sunt:

• costul relativ scăzut al unui sistem cu mai multe procesoare;
• tehnologia circuitelor integrate a avansat în asemenea măsură întrucât pe un

singur cip pot fi înglobate milioane de tranzitoare;

• ciclul de timp al procesorului serial se apropie de limitele fizice sub care nu este posibilă nici o îmbunătățire.

În dezvoltarea conceptului de paralelism s-au conturat două direcții de cercetare:

• in problema hardului, respectiv care este arhitectura calculatorului care avantajează anumiți algoritmi de rezolvare a unor probleme diverse;
• calcul paralel orientat pe problemă, respectiv cât de mult îmbunătățesc algo-ritmii paraleli viteza de calcul pentru o problemă dată

Programarea paralelă-este arta de a programa o colecție de calculatoare pentru a executa eficient o singură aplicație. Dacă aplicația este numerică sau de calcul simbolic, eficiența înseamnă atingerea unei viteze mari de execuție (invers proporțională cu numărul de procesoare). În cazul unei aplicații în timp real sau a unui sistem de operare, eficiența constă în satisfacerea în timp real a cerințelor impuse de unități sau utilizatori. Programarea paralelă caută căile de divizare a aplicațiilor în unități (procese) care pot fi executate concurent pe mai multe procesoare.

Presupune:

• Specificarea problemei;
• Identificarea unităților fundamentale și interacțiunile dintre acestea;
• Transpunerea acestor unități fundamentele în procese cu interacțiunile specificate prin primitive de comunicare.

Un algoritm secvențial specifică o execuție secvențială a unui set de instrucțiuni. Execuția sa este numită proces. Un algoritm paralel specifică doi sau mai mulți algoritmi secvențiali care pot fi executați simultan ca procese paralele (concurente). Astfel, un proces este o colecție de instrucțiuni de control secvențiale care accesează date locale sau globale și care poate fi executat în paralel cu alte unități de program. Procesoarele pe care se execută un program paralel pot fi grupate într-o unitate (multiprocesor sau calculator paralel) sau pot fi separate ca mașini autonome conectate printr-o rețea.

Limbajul de calcul

Programarea paralelă necesită un limbaj de calcul și un limbaj de coordonare. Limbajul de coordonare este cheia ce permite utilizatorului unificarea într-un program a mai multor activități separate, fiecare specificate utilizând limbajul de calcul. Limbajul de calcul permite calcularea unor valori și manipularea obiectelor-date locale. Limbajul de coordonare permite crearea activităților (procese) simultane și comunicarea între acestea. De obicei, funcțiile standard ale limbajului de calcul și ale limbajului de coordonare sunt unite într-un super-limbaj.

Un limbaj concurent este un limbaj de programare de nivel înalt pentru programarea concurentă, adică care oferă următoarele facilități:

• descrierea proceselor paralele;
• mijloace de comunicare Între procese;
• posibilități de sincronizare a proceselor.

Limbajele concurente sunt de obicei orientate funcție de o anumită arhitectură: sistem monoprocesor, multiprocesor sau sistem distribuit.

Pentru o cât mai bună înțelegere a modului de construcție a algoritmilor paraleli, se consideră următoarea problemă din viața cotidiană (Williams, 1990).

*Problema Familială

. O familie, compusă din Tata, Mama și copii Ioan, Toma și Simona, a terminat prânzul. Rămâne de curățat masa, spălat vasele, șters și pus la loc în dulap.

Soluții:

Există un număr de soluții care depinde de numărul de persoane (sau procesoare!) care sunt disponibile. Se remarcă următoarele:

Modul secvențial cu utilizarea unei persoane (procesor serial). Mama curăță masa, spală vasele și le pune în dulap, în timp ce Tata duce copii în parc. Modul secvențial utilizand patru persoane (procesoare pipe-line):

Tata curăță masa când s-a terminat prânzul; Ioan spală vasele, când tata a terminat de curățat; Toma șterge vasele, când Ioan a terminat; Simona le pune în dulap, când Toma a terminat; Mama pleacă la cumpărături!

Modul banda rulanta (pipe-line) utilizând patru persoane (procesor vectorial): Tata ia unobiect de pe masă, i-l dă lui Ioan și pleacă să aducă altul; Ioan spală obiectul primit, i-l dă lui Toma și așteaptă să primească alt obiect de la Tata; Toma șterge obiectul primit, i-l dă lui Simona și așteaptă să primească un alt obiect de la Ioan; Simona șterge obiectul primit și așteaptă să primească altul de la Toma. Mama îi privește cu admirație!

Din păcate, pot să apară probleme dacă Ioan spală încet vasele. Datorită sincronizării, ceilalți trebuie să aștepte după el!

Modul de utilizare a mai multor persoane (procesor matricial). Se presupune că familia este suficient de numeroasă ca fiecare să fie responsabil de un singur obiect de pe masă. Șeful familiei direcționează orice mișcare determinând fiecare persoană să facă simultan același lucru. Dacă șeful spune"curățați", fiecare va lua un obiect de pe masă. Când șeful spune "spălați", fiecare va spăla obiectul său ș.a.m.d. Șeful poate decide ca anumiți membrii ai familiei să nu lucreze. De exemplu, poate cere să fie spălate numai 5 pahare, astfel încât o serie de membrii rămân momentan fără activitate. Modul selectiv de transmitere a mesajelor (procesare paralela cu transmitere de mesaje). Obiectele care se curăță sunt "mesaje". Spre deosebire de modelul anterior, în care mesajele sunt transmise unidirecțional, mesajele pot fi transmise în mai multe direcții Dacă un obiect este curat, Tata îl transmite direct lui Simona; Dacă Toma primește un obiect murdar, îl returnează lui Ioan. Transmiterea obiectelor se poate face printr-un spațiu rezervat comunicării (masă, zonă tampon, buffer) care admite o anumită încărcare . Modul masa comuna (procesare paralela cu memorie comună). Obiectele murdare, ude sau curate stau pe aceeași masă. Fiecare persoană dispune de un spațiu mic de depozitare. Astfel, anumite obiecte, ca cele din apa de spălare, nu sunt accesibile tuturor persoanelor, numai cele de pe masă. Este necesară o atenție sporită pentru a nu re-spăla sau re-șterge lucrurile curate, respectiv uscate. Soluția grupului de procesoare. Modele similare se pot construi înlocuind oamenii cu procesoare. Modelele depind de numărul și tipul elementelor de procesare.

• Un exemplu similar, din viața cotidiană, a fost propus de T. Jebeleanu:

O companie în care șeful lucrează zi și noapte, pe când cei 1000 de angajați nu lucrează numai când șeful vine în biroul lor.

Modalitățile de creștere a eficienței activității din companie sunt:angajarea mai multor persoane (mai multă memorie), activitatea este imbunătățită, dar eficiența descrește;

• angajarea unui nou șef mai competent (un CPU mairapid) -efectul este similar cu cel din cazul anterior;
• seful este suplinit de mai mulți directori (procesoare) cu sarciniprecise: unii

aduc informațiile de la angajați, alții le prelucrează, alții decid unde să fie trimise rezultatele, alții transmit rezultatele *acești directori lucrează în paralel!

• se angajează șefi de echipă (memorii cache care introduc un anumit paralelism în utilizarea hardware-ului, de partea memoriei);
• se unesc mai multe companii (paralelism în sisteme cu granulație mare) -intervin probleme de comunicare între șefi, iar organizarea întregului ansamblu este mai dificilă decât problema inițială a organizării companiei mici.

Clasificarea sistemelor paralele

Clasificarea cea mai des utilizată este următoarea (clasificarea Flynn). Conform acestei clasificări calculatoarele paralele aparțin unuia din următoarele patru sisteme:

• SISD: sistem cu un singur set de instrucțiuni și un singur set de date;
• SIMD: sistem cu un singur set de instrucțiuni și mai multe seturi de date;
• MISD: sistem cu mai multe seturi de instrucțiuni și un singur set de date;
• MIMD: cu mai multe seturi de instrucțiuni și mai multe seturi de date.

Sistemele paralele actuale fac parte din categoria SIMD sau MIMD. In primul caz procesarea paralelă are loc în pași sincronizați (sistemul este condus printr-un unic controlor -respectă același tact dat de un ceas comun), iar în cazul al doilea, în pași independenți (fiecare procesor are propriul controlorul -ceas propriu).

Modele de programare paralelă

Productivitatea actualelor paradigme de programare paralele(shared memory/message passing)este una scazuta. Creare_thread, sincronizare_threads, alocare Shared_Mem, Excl_Mut(lock/unlock). Aceste modele sunt nesatisfacatoare, conducand la o programare, testare si depanare extreme de dificila. Nu iau in considerare eterogenitatea arhitecturii iar scalabilitatea acestor modele este una scazuta.

Modele productive, performante dar si simple de programare paralela pe sisteme multicore si manycore.

Metode de evidentiere a paralelismelor la nivelul limbajelor de programare. Sa se puna in evident paralelismele inter-thread-uri, alocarile de memorie, accesul la zonele de date partajate si modurile de sincronizare.

Transactional Memory TM Tranzactia constituie o secventa de cod care excuta in mod speculative, mai multe citiri si scrieri la nivelul unei memorii partajate. Tranzactia este atomica (se executa din punct de vedere logic in totalitate sau deloc), consistent(din punct de vedere al variabilelor partajate inter-tranzactii) si durabila (odata inceputa, nu mai poate fi abordata).

Speculativ-rularea programului nu tine cont de sectiunile critice. Daca apar conflicte pe variabilele partajate se vor detecte-firele violate isi vor relua executia tranzactiilor-roll-backs (checkpoint). TM simplifica mult tehnicile de excluziune mutual din programarea paralela. Avantajul principal nu il constituie atat performanta rularii, cat corectitudinea acesteia,chiar si in conditiile în care programatrul efectueaza in mod eronat paralelizarea aplicatiei. Productivitatea si facilizarea programarii constituie alte obiectiveimportante associate acestui concept. Stanford-Transactional Memory Coherence and Consistency,o memorie tranzactionala implementat in hardware-Protocoalele de coerenta se implementeaza la nivelul tranzactiei si nu la nivelul scrierilor individuale. Consortiul FP7 NoE HiPEAC implementeaza conceptual TM in GCC.( hipeac.net)

Bibliografie

• Introduction to Parallel Computing-Frank Willmore(Texas Advanced Computing center-TACC)
• https://computing.llnl.gov/tutorials/parallel_comp/ Arhivat în 10 iunie 2013, la Wayback Machine.
• Carte Algoritmi de Calcul Paralel-Bogdan Dumitrescu(Sept.2001)
• http://vega.unitbv.ro/~romanca/AOC/Carte-Arh_Calculatoarelor.pdf Arhivat în 14 septembrie 2014, la Wayback Machine.
• https://computing.llnl.gov/tutorials/parallel_comp/#Whatis Arhivat în 10 iunie 2013, la Wayback Machine.
• http://webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2009.pps Arhivat în 19 februarie 2012, la Wayback Machine.