Algoritmi de calcul paralel

În programare un algoritm de calcul paralel sau concurent, în opoziție cu unul secvențial, este un algoritm care poate fi executat (simultan) pe porțiuni pe mai multe mașini de calcul, apoi reasamblat pentru aflarea rezultatului final.

Algoritmii de calcul paralel sunt importanți datorită îmbunătățirilor aduse sistemelor de calcul multiprocesor. În general e mai ușor să construiești un singur microprocesor rapid decât o serie de microprocesoare lente care îndeplinesc aceeași funcție. În prezent creșterea vitezei unui singur procesor nu mai este posibilă atingăndu-se pragul superior în ceea ce privește mărimea și temperatura de funcționare. Atingerea acestui prag face practică implementarea de sisteme multiprocesor și pe sistemele de dimensiuni reduse cum ar fi calculatoarele personale.

Motivație

Conceptul de paralelism a fost investigat în ultimele trei decenii. În trecut, calculul paralel rămăsese la nivel de concept, deoarece costurile inițiale legate de implementare erau ridicate. Din aceste cauze nu era practică investitia inițială într-un sistem de calcul paralel. În ultimii ani odată cu scaderea costurilor tehnologiei au apărut o multitudine de mașini de calcul care pot reduce timpul de rezolvare al problemelor prin implementarea unor algoritmi de calcul paralel.

Problematica programării paralele

Orice rezolvare de problemă prin programare paralelă, necesită în prealabil determinarea necesității adoptării unei soluții paralele, deoarece pot exista soluții de rezolvare secvențiale mai eficiente. Un exemplu de problemă de calcul paralel ar fi simularea unui cutremur și determinarea punctului cel mai afectat de acesta. Pe de altă parte calculul seriei Fibonacci folosind formula: F(n) = F(n-1) + F(n-2) nu poate fi făcut folosind un algoritm paralel deoarece fiecare termen depinde de cel anterior. Următorii pași presupun:

• Identificarea părților paralelizabile ale programului
• Identificarea botellneck-urilor
• Identificarea potențialilor inhibitori ai paralelismului. Un exemplu de astfel de inhibitor ar fi acela de dependență al datelor, așa cum am demonstrat în problema seriei lui Fibonacci
• Investigarea cât mai multor algoritmi de calcul paralel, unele soluții fiind mai eficiente decât altele.

Exemple de aplicații

• Modelare și simulare: prognoza meteo, dinamica moleculară
• Inteligența artificială: rețele neuronale
• Grafica: Multimedia, realitate virtuală, cinematografie
• Motoare de căutare

Proiectarea unui algoritm paralel

Una dintre cele mai importante trăsături ale unui algoritm paralel este divizarea problemei în subprobleme care pot fi distribuite pe mai multe taskuri. Pentru proiectarea unui algoritm paralel se pot considera o serie de abordări. Prima ar fi paralelizarea unui algoritm secvențial deja existent. Pentru aceasta va trebui să se determine paralelismul care apare în mod natural în cadrul unui algoritm secvențial . Uneori, se preferă găsirea unei soluții diferite de cea oferită de algoritmul secvențial ceea ce presupune o regândire a întregului algoritm. Indiferent de modul de abordare în cadrul unui algoritm paralel nu se pot ignora o serie de considerații importante. Una din acestea este costul de comunicație între procese. Dacă la un algoritm secvențial costul sau complexitatea este exprimată în spațiu (mărimea memoriei ocupate) și timp (numărul de cicli de ceas) necesar pentru a executa un program, la cel paralel trebuie luat în considerare și modul în care se comunică între procese.

Problema comunicației

Există unii algoritmi de calcul paralel care nu au nevoie de comunicare între procese. Spre exemplu dacă ne imaginăm un algoritm paralel care face conversia unei imagini color în una alb negru. Datele din acea imagine pot fi distribuite pe mai multe taskuri independente. Acest tip de probleme sunt denumite "embarrassingly parallel" (paralelism jenant) deoarece comunicarea ]între taskuri este foarte redusă. Cei mai mulți algoritmi paraleli sunt algoritmi complecși în care comunicația între procese are o importanță majoră. Complexitatea algoritmilor paraleli este calculată în funcție de memoria folosită și timp. Ei trebuie să mai optimizeze folosirea unei alte resurse, comunicarea între procese/procesoare. Sunt două modalități prin care procesele/procesoarele comunică: Memorie partajată sau Folosind mesaje. Modelul cu memorie partajată se referă la programarea într-un mediu multiprocesor pentru care comunicația între procese se realizează prin intermediul unei memorii comune. Modelul cu transfer de mesaje este adecvat implementării unui algoritm paralel într-o rețea de calculatoare.

Pentru ca un program să poată fi executat în paralel acesta trebuie descompus într-o serie de procese. Aceasta descompunere presupune partiționarea algoritmului și alocarea proceselor. Partiționarea reprezintă specificarea setului de taskuri care implementează algoritmul în modul cel mai eficient pe o mașină de calcul paralel. Alocarea reprezintă modul de distribuire a task-urilor procesoarelor.

Partiționarea problemei

Granularitatea unui algoritm

Performanța unui algoritm de calcul paralel depinde de granularitate. Aceasta se referă la mărimea task-ului în comparație cu timpul necesar comunicației și sincronizării datelor. Dacă timpul necesar comunicației și sincronizării este mai mare decât timpul de execuție al task-ului atunci granularitatea este mică. O soluție este partiționarea programului în taskuri de dimensiuni mai mari cu o granularitate grosieră. Dezavantajul acestei metode este reducerea gradului de paralelism. Îmbunătățirea performanțelor unui algoritm de calcul paralel se face prin găsirea unui compromis între mărimea task-ului și consumul suplimentar de resurse. De obicei este găsită o corelare între numărul de taskuri, dimensiunea acestora și menținerea la minimu necesar a consumului suplimentar de resurse. Cea mai bună granularitate este cea obținută prin adaptarea algoritmului pe platforma hardware pe care rulează. În majoritatea cazurilor overhead-ul asociat comunicațiilor și sincronizării este mare în comparație cu timpul de execuție caz în care se preferă o granularitate grosieră. Partiționarea unui algoritm se poate face în două moduri:

1. Statică: Partiționarea se face înainte de execuție. Avantajul acestei metode este acela că necesită un volum redus de comunicații. Pe de altă parte metoda aceasta prezintă dezavantajul ca gradul de paralelism să fie dat de datele de intrare.
2. Dinamică: Generarea task-urilor este făcută în timpul de execuție al programului. Avantajul acestei metode este dat de menținerea procesoarelor ocupate cu prețul creșterii volumului comunicației dintre procese.

   

   Alocarea task-urilor în funcție de disponibilitate

Alocarea

Alocarea reprezintă distribuirea de taskuri procesoarelor. Planificarea ca și în cazul partiționării poate fi statică sau dinamică. În cazul alocării statice sarcinile și ordinea de execuție sunt cunoscute înainte de execuție. Algoritmii de calcul paralel ce folosesc planificarea statică necesită un volum mic de comunicare între procese potrivită pentru cazurile când costurile de comunicație este mare. În cazul planificării dinamice alocarea sarcinilor este făcută la rulare. Această tehnică permite distribuirea uniformă a încărcării procesoarelor și oferă flexibilitate în utilizarea unui număr mare de procesoare. Astfel dacă un procesor termină mai repede task-ul alocat i se poate atribui un alt task mărind în acest mod eficiența algoritmului.

Dezavantaje:

• volumul de "overhead" este mare
• modul de execuție este greu de urmărit
• analiza performanțelor devine dificilă, ca urmare a alocării task-urilor în timpul rulării.

Limitele programării paralele

Conform legii lui Amdahl accelerarea unui program este dată de următoarea formulă: $acc={\frac {1}{(1-P)}}$, unde P reprezintă porțiunea din cod care poate fi paralelizată. Dacă nici o porțiune a programului nu poate fi paralelizată atunci accelerarea este 1 (algoritm secvențial). Daca P=1 (tot codul poate fi paralelizat), atunci accelerarea este infinită (cel puțin teoretic). Dacă luam în considerare că un algoritm paralel rulează pe mai multe procesoare obținem următoarea formulă:$acc={\frac {1}{{\frac {P}{N}}+{S}}}$, unde P reprezintă partea din algoritm care poate fi paralelizată, N reprezintă numărul de procesoare și S partea care nu a fost paralelizată.Cu toate că un algoritm paralel are limitele sale conform celei de-a doua formule putem concluziona că aceștia sunt foarte eficienți în rezolvarea problemelor de dimensiuni mari, în care partea secvențială rămâne neschimbată.

Factorii ce afectează performanța algoritmilor paraleli:

• Încărcarea neechilibrată a porcesoarelor:
  1. Imposibilitatea împărțirii in taskuri perfect egale
  2. Variația gradului de paralelism în cadrul algoritmului
• Calculele suplimentare ce apar în cazul în care cel mai rapid algoritm secvențial nu poate fi paralelizat și se alege un algoritm paralel greoi, dar paralelizabil
• Comunicația între procese
• Concurența la setul de date partajate

Bibliografie

• en Ian Foster: Designing and Building Parallel Programs, 1995, Addison Wesley Arhivat în 14 octombrie 2006, la Wayback Machine.
• Noțiuni de programare paralelă și algoritmi paraleli^{[nefuncțională]}
• en Introduction to Parallel Computing Arhivat în 11 mai 2011, la Wayback Machine.
• en The Landscape of Parallel Computing Research: A View From Berkeley
• en Parallel Computing Research at Illinois The UPCRC Agenda Arhivat în 9 decembrie 2008, la Wayback Machine.
• en Design de algoritmi paraleli
• A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to Parallel Computing, Second Edition, 2003, AddisonWesley