UNIVERSITATEA "VASILE ALECSANDRI"

din BACĂU
FACULTATEA de ŞTIINŢE

ALGORITMI PARALELI Şl
DISTRIBUIŢI
Note de curs

COLECŢIA
ŞTIINŢE

Gloria Cerasela Crişan

® Editura ALMA MATER - BACĂU

2014
 U n i v e r s i t a t e a „ V a s i l c A l e c s a n d r i " din Bacău
Facultatea de Ştiinţe
D e p a r t a m e n t u l de M a t e m a t i c ă , I n f o r m a t i c ă şi Ştiinţele E d u c a ţ i e i

Algoritmi paraleli şi distribuiţi

Note de curs

Universitatea din Bacau

Universitatea
.VASILE A L E C S A N D R T
din Bacâu
BiDlioteca
Cota IV

[Link]. univ. dr. Gloria C e r a s e l a C r i ş a n

Bacău
2014
 CUPRINS

Introducere 5

1. L i m i t e l e p r o c e s ă r i i s e c v e n ţ i a l e şi n e c e s i t a t e a 7
programării paralele sau distribuite
1.1 Arhitectura de tip von Xeumann 7
1.2 Calcul concurent, calcul paralel, calcul distribuit 8
1.3 Caracteristicile aplicaţiilor concurente 12
1.4 Metode de scriere a aplicaţiilor concurente 16

2. P a r a l e l i s m i m p l i c i t 19
2.1. Procesare de tip linie de asamblare 19
2.2. Procesare super-scalară 20
2.3. Procesare cu spaţii mari de memorie 22
2.4. Folosirea ierarhiilor de memorii cache 23
2.5. Utilizarea datelor contigue 24
2.6. Software-ul şi paralelismul implicit 25

3. Paralelism explicit 27
3.1. Controlul în aplicaţiile paralele 27
3.2. Comunicaţiile în aplicaţiile paralele 30

4. R e z o l v a r e a u n e i p r o b l e m e p r i n c a l c u l c o n c u r e n t 43
4.1. Graful de precedenţă 43
4.2. Metode de descompunere a rezolvării unei probleme 46

5. T e h n i c i e f e c t i v e d e p a r a l e l i z a r e 49
5.1. Paralelizarea calculului numeric 49
5.2. Paralelizarea rezolvării de probleme prin programare 54
dinamică
5.3. Paralelizarea sortării şi a problemelor conexe 59

6. P r o b l e m e a c t u a l e a l e c a l c u l u l u i p a r a l e l 69
6.1. De la TSP la MDPVRPTW 69

6.2. Potenţialul actual al calculului paralel 75

7. P r o b l e m e a c t u a l e a l e c a l c u l u l u i d i s t r i b u i t 77

Bibliografic 79

3
 Introducere

Complexitatea lumii în care trăim, globalizarea şi necesitatea deciziilor rapide şi

corecte au condus la dependenţa aproape totală a societăţii actuale de sistemele de calcul şi de
comunicaţii. Puţine sunt zonele de pe glob lipsite de „invazia" reţelelor de calculatoare sau a
telefoanelor mobile, dar influenţa indirectă a tehnologiei actuale este omniprezentă. De
exemplu, zone nelocuite sunt cartografiate cu ajutorul sateliţilor, modelele climatice descriu
evoluţia condiţiilor atmosferice de pe întregul glob, sistemele gco-staţionarc permit
localizarea cu o precizie uimitoare, chiar spaţiul extraterestru este acum studiat.
Sistemele de calcul individuale, reţelele de calculatoare şi dispozitivele de
comunicaţie sunt astăzi ajutoare nepreţuite, indispensabile societăţii in care trăim, iar cei care
contribuie la utilizarea şi mai ales la dezvoltarea lor rezolvă eficient problemele actuale şi
construiesc lumea de mâine. De aceea, specialiştii în tehnologie, calculatoare şi informatică,
bazându-se pe solide cunoştinţe, cooperează pentru a oferi celor interesaţi produse, modele şi
soluţii.

Care sunt specializările actualc oferite de universităţi?

Dezvoltarea fără precedent a metodelor şi a maşinilor electronice de calcul a condus la
existenţa în România a trei specializări de licenţă, care se întrepătrund, dar care oferă viziuni
şi compctcnţc diferite:
• Tehnologia informaţiei, care se referă în special la partea hardware, de arhitectură
şi reţele de calcul;
• Ştiinfa calculatoarelor, care se ocupă cu fundamentarea teoretică, ştiinţifică a
modelelor, realizând legătura cu matematica şi ştiinţele computaţionale, axându-se
pe proiectarea algoritmilor şi inteligenţa artificială;
• Informatica, axată pe software şi legătura cu utilizatorii, care asigură prin
limbajele de programare interfaţa între problemele vieţii reale, metodele teoretice
de abordare a lor şi resursele disponibile.

Cui se adresează acest curs?

Cursul „Algoritmi paraleli şi distribuiţi" arc drept scop familiarizarea studenţilor cu
programarea concurentă, pentru a putea înţelege şi utiliza eficient sistemele moderne de
calcul.
Cursul de faţă se adresează studenţilor Universităţii „Vasile Alecsandri" din Bacău,
atât celor din anul III de la specializarea Informatică a Facultăţii de Ştiinţe, cât şi celor de la
specializarea Calculatoare şi tehnologia informaţiei de la Facultatea de Inginerie. Cuprinsul
cursului urmează atât fişa disciplinei în vigoare, cât şi suporturile de curs recunoscute pe plan
mondial şi cele predate la alte universităţi din ţară.

5
 Capitolul 1

Limitele procesării secvenţiale şi necesitatea p r o g r a m ă r i i

paralele sau distribuite

Modelul clasic de execuţie a unei aplicaţii constă in procesarea sa secvenţială,

instrucţiune cu instrucţiune. Astfel, se consideră că există un indicator al instrucţiunii aflate în
execuţie, care parcurge aplicaţia (nu neapărat in ordine), începând cu prima instrucţiune.
Instrucţiunea curentă preia din memorie datele ncccsarc, Ic prelucrează (pc procesorul
sistemului de calcul), apoi realizează în memorie actualizările ncccsarc (dacă este cazul) şi
predă următoarei instrucţiuni care trebuie cxccutatc controlul unităţii de procesare. Acest
grup de activităţi sc realizează până când aplicaţia se închcic. Acest model descrie execuţia
unei aplicaţii pc un sistem de calcul mono-procesor, realizat conform arhitecturii von
Ncumann.

1.1. Arhitectura de tip von Neumann

Savantul american de origine ungară John von Neumann a propus în 1945 cel mai
cunoscut model al unui calculator. Această descriere conceptuală, realizată când tehnologia
era la nivel de pionierat, este şi astăzi considerată una dintre cele mai importante etape în
dezvoltarea ştiinţei calculatoarelor.
Modelul descris în [13] (cunoscut mai târziu sub
numele de modelul von Neumann sau arhitectura
Princeton) stabileşte următoarele caracteristici ale unui
sistem de calcul:
• Calculatorul este compus din: memorie, unitatea
aritmetico-logică, unitatea de control şi
periferice;
• in timpul execuţiei, programul este stocat în
memorie;
• La un anumit moment, memoria poate fi
acccsată fie dc unitatea de control, fie de
unitatea aritmetico-logică;
• Instrucţiunile programului sc execută secvenţial.

John von Neumann

(1903-1957)

La momentul respectiv, sistemul dc calcul era considerat independent, procesorul

(alcătuit din unitatea aritmetico-logică şi unitatea dc control) realizând accesul la memorie.
Pe lângă faptul că instrucţiunile programului se execută secvenţial, memoria nu poate fl
accesată simultan de unitatea de control şi de unitatea aritmetico-logică (adică nu se pot
produce modificări în starea programului simultan cu transferul de date), deoarece există o

7
singură magistrală de date între memorie şi procesor. O alternativă la modelul von Neumann
este modelul Harvard, caracterizat prin tipuri diferite de memorii: unul pentru date (de tip
citire/scriere) şi altul pentru program (de tip read-only). Astfel, se pot executa simultan
schimbări in starea programului şi citiri/scrieri dc date. Modelul Harvard modificat permite
ca memoria dedicată programului să fie tot de tip read/write. Acest model este utilizat de
diverşi producători de procesoare (familia ARM9 este un exemplu) sau este folosit pentru
dispozitive specializate (microcontrolere).
Dezvoltarea tehnologică ulterioară şi necesităţile tot mai mari de putere de calcul au
evidenţiat limitele modelului von Neumann. astfel că au apărut diverse metode de creştere a
vitezei de execuţie a unui program. Dc exemplu, memoriile intermediare de tip cache oferă
acces mai rapid la datele necesare execuţiei unei instrucţiuni. Posibilitatea accesului rapid la
date şi dezvoltările hardware au dus la realizarea în 2005 a primelor proccsoare dual-cores.
carc sunt de fapt două procesoare cu aspect fizic unitar, care posedă un sistem de memorii
cache. Au urmat apoi proccsoare din ce în ce mai complexe, cu arhitecturi care utilizează
ierarhii din ce în ce mai dezvoltate de memorii cache. cum este cel din figura 1.

UiJOîîWi l2.2C4e*6. u (JwerB.

[Link]) 111 *4M. iiii^re» LII > 64KB i

| llaiUKB) lloO«K>t [ [Link]» j ii- • L1C.W6. Licaere. LleiUl:6< | HoiMKBI "|

Cote PSC Cot P«2 Cc<» F9> Cot Psj C«f»5 Coe Cot
KI«C ' Fttsl FCF*: Ftrsj KMS FLfeT
1 f j
Figura 1. Arhitectura procesorului 8-cores AMD FX - Bulldozer [18]

La un alt nivel arhitectural, aceeaşi problemă a necesităţii de resurse de calcul din ce

în ce mai puternice, a fost rezolvată în anii 70 ai secolului trecut prin apariţia calculatoarelor
multi-proccsor: sisteme de calcul carc includ mai multe procesoare alăturate, concctate prin
magistrale şi care partajează memorie comună, astfel încât manevra datelor să fie rapidă.
Supercalculatoarele actuale sunt sisteme de calcul multi-procesor cu caracteristici uimitoare
fiind utilizate in cercetarea fenomenelor globale [28].
Din momentul în care s-au putut cupla mai multe procesoare s-a deschis posibilitatea
executării pe un sistem de calcul a mai multor aplicaţii simultan. De asemenea, conectarea
calculatoarelor independente în reţele a realizat efectiv modelul cuplării prin magistrale
externe plăcilor de bază a mai multor sisteme independente de calcul. Programarea
secvenţială devine de acum o opţiune, nu o cerinţă (impusă de modelul von Neumann).
Calea către programarea paralelă sau distribuită a fost deschisă dc dezvoltarea
hardware, de explozia comunicaţiilor electronice şi de ncccsităţilc în continuă creştere ale
societăţii.

1.2 Calcul concurent, calcul paralel, calcul distribuit

Sistemul de operare al unui calculator mono-procesor este pus în situaţia de a

coordona mai multe procese şi a le executa în mod concurent. De exemplu, transferurile dc
date dc la/către perifericele de intrarc-ieşirc, execuţia unor aplicaţii, ctc. se realizează

8
simultan din punctul dc vedere al utilizatorului, fără ca acesta să observe sincope. Pc dc altă
parte, arhitectura mono-procesor impune execuţia unei singure aplicaţii la un anumit moment
de timp. Metoda prin care se realizează aceste procese sc numeşte multitasking şi înseamnă
partajarea timpului de lucru al procesorului în intervale disjuncte şi alocarea acestor intervale
diverselor proccsc aflate în execuţie. Cum aceste intervale sunt foarte scurte, utilizatorul nu
percepe schimbările realizate de sistemul de operare, ci arc impresia că toate procesele se
desfăşoară simultan.

Calculul concurent este o caracteristică software, opusă calculului serial, care permite
execuţia simultană a mai multor aplicaţii. Dc exemplu, pc un procesor mono-nuclcu, calculul
concurent sc poate realiza prin muhitasking (programele în execuţie primesc intervale
disjuncte de timp pentru accesarea procesorului; la fiecare moment dc timp un singur
program se execută; la expirarea timpului alocat, starea programului în execuţie se salvează şi
se dă controlul procesorului altui program; aceste schimbări se realizează des. astfel încât
utilizatorul arc senzaţia că toate programele sc cxccută în paralel). Pe un calculator multi-
procesor, care deci este alcătuit din mai multe procesoare care partajează memorie comună,
calculul concurent se realizează efectiv sub forma calculului jxiralel (care este deci o
proprietate hardware). Pc dc altă parte, în cazul reţelelor de calculatoare, alcătuite din sisteme
independente, cu memorii independente, calculul concurent capătă forma calculului distribuit
(care este, de asemenea, caracteristică hardware).

După modelul dc succes al sistemelor dc operare, care gestionează simultan zeci de

proccsc. programatorii actuali ar trebui să cunoască limbajele de programare care permit
execuţia în paralel. A scrie o aplicaţie paralelă este insă mult mai dificil decât a scrie o
aplicaţie secvenţială, deoarece necesită înţelegerea profundă a problemei, descompunerea
acesteia în sub-problemc care se pot rezolva în paralel, rezolvarea sub-problcmelor şi
compuncrca rezultatului problemei iniţiale din soluţiile sub-problemelor. Se poate întâmpla
ca o aplicaţie paralelă să fie, în anumite cazuri, mai incficicntă decât aplicaţia secvenţială.
Câştigurile aduse însă dc aplicaţiile paralele cficicnte, proiectate şi realizate pentru abordarea
unor probleme complexe, ale vieţii reale, sunt însă motive temeinice pentru ca programatorii
să înveţe limbajele calculului paralel şi distribuit.

Un exemplu în acest sens este studiul vitezei dc execuţie a aplicaţiei secvenţiale şi a

celei paralele utilizate pentru calcularea unui termen al şirului lui Fibonacci. Vom nota cu
Fib(n) termenul generic al şirului lui Fibonacci; acesta sc pate calcula cu formula rccursivă:

Fib{ 0) = Fib( 1) = I

Fib{n) = Fib{n -1) + Fib{n - 2), Vn> 2

Pentru a calcula în mod iterativ valoarea lui Fib(n) se poate folosi următoarea metodă:
Functionfin)
if(n < 2) return 1
x- 1
y=l
z =2
k =2
while (k < n)
x=y

9
 k =k + I
return z

Această metodă (iterativă) are avantajul că urmează şablonul matematic al construirii

valorilor şirului din aproape în aproape. Există însă o altă metodă, mai apropiată dc obiectul
acestui curs. care face trecerea spre abordarea concurcntă a acestei probleme, şi anume
metoda recursivă:

Function g(n)
if(n < 2) return 1
return g(n - l)+g(n - 2)

Această metodă ncccsită cunoştinţe mai avansate dc programare şi este mai înceată
(sau produce depăşiri dc memorie) la execuţia în limbajul C, chiar pentru valori comune ale
lui n. Avantajul ei este însă că se auto-apelează (pentru n > 2) cu factor dc multiplicare 2.
Aceasta înseamnă, de exemplu, că pentru aflarea lui #(8) se lansează o copie a sa care
calculează g(7) şi încă una pentru găsirea lui #(6). Fiecare dintre accstca lansează alte două
execuţii, ctc.
în tabelul 1 este prezentat modul în care lucrează funcţia g dacă este apelată pentru
valoarea n = 4. Coloanele tabelului arată modul de încărcare pe stivă a copiilor Iui g, până
când se calculează valoarea g(4). Rândurile tabelului arată succcsiunea temporală a cxccuţiei
proccdurii g pentru valoarea 4. Apelul 1 este apelul procedurii, care lansează imediat pc stivă
apelul 2, adică o copie a codului pentru valoarea n = 3 şi apoi intră în aşteptare (idle) până
când primeşte valoarea 3), adică 3. Apelul 2 lansează o nouă copie a aplicaţiei, pentru a
calcula g(2), etc. Starea dc execuţie este indicată prin culoarea de fundal gri; starea idle a unui
anumit proces este indicată prin diagonalele trasate. Dc exemplu, apelul 3 ocupă timp de 4
unităţi dc timp o unitate dc procesare (începând cu momentul 3), din carc jumătate stă în
aşteptare (este idle). Se observă că pe stivă, pentru n = 4, vor exista cel mult 4 copii în
execuţie şi că unele copii stau in aşteptare destul de mult timp. astfel explicându-se faptul că
execuţia lui g este mai înceată decât cea a l u i / pentru aceeaşi valoare a lui n.

Apel 1 Apel 2 Apel 3 Apel 4

(main)
realizat de: - Apel 1 Apel 2 Apel 3
Momente de
timp
1 8(4)
2 8(3)

X
3 8(2)
4 g(D

X
5 return 1
6 8(1)= 1
7 8(0)
8 return 1
9 8(0)-1
10 rctum 2
11 8(2)-2

10
 Apel 1 Apel 2 Apel 3 Apel 4
(w ain)
realizat de: Apel 1 Apel 2 Apel 3
\ 7
-

12 B(0 1
13 return 1

/ \
14 g(l)=l
15 rctum 3
16 g(3) = 3
17
\ /
g<2)
18
\ /
8(0
19 return 1
20 V/ g(D=l
A
/ \
21 g(0)
22 return 1
/ \
/ \
23 K(0)=1
24 return 2
25 8(2) = 2
26 return 5
Tabelul 1. Evoluţia temporală a apelului recurşi v g(4)

Trecerea spre execuţia pe mai multe fire urmează modelul din tabelul 1 şi presupune
că sunt disponibile unităţi dc procesare astfel încât să poată prelua execuţia la nevoie şi astfel
firele dc cxccuţic să nu aştepte mai mult decât este necesar. Pentru lansarea succesivă a
apelurilor se introduc două funcţii specifice calculului concurent, care permit multiplicarea
execuţiei şi respectiv închiderea tuturor firelor lansate şi continuarea execuţiei în clasicul mod
serial. Aceste două noi comenzi sunt:
• spawn - procedură prin care un proces (părinte) lansează un proces (fiu)
• sync - proccdură prin care se aşteptă încheierea tuturor proceselor lansate in apelul
curent prin spawn şi continuarea numai cu procesul părinte.
Folosind aceste două noi comenzi, procedura recursivă concurentă pentru calculul
valorii generice din şirul lui Fibonacci devine:

Function h(n)
i f f n < 2) return 1
x = spawn h(n- 1)
//dc aici aplicaţia arc 1 fir-părinte + 1 fir-fiu
y • spawn h(n - 2)
//de aici aplicaţia are 1 fir-părinte + 2 fire-fiu
sync
//aici se ajunge după ce fii se încheie
return x + y

în tabelul 2 sunt evidenţiate apelurile succesive realizate de spawn şi sync, pentru

fiecare apel este menţionat şi apelul său-părinte (de exemplu, apelurile 4 şi 5 sunt lansate de
apelul 2). Apelul principal h(4) lansează iniţial în execuţie pe altă unitate de procesare
calculul variabilei x ca valoarea întoarsă la apelul h(3) şi continuă execuţia lansând la
momentul imediat următor, pe o altă unitate dc procesare, calculul valorii variabilei y ca
valoarea întoarsă dc /;(2). Fiecare dintre aceste apeluri ocupă apoi alte două unităţi de
procesare. Se observă că la momentul 5 de timp. sunt necesare 9 unităţi de procesare, din carc

9
5 lucrează şi 4 sunt în starea idle. Se observă de asemenea că apelul /;(4) necesită 12 unităţi
de timp pentru execuţie, pe când apelul #(4) are nevoie de 26 unităţi de timp şi de cel mult 4
execuţii simultane.
La fel ca în tabelul 1, zonele gri reprezintă intervalele de timp în care procesoarele
sunt alocatc, iar zonele care au diagonale sunt intervalele de timp în care procesoarele stau in
aşteptare {idle). Observăm insă că apelul 1 avansează şi la momentul 2, când realizează
lansarea apelului 3, spre deosebire de situaţia prezentată în tabelul 1. când este deja in
aşteptare. Şi în acest caz se observă un dezechilibru al încărcării procesoarelor, dc exemplu
ultimele 5 proccsc lucrează 2 intervale de timp. pe când primul procesor este ocupat toate
cclc 12 intervale de timp.

Apel 1 Apel 2 Apel 3 Apel 4 Apel 5 Apel 6 Apel 7 Apel 8 Apel 9

(main)
fiul lui: - Apel 1 Apel 1 Apel 2 Apel 2 Apel 3 Apel 3 Apel 4 Apel 4
Momc
nte de
timp
1 h( 4)
2 />(3)
3 h( 2) h(2)

XX X
4 h( 1) AO) h{ 1)
5 return retum h(0) retum m
1 1 1
6 h( 1)=1 h( 1)=1 A(1)=1 retum retum
1 1
7 A(0)=1 h( O M
8

9 h( 2 ) - 2
X
h{iy=2
retum
2
retum
2

10

11
X rctum
3

12 rctum
5
Tabelul 2. Evoluţia temporală a apelului recursiv paralel h(4)

1.3 Caracteristicile aplicaţiilor concurente

Arhitectura von Neumann reprezintă modelul unui sistem dc calcul cu un singur

element de procesare. Natura însă a evoluat dintotdeauna prin proccsc concurente. In accst
sens pot fi considerate:
• dezvoltarea unui organism, alcătuit din organe cu rol specific, care lucrează
conform scopului lor dar şi în corelare cu celelalte organe;
• evoluţia unui sistem social (sistem complcx, alcătuit din indivizi oarecum
asemănători care intcracţionează, dc exemplu: un stup de albine, un banc de peşti,
o turmă de animale, populaţia unui contincnt, posesorii de conturi Facebook, etc.).
Acest model este preluat în zilele noastre cu succes de reţelele de calculatoare sau de
telefonie mobilă, dc sistemele intcrconectatc dc calcul care permit tranzacţiile online, dar şi

12
dc supcrcalculatoarc, carc oferă în mod curcnl acces simultan la mii de procesoare. Calculul
concurent nu este decât modelul actual a ceea ce natura face de milioane de ani: se dezvoltă
prin evoluţii simultane ale ecosistemelor, populaţiilor, evenimentelor geologice, etc.
Tehnologia ne permite ca mişcarea planetelor, evenimentele climatice, migraţiile păsărilor,
servirea clienţilor la un magazin, conduccrca corporaţiilor trans-naţionale, tranzacţiile
bancare sau vizionarea filmelor să fie acum studiate sau realizate prin sisteme de calcul
paralel sau distribuit. Globalizarea lumii în care trăim este posibilă şi datorită dezvoltării
calculului concurent.
Odată cu dezvoltarea tehnologică şi apariţia sistemelor de calcul care pot oferi acces
simultan la mai multe unităţi de procesare, cercetătorii au realizat diverse clasificări ale
acestor sisteme. Clasificarea următoare se referă la funcţionalitatea sistemelor dc calcul, deci
la modul în care aplicaţia realizează prelucrarea datelor.

Clasificarea Flynn (Michacl Flynn. 1966)

Una dintre ccle mai vechi clasificări ale prelucrărilor clectronicc consideră numărul de
prelucrări care se pot realiza simultan şi de fluxuri de date care se pot proccsa în acelaşi timp.
Conform acestei clasificări, calculul electronic se poate realiza prin:
• Single Jnstruction Singe Data (S/SD) - proccsarc serială, aplicaţia avansează
instrucţiune cu instrucţiune, pe un singur fir de execuţie, cu un singur set de date.
Un astfel de exemplu este calculul pe un PC dotat cu un procesor mono-nucleu.
• Single Jnstruction Multiple Data (S/MD) - aplicaţia avansează instrucţiune cu
instrucţiune, pe un singur fir de execuţie, procesând simultan mai multe seturi de
date. O astfel dc situaţie este întâlnită în cazul procesorului vectorial, care
manevrează simultan datele, utilizând un vector dc memorii. Astfel dc procesoare
sunt utilizate când există colecţii dc date carc ncccsită acccaşi prelucrare; dc
exemplu, procesarea grafică pentru jocuri.
• Multiple Jnstruction Single Data (MJSD) - aplicaţia constă din mai multe fire de
cxccuţic carc proccscază acelaşi set dc date. Accstc arhitecturi nu apar foarte des
în practică, unul dintre cazuri este calculul dc toleranţă zero la erori, când se
prelucrează pe mai multe fire dc cxccuţic acclaşi set de date, în vederea mascării
(eliminării) erorilor.
• Multiple Jnstruction, Multiple Data (M/MD) - aplicaţia constă din mai multe fire
de execuţie care procesează mai multe seturi de date. în general, un fir de execuţie
este alocat unui nucleu. Acest tip dc procesare este realizat de marea majoritate a
supcrcalculatoarclor din Top 500 actual [28]. La rândul lor, procesările de tip
MIMD pot fi:
O Single Program, Multiple Data (SPMD) - când copii ale aplicaţiei se
execută pe mai multe seturi de date, fiecare proces având evoluţie proprie
(deoarece seturile diferite de date conduc la trasee diferite în execuţie,
controlate de instrucţiuni i f , case/switch. while, do-while sau for). Accstca
sunt cel mai des întâlnite situaţii, când codul unei aplicaţii dcscric
procesările fiecărui fir de execuţie,
o Multiple Program. Multiple Data (MPMD) - când o aplicaţie dc tip maşter
lansează pe alte unităţi de procesare (nuclci - cores) alte aplicaţii dc tip
slave.

13
 Aplicaţiile concurente sc pot evalua folosind clasicele măsuri software, destinate
tuturor categoriilor de aplicaţii. Aceste măsuri se pot clasifica astfel:
• măsuri cantitative: număr de linii dc cod. mărimea (în biţi) a fişierului cxccutabil.
viteza dc execuţie, numărul dc orc dc programare necesare proiectării, dezvoltării
şi testării, etc.;
• măsuri calitativc: corectitudine (rezolvă problema propusă), completitudine
(rezolvă toate cazurile posibile), scalabilitatc (capabilă de a procesa chiar şi
volume de date mai mari decât cele aşteptate, sau se poate uşor dezvolta astfel
încât să le accepte), mentcnabilitate (uşurinţa in exploatare şi actualizare), etc.
Măsurile software specificc programelor care se avansează simultan pc mai multe fire
dc cxccuţic se referă atât la caracteristicile de consum total ale resurselor implicate (timp dc
procesare, număr de procesoare), cât şi la economiile realizate prin utilizarea acestora (cât
timp se câştigă dacă utilizez in paralel mai multe procesoare, decât dacă folosesc un singur
procesor). In continuare sunt prezentate câteva măsuri specifice calculului concurent.

Acceleraţia (speed-up) este raportul dintre timpul dc cxccuţic pc o singură unitate de

procesare şi timpul de execuţie pe n astfel de unităţi. Este o măsură a-dimensională, care în
mod normal este supraunitară - dacă aplicaţia are o acceleraţie subunitară. atunci varianta
paralelă nu sc justifică, deoarccc necesită un timp de execuţie mai mare decât varianta serială.
Dacă sc notează:
T(n) timpul ncccsar execuţiei pe n unităţi dc procesare (nuclci),
atunci acceleraţia are expresia:

T(n)
in cazul unei descompuneri ideale pe n fire dc cxccuţic, fără costuri suplimentare
datorate comunicaţiilor şi dacă cele n fire de execuţie reuşesc fiecare să se încheie în timpul
rp) . . . .,
, atunci acceleraţia este n. Din formula acceleraţiei sc dcducc deci că o valoare teoretică
maxima a acestei mărimi este //.
Eficienţa (jiarallel ejficiency) este o măsură derivată din acccicraţic, fiind raportul
dintre accasta şi numărul de procesoare utilizate:

n
în baza observaţiei anterioare, deducem că eficienţa unei aplicaţii concurente are
întotdeauna o valoare subunitară, iar eficienţa unei aplicaţii concurente ideale este 1.

Echilibrul (balance) sc referă la o caracteristică generală a cxccuţici pe diverse unităţi

de procesare (poate fi şi timpul necesar execuţiei), măsurată prin valorile qt 1 <i<n unde n
este numărul nucleilor:

B(n) =

De exemplu, dacă ne referim la q t 1 < / <, n ca fiind timpul de execuţie pc procesorul

/", atunci echilibrul aplicaţici h care lucrează ca în Tabelul 2 este B(n) = = 16,7%. in

general, sc urmăreşte ca aplicaţiile concurente să fie cchilibratc, adică B(n) să fie cât mai
aproape de 100%.

14
 Din punct de vedere constructiv, calculatoarelor paralele li se pot aplica diverse
măsuri: numărul de nuclei, memoria RAM. consumul de energie, viteza de procesare. O
măsură a vitezei de procesare ieşită din uz este numărul de instrucţiuni pe secundă. Cum
aceste instrucţiuni pot ncccsită intervale dc tip dc lungimi diferite pentru execuţie, acum se
utilizează numărul de operaţii in virgulă mobilă pe secundă (floating poinl operations per
second-FLOP/s).

Multiplii unităţii de măsură FLOP/s sunt:

1 kFLOP/s - IO3 FLOP/s (kilo)
1 MFLOP/s = IO6 FLOP/s (mega)
1 GFLOP/s - 10" FLOP/s (giga)
1 TFLOP/s - IO12 FLOP/s (tera)
1 PFLOP/s= 10''FLOP/s (peta)
1 EFLOP/s = IO18 FLOP/s (exa)
1 Z FLOP/s = IO21 FLOP/s (zctta)
1 YFLOP/s = IO24 FLOP/s (yotta)
Procesoarele actuale pot realiza 4 operaţii in virgulă mobilă pe unitate dc ceas (clock
cvcle). Un procesor de 2.5 GHz cu 4 nuclei poate realiza deci
4-4-2,5 GFLOP / s = 40 GFLOP / s.

Dezvoltarea tehnologică a fost surprinsă în anii '60 de o observaţie empirică, al cărei

adevăr s-a menţinut până acum. Acest enunţ este cunoscut ca Legea lui Moore (Gordon
Moore, 1965) şi trebuie înţeles ca o constatare empirică observată a Fi adevărată din 1965 şi
până azi:
Performanţele procesoarelor (măsurate prin numărul de tranzistoare care formează
un circuit integrat) se dublează la fiecare 2 ani.

Legea lui Amdahl (Gene Amdahl, 1967)

Acceleraţia aplicaţiilor paralele are o creştere sub-liniară odată cu creşterea
numărului de procesoare.
Presupunem o aplicaţie concurentă oarecare, pentru carc notăm T(\) = a + b, unde a
este intervalul de timp ncccsar execuţiei părţii nc-paralelizabile şi b este timpul ncccsar
cxccuţici părţii paralclizabile pe o singură unitate de procesare. înlocuind aceste valori în
formula acceleraţiei, obţinem:

v
' b
a+ -
n
în ca/ul unui echilibru perfect şi dacă nu sunt ncccsare alte instrucţiuni pentru
repartizarea, controlul firelor de execuţie, colectarea datelor, ctc.. atunci pe n unităţi dc
b
procesare se poate cxccuta accastă parte a aplicaţici în timpul a + ~ . Trecând la limită, avem
n
că:
,. c, , a + b
hmS(n) =
m-*m (j
Cum accastă valoare este o constantă carc depinde de aplicaţia în cauză. înseamnă că
există un prag al numărului dc procesoare începând de la care adăugarea de noi procesoare nu
mai determină o îmbunătăţire semnificativă a aecclcraţici. Această concluzie se menţine chiar
în cazul unei aplicaţii pcrfcct echilibrate.

15
Legea lui Gustafson (John Gustafson. 1988)
Pe o configuraţie hardw are dată (numărul de procesoare n fixat) se pot scrie aplicafii
paralele care au acceleraţie liniara.
Cu notaţiile anterioare avem că:

lim S(n) = lim — — - = n

b-*x b-*x a 1
— + —

b n
Deci dacă partea paralelizabilă este suficicnt de mare, atunci acceleraţia este aproximativ
egală cu numărul de procesoare. Legea lui Gustafson specifică o regulă simplă: dacă vrem să
ne apropiem dc eficienţa ideală a unei aplicaţii paralele, partea paralelizată trebuie să fie cât
mai consistentă.

Gordon Earl Moore (1929 - ) Gene Myron Amdahl (1922 - ) John Gustafson (1955 - )

1.4 Metode de scriere a aplicaţiilor concurente

Paralelizarea aplicaţiilor seriale deja scrise necesită o înţelegere profundă a problemei

rezolvate serial, pentru a obţine o aplicaţie eficientă. Cum la momentul scrierii codului nu sc
cunoaşte arhitectura pe care se va executa, programatorul ar trebui să aleagă o metodă carc să
funcţioneze cât mai eficicnt în cât mai multe cazuri, cu diverse date de intrare. Una dintre
provocările calculului concurent este proiectarea firelor dc cxecuţie astfel încât acestea să
lucreze echilibrat (conform definiţiei din subcapitolul anterior).
Un exemplu în acest sens este modul în care se adună în paralel, pe un multi-
calculator cu 4 procesoare, 16 valori numerice, stocate într-un vector a(i)lii{l6. Presupunem
că datele sunt stocate pc fiecare procesor. Dacă s-ar împărţi vectorul în 4 zone:
{fl(l),a(2),a(3),fl(4)}, {a(5),a(6),a(7),a(8)}, {<i(9),a(10),a(l l).a(12)} şi
{tf(13).a(14),0(15).a(16)}, fiecare alocată unui proccsor, atunci toate cele 4 procesoare ar fi
perfect echilibrate deoarece ar lucra acelaşi interval de timp pentru a calcula suma parţială
corespunzătoare zonei dc vector alocatc, iar la sfârşit unul dintre ele ar colecta valorile găsite
de celelalte 3 şi ar afişa rezultatul obţinut. Această metodă este cea care asigură echilibrul cel
mai bun pentru aplicaţia paralelă.
Dacă însă avem la dispoziţie 16 calculatoare legate într-o reţea locală (LAN) peer-to-
peer de tip inel şi câte o componentă a vectorului este stocată pc ficcare calculator, atunci

16
adunarea distribuita eficientă accstor valori va ţine cont şi dc timpul ncccsar comunicaţiilor.
O metodă eficientă (din punctul de vedere al încărcării procesoarelor) este prezentată în
tabelul 3. Prima dată se realizează 8 transferuri simultane de date între vecini, la finalul
cărora, de exemplu, procesorul I stochează suma valorilor a( I) şi a(2). specificată în tabel pe
primul rând ca 0(1-2). La pasul următor lucrează doar 4 procesoare care trimit valoarea
stocată către un procesor aflat la distanţă 2 (de exemplu, procesorul 3 trimite valoarea 0(3-4)
către procesorul I. care după recepţionare va aduna propria valoare stocată şi deci va
cunoaşte valoarea a( I -4).
Dacă la pasul 1 se realizează 8 transferuri între vecini. înseamnă că pe reţea se vor
înregistra 8 transferuri simultane dc date. Considerând costul comunicării unei valori intre
două calculatoare din reţea ca fiind numărul de calculatoare prin carc trccc valoarea
transferată, atunci costul realizării pasului 1 este 8. la fel ca şi în etapa a doua. Pasul 3 constă
în transferul valorilor stocatc pe calculatoarele 5 şi 12. cu cost total 8. iar în ultima etapă doar
calculatorul 16 realizează o concxiunc dc cost 1 cu sistemul 1. vecinul său, prin circularitatc.
Accastă metodă ncccsită deci 4 unităţi dc timp şi are cost 25.

pasul 0 pasul 1 pasul 2 pasul 3 pasul 4

0(1) a( 1-2) fld-4) a{ 1-8) 0(1-16)
«(2) t î T
a(3) 0(3-4) î î
0(4) t T
a<5) a(5-6) 0(5-8) î
a( 6) t î
a( 7) a( 7-8) t
0( 8) t
a( 9) i
a( 10) a( 9-10) i
a(ll) i i
a( 12) a(l1-12) 0(9-12) i
0(13) i i
0(14) 0(13-14) i i
fl(15) i i i
0(16) «(15-16) 0(13-16) 0(9-16)
cost
8*1=8 4*2 = 8 2*4 = 8 1*1 = 1
comunicaţii
cost total
25
comunicaţii
Tabelul 3. Etapele adunării distribuite a 16 valori într-o reţeapeer-to-peer

Aceste consideraţii arată că o aplicaţie simplă, de adunare a unor valori, poate fi

eficientizată doar dacă se cunosc informaţii suplimentare legate de configuraţia pe care se va
executa şi dacă programatorul ştie care este critcriul de eficientizare urmărit. Unele aplicaţii
concurente pot avea acces la un număr practic nelimitat de unităţi de procesare, altele pot
utiliza reţele de tip broadband, altele manevrează volume mari de date. care nu pot fi
transmise pe distanţe mari. în concluzie, nu există o reţetă universală pentru scrierea unei
bune aplicaţii concurente. Este nevoie de experienţă şi cunoştinţe avansate pentru a realiza
coduri paralele sau distribuite eficiente.

17
 Capitolul 2

P a r a l e l i s m implicit

Arhitectura sistemului de calcul poate fi orientată prin diverse dezvoltări tehnologice

spre creşterea vitezei de procesare. Aceste metode fizice de paralelizare alcătuiesc facilităţile
de paralelism implicit, oferite dc caracteristicile resurselor dc calcul utilizate. In contrast,
programarea concurentă, adică specificarea prin program a proccsclor care sc desfăşoară
simultan reprezintă paralelismul explicit, care va fi abordat în capitolul următor.
Paralelismul implicit speculează noile facilităţi tehnologice; acum procesoarele nu
mai execută secvenţial instrucţiunile unui program, ci există diverse metode prin care acestea
se pot suprapune temporal. Accste metode sunt:
• procesare de tip linie de asamblare
• procesare super-scalară
• folosirea procesoarelor care manevrează cuvinte lungi
• ierarhiile de memorii cache
• utilizarea datelor contigue (ţine de programare, dar foloseşte stocarea la adrese
fizice a datelor).

2.1. Procesare de tip linie de asamblare

Procesarea de tip linie de asamblare (pipelining) se referă la fragmentarea

instrucţiunilor cxccutatc pc un procesor, astfel încât să fie posibilă cxccuţia lor simultană,
asemănător lucrului pc o linie de asamblare. La nivel teoretic, se consideră că o instrucţiune
se realizează pe procesor în 5 faze: instruction fetch (1F - încărcarea instrucţiunii), decode (D
- traduccrc), data fetch (DF - încărcarea datelor) execute (E - proccsarc cfcctivă) şi write-back
(WB - scriere a rezultatului în memorie). Practic însă, ficcare procesor are propriile faze de
lucru. De exemplu, AMD FX are 15 faze pentru procesarea valorilor întregi.
Executarea unei aplicaţii, dacă operaţiile de manevră a datelor permit, s-ar putea
desfăşura la nivel optim ca în figura 2 (se execută integral 6 instrucţiuni în 10 unităţi de ceas).

Timpul
0 1 2 3 4 5 6 7 8 9
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
Figura 2. Dezvoltarea temporală pentru o proccsarc ideală dc tip pipeline

în situaţia ideală prezentată în figura 2 se observă că procesoarele modeme pot

executa în paralel mai multe faze din instrucţiuni diferite (în intervalul 5 sunt deja în execuţie

19
 toate fazele, câte una din primele 5 instrucţiuni). Această situaţie nu apare mereu în realitate,
deoarece pot apărea întârzieri. De exemplu:
• dacă instrucţiunea curentă arc nevoie de încărcarea unor date (faza DF) carc la
momentul respectiv sunt actualizate printr-o fază dc WB a unei instrucţiuni
anterioare. în acest caz aşteptarea este obligatorie.
• dacă instrucţiunea din care se doreşte cxccuţia fazei IF face parte dintr-o
instrucţiune alternativă (if-then-else), dar încă nu s-a produs faza E din aceasta,
deci la momentul respectiv nu se cunoaşte pe care ramură avansează aplicaţia. în
acest caz se pot utiliza resurse suplimentare pentru încărcarea simultană a ambelor
ramuri ale instrucţiunii i f , iar când se cunoaşte care ramură este cea aleasă, se
renunţă la cealaltă. Accastă rezolvare se utilizează în mod curent, deoarece situaţia
apare des în programare - aproximativ 15% din instrucţiunile unei aplicaţii sunt
instrucţiuni alternative. Sub numele dc descompunere speculativă, aceeaşi idee
este tratată în subcapitolul 4.2.
Proccsarca dc tip pipeline este numită şi procesare scalară, dcoarccc permite
creştcrea vitezei dc procesare liniar cu creşterca numărului dc faze din instrucţiuni diferite
care se pot executa simultan.

2.2. Procesare super-scalară

O altă posibilitate dc realizare a paralelismului implicit este construcţia unor

procesoare super-scalare, prin adăugarea de resurse suplimentare. De exemplu, prin
utilizarea a două unităţi aritmetico-logice, se poate considcra că un procesor poate lucra
simultan cu două linii dc execuţie (ca în figura 3), controlate de o unitate specifică, numită
dispecer.

Timpul
0 1 2 4 5 6 7 8 9
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
IF D DF E WB
Figura 3. Dezvoltarea temporală pentru o procesare ideală cu două fluxuri pipeline

Acest tip de procesare asigură, în cazul ideal, o viteză dublă faţă de proccsarca pc un
singur flux pipeline (în exemplul din figura 3 se execută integral 12 instrucţiuni în 10 unităţi
de ceas). Exemplul următor arată că modul de programare este esenţial pentru viteza efectivă
de execuţie [7].
Să presupunem că dorim să adunăm 4 valori întregi, stocate fiecare pe 4 octeţi, în
variabilele a, b, c şi d, aflate în memorie înccpând cu adresa hexazecimală 1000. Prima

20
versiune a codului in limbaj de asamblare realizează ((a + />) + (<• + </)). Figura 4 arată timpul
necesar acestei versiuni.

Versiunea 1
1 load Rl, 01000
2 load R2, 01008
3 add Rl, 61004
4 add R2, G100C
5 add Rl, R2
6 store Rl, 92000

Timpul
10 II
IF D DF
IF D DF
IF D DF
IF D DF
IF D
IF D1 J DF WB
Figura 4. Dezvoltarea temporală pentru versiunea 1 cu 2 fluxuri pipeline

în acest caz, instrucţiunile 1 şi 2 se pot lansa simultan, dcoarccc sunt independente.

Fiind instrucţiuni dc preluare în rcgiştri. nu mai conţin şi fazele execute şi write-back. La fel.
pcrcchca dc instrucţiuni 3 şi 4 sc lansează simultan. Instrucţiunea 6 este dependentă dc a
cincca, astfel că faza data fetch este întârziată. Şi instrucţiunea 5 este nevoită să aştepte
finalizarea cclor două prcccdcntc pentru a intra în faza data fetch. Astfel, întreaga secvcnţă de
cod necesită 10 unităţi de timp.
Considerând acum aceeaşi metodă de calcul, dar inter-schimbând instrucţiunile 2 şi 3,
obţinem:

Versiunea 2
1 load Rl, 01000
2 add Rl, 01004
3 load R2, 01008
4 add R2, 01OOC
5 add Rl, R2
6 store Rl, 02000

Această schimbare care pare minoră conduce la prelungirea timpului de procesare, aşa
cum este arătat în figura 5.

Timpul
0 1 10 II
IF D DF
IF D DF E
IF D DF
IF 1) DF 1 E

H
IF D 1 DFI E J
IF DF 1 E I WB
Figura 5. Dezvoltarea temporală pentru versiunea 2 cu 2 fluxuri pipeline

21
 Dc accastâ dată, perechea de instrucţiuni 1 şi 2 nu se mai poate lansa la acelaşi
moment, deoarccc sunt dependente. La fel se întâmpla cu perechea următoare; instrucţiunea 5
aşteaptă încheierea instrucţiunii 4 pentru a intra în faza data fetch. Instrucţiunea 6 se lansează
imediat după lansarea instrucţiunii 5 şi astfel versiunea 2 propusă mai sus necesită 11 unităţi
de timp.
O altă posibilitate pentru adunarea celor patru valori este prezentată în continuare: se
utilizează un singur registru de memorie, folosind adunări succesive: (((a + b) + c) + d). in
acest ultim caz, figura 6 prezintă modul de cxccuţic.

Versiunea 3
1 load Rl, 81000
2 add Rl, 91004
3 add Rl, 01008
4 add Rl, 8100C
5 store Rl, 82000

11

WB
Figura 6. Dezvoltarea 3 cu 2 fluxuri pipeline

in acest caz, toate instrucţiunile sunt dependente, astfel că întârzierile se propagă şi se

amplifică. Acest al treilea mod dc rezolvare ncccsită 12 unităţi de timp, fiind astfel cel mai
ineficient din acest punct dc vedere, dar este cel mai cficicnt din punct dc vedere al memoriei
utilizate pe procesor (un singur registru).
Discuţia celor trei situaţii de mai sus arată importanţa cunoaşterii arhitecturii pe care
se execută aplicaţia şi utilizarea eficientă a accstcia.

2.3. Procesare cu spaţii mari de memorie

O altă metodă de realizare a paralelismului implicit este folosirea procesoarelor cu

spaţii mari de memorie alocate pentru instrucţiuni (very long instruction word processors -
VLIWprocessors). Procesoarele au evoluat dc la cuvinte de memorie de 2 octeţi (16 biţi) la
cele de 4 octeţi (32 de biţi), iar cele actuale utilizează cuvinte de memorie de 8 octeţi (64 dc
biţi). în cazul în carc instrucţiunile au cel mult 4 octeţi, arhitecturilc modeme pot deci prelua
simultan din codul obicct (rezultat la compilare) câte două instrucţiuni. Aceasta este însă o
metodă statică, dcoarece la compilare se produce împachetarea grupurilor de câte două
instrucţiuni carc sc pot executa în paralel.
Metoda nu conduce deci la o înjumătăţire a timpului de proccsare, deoarece:
• nu toate instrucţiunile se pot împachcta în grupuri de câte două;
• timpul de execuţie al grupului este egal cu cel mai mare dintre timpii de execuţie
al instrucţiunilor din grup.

22
 2.4. Folosirea ierarhiilor de memorii cache

Cea de-a patra metodă dc paralelizare implicită constă in utilizarea ierarhiilor de

memorii cache, care permit scăderea timpului de transfer al datelor din memoria principală
(RAM) în memoria internă (regiştri), pentru a fi proccsatc dc programul în execuţie.
Caracteristicile sistemului de calcul care sunt implicate în viteza dc transfer a datelor către
procesor sunt: latenţa (timpul de la lansarea cererii şi până la începerea sosirii datelor) şi
lărgimea de bandă (raportul dintre cantitatea de date şi timpul necesar ajungerii lor în
memoria internă). în situaţia în care nu sunt utilizate memorii intermediare dc tip cache,
datele aflate în RAM pot întârzia major procesarea, aşa cum rezultă din următorul exemplu.

Exemplu. Presupunem un procesor cu frecvenţa de 1 GHz. care poate executa 4 instrucţiuni

pc ciclu dc ccas. conectat la o memorie RAM cu latenţă de 100 ns. Frecvenţa dc 1 GHz - 10"
Hz conduce la execuţia unei instrucţiuni în IO"9 s = 1 ns (nanosccundă). Pentru adunarea a doi
vectori sc cxccută în mod repetat codul următor:

1 load Rl, e a(i]

2 load R2, 9 b[i)
3 add Rl, R2
4 store Rl, 0 c[i]

Dacă presupunem că grupul format din cele patru instrucţiuni se lansează

concomitent, atunci primele două se încheie după 100 (latenţa) + 1 (execuţie) = 101 ns.
Adunarea se încheie după 102 ns (după cc se cunosc termenii adunării mai este nevoie de 1
ns pentru a se afla suma lor), iar stocarea în RAM a valorii obţinute mai are nevoie de încă
101 ns (1 ns pentru execuţie şi 100 ns transferul sumei în RAM). în final, valoarea variabilei
c[lj ajunge în RAM după 203 ns, iar procesarea pentru aflarea valorii c[2) poate înccpe după
ce prima instrucţiune s-a închciat, adică după 101 ns. Registrul Rl este blocat dc
instrucţiunile corespunzătoare valorii c/7/, deci instrucţiunea

load Rl, 9 a[2]

sc execută în intervalul 203-304 ns. Deşi instrucţiunea

load R2, 8 b[2)

se execută mai devreme, dcoarccc registrul R2 este eliberat la momentul 102 ns. valoarea din
R2 aşteaptă depunerea valorii variabilei a[2] în Rl şi deci instrucţiunea

add Rl, R2

sc execută în intervalul 304-305 ns. Transferul valorii a[2] + b[2) sc facc în intervalul 305-
406 ns. în concluzic, execuţia repetată a blocului dc 4 instrucţiuni se face în blocuri de 203
ns, deci timpul total nccesar este de n • 203 ns în cazul în care vectorii au câte n componente.
Dintre cele 4 instrucţiuni necesare aflării unui element din vectorul-sumă. trei (prima,
a doua şi a patra) necesită 101 ns pentru execuţie şi cea de-a treia se execută într-o
nanosecundă; dc asemenea, primele două se pot executa concomitent, însă ultimele două se
cxccută secvcnţial după ce primele două s-au închciat.

Dacă însă se folosesc memorii cache, care pot stoca integral cei trei vectori şi dacă
presupunem că lărgimea de bandă permite transferul datelor într-o singură fază, atunci prima

23
dată se aduc toate datele de intrare în cache (100 ns), apoi se calculează toate valorile
vectorului c (aproximativ n ns deoarece se pot executa 4 instrucţiuni in paralel, iar aflarea
unei valori din vectorul c necesită tot 4 instrucţiuni) şi în final toate valorile se trec in RAM
în 100 ns. in accst caz timpul total este dc n + 200 ns. dc aproximativ 200 de ori mai mic
dccât în cazul în carc nu sc utilizează memorii cache.

2.5. Utilizarea datelor contigue

Creşterea vitezei dc proccsare a datelor prin metode implicite sc mai poate realiza prin
eliminarea accesării datelor stocate la distanţă (stride elimination). Aducerea datelor din
memoria secundară (de exemplu, hard-disc) în memoria principală (RAM) nu se face
individual, ci prin intermediul paginilor de memorie - un grup de adrese adiacente in
memorie, care include şi valoarea cerută de procesor Un grup de date alăturate in memorie se
numesc date contigue (contiguous data). De obicei o pagină de memorie are 4 kB şi această
metodă a fost implementată deoarece s-a considerat că, de obicci, aplicaţiile folosesc date
stocate în zone alăturate. Acest principiu poate fi utilizat în reducerea timpului de procesare a
matricelor mari. Programatorii nu dau mare importanţă ordinii de parcurgere a unei matricc,
dar în cele ce urmează vom vedea că în cazul unor matrice mari. aceasta are impact major
asupra timpului dc cxccuţic.

Exemplu. Considerăm că matricea A arc dimensiunea (1000, 1000) şi că este ncccsară o

aplicaţie carc să genereze un vector b cu 1000 dc componcntc, fiecare dintre accstca fiind
suma elementelor din A situate pe câte o linie.

Versiunea 1 dc rezolvare a problemei este:

f o r (i - 0; i < 1000; i++)
b [ i ] - 0;
f o r (i = 0; i < 1000; i++)
f o r ( j - 0; j < 1000; j+*)
b l j ) +*a [ j j [ i l ;
în acest caz. pentru i fixat, la fiecare exccuţic a ultimei instrucţiuni, este adusă în RAM o altă
pagină de memorie, deoarece, după cum se ştie, matricele se stochcază pe linii. Dacă tipul dc
date este de 4 octeţi, atunci o pagină stochează 1000 de valori. Deşi sunt aduşi de fiecare dată
câte 4 kB de date, este utilizată doar o singură valoare - şi anume a [ j ] [ i ) . Pentru a sc
executa complet structura f o r interioară sunt necesare deci 1000 de transferuri din hard-disc
în RAM.

O simplă interschimbare a celor doi indici conduce la:

Versiunea 2
f o r (i = 0; i < 1000; i++)
b [ i ] - 0;
f o r (i = 0; i < 1000; i++)
f o r <j - 0; j < 1000; j++>
b [ i ] += a f i l 1 3 ] ;
în accst caz, pentru / fixat, execuţia complctă a structurii f o r interne necesită doar câteva
transferuri dc date dc pe hard-disc (în funcţic de tipul dc dată utilizat şi dc poziţia în pagina
dc memorie a valorii a [ i ] I j ]).

24
 2.6. Software-ul şi paralelismul implicit

în concluzie, există metode implicite pentru creşterea vitezei de execuţie a unei

aplicaţii, bazate atât pe facilităţile hardware, cât şi pe folosirea cunoştinţelor de arhitectura
calculatoarelor. Un hun programator nu este cel care stăpâneşte doar tehnicile şi metodele de
programare. Pentru aplicaţiile complexe ale zilei de azi, este nevoie şi de cunoştinţe din
Ştiinţa calculatoarelor şi Tehnologia informaţiei.

Dacă avem la dispoziţie un singur procesor, modul în care se realizează programarea

activităţilor se reflectă în timpul total, necesar încheierii tuturor activităţilor. Exemplul
următor arată importanţa programării eficiente a mai multor activităţi pe un singur procesor şi
subliniază faptul că sistemul de operare este o aplicaţie esenţială în exploatarea eficientă a
resurselor de calcul. Alegerea unui sistem de operare se va face şi analizând eficienţa
dispecerului de activităţi (aplicaţic-nuclcu care se ocupă cu gestionarea proceselor
concurente).

Kxemplu. Presupunem că avem la dispoziţie un singur procesor şi că pe acesta

trebuiesc programate două activităţi. Al şi A2. Fiecare dintre acestea constă într-o înşiruire dc
patru sarcini, care vor fi specificate prin timpul necesar (în secunde) şi o caracteristică: p dacă
utilizează procesorul sau /', dacă nu necesită procesare (sarcina respectivă poate fi de exemplu
o listare).
Al:2p 1/2p li
A2: 3p 1/ 1 p 31
Pentru a realiza cele două activităţi, vom folosi mai întâi o metodă greedy: vom
programa pe procesor sarcinile disponibile care necesită timpul cel mai îndelungat. în figura
7, pe axa orizontală a timpului sunt evidenţiate sarcinile rezolvate de procesor, iar in paralel
cu acestea, sarcinile care nu necesită intervenţia procesorului.

timp procesare (p) măsurat in secunde

A2 H Al 1 A2 B Al M 1
1 2 3 4 5 6 7 8 9 10 11 12
timp idle (/') măsurat în secunde
A2 IXAI^r A2
1 1 1 1 1 1 Al
4 5 6 7 8 9 10 II 12
Figura 7. Programarea greedy pe un singur procesor

Se observă că această strategie conduce la încheierea activităţilor după 9 s, dacă

ultimele sarcini din fiecare activitate se pot executa în paralel (de exemplu, prima este o
listare iar a doua este o copiere dc fişiere). Dacă nu este posibil, atunci programarea va dura
10 s pentru că ultima sarcină a activităţii Al se va executa după ce se încheie integral
activitatea A2.
O altă programare poate începe cu Al şi continuă cu sarcinile care se pot lansa când
procesorul este eliberat (ca în figura 8). in cel de-al doilea caz, încheierea ambelor activităţi
s-a tăcut după 11 s. Acest exemplu arată din nou importanţa metodelor eficiente dc
implementare a paralelismului implicit. De asemenea, arată complexitatea algoritmilor
implementaţi de o aplicaţie de tip dispecer dc activităţi.

25
 6 7 8 9 10 11 12

A2 A2
0 1 4 5 6 7 8 9 10 11 12
Figura 8. Altă programare a aceloraşi activităţi

Paralelismul implicit se referă la exploatarea eficientă a caracteristicilor harjware-

ului pe care se executa aplicaţiile. Un programator preocupat de calitatea aplicaţiei pe care
o proiectează şi realizează nu poate ignora aceste caracteristici.

26
 Capitolul 3

Paralelism explicit

Acest capitol este dedicat arhitccturilor cu mai multe unităţi de procesare, care permit
specificarea explicită a proceselor care se pot desfăşura concurent. Spre deosebire de
capitolul anterior (Paralelism implicit), care tratează cazul unei arhitecturi mono-procesor.
acest capitol descrie facilităţile oferite de colecţiile de procesoare.
Trecerea de la programarea secvenţială la programarea paralelă nu este uşoară.
Metoda paralelizării unor aplicaţii secvenţiale deja scrise nu este cea mai eficientă. Pot exista
caractcristici ale problemei care nu sunt speculate de aplicaţiile secvenţiale şi care scapă
atenţiei programatorilor şi in cazurile paralele. Pe de altă parte, scrierea de la început a unor
aplicaţii paralele este o activitate dificilă, care necesită solide şi moderne cunoştinţe de
programare.

3.1. Controlul în aplicaţiile paralele

Aşa cum în cazul aplicaţiilor secvenţiale controlul (adică paşii aplicaţiei) este
spccificat prin instrucţiuni, în cazul aplicaţiilor paralele este necesară specificarea controlului
(ce face fiecare proces) dar şi a modelului de comunicare (cum/când/cine/ce comunică).
O aplicaţie paralelă lipsită de comunicaţii poate fi gândită ca o cxccuţic în izolare a
proceselor, deci ar putea fi înlocuită cu înlănţuirea secvenţială a proceselor pe un singur
procesor. în acest caz. timpul de execuţie ar fi egal cu suma timpilor de execuţie a fiecărui
proces, câştigul adus de procesarea paralelă fiind reducerea vitezei de procesare (folosind
formulele din Capitolul I, în cazul a n procese perfect echilibrate ca timp de execuţie,
acceleraţia este n şi eficienţa este 1). Deşi acesta este o situaţie extrem de eficientă,
rezolvarea unor probleme complexe a dovedit că o descompunere în procese care comunică
reuşeşte să găsească soluţii mai bune decât dacă nu există comunicare între procese. O
strategie de comunicare prin care procesele să schimbe inteligent date este cheia pentru a
obţine soluţii de calitate la problemele dificile ale lumii actuale.

Controlul procesării reflectă granularitatea paralelizării:

• dacă paralelizarea este de granularitatc mare (coarse-grained), atunci se execută
pe fiecare unitate de procesare câte un program (aceste programe pot fi identice
sau diferite între ele) cu propria evoluţie, deci propriul control;
• dacă paralelizarea este de granularitatc mică (fine-grained), atunci se execută o
singură aplicaţie, asigurându-se un control unic şi se prelucrează simultan seturi
diferite de date.

Exemplu de control la nivel de program (granularitate mare)

în arhitectura MIMD (Multiple Instructions Multiple Data) se pot implementa
aplicaţii paralele in care fiecare unitate independentă de procesare execută un proces
secvenţial. Cea mai comună situaţie este utilizarea unei reţele de calculatoare mono-procesor,
fiecare dotate cu aplicaţii şi sistem de operare şi care execută diverse procese din aplicaţia

27
paralelă. Această soluţie este generală (se poate utiliza pentru o clasă largă de aplicaţii
paralele), flexibilă (se poate echilibra în funcţie dc consumul de resurse), dar necesită spaţii
suplimentare de memorie, dcoarccc fiecare sistem dc calcul este controlat independent (figura
9). Sistemele bazate pe multiple proccsoare (CPUs) sunt construite pentru a scădea latenţa:
• memoria cache este destinată măririi şanselor ca datele neccsarc să fie deja
disponibile, datorită precedentelor transferuri din memoriile externe
procesorului;
• unitatea de control (UC) permite predicţia ramificării codului (branch
prediction - codul sc execută în avans, pe ramura cea mai probabilă a
structurilor dc decizie, dar există şi instrumente de restaurare şi avans pe
celelalte ramuri. în cazul în carc predicţia s-a dovedit a fi incorectă).
Structurile de decizie pot fi: instrucţiunea if-then-else, instrucţiunea
case/switch sau cclc carc realizează controlul instrucţiunilor repetitive (dacă sc
reiau sau sc trccc la următoarea instrucţiune).
• unitatea de control (UC) pe mii te utilizarea rapidă a valorilor calculate recent
(dala fonvarding) prin mecanisme dc urmărire a locului din aplicaţie în care
este ncccsară o valoare tocmai calculată şi utilizarea acestei valori deşi aceasta
nu a fost încă depusă în zona de memoria secundară (pe hard-disc).
Orientarea către eliminarea latenţei face ca sistemele de calcul bazate pe CPU să fie
extrem de eficiente în cazul aplicaţiilor secvenţiale. Industria hardware a urmărit, de la
începuturi, eficientizarca acestor aplicaţii. Doar după ce s-a pus problema calculului paralel,
au început să apară preocupări în eficientizarca hardware pe accastă direcţie.

Figura 9. CPU - Unităţi de procesare care posedă individual unităţi de control

O altă soluţie (modernă) este oferită de accelcratoarclc grafice (arhitectură SI MD -

Single lnstruction Multiple Data), care rezolvă o clasă mai restrânsă de probleme cu un cost
scăzut - necesită memorie puţină, existând un singur punct dc control (figura 10). Aplicaţiile
care utilizează facilităţile GPU (Graphics Processing Unit) speculează arhitectura lor,
specializată pentru eficientizarca unui mare număr de procese, care manevrează in acelaşi fel
seturi diferite de date.

Figura 10. GPU - Unităţi de procesare controlate de o singură unitate de control

28
 Controlul este deci exterior unităţilor de procesare, care nu mai oferă facilităţile
branch prediction sau data J'orwarding. Unităţile aritmetico-logice (UALs) sunt numeroase,
eficiente energetic şi permit cxccuţic dc tip pipeline. Deşi memoria disponibilă pentru GPU
inducc o latenţă mult mai mare decât în cazul unui CPU (lipscsc facilităţile descrise în lista
precedentă), numărul marc dc operaţii care se pot suprapune (arhitectura este putcmic
orientală către suprapunerea de tip piţ>eline) face ca aproape la fiecare ciclu de ceas sa fie
încheiată execuţia unei instrucţiuni. Aceste caracteristici fac ca dispozitivele hardware de tip
GPU să poată executa mult mai eficient unele aplicaţii paralele decât dispozitivele CPU.

Exemplu dc control la nivel dc instrucţiune (granularitate mică)

in cazul arhitecturii SIMD (Single lnstruction Multiple Data) se pot executa
concomitent operaţii pe fiecare componentă a unei structuri de date. De exemplu, dacă dorim
să adunăm doi vectori a şi b cu câtc 1000 dc componente şi să stocăm valorile rezultate într-
un alt vector c, atunci aplicaţia secvenţială va conţinc instrucţiunile:

for (i - 0; i < 1000; i++)

c[i) - a[il + b[ij;

iar dacă dorim folosirea facilităţilor SIMD, atunci codul paralel (care alocă o poziţie din
vectorul c unui proces şi fiecare proces are acces la componentele corespunzătoare din cei doi
vectori dc intrare) va conţinc instrucţiunea:

c[currentJ = afeurrent) + b[current];

în primul caz procesorul execută 2000 de atribuiri (sunt necesare 1000 dc atribuiri
pentru contorul / şi 1000 de atribuiri pentru elementele vectorului c). în al doilea caz se
execută simultan 1000 dc atribuiri pentru variabila locală current şi apoi simultan 1000 de
atribuiri pentru calculul valorii corespunzătoare din vectorul c.
Situaţia sc complică dacă există instrucţiuni decizionale în codul secvenţial. De
exemplu, dacă există instrucţiunea:

if (x -- 0) z - y; else z = y/x;

execuţia sa pe seturi diferite dc date ncccsită doi paşi: întâi se atribuie valoarea din y
variabilei z pentru toate procesele care au valoarea 0 stocată în variabila x şi apoi se atribuie
valoarea y/x variabilei z pentru restul proceselor. în toate procesele paralele, se lucrează pe
valorile curente (locale procesului) ale variabilelor. Instrucţiunea pentru versiunea paralelă
este:

where <x — 0) z - y; elsewhere z - y/x;

Presupunând că această instrucţiune se execută pe patru seturi de date (D1-D4):

Dl D2 D3 D4
înainte dc x 0 JC 2 * 3 x 0
where y 7 y 8 .V 3 y 2
z z z z

• n etapa 1 în execuţia instrucţiunii where constă în alocarea valorilor variabilei z din

« « v i l e Dl şi D4:

29
 Dl D2 D3 D4
etapa 1 din r 0 x 2 .r 3 * 0
where y 7 .v 3 2
z 7 z z : 2

şi a doua etapă alocă valori pentru variabila r din seturile D2 şi D3:

Dl D2 D3 D4
etapa 2 din * 0 x 2 .r 3 x 0
where v 7 v 8 y 3 v 2
I- 1 r 4 z 1 z 2

Această metodă de rezolvare foloseşte o mascare a activităţii (activity niask),

permiţând separarea proceselor în grupuri care execută aceeaşi prelucrare pe seturi diferite de
date. Cu cât structurile de dccizic sunt mai numeroase sau mai complcxc (de exemplu
instrucţiunea c a s e / s w i t c h ) , cu atât masca de activitate împarte proccsclc în tot mai multe
grupuri. întârziind execuţia aplicaţiei paralele.

3.2. Comunicaţiile în aplicaţiile paralele

Comunicaţia este esenţială pentru cficientizarea aplicaţiilor paralele. Scrierea unor

aplicaţii care se desfăşoară simultan ftră ca acestea să comunice nu îmbunătăţeşte decât
timpul total de execuţie, fără însă a economisi resursele de calcul, aşa cum am văzut la
începutul acestui capitol. în loc să executăm în paralel procesele, acestea sc pot înscria şi
cxccută pe un singur procesor, evident în timp mai lung. dar cu aceleaşi costuri totale.
Comunicaţia între procese sc poate executa:
• prin spaţiu partajat de adrese (shared address space)
• prin schimb de mesaje (messagepassing).
Aceste metode de comunicaţie sunt destinate exploatării a două tipuri de arhitecturi.
Din nou, subliniem faptul că aplicaţiile paralele actuale sunt proiectate astfel încât să utilizeze
extrem de eficicnt caracteristicilc platformei pe care urmează a se implementa. O aplicaţie
paralelă nu poate fi cficientizată pentru toate arhitecturile.

3.2.1. Comunicaţiile prin spaţiu partajat de adrese

Principiul comunicaţiilor prin spaţiu partajat de adrese este des întâlnit în natură, fiind
o alternativă la mai des întâlnitul principiu al schimbului de mesaje. în locul sincronizării
expeditorului cu destinatarul de fiecare dată când este necesară o transmisie de date (schimb
de mesaje), comunicaţia prin adrese partajate nu necesită sincronizare: expeditorul depune în
spaţiul comun valoarea pe care doreşte să o transmită şi destinatarul o accesează atunci când
are nevoie de valoarea respectivă.
Aceeaşi metodă este întâlnită în natură la coloniile de furnici, care depun pe sol o
substanţă specifică (feromon) pe care o recunosc şi o interpretează cele care trec ulterior prin
acelaşi loc. Deşi sunt insecte aproape oarbe, furnicile reuşesc să găsească în scurt timp
drumul cel mai scurt de la sursa de hrană la cuib. Un alt model este partajarea vehiculelor,
pentru economisirea carburantului, micşorarea emisiilor poluante şi descongestionarea
şoselelor. în figura 11 este prezentat indicatorul pentru benzile HOV (high-occupancy vehicle
lanes) dedicate, iar în figura 12 se află o imagine a unei astfel de benzi. Controlul utilizării

30
r^enzilor HOV se face prin sisteme automate de captare şi interpretare a imaginilor,
asigurându-se acces liber doar autovehiculelor în care se află cel puţin două persoane
t posesorii celorlalte autovehicule sunt amendaţi).

HCV 2- CNLY
? OR MC
PCRSOtK
f LH VLHlC.t

Figura 11. Indicatorul rutier High-occupancy vehicle (HOV) în vigoare în SUA

Figura 12. Bandă dedicată HOV]n California, SUA [29)

Sistemele de calcul care suportă programarea de tip SPMD se numesc sisteme mulţi-
procesor. Dacă timpul pentru accesarea memoriei este identic pentru Fiecare spaţiu dc
memorie, atunci platforma este de tip Uniform Memory Access (UMA) (figura 13). In caz
contrar, platforma este de tip Non-uniform Memory Access (NUMA) (figura 14).
Comenzile de scriere în memoria comună sunt complexe la nivelul implementării,
deoarece necesită mecanisme dc blocare, specificate în continuare, in acest subcapitol.

Figura 13. Platformă UMA. spaţiu partajat de memorie

31
 Figura 14. Platformă NUM A, spaţiu partajat dc memorie

Cea mai eficientă arhitectură cu adrese partajate este oferită de memoria P R A M

(Parallel Random Access Machine): mai multe proccsoare accesează un spaţiu comun dc
memorie. Un model asemănător este metoda didactică a rezolvării la tablă a unei probleme:
profesorul scrie informaţiile la tablă, iar elevii le preiau, asigurându-se că la momentul când
profesorul şterge tabla şi depune noi informaţii pe tablă, cele precedente au fost deja utilizate
(învăţate sau scrisc în caictc) şi dcci nu mai este necesară prezenţa lor în spaţiul comun (adică
tabla).
Accst model este cunoscut în Inteligenţa Artificială sub numele dc modelul
Bluckboard [31], fiind folosit pentru a rezolva probleme complexe care se descompun în sub-
problcmc dependente, având următoarele componente:
• baze de cunoştinţe (knowledge sources) stocate distribuit; fiecare astfel de bază poate
rezolva independent o sub-problemă;
• o zonă de memorie la carc au acces bazele de cunoştinţe, care conţine problema
iniţială, sub-problemele în care aceasta s-a descompus, soluţiile acestor sub-problcme,
modul în care se utilizează aceste soluţii în rezolvarea altor sub-probleme sau a
problemei iniţiale, ctc.;
• un modul de control, care asigură desfăşurarea eficientă a procesului de rezolvare a
problemei iniţiale, carc defineşte şi urmăreşte strategia dc rezolvare a acesteia. Scopul
modulului este de a împiedica deducţiile nefolositoare rezolvării problemei.
Proiectarea şi programarea accstui modul este esenţială şi arată importanţa
conccptului dc oportunism in informatică. Spccularea oricăror informaţii şi metode
care ajută la rezolvarea rapidă a problemelor ajunge să fie o artă, carc se bazează pe
cunoştinţe avansate, pc experienţa şi pe cooperarea echipei de specialişti care lucrează
la rezolvarea problemei respective.
Câteva sisteme open-source destinate implementării modelului tablei sunt [21,31].

Cea mai dificilă activitate în cazul spaţiului partajat dc memorie o reprezintă

asigurarea transferului corect de date. Pe parcursul execuţiei aplicaţiei paralele, se pot
produce transferuri de date în alt mod decât cel intenţionat la proiectarea algoritmului. Dc
exemplu, dacă mai multe proccsc doresc simultan să serie acccaşi zonă de memorie, atunci
unele dintre valorile care se intenţionează a se stoca sc pierd, deci activitatea realizată de
aceste procese este irosită. Strategia utilizată în cazul PRAM poate fi:
• Exclusive Read, Exclusive Write (EREW) - modelul cel mai restrictiv, când atât
citirilc cât şi scrierile se execută sccvcnţial; dacă la un anumit moment, procesele
încearcă să scrie simultan aceeaşi zonă de memorie, atunci acestea sunt serializate.
La fel se întâmplă şi la tentativa de citire simultană. Asigurând cel mai înalt grad
de securitate a datelor, acest model produec şi cea mai marc întârziere, prin

32
 serializarea proceselor care în celelalte cazuri (descrise in continuare) s-ar putea
desfăşură în paralel.
• Concurrent Read. Exclusive Write (CREW) - modelul cel mai întâlnit, care
serializcază scrierile, dar permite citirile simultane din aceeaşi zonă de date.
• Exclusive Read. Concurrent Write (ERCW) - modelul care serializcază citirile
accicaşi zone de memorie, dar permite scrierea simultană în acelaşi loc.
• Concurrent Read. Concurrent Write (CRCW) - cel mai puternic model PRAM.
carc eliberează programatorul dc grija operaţiilor dc intrare/ieşire. Toate operaţiile
de citire/scriere carc doresc să acceseze simultan o zonă de memorie sc execută
(unele având efectul scontat dc programatorul procesului, altele nu) şi aplicaţia nu
întârzie.

Accesul concurent este lăsat Ia decizia protocoalelor dc tratare a evenimentelor carc ar

putea apărea. Cum am văzut deja. proccsclc accesează concurent aceeaşi zonă de memorie,
insă nu este garantat succesul tuturor accesărilor. Dacă citirea simultană nu pune probleme,
deoarece nu este importantă o eventuală scrializare decât din punctul de vedere al timpului
necesar, scricrca simultană este rezolvată prin unul dintre următoarele protocoale de
rezolvare a conflictelor:
• Common: scrierea se realizează doar dacă toate proceselc încearcă să scrie aceeaşi
valoare, altfel toate procesele eşuează în tentativa de scriere şi apoi toate continuă
cxccuţia.
• Arbitrary: unul (oarecare) dintre procese scrie efectiv şi celelalte eşuează; apoi
toate continuă.
• Prioritv: scrie procesul care are cea mai înaltă prioritate, celelalte eşuează şi apoi
toate continuă. Acest protocol presupune că fiecărui proces i se alocă (la creare) o
prioritate.
• Suni (sau orice alt operator asociativ): se scrie suma (sau rezultatul aplicării
operatorului) valorilor pe care intenţionează să le scrie fiecare proces şi apoi
fiecare proces îşi continuă cxccuţia.

3.2.2. Comunicaţiile prin schimb de mesaje

Principiul schimbului de mesaje este asemănător sistemului poştal clasic: pentru a

prelua o informaţie, expeditorul trimite o scrisoare destinatarului, folosind un plic pe carc
specifică datele dc identificare ale cclor doi, în care împachetează mesajul. Atât destinatarul
cât şi expeditorul pot înţelege mesajul, fiind deci în posesia unor facilităţi de procesare şi
stocare a mesajului. La fel, unităţile dc procesare care schimbă mesaje posedă spaţii exclusive
dc memorie (figura 15), au identificatori unici carc îi individualizează în grupul dc posibili
participanţi la schimbul de mesaje şi pot folosi funcţiile dedicate: Send sau Receive.

UP M UP M ••• UP M

Figura 15. Platformă cu spaţiu exclusiv dc memorie, pentru comunicare

prin schimb de mesaje

33
 Limbajele de programare care permit schimbul de mesaje implementează şablonul
general MPI (Message Passing Interjace). aflat acum la versiunea 3 [32]. Printre cele mai
utilizate implementări MPI menţionăm [23. 25, 26].
Sistemele distribuite (cu spaţii exclusive de memorie) folosesc comunicarea prin
schimb de mesaje, pe când metoda alternativă (comunicarea prin acces la memoria comună)
este potrivită sistemelor de calcul paralel.
Schimbul de mesaje se realizează întotdeauna într-un context (un grup), care defineşte
o submulţimc a calculatoarelor legate în reţea care pot comunica. La un moment dat. intr-o
aplicaţie distribuită, pot exista mai multe grupuri, dar o comunicaţie are loc într-un anumit
grup. O comunicaţie presupune existenţa a cel puţin unui expeditor (sursă) şi a cel puţin unui
destinatar.
In funcţie de participanţii la comunicaţie, acestea pot fi de următoarele tipuri:
• 1 - 1 (one-to-one), când schimbul de mesaje se realizează prin perechea dc
comenzi Send (la sursă)//teci/ve (la destinaţie);
• I - toţi (one-to-all), când sursa trimite câte un mesaj fiecărui proces din grup.
folosind una dintre comenzile Broadcast sau Seat ier,
• toţi - 1 fall-to-one), când un singur destinatar colectează mesaje dc la toţi
participanţii din grup, cu ajutorul comcnzilor Gather sau Reduce.

In comunicarea de tip / - / există o singură sursă şi un singur destinatar, fiecare dintre

aceste proccse cunoscând identificatorul procesului cu care corespondează. Schimbul de date
se realizează printr-o zonă de memorie dedicată ( b u f f e r ) , care se utilizează ca spaţiu de
stocare intermediar şi permite eliberarea memoriei celor doi participanţi Ia schimb (figura
16).

mesaj
Memorie sursă Buffer sursă Buffer destinaţie Memorie destinaţie
(MS) (BS) (BD) (MD)
Sursă Destinaţie

Figura 16. Transmiterea unui mesaj între sursă şi destinaţie

Pentru realizarea transmisiei, sursa trebuie să execute o comandă Send, iar destinaţia
arc de executat o comanda Receive. în modelul general, parametrii acestor comenzi sunt:
Send (mesaj, destinatar, eticheta, grup)
Receive (mesaj, sursa, eticheta, grup. stare)
unde: mesaj descrie identificatorul structurii locale de date care conţine mesajul,
destinatar/sursa sunt identificatorii celuilalt proces, eticheta permite împerecherea corectă a
celor două comenzi, deoarece identifică mesajul în mod unic, grup reprezintă contextul în
care se realizează comunicarea, iar stare este o structură de date care reflectă modul în care s-
a realizat efectiv comunicaţia.
Existenţa buffcr-ului care intermediază schimbul permite următoarele variante de
comunicare:
• hlocking. în care sursa rămâne în execuţia comenzii Send până când bufler-ul său
(BS din figura 16) poate fi rescris. De asemenea, destinaţia stă în execuţia
comenzii Receive până când bufler-ul său (BD din aceeaşi figură) conţine întreg
mesajul transmis. După ce se îndeplineşte condiţia corespunzătoare lui, fiecare
proces poate inccpc execuţia următoarei instrucţiuni. Accastă variantă presupune
dcci că procesele nu pot avansa decât după ce comunicaţia s-a realizat efectiv
(deci se poate spune „comunicaţia a sincronizat procesele").

34
 • non-blocking. in care fiecare dintre comenzile Send/Receive este împărţită în două
faze, între carc fiecare proccs poate cxccuta alte comenzi:
o iniţierea comunicării
o testarea realizării comunicării.
Această variantă permite ca aplicaţiile să avanseze ne-sincron, nefiind necesară
[Link]ţia în acciaşi timp a comcnzii Send la sursă şi a comenzii Receive la
destinaţie.

in ambele variante, în funcţie de răspunsul la întrebarea „Ce se poate spune despre

procesul Destinaţie, dacă procesul Sursă a încheiat comanda Send?", există mai multe moduri
de implementare a comunicaţici:
• standard, când nu se cunoaşte starea în care se află procesul Destinaţie,
programatorul nu se poate baza nici măcar pe faptul că BD conţine mesajul:
• buffered, când comanda Send a procesului Sursă sc poate încheia fără ca procesul
Destinaţie să fi început execuţia comenzii Receive;
• sychronous, când la închcicrca comcnzii Send a procesului Sursă, procesul
Destinaţie a început execuţia comenzii Receive şi mesajul a înccput să fie
recepţionat;
• ready, când comanda Send a proccsului Sursă poate începe numai după ce
comanda Receive din procesul destinaţie şi-a început execuţia.

in cazul comunicării de tip 1 - toţi, se presupune existenţa unui grup, în cadrul căruia
există un proces Sursă, care transmite câte un mesaj fiecărui proces din grup. inclusiv lui
însuşi. Comanda Broadcast transmite acelaşi mesaj tuturor proceselor din grup:

Broadcast (mesaj, sursa, grup)

Pentru a se realiza difuzarea mesajului în grup, fiecare proces execută comenzi

Broadcast idcnticc; dacă presupunem că grupul este format din n calculatoare, atunci cele n
comenzi Broadcast sunt echivalente cu n comenzi Send executate de Sursă şi câte o comandă
Receive executată de fiecare proces. Dacă grupul este mare, atunci Sursa poate provoca
aglomerări pe canalul de comunicaţie. Această problemă va fi tratată în continuare, în acest
subcapitol. In figura 17 este prezentat un grup de 4 calculatoare carc au identificatorii 1 - 4,
în carc sursa comcnzii Broadcast este proccsul cu identificatorul 1 şi mesajul conţine
valoarea variabilei a.

date date
a a
1 1 Broadcast (a. 1, grup) 1 7
O
35
y 2
|
2 7
2 3 3 7
c. Q. 4
4 7

Figura 17. Efectul unei comenzi Broadcast într-un grup de 4 procese

Comanda Scatter transmite mesaje diferite tuturor proceselor care compun un grup:

Scatter (colecţie, element, sursa, grup)

35
 Această comandă este generalizarea comenzii Broadcast, în sensul că o colecţie de
date stocată la sursă este fragmentată şi fiecare element este transmis unui proces, în ordinea
identificatorilor proceselor din grup. Dacă presupunem că grupul arc n calculatoare, atunci
comenzile Scatter executate dc fiecare sunt echivalente cu n comenzi Send executate de Sursă
şi câte o comandă Receive executată de fiecare proces. în figura 18 este prezentat rezultatul
unei comenzi Scatter executată pe fiecare dintre cele 4 procese ale unui grup, in carc procesul
1 este sursa şi trimite fiecărui proces din grup (in ordinea identificatorilor) câte o componentă
a vectorului A.

date date
A b A b
1 7 3 5 | 2 Scatter (A. b, 1, grup) 1 7 3 5 2 7
av 2 '.j
t/j 2 3
? 3
c. 4
£
CL 4
3 5
2

Figura 18. Efectul unei comenzi Scatter într-un grup de 4 procese

Comunicaţiile de tip toţi - 1 presupun colectarea la destinaţie a mesajelor transmise de

fiecare proces din grup. Comanda Gather este opusă comcnzi Scatter. deoarece proccsul
destinaţie construieşte în ordinea identificatorilor proceselor participante o structură de date
prin rccepţionarea mesajelor transmise de fiecare proccs:

Gather (element, colecţie, destinatie, grup)

în cazul unui grup de /; calculatoare, comenzile Gather executate de fiecare sunt

echivalente cu n comenzi Receive executate de Destinaţie şi câte o comandă Send executată
de fiecarc proces. în figura 19 sc prezintă efectul comenzii Gather cu destinaţia 1 într-un grup
dc 4 proccsc.

date date
A b A b
1 2 1 2 | 9 4 | 6 2
Gather (b. A, 1. grup)
S 8 2 9
£
a> 2 9 a>
3 4 3 4
a. 4 c. 4 6
6

Figura 19. Efectul unei comenzi Gather într-un grup de 4 procese

Comanda Reduce presupune utilizarea unui operator asociativ (fie predefinit, fie
definit în aplicaţie) - exemplul din Figura 20 se referă la operatorul de adunare (SUM). Prin
comanda Reduce, la destinaţie se colectează valorile obţinute prin aplicarea repetată a
operatorului specificat, pentru fiecare dintre structurile de date primite de la Fiecare proces
din grup. Dacă presupunem că grupul are n calculatoare, atunci comenzile Reduce executate
de fiecarc sunt echivalente cu n comenzi Receive executate de Destinaţie, câte o comandă
Send executată de fiecarc proces şi o prelucrare a rezultatelor finale. în figura 20, fiecarc
dintre cele 4 componente ale vectorului B se obţine prin adunarea componentelor
corespunzătoare din fiecare vector A, stocat pe fiecare calculator din grup. De exemplu, B[l]
este suma valorilor stocate în A(l] de către fiecare proces.

36
 date date
A B
1 2 2 1 0 Reduce (A, B. SUM. 1. grup) 1 7 | 6 3 | 6
• K 2
8 2 3 1 0 4 V
* 3 0 3 1 1 3
c. 4 c. 4
2 0 1 1

Figura 20. unei comenzi Reduce intr-un de 4 procese

Conectarea unităţilor de procesare

Reţelele alcătuite prin conectarea mai multor unităţi dc procesare destinate calculului
paralel sunt de obicei reţele regulate, cu o topologie strict orientată către viteze mari de
transmisie a mesajelor şi distanţe scurte între procesoare. Dc aceea, reţelele mici sunt
complete de cele mai multe ori. iar cele mari respectă următoarele topologii [7]:
• Stea (s/ar): un procesor este legat la toate cclclaltc proccsoare. Dc obicci este o
reţea eterogenă, procesorul central asumându-şi rolul de server, iar celelalte - pe
cel de client.
• Vector (cu sau fară circularitatc; în primul caz obţinem reţeaua de tip inel): toate
procesoarele sunt conectate la o magistrală (bus).
• Arbore (tree): topologia este dc arbore (graf neorientat concx şi ftră circuite). în
figura 21 a) este prezentat un arbore binar cu 8 noduri terminale. Cea mai dificilă
problemă a acestei topologii este aglomerarea mesajelor în zona rădăcinii,
dcoarccc muchiile conexe rădăcinii fac trecerea între sub-arborelc stâng şi cel
drept al acesteia. Din acest motiv, arborii sunt cficicntizaţi prin creşterea lărgimii
de bandă pentru conexiunile din apropierea rădăcinii, ca în figura 21 b).
• Plasă (mesh): procesoarele sunt legate cu vecinii aflaţi în nodurile unei reţele cu
două sau mai multe dimensiuni. Reţeaua poate fi cu circularitate (toroidală) sau
deschisă. în figura 22 sunt prezentate cclc două cazuri pentru o plasă 2D cu 9
noduri. în figura 23 sc află o reţea mesh 3D cu 27 de noduri. Pentru cazul general,
se defineşte reţeaua de tip k-d mesh: o plasă din k noduri în d dimensiuni. O reţea
2-d mesh este denumită hipercub. în figura 24 este prezentată seria 2-0 (a), 2-1
(b), 2-2 (c), 2-3 (d) şi 2-4 (e) de hipercuburi.

• • • •

a) b)
Figura 21. Reţea arbore (tree) şi arbore masiv (fat tree)

37
 A — <
A
» 1 •

t (
•
t <

— < 1— . U — i t-
„
a) b)
Figura 22. Reţea plasă 2D a) deschisă b) circulară

Figura 23. Reţea plasă 3D, deschisă |7)

a) b) c) d) e)
Figura 24. Hipercuburi in k = O - 4 dimensiuni [7J

38
 Metode eficiente de comunicare multiplă

jn cazul comunicaţiilor multiple se pot produce aglomerări pe canale, cu consecinţe

negative în ce priveşte viteza transferului, implicit a aplicaţiei de calcul paralel. Sincronizarea
tuturor proceselor care participă în comunicaţia colectivă conduce la avansarea lor la
următoarea instrucţiune numai după ce şi cel mai întârziat proces a ajuns şi a executat
comunicaţia respectivă, in figura 25 este prezentată influenţa unei comunicaţii colective într-
un grup dc 5 procese, care au ajuns la momente diferite dc timp la execuţia acestei
comunicaţii. Proccselc îşi pot continua cxccuţia numai după ce procesul PI (cel mai întârziat)
a ajuns în punctul de sincronizare. Procesele P2-P5 sunt nevoite să aştepte procesul PI
i timpul de aşteptare este figurat prin linie punctată).

PI

P2

P3

P4
timp

Figura 25. întârzierea (linie întreruptă) indusă de sincronizarea comunicaţiilor colective

La nivelul implementării comenzilor colective este deci extrem de important modul în

care acestea se realizează. Câteva astfel de situaţii, determinate de topologia conexiunilor,
sunt prezentate în continuare.

Implementarea unei comenzi Broadcast pe un inel de 8 calculatoare

Dacă presupunem că sursa este calculatorul cu identificatorul 0 şi că sensul de
parcurgere a reţelei este cel din figura 26. atunci săgeţile punctate descriu o metodă de
transmisie în 3 paşi a mesajului către toate celelalte calculatoare din inel.

o—©• <D O

© G> <D ©

• •
Figura 26 Implementarea optimă a comenzii Broadcast pe inel (7]

39
 Primul pas consta in comunicaţia intre 0 şi 4. La pasul 2 se efectuează două
comunicaţii: 0-2 şi 4-6. La pasul 3 se realizează 4 schimburi de mesaje: 0-1, 2-3, 4-5 şi 6-7.
Dacă fiecare hop (calculator intermediar) dintr-o comunicaţie este traversat într-o unitate dc
timp, atunci pentru încheierea comenzii Broadcast pc cclc 8 calculatoare sunt necesare: 4 + 2
+ 1 = 7 unităţi de timp, adică timpul optim, deoarece doar comunicaţia 0 - 7 (cel mai lung
traseu) necesită 7 unităţi dc timp. Metoda descrisă (care se numeşte metoda dublării
recursive, deoarece la fiecare pas se dublează numărul de transmisii de date) are o proprietate
foarte importantă: //ea//v canal de comunicaţie este parcurs mereu de cel mult un mesaj, deci
niciun canal nu este aglomerat.

Implementarea unei comenzi Broadcast pe o reţea mesh 2D cu 16 calculatoare [7]

Considerând că sursa este calculatorul cu identificatorul 0. atunci metoda dublării
recursive realizează comunicaţia în 4 paşi. astfel (figura 27):
• pasul 1: 0 - 8, un singur transfer, realizat în 2 unităţi de timp
• pasul 2: 0 - 4 şi 8 - 12, două transferuri simultane, care necesită o unitate dc timp
• pasul 3: 0 - 2, 4 - 6, 8 - 10 şi 12 - 14. patru trasferuri în paralel, pentru carc sunt
necesare 2 unităţi de timp
• pasul 4: 0 - 1, 2 - 3, 4 - 5. 6 - 7, 8 - 9, 10 - 11, 12 - 13 şi 14 - 15, opt schimburi
simultane de mesaje, efectuate într-o unitate de timp.
în total au fost necesare 6 unităţi de timp, ceea ce reprezintă un timp optim, deoarece
cel mai îndepărtat calculator de 0 (şi anume cel cu identificatorul 15) poate recepţiona
mesajul după ce acesta trece prin cel puţin alte 5 calculatoare (se poate observa că distanţa
Hamming între colţurile opuse ale reţelei mesh 2D din figura 27 este 6). Comanda colectivă
este realizată Jără aglomerări şi metoda dublării recursive este din nou cea mai eficientă.

Figura 27 Implementarea optimă a comcnzii Broadcast pe reţea mesh 2D

40
 t-menlarea unei comenzi Broadcast pe o reţea mesh 3D cu 8 calculatoare [7]
Pentru reţeaua mesh 3D din figura 28, execuţia unei comenzi Broadcast cu sursa 0
r r a [Link] dublării recursive conducc la 3 faze în transmisie, evidenţiate prin săgeţile
i r r r r j p t e care sunt numerotate corespunzător:
• o primă comunicaţie între 0 şi 4, care durează o unitate dc timp;
• două transmisii efectuatc în paralel, 0 — 2 şi 4 — 6, care durează tot o unitate dc
timp;
• patru schimburi simultane dc mesaje. 0 - 1 . 2 - 3 , 4 - 5 şi 6 - 7 . care de asemenea
durează o unitate de timp.
Metoda dublării recursive este optimă, deoarece realizează transmisia în cel mai scurt
— j t «calculatoarele 0 şi 7 au nevoie dc 3 unităţi de timp pentru a transfera un mesaj) şi nu
ct. - :J aglomerare pe canalele de comunicaţie.

Figura 28. Implementarea optimă a comenzii Broadcast pe reţea mesh 3D

in concluzie, implementarea comenzilor colective este extrem de importantă în cazul

i r . :aţiilor distribuite şi depinde atât de topologia reţelei, cât şi de sursă/destinaţie. Modelele
rrezentate sunt ideale, în sensul că reţelele reale nu sunt nici echilibrate, nici statice şi foarte
rar au 8 sau 16 componente.
Pentru o eficientizare a comunicaţiilor in calculul distribuit este deci nevoie de
r+noaşterea reţelei, a dinamicii acesteia, a frecvenţei schimburilor de mesaje şi a încărcării
canalelor de comunicaţie. Experienţa şi cunoştinţele programatorului sunt deci extrem de
-•tportante pentru scrierea unor aplicaţii distribuite eficiente.

41
 Capitolul 4

R e z o l v a r e a unei p r o b l e m e prin calcul c o n c u r e n t

Proiectarea unui bun algoritm concurent este dificilă, dcoarecc trebuie să rcspcctc
mncipiile generale dc cficicnţă. carc să îi asigure succcsul indiferent dc condiţiilc dc
execuţie, dar să şi ţină cont de particularităţile problemei rezolvate. Principiile generale de
e-'cienţă sunt prezentate în continuare, exemplificate pentru câteva probleme simple;
rrogramatorul care este pus in situaţii efective de rezolvare a unei probleme poate astfel
iplica aceste principii şi le poate adapta situaţiei sale concrete, in capitolul următor sunt
iescrisc câteva probleme reale, care apar des în proiectele software şi pentru care principiile
pencralc dc cficicnţă sunt discutatc.

4.1. Graful de precedenţă

Folosirea acestui instrument vizual uşurează proiectarea algoritmilor concurenţi,

ieoarece permite observarea modului în care intcracţioncază procesele. Graful de prcccdenţă
descrie ordinea în care proccsclc sc execută pentru a rezolva problema în mod concurent.
Graful de precedenţă este graful orientat aciclic în carc nodurile sunt procese şi arcul
. J) arată că procesul j poate înccpc numai după ce procesul i s-a încheiat. Reamintim că un
vraf orientat G este o pereche dc mulţimi ( V , E ) unde V este mulţimea nodurilor, iar E este
-nulţimea arcelor. E C.V xV . Graful este aciclic dacă nu există un drum închis (o succesiune
de arce care să înceapă şi să se încheie în acelaşi nod), in figura 29 este prezentat un graf
orientat ciclic, iar în figura 30 este unul aciclic, obţinut din cel din figura precedentă prin
schimbarea direcţiei unui singur arc. evidenţiat prin săgeată groasă.

Figura 29. Graf orientat ciclic Figura 30. Graf orientat aciclic

Eiemple de grafuri de prcccdcnţă

Problema I: Plecând de la matricea pătrată A(n,n) şi de la vectorul b{n), să se
calculczc cu ajutorul formulei c = A b valorile stocatc în vectorul c.
Pentru rezolvarea prin programare concurentă a accstci probleme, putem alege o granularitatc
fină. creând n procese şi repartizând fiecărui proces Pt,]<i<n calculul clementului cr
Astfel. procesul Pt are nevoie de linia i din matricea A şi de vectorul b. Procesele sunt
independente, pot fi realizate simultan în cazul ideal, când se pot repartiza fiecare unei unităţi

43
de procesare, sau se pot executa în orice ordine atunci când nu sunt suficiente unităţi de
procesare. Graful de precedenţă are deci n noduri şi niciun arc (figura 31).

0 O O o o
1 2 3 ... n- 1 n

Figura 31. Graful de precedenţă pentru n procese independente

în cazul în care se implementează o granularitate constantă k, indiferent de

dimensiunile matricei A, atunci cele k procese se alocă astfel:
• P\ calculează cl,c2,...,cll;
~k

• Pi calculează cn ,cn ,...,c„;

• calculează c „ ,c „ ,...,c„.
U-lP+l
k
(4-D-+2
k

în figura 32 este prezentat graful de precedenţă pentru k = 4.

O O O O
1 2 3 4

Figura 32. Graful de precedenţă pentru 4 procese independente

Problema 2: Plecând de la comanda SQL

SELECT * FROM CARS
WHERE MODEL = "LOGAN" AND AN = 2012 AND
(CULOARE = "ALB" OR CULOARE = "GRI");
să se descrie cum se poate executa eficient (rapid) în paralel.

Rezolvare. Această comandă SELECT foloseşte un singur tabel (CARS), din care
extrage articolele care îndeplinesc o condiţie complexă. Vom nota sub-mulţimile de articole
din CARS care sunt implicate în această execuţie astfel:
• A este formată din maşinile Logan;
• A conţine maşinile produse în anul 2012;
• A are date despre maşinile albe;
• A se referă la maşinile gri.
Comanda SELECT are deci scop listarea elementelor mulţimii
A= A,r\A2r\(A3UA4).
Elementele mulţimii A se pot afla în paralel în mai multe moduri. în cele două cazuri
pe care le vom analiza, paralelismul execuţiei va fi evaluat, folosind graful de precedenţă.
Rezolvarea 1. O posibilă rezolvare a problemei construieşte mulţimea^ astfel:
• As=AlC\A2
• A =A,UA4
• A = A5r\A6.

44
 Dacă există procesoare disponibile, atunci graful de precedenţă pentru acest mod de
rezolvare a problemei este prezentat în figura 33 (mulţimile As şi Ab se pot găsi în paralel).

A, O-

Aa

Figura 33. Graful de precedenţă pentru rezolvarea 1

Gradul de concurenţă este dat de numărul de procese care se pot desfăşura simultan. în acest
+
: i z . gradul mediu de concurenţă este ^ ^ = 2,33. Dacă presupunem că durata de

n rcuţie a proceselor este aceeaşi (în lipsa unor informaţii privind durata lor reală), atunci
mimul critic în graful de precedenţă din figura 33 are lungimea 2. Reamintim că drumul
: -;.v într-un graf aciclic este lungimea celui mai mare drum care leagă două noduri.
Rezolvarea 2. O rezolvare cu un grad mediu de concurenţă mai scăzut poate construi
mulţimea^ astfel:
. A5 = A}\JA4
. A6 = A2r\A5
• A = A]C\A6.

Figura 34. Graful de precedenţă pentru rezolvarea 2

; , , , - 4 + 1 + 1 + 1 , „^ . , , ..
In acest caz, gradul mediu de concurenţa este = 1,75 şi drumul critic are
Msmea 5.

45
 în capitolul următor vom prezenta o problemă pentru care vom analiza din nou efectul
ordinii efectuării unor operaţii asociative. Aici am considerat că durata proceselor este
identică; în subcapitolul 5.2 vom vedea care este impactul unor durate diverse asupra
timpului total de execuţie al unei aplicaţii paralele.

Evaluarea paralelismului
în cazul unei aplicaţii paralele, programatorii sunt interesaţi de optimizarea
următoarelor caracteristici:
• gradul maxim de concurenţă, care arată numărul maxim de unităţi de procesare
disponibile, fiind deci o valoare limitată de configuraţia hardware pe care se
execută aplicaţia;
• gradul mediu de concurenţă, care arată cât de „paralelizată" este o aplicaţie, fiind
o imagine a eficienţei algoritmului;
• drumul critic al grafului de precedenţă, care este lungimea maximă a drumurilor în
graf, obţinută prin ponderarea nodurilor cu timpii corespunzători de execuţie.
Această valoare arată timpul total de execuţie.

Aceste măsuri sunt caracteristice aplicaţiilor concurente, adăugându-se măsurilor

cantitative generale ale aplicaţiilor (complexitate, număr de linii de cod, timp de execuţie,
etc.) şi celor calitative, specifice Ingineriei software (portabilitate, claritate, mentenabilitate,
etc.). Cele două probleme concrete prezentate anterior arată cum graful de precedenţă este un
instrument general, care poate evalua eficienţa unei metode concurente de rezolvare.

4.2. Metode de descompunere a rezolvării unei probleme

Realizarea unei aplicaţii concurente presupune (printre altele) şi partajarea activităţii

între mai multe procese desfăşurate concurent. Descompunerea se referă atât la efortul de
procesare (descompunere funcţională), cât şi la repartizarea datelor pe mai multe procese
(idescompunerea domeniului). De fapt, această clasificare urmează clasificarea Flynn
(descrisă în subcapitolul 1.3), considerând dimensiunea proceselor (pentru descompunerea
funcţională) şi a datelor (pentru descompunerea domeniului). O aplicaţie complexă poate
folosi diverse tipuri de descompunere, caz în care descompunerea sa devine hibridă.

4.2.1. Descompunere funcţională

Descompunerea funcţională descrie modul în care efortul computaţional se

repartizează unor procese care avansează concurent. Problema care se rezolvă poate avea o
descompunere „naturală" în procese - caz în care programatorul o poate folosi. Există însă şi
metode generale, care se pot aplica unor categorii de probleme.
Descompunerea recursivă este o descompunere funcţională care lansează recursiv
procese, care rezolvă fiecare câte o sub-problemă. Dacă metoda de rezolvare este de tip
divide-et-impera, atunci fiecare sub-problemă se poate rezolva folosind un proces, lansat prin
recursivitate; soluţiile sub-problemelor sunt colectate de procesul iniţial, care construieşte din
acestea soluţia problemei. Comunicaţiile în acest caz se rezumă doar la lansarea recursivă a
noilor procese şi la colectarea soluţiilor, deoarece sub-problemele derivate prin divide-et-
impera sunt independente. Dacă problema se rezolvă prin programarea dinamică, atunci tot
prin recursivitate se pot genera procese destinate rezolvării sub-problemelor. Modelul
comunicaţiilor va fi mai complicat, deoarece în acest caz sub-problemele sunt dependente.

46
 Exemple de paralelizare prin descompunere recursivă sunt: calculul termenului
iszsmc din şirul lui Fibonacci (prezentat în Capitolul 1), sau sortarea prin metoda rapidă
,iuDct-sorr).
Descompunerea speculativă este descompunerea funcţională în care se lansează (pe
T : c e s o a r e care altfel nu ar avea încărcare) în avans procese-alternative: procese care
- .oe ează ramurile unei instrucţiuni if-then-else sau case/switch. Când procesul-părinte
. a r c e la respectiva instrucţiune şi decide care este ramura pe care se va avansa, atunci se
inc - i toate procesele-fiu şi se preia starea procesului-ftu corespunzător ramurii alese.

4.2.2. Descompunerea domeniului

Descompunerea domeniului se referă la repartizarea datelor problemei pe diverse

rrccese. care le vor prelucra în paralel. La nevoie, în final, rezultatele proceselor se
±s^r.?!ează în soluţia problemei.
Un exemplu de descompunerea a domeniului este descompunerea exploratorie, în
re spaţiul de soluţii este partajat în mulţimi disjuncte, fiecare apoi fiind repartizată unui
rrcces spre investigare. Fiecare proces găseşte o soluţie optimă în mulţimea sa; aceste soluţii
r c a m e sunt preluate de un proces şi este aleasă cea mai bună dintre ele, care devine soluţia
rcc clemei. O astfel de problemă este alegerea mutărilor într-un joc (de exemplu, în jocul de
xil- algoritmul poate dezvolta un arbore, care are în rădăcină starea curentă şi fii rădăcinii
smt toate mutările posibile. Fiecare dintre fii rădăcinii este repartizat (ca fiind starea curentă)
zrui proces, care alege cea mai bună mutare, ţinând cont şi de mutările adversarului. Apoi se
ilege dintre aceste soluţii foarte bune, pe cea mai bună.
Un alt exemplu este descompunerea datelor, când se partajează datele pe procese
aceeaşi idee ca în cazul SIMD din clasificarea Flynn). Datele de intrare se partajează dacă se
execută o interogare pe o bază de date distribuită: de la fiecare centru de stocare se
recepţionează rezultatele intermediare, care sunt asamblate pe sistemul clientului.
Descompunerea datelor de ieşire se poate realiza dacă se consideră calculele numeric
—tensive, de exemplu problema 1 de la subcapitolul 4.1.

Descompunerea problemei este extrem de importantă în calitatea aplicaţiei care o

-ezoh ă, deoarece determină echilibrul, încărcarea şi comunicaţiile între procese.

47
 Capitolul 5

Tehnici efective de paralelizare

în acest capitol sunt prezentate câteva metode de paralelizare pentru aplicaţii des
întâlnite în proiectele software. Am ales două exemple din calculul numeric şi câteva
rrobleme conexe sortării, pentru a ilustra posibilităţi diverse de paralelizare; la fiecare
rroblemă am evidenţiat specificul său, avantajele metodei alese, dar şi dezavantajele sale.
Rămâne ca programatorul să decidă modul efectiv de implementare a paralelizării, în funcţie
de problemă, infrastructură şi propria experienţă.

5.1. Paralelizarea calculului numeric

Calculul numeric este un domeniu în care utilizarea resurselor de calcul în paralel

aduce mari avantaje şi se realizează relativ uşor, existând situaţii în care descompunerea
problemei este oarecum naturală. Dintre probleme care se pretează abordării prin calculul
paralel, în continuare este prezentată în detaliu Metoda lui Gauss a eliminării succesive
pentru rezolvarea sistemelor liniare de ecuaţii. Vom începe cu descrierea problemei, vom
continua cu metoda secvenţială de rezolvare, urmată de o metodă paralelă şi vom încheia cu
câteva concluzii.

A rezolva un sistem de ecuaţii liniare înseamnă a găsi variabilele reale (jc,) lsis „,
n e N care satisfac simultan ecuaţiile:
"a„x, + al2x2+...alrtx„ =bx
a2lxl+a22x2+...a2nxn =b2
unde (a iy ) I£MS „ şi (b,)Kiin sunt numere reale.

a„^x+an2x2+...annxn =bn
Această problemă este echivalentă cu găsirea unui vector x cu n elemente reale care să
satisfacă ecuaţia matriceală A-x-b, unde A este matricea coeficienţilor şi b este vectorul
termenilor liberi ai sistemului considerat.
în acest curs vom considera că sistemul are o soluţie unică şi că toate operaţiile de
împărţire descrise în metoda de rezolvare se pot executa (la nevoie ecuaţiile se permută).
Metoda lui Gauss a eliminării succesive constă din două etape:
1. ecuaţiile se transformă în mod repetat până când sistemul ajunge la forma
triunghiular-superioară
x + c x
\ u2 „x„ =d [
x2 +... c2n Xn d2

x„n = d„n
2. se rezolvă sistemul „de jos în sus".

49
 5.1.1. Exemplu de rezolvare prin metoda lui Gauss

Pentru a avea o perspectivă asupra metodei generale de rezolvare, vom începe prin a
rezolva prin metoda lui Gauss următorul sistem liniar de 3 ecuaţii cu 3 necunoscute
( Xj ţ X2 5 Xj ^ ^
2x, + 2x2 + 2x} = 6
< 2xt + 4x2 + 6x3 = 12
3.x, -6x2 -9x3 = -12
Prima etapă începe prin împărţirea coeficienţilor primei ecuaţii la 2, pentru a se obţine
coeficientul lui xj egal cu 1 (.se normalizează prima ecuaţie):
"i- X2 — 3
x] + 4jc, +6a: 3 = 12
3xt - 6x2 - 9x3 - -12
Pasul următor constă în eliminarea variabilei x j din ecuaţiile 2 şi 3. Pentru a atinge
acest ţel vom înmulţi prima ecuaţie cu 2 şi o vom scădea din cea de-a doua. La fel, o vom
înmulţi pe prima cu 3 şi o vom scădea din a treia:
Xj X2 Xş 3|(2)|(3) x3 = 3
2xt + 4x2 + 6X3 12 2X2 + 4jc3 = 6
3x. •6X2 - 9 X 3 = - 1 2 - 9X2 -1 2JC3 = —21
începând de la acest moment, prima ecuaţie va rămâne neschimbată până la sfârşitul
acestei etape. Ultimele două ecuaţii constituie un sistem de două ecuaţii cu două necunoscute,
pentru care aplicăm din nou metoda reducerii. Vom împărţi prima dintre aceste două ecuaţii
cu 2 (o vom normaliza) şi astfel sistemul devine:
^1 ^ Xş 3
x2 + 2x} = 3
— 9x2 - 1 2 X 3 = - 2 1
La pasul următor se înmulţeşte această ecuaţie cu (-9) şi se scade din ultima:
Xj I X'y I X^ 3 + x, = 3
2jc3 = 3|(-9) x2 + 2;c3 = 3
-9x2 -12*3 =—21 6X3 = 6
Am ajuns la ultima prelucrare, când normalizarea ultimei ecuaţii conduce la sistemul:
= 3
X'2 1 =3
= 1
Cea de-a doua etapă începe prin atribuirea valorii 1 variabilei xj, conform ultimei
ecuaţii. Această valoare se introduce în toate celelalte ecuaţii, obţinându-se sistemul:
xl+ x2 = 3 — 1 x^ "i- X2 2
x2 =3-2-1 x2 = 1
x, = 1 X, = 1
Procedeul se repetă pentru sistemul triunghiular alcătuit din primele două ecuaţii:
variabila x^ ia valoarea 1, care se înlocuieşte în prima ecuaţie:

50
 -v, = 2 - 1 x] = 1
• x 2 = 1 => - x2 = 1
x3 = 1
Sistemul este rezolvat, soluţia unică fiind tripletul (1, 1, 1).

5.1.2. Metoda lui Gauss - versiunea secvenţială

Pentru descrierea la nivel general a primei etape vom utiliza A*, matricea extinsă a
- >:emului, obţinută prin adăugarea la A a coloanei termenilor liberi:
A' =(A\b)
deci A are n linii şi n + 1 coloane. Toate operaţiile se vor realiza pe această matrice şi
>£ vom considera transformări de variabile, deci vom utiliza acelaşi nume pentru elementele
A . deşi valorile se modifică. De exemplu, coeficientul lui X2 din a doua ecuaţie va fi
mereu deşi va avea diverse valori ( a ^ este deci o variabilă).

Varianta secvenţială a etapei 1 (triangularizarea matricei extinse)

f o r (i = 1; i <= n; i++)
// normalizarea rândului i:
f o r ( j = 1; j <= n; j++)
a
ij = aij t a
n

b,=b,/an
II eliminarea variabilei x, din toate rândurile k de după rândul;':
f o r (k = i + 1; k <= n; k++)
f o r ( j = i ; j <= n; j++)
a
% = kj-aki-aij
K =K~aklbi

'• arianta secvenţială a etapei 2 (rezolvarea efectivă a sistemului):

f o r (i = n; i >= 1; i —)
// eliminarea necunoscutei x,
= b,
II înlocuirea valorii găsite în toate rândurile k de deasupra rândul i:
f o r (k = 1; k <= i - 1; k++)
h =hk~ a
k, 'b,

5.1.3. Metoda lui Gauss - versiunea paralelă

Una dintre metodele de paralelizare consideră n procese, care stochează fiecare câte o
:nie din matricea extinsă, o prelucrează şi la nevoie transmite celorlalte procese valorile
raxate. Dacă alegem o sincronizare a proceselor la sfârşitul fiecărei iteraţii controlate de
. inabila / de mai sus, atunci varianta paralelă a metodei descrise mai sus evoluează astfel:
/Etapa 1, prima iteraţie: se prelucrează prima coloană din matricea extinsă
//(lucrează toate procesele):
• procesul Pt realizează normalizarea primei linii

51
• procesul Pl transmite proceselor P2- Pnvalorile a]2...au (valoarea aflată în au
este 1, deci nu se mai transmite)
• procesele P2 - Pn realizează transformări liniare ale valorilor stocate, astfel ca
fiecare dintre valorile stocate pe prima poziţie (variabilele an, 2<i<n) să fie
zero
//iteraţia 2: se prelucrează a doua coloană din matricea extinsă
//(lucrează procesele P2- Pn):
• procesul P2 realizează normalizarea celei de-a doua linii
• procesul P2 transmite proceselor P,- Pn valorile a2i...aZn (a22= 1, deci nu se mai
transmite)
• procesele P} - Pn realizează transformări liniare ale valorilor stocate pe ultimele n
poziţii, astfel ca fiecare dintre valorile stocate pe a doua poziţie (variabilele ai2, cu
3 < j < n ) să fie zero
//aceşti paşi se repetă astfel că la penultima iteraţie a etapei 1 lucrează doar procesele
Pn -
• procesul /*„_, realizează normalizarea penultimei linii
• procesul transmite procesului Pn valoarea an_, n
• procesul Pn realizează o transformare liniară ale valorilor stocate pe ultimele 2
poziţii, astfel ca a n să fie zero
//la ultima iteraţie a etapei 1, procesul Pn asigură coeficientul 1 pentru ultima ecuaţie,
care are o singură necunoscută şi care face posibilă începerea etapei 2, de rezolvare
efectivă a sistemului de ecuaţii liniare:
• procesul Pn realizează normalizarea ultimei linii (ecuaţia devine deci xn = bn)
//etapa 2, prima iteraţie (lucrează toate procesele: variabila xn are deci valoarea bn, pe
care procesul Pn o transmite tuturor celorlalte procese; fiecare dintre acestea îşi
recalculează termenul liber corespunzător):
• procesul Pn transmite proceselor Pl - faptul că variabila xn are valoarea bn
(aceasta este prima necunoscută aflată, sistemul triunghiular rezolvându-se „de jos
în sus")
• fiecare dintre procesele Px-Pn_x actualizează câte o valoare b]..bt^] (la sfârşitul
acestei iteraţii, penultima ecuaţie a sistemului nostru devine xn_x = bn_x)
//etapa 2, a doua iteraţie (lucrează procesele P] - Pn_x: valoarea bn_t a necunoscutei
xn_, este transmisă proceselor Pl - Pn_2 de către procesul , iar fiecare dintre acestea
recalculează termenul său liber):
• procesul />„_, transmite proceselor P{ - Pn_2 faptul că variabila xn_x are valoarea
V,
• fiecare dintre procesele P} - Pn_2 actualizează valoarea variabilei corespunzătoare
dintre b,...b
I n—Z,
//aceşti paşi se repetă astfel că la penultima iteraţie a etapei 2 lucrează doar procesele
P, Şi Pi-
• procesul P2 transmite procesului Pt valoarea b2 pentru variabila x2

52
 • procesul P] actualizează valoarea variabilei b}
la. sfârşitul acestui algoritm, procesul f\ este în posesia valorii pentru necunoscuta
.r,, fiecare proces cunoaşte câte o necunoscută şi o poate afişa:
• fiecare dintre procesele Pt - Pn afişează valoarea necunoscutei corespunzătoare din
secvenţa xl...xn.

Observaţii privind eficienţa acestei metode de paralelizare

Aşa cum am prezentat în capitolul 4, vom utiliza graful de precedenţă şi metoda de

descompunere a problemei pentru a analiza eficienţa aplicaţiei.
în figura 35 este prezentat graful de precedenţă pentru iteraţia k a primei etape, iar în
ngura 36 se află graful de precedenţă pentru iteraţia k din etapa a doua.

Figura 35. Graful de precedenţă pentru iteraţia k, etapa 1

Figura 36. Graful de precedenţă pentru iteraţia k, etapa 2

1. Aşa cum am menţionat deja, metoda rezolvă doar sistemele compatibile unic
determinate (care au soluţie unică), când elementele au sunt nenule, permiţând
normalizarea ecuaţiilor.
2. Sincronizarea implicită, produsă de comunicaţiile colective (un proces transmite şi
un grup de procese recepţionează) este inerent înceată, aşa cum se prezintă în
subcapitolul 3.2.
3. în medie, jumătate dintre procese lucrează, în timp ce cealaltă jumătate este în
stare idle, ceea ce este ineficient. Pentru realizarea primei etape a algoritmului, de
exemplu, toate procesele lucrează la început, iar pe măsură ce prima etapă
avansează, numărul proceselor care aşteaptă creşte cu o unitate la fiecare iteraţie.
La fel se întâmplă şi în a doua etapă.
4. Descompunerea problemei este atât funcţională, cât şi în domeniu, deci este
hibridă (conform clasificării din subcapitolul 4.2).

Această metodă nu este eficientă, dar a fost aleasă cu scop didactic, deoarece se
bazează pe metoda secvenţială şi se dezvoltă cu minime transformări. Există multe alte

53
metode de paralelizare a rezolvării sistemelor de ecuaţii liniare. Programatorul o va alege pe
cea care se potriveşte arhitecturii şi restricţiilor problemei sale. De exemplu, într-o reţea în
care comunicaţiile au costuri înalte, ar putea alege alocarea unui grup de ecuaţii unui singur
proces, pentru a scădea numărul de comunicaţii. Sau, dacă matricea corespunzătoare
sistemului are multe elemente nule (sparse matrix), ar putea folosi metode mai elaborate,
cum ar fi cele dedicate matricelor tri-diagonale, care apar în modelarea fenomenelor de
difuzie.

5.2. Paralelizarea tehnicilor de programare dinamică

Una dintre provocările vieţii contemporane este complexitatea problemelor abordate:

situaţiile actuale sunt atât de complicate, cu atât de mulţi parametri care sunt interdependenţi,
cu mulţimi atât de mari de cazuri posibile, încât sunt esenţiale metodele care speculează orice
caracteristică şi reuşesc să reducă din resursele consumate pentru a găsi o soluţie. A specula
în acest sens nu are deloc conotaţii negative, deoarece implică o cunoaştere profundă a
problemei abordate, un grad înalt de expertiză în alegerea resurselor utilizate, a metodelor de
rezolvare sau a platformei de calcul. Scopul este întotdeauna eficientizarea procesării
electronice, pentru a obţine cu costuri minime (timp de procesare, unităţi de procesare,
transmisii de date, etc.) o soluţie de calitate cât mai bună la problema abordată.
Un exemplu care ilustrează importanţa metodei în abordarea unei probleme este
prezentat în continuare.
Primăria municipiului Bucureşti are în vedere trimiterea unei scrisori de felicitare
tuturor femeilor în vârstă de peste 70 de ani, cu ocazia zilei de 8 Martie. Consultând baza de
date de la Direcţia Generală de Evidenţă a Persoanelor cu domiciliul în Municipiul Bucureşti,
se cunoaşte că există 2 milioane de locuitori, dintre care 1 milion de femei şi 20.000 de
persoane în vârstă de peste 70 de ani. Se mai cunoaşte că un test al unui articol din baza de
date se realizează într-o nanosecundă şi că sistemul de gestiune al bazei de date are
implementat un modul de optimizare a interogărilor, care nu mai testează şi al doilea operand
al unei expresii logice compuse, în cazul în care operatorul este AND, iar primul operand
returnează valoarea FALSE. Vom studia diverse metode de rezolvare a acestei probleme.
Una dintre comenzile SQL care s-ar putea utiliza este:
SELECT * FROM TABEL WHERE SEX = "F" AND VARSTA >=70;
care testează toate cele 2 milioane de articole din TABEL, dar în cazul celor 1 milion
de femei se mai execută şi testul de vârstă, deci sunt necesare 2.000.000 + 1.000.000 =
3.000.000 teste, care se realizează în 3 • IO6 • 10~9 = 0,003 s.
O altă posibilitate ar fi comanda:
SELECT * FROM TABEL WHERE VARSTA >=70 AND SEX = "F";
care diferă de precedenta doar prin interschimbarea operanzilor din condiţia de test. In
acest caz, se realizează 2.000.000 + 20.000 = 2.020.000 teste, care necesită 0,00202 s. Deşi
timpul necesar nu diferă în mod esenţial de cel obţinut în primul caz, raportul lor arată o
creştere a vitezei de calcul cu aproximativ 32% . Aceasta este o situaţie care ar putea apărea o
dată pe an, de 8 Martie, dar există scenarii care apar frecvent. Un astfel de exemplu este
interogarea bazei de date a autoturismelor înmatriculate în România (aproximativ 4,5
milioane de unităţi) în cazul unui eveniment rutier în care nu s-a putut afla numărul de
înmatriculare, ci doar culoarea şi marca. Conform observaţiilor anterioare, este mai eficientă
testarea prima dată a condiţiei mai restrictive.
Exemplul următor este mult mai elaborat, apare mult mai des în ştiinţele
computaţionale şi arată impactul major al folosirii unor metode inteligente.

54
 înmulţirea matricelor este o operaţie frecventă în cazul modelării proceselor
-.dustriale; de exemplu, comportarea aerodinamică a unui vehicul se poate modela folosind
— etoda elementului finit {Finite Element Analvsis - FEA), care rezolvă numeric sisteme de
ec -arii diferenţiale. înmulţirea matricelor este o operaţie comună, care se învaţă în primele
.-•arsuri de programare a calculatoarelor. în majoritatea cazurilor, programatorii nu dau atenţie
icestei operaţii, considerând că nu pot interveni în optimizarea costului său. Dacă însă
—ancele sunt de dimensiuni mari şi înmulţirea lor este frecventă, atunci se pune problema
icamizării calculelor. Vom studia în continuare problema ordinii optime pentru înmulţirea
—ii multor matrice. Vom începe printr-un exemplu.

Problema 1
Se dau matricele ,4,(10,20), A2 (20,30) şi ^ ( 3 0 , 4 0 ) . Să se afle ordinea înmulţirii lor
; - consum minim de resurse (cu cât mai puţine operaţii de înmulţire).
Rezolvare
Pentru aflarea fiecărui element al produsului matricelor A(m,n)şi B(n, p) sunt
necesare n înmulţiri; cum matricea rezultat C = A - B are m p elemente, înseamnă că pentru
i înmulţi matricele A şi B sunt necesare m-n- p înmulţiri.
Produsul matricelor din problema noastră se poate realiza în două moduri:
• cazul 1. (A]xA2)xA3, când se realizează mai întâi 10-20-30 = 6.000 de
înmulţiri şi apoi matricea rezultată (care are dimensiunile 10, 30) se înmulţeşte cu
A}. Ultima operaţie necesită încă 10-30-40 = 12.000 înmulţiri, deci în total sunt
necesare 18.000 de înmulţiri.
• cazul 2. A1x(A2xA3), când sunt necesare mai întâi 2 0 - 3 0 - 4 0 = 24.000 de
înmulţiri şi apoi matricea rezultată (care are dimensiunile 20, 40) se înmulţeşte cu
A,. Acest lucru mai adaugă 10-20-40 = 8.000 înmulţiri, deci în total sunt
necesare 32.000 de înmulţiri.
Se observă cum ordinea efectuării operaţiilor a condus la o diferenţă foarte mare în ce
pnveşte consumul de resurse: în cel de-al doilea caz, au fost necesare cu peste 75% mai multe
înmulţiri decât în primul caz. Cazul 1 reprezintă deci alegerea optimă.

Problema 2 (Generalizare)
Se dau n matrice (Af(rt c,.)),<,.<„ şi se doreşte obţinerea matricei produs
A x.-t- x...xAtl. Să se afle ordinea optimă (cu cât mai puţine înmulţiri) în care ar trebui să fie
înmulţite.
Discuţie
Evident, pentru a putea înmulţi matricele, avem c ; = rM, 1 < i < n.
Dacă ne-am propune rezolvarea problemei prin metoda forţei brute, ar trebui
inspectate toate posibilităţile. A număra soluţiile posibile înseamnă a număra în câte moduri
se poate realiza înmulţirea a n matrice, cu alte cuvinte, în câte moduri putem ordona cele
t - 1 produse. Acest lucru înseamnă să alocăm fiecărui semn x din A,xA2 x...xAn câte un
număr din mulţimea {l,2,...,« — l}. Alocarea se poate face în (w-1)! moduri, deci
:omplexitatea problemei creşte exponenţial în funcţie de numărul de matrice. Forţa brută este
ieci exclusă, rămâne să găsim o altă metodă care să asigure o rezolvare eficientă. Această
rezolvare se bazează pe programarea dinamică.
Programarea dinamică este o metodă de rezolvare a problemelor complexe prin
descompunerea lor în probleme mai simple, care se rezolvă (eventual prin repetarea
rrocedeului) uşor şi ale căror soluţii se folosesc în construirea soluţiei problemei iniţiale. în

55
Informatică mai există o metodă de descompunere, numită divide-and-conquer (divide et
impera), care impune ca sub-problemele să fie independente. Prin faptul că sub-problemele se
pot suprapune, Programarea dinamică este mai dificil de aplicat, deoarece soluţiile sub-
problemelor au componente comune, care pot avea parametri diferiţi şi deci compunerea lor
necesită atenţie sporită. Provocarea în cazul programării dinamice nu o reprezintă
descompunerea problemei, ci găsirea metodei eficiente de re-compunere a soluţiilor.
Problema propusă este un exemplu de aplicare cu succes a programării dinamice.
Vom prezenta întâi varianta secvenţială şi apoi pe cea paralelă.
Rezolvare
Vom nota prin C(i,j) costul optim pentru realizarea A,*...* A,\ < i < j < n.
Soluţia problemei este C(l,n) şi în mod evident C(i,i) = 0,1 <i < n. Pentru i < j , vom căuta
o relaţie care să permită calculul valorilor C(i,j) pe baza valorilor intermediare C(i,k) şi
C(k,j), unde i<k < j.
Presupunem deci că i < j . Pe ultimul produs de matrice efectuat pentru obţinerea cu
cost minim a A^.-.xAj îl vom evidenţia scriind (A, x . . . x Ak) x (Ak+l x...Ai),i<k <j .
C(i,j) este deci valoarea dată de „cel mai bun" k ales între i şi j, astfel încât

C(i,k) + C(k + \,j) + costul ultimului produs

să fie minim. Ultimul produs se realizează între două matrice care au dimensiunile (ri, ck) şi
(rM,Cj) şi este deci de cost rf • rk+l •cr
în concluzie, relaţia care permite adăugarea unui nou produs şirului deja realizat de
produse de matrice este:

—• \min(C(i,k) + C(k + l,j) + rrrk+l-c.),pentrui<j

C(i,j) = \f<J
[0, pentru i = j

Aşa cum am menţionat în partea de Discuţii de mai sus, găsirea acestei formule
reprezintă dificultatea rezolvării problemei propuse. De aici înainte, urmează o parte
algoritmică simplă, care porneşte de la valorile C(i,i) = 0,\<i<n şi construieşte iterativ
elemente de tip C(i, j), până când ajunge la C(1,/j) .
Interesant este faptul că valorile sunt guvernate de 2 indici, nu avem de-a face cu un
şir, aşa cum suntem obişnuiţi din alte situaţii. Se generează deci o matrice pătratică de
dimensiune n, în care sunt definite doar elementele aflate în triunghiul superior: se porneşte
de la n elemente zero aflate pe diagonala principală şi la fiecare pas se calculează cu unul mai
puţine, poziţionate paralel cu această diagonală, către dreapta-sus, până se ajunge la
elementul aflat în colţul din dreapta-sus, care reprezintă şi soluţia problemei noastre.

Algoritmul secvenţial
for ( i = 1; i <= n ; i++)
// iniţializarea elementelor de pe diagonala principală:
C(i,i) = 0
for (j = 1; j < n ; j++)
f o r ( i = 1 ; i <= n - j; i++)
compute C(i,i + j)
return C(l,/z)

56
 Exemplu pentru înmulţirea a 4 matrice
Să presupunem că avem de înmulţit 4 matrice, care au dimensiunile (10,20), (20,30),
:
- i şi (40,50). Vom descrie grafic evoluţia algoritmului, folosind şablonul de comunicaţii
o u [Link] 37, în care nodurile conţin cei doi indici, valoarea costului minim şi dimensiunile
nacrxei corespunzătoare. Observăm că nodurile corespund elementelor matricei, care ar
j c e a fi alocate fiecare câte unui proces.

Primul pas contă în completarea valorilor pentru cele 4 noduri poziţionate pe

; ir^oala principală: C(l,l), C(2,2), C(3,3) şi C(4,4) primesc fiecare valoarea 0, iar
a ~ emisiunile matricelor sunt cele iniţiale.
Urmează calcularea valorilor C(l,2), C(2,3) şi C(3,4), conform săgeţilor drepte şi a
:c*?ervaţiei anterioare (pentru a înmulţi matricele A(m,n)şi B(n,p) sunt necesare m n p
- — Jţiri). De exemplu, C(l,2) are valoarea 10 • 20-30 = 6.000, iar dimensiunea produsului
gemelor două matrice este (10,30).
La etapa următoare se calculează C(l,3) şi C(2,4). Pentru claritate, au fost desenate
i n i e subţire arcele incidente nodului care calculează C(l,3). Conform definiţiei,
C(l,3) = min {6.000 +10 • 30 • 40,10 • 20 • 40 + 24.000}
C(1.3) = min{18.000, 32.000} = 18.000 - observăm că am regăsit rezultatul de la
F'^oblema 1.
Similar, se calculează C(2,4):
C(2,4) = min {24.000 + 20 • 40 • 50, 20 • 30 • 40 + 24.000}
C(2,4) = min{64.000, 48.000} = 48.000

57
 Ultima etapă constă în aflarea valorii C( 1,4), figurată în desen prin linii groase
C(l,4) = min {18.000 + 1 0 • 40 • 5 0 , 6 . 0 0 0 + 60.000 + 1 0 • 30 • 50,10 • 20 • 50 + 48.000}
C(l,4) = min {38.000,81.000, 58.000} = 38.000
Prin marcarea în graf a drumului care conduce la costul optim, aflăm că în acest caz
cea mai eficientă ordine a efectuării operaţiilor este cea naturală, de la stânga la dreapta.

Algoritmul paralel
Paralelizarea algoritmului general (pentru matrice de dimensiune n) se poate realiza
folosind n procese care sincronizează la fiecare sfârşit al iteraţiei conduse de variabila j din
metoda secvenţială descrisă deja.
Figura 37 sugerează şablonul comunicaţiilor pentru cazul general (n procese), care şi
de această dată sunt colective (all-to-all), deoarece la flecare pas sunt necesare valori din
toate iteraţiile precedente. Fiecare proces Pi construieşte propria matrice C (care este deci
stocată redundant, dar astfel se scade numărul comunicaţiilor), fie calculând valorile de pe
coloana i, cea care îi este alocată, fie primind de la celelalte procese valorile aflate pe
celelalte coloane.
Evoluţia metodei paralele poate fi descrisă ca o undă care porneşte de pe diagonala
principală şi înaintează până în colţul din dreapta-sus al matricei C. In algoritmul paralel,
secvenţa repetitivă for_all desemnează execuţii în paralel.

for_all (k = 1; k <= n; k++)

process Pk computes
for (i = 1; i <= n; i++)
// iniţializarea elementelor de pe diagonala principală:
C(i,/) = 0
for (j = 1; j < n; j++)
for_all (i « 1; i <= n - j; i++)
process Pi+J computes C(i,i + j )
Broadcast {C(i,i + j ) , Pi+J , all)
process Pn writes C(l,w)

Dezvoltarea simultană ca o undă a mai multor procese este întâlnită în natură

(valurile, fronturile atmosferice de exemplu) şi este preluată în calculul paralel prin algoritmii
sistolici introduşi în anii 80 ai secolului trecut [10],

Observaţii privind eficienţa acestei metode de paralelizare

Graful din figura 37 descrie modul în care se poate descompune algoritmul, alocând
câte o valoare din matricea C pe fiecare proces. Acest mod de descompunere este extrem de

ineficient, deoarece din cele ^ procesoare, ar lucra simultan cel mult n.

O altă strategie ar fi descompunerea pe n procese, care să lucreze toate la început, iar

pe măsură ce aplicaţia avansează, să lucreze din ce în ce mai puţine, asemănător cu exemplul
din subcapitolul anterior. Cele patru consideraţii menţionate acolo se menţin şi în cazul de
faţă.

58
 5.3. Paralelizarea sortării şi a problemelor conexe

Sortarea presupune ordonarea unei secvenţe după un anumit criteriu. în prelucrarea

datelor, sortarea este o problemă des întâlnită, căreia i se acordă o mare importanţă. Volumele
actuale de date şi prelucrările dese necesită metode eficiente de sortare. Conceptul Big Data
se referă tocmai la astfel de volume uriaşe de date complexe, cărora nu li se mai pot aplica
prelucrările tradiţionale [11]. Facilităţile hardware şi de comunicaţie recente permit
implementarea unor metode paralele de sortare, care sunt utilizate în abordarea altor
probleme, bazate pe sortare.
Necesitatea cunoaşterii unor metode eficiente de sortare provine atât din nevoile
intrinseci, de ordonare a unor volume mari de date, cât şi extrinseci, în rezolvarea unor alte
probleme care presupun şi sortări diverse [9], Aceste probleme sunt prezentate în continuare.
Toate aceste probleme manevrează o secvenţă de valori total ordonate (între oricare două
elemente se poate stabili o ordine).

5.3.1. Problema găsirii optimului

Problema găsirii optimului constă în aflarea celui mai mic (mare) element dintr-o
secvenţă. în cele ce urmează vom trata cazul căutării valorii minime. Algoritmul secvenţial
constă în preluarea primei valori din secvenţă în variabila min şi apoi parcurgerea secvenţei
începând de la al doilea element şi până la sfârşit, compararea valorii curente cu valoarea
stocată în variabila min şi actualizarea variabilei min dacă valoarea sa este mai mare decât
valoarea curentă:

min = a[1]
for (i = 2; i <= n; i++)
if (a[i] < min) then min a[i]

în cazul paralel, algoritmul lucrează după modelul turneului. Vom începe cu

următorul exemplu: presupunem că avem de prelucrat 8 valori şi strategia folosită va fi să
comparăm perechi de elemente alăturate, păstrând cea mai mică valoare din fiecare pereche şi
generând la fiecare pas o nouă secvenţă, având jumătate din numărul anterior de elemente.
Procesul se opreşte când lungimea secvenţei este 1 şi valoarea respectivă este deci cel mai
mic element din secvenţa iniţială (valoarea 1 este încercuită).

Valorile iniţiale: 7 4 3 6 2 1 8 5

Pasul 1: 4 3 1 5

Pasul 2: 3 1

Pasul 3, final:
O
O versiune a metodei turneului care păstrează constantă lungimea secvenţei lucrează
astfel:
• dist = 1
• cât timp dist permite comparare:
o se compară elementele aflate la distanţa dist

59
 o se inter-schimbă elementele comparate, dacă 3_r- tu. san: x i . - a t e
crescător
o se dublează dist
• se preia în variabila min elementul de pe prima poziţie.

Această descriere în limbaj natural lucrează astfel pentru x> _

Valorile iniţiale: 7 4 3 6 2 Îl t 5 j

Pasul 1: 4 7 3 6 1 2 i 5 i
j V
V
V

Pasul 2: 4 6 1— 2 5 1

Pasul 3, final: 7 4 6 3 2 5 f

Observăm că pentru găsirea optimului unei secvenţe de 1 . - g — e * = Z fost

necesari 3 = log2(8) paşi. în cazul general, pentru n = 2 k , procedura :r ascrel

for (i = 1; i <= log2 (n) ; i++)

for_all(j = 0; j < n/21; j++)
if a[j*2i+l]>a[j*2i+2i~1+l] then
swap (a [ j *2 i +l ] , a [ j *2i+2i"1+l])

Observăm din nou secvenţa repetitivă for all care desemnează ; : in paralel.
Pentru interschimbare s-a folosit metoda swap care are 2 a r g u m e n t Dacă n_ : putere
a lui 2, atunci vor exista paşi la care nu se vor putea realiza perech e : >c -or r a n s f e r a
valorile în etapa următoare, la fel cum în turnee unii jucători trec "-. raza -m-Jniere rară a
disputa meciul.
Paralelizarea cu sincronizare la fiecare actualizare a contorul-: necesnă I procese
la pasul 1 şi pe măsură ce rezolvarea avansează, numărul acestora se in; la fiecare
pas. Fiecare proces execută (la fiecare pas) o singură comparaţie şi ever.r_a : naer>cm—bare.
Dacă însă se alege o rezolvare prin memorie partajată, atunc. procesele icare [Link]-
schimbă eventual valori în perechi independente) pot lucra extrem de e n c i e m si iară a se
produce coliziunile la scriere descrise în subcapitolul 3.2. D e z a v a n t a j memoriei
comune este faptul că scrierile se produc la aceleaşi momente de timp in : a:e procesele. Un
bun programator va încerca să disperseze în timp accesul la memorie al proceselor paralele.

5.3.2. Problema găsirii rangului

Rezolvarea problemei rangului constă în găsirea poziţiei elementului x in secvenţa

sortată, fară sortarea efectivă. Datele de intrare sunt deci o secvenţă şi un elemer.î al acesteia,
iar rezultatul este poziţia căutată.
Metoda secvenţială constă în numărarea în variabila r a elementelor mai mici decât x
şi întoarcerea valorii r + 1. Metoda cu mai multe procese şi schimb de mesaje va utiliza un
proces conducător (maşter) - Po, care gestionează întreaga aplicaţie, comandă celorlalte
procese - executant (slave) sarcinile pe care le au de executat şi colectează rezultatele printr-o
comanda colectivă (Reduce). Dacă lungimea secvenţei este foarte mare şi există unităţi de
procesare care se pot utiliza, prin fragmentarea sarcinilor se poate ajunge la o foarte mare
economie de timp. De exemplu, împărţirea unei secvenţe în 10 sub-secvenţe de lungimi

60
aproximativ egale şi alocarea lor pe 10 procesoare identice conduce la micşorarea de
(aproape) 10 ori a timpului de lucru (în cazul aplicaţiilor paralele se adaugă timpul necesar
transferurilor de date, al sincronizării proceselor şi al acţiunilor specifice calculului paralel).
Etapele rezolvării paralele sunt:
• procesul P0 transmite fiecărui alt proces câte o sub-secvenţă; acestea sunt
independente şi de lungimi aproximativ egale (prin comanda Send);
• procesul Pq transmite tuturor celorlalte procese valoarea x (prin comanda
Broadcast);
• fiecare dintre procesele Pi-Pk află în mod independent rangul lui x în sub-secvenţa
proprie, calculând valoarea variabilei />;
• procesul Po colectează valorile rk (prin comanda Reduce cu operatorul SUM);
• procesul Po afişează rezultatul comenzii Reduce.
Spre deosebire de problema precedentă, când am văzut că ambele metode de
comunicaţie se pot utiliza, aici este recomandată comunicarea prin schimb de mesaje.
Strategia de rezolvare de tip master/slave este determinată de o formulă simplă de compunere
a rezultatelor sub-problemelor pentru obţinerea rezultatului problemei iniţiale (valorile se
însumează; comanda Reduce fiind special concepută pentru astfel de situaţii).

5.3.3. Problema selecţiei

Problema selecţiei constă în găsirea într-o secvenţă, fără sortarea prealabilă a

secvenţei, a elementului cu rangul j (adică în acea secvenţă există j-1 elemente mai mici decât
răspunsul la problemă, în eventualitatea în care acesta există). Datele de intrare sunt secvenţa
şi valoarea variabilei j, iar rezultatul constă într-una din valorile secvenţei, care îndeplineşte
cerinţa problemei, stocată în variabila x, sau faptul că problema nu are soluţie.
Problema selecţiei este inversa problemei găsirii rangului, dar este mai complexă
decât aceasta, deoarece rezolvarea sa se face prin repetări ale rezolvării problemei găsirii
rangului (încercări repetate, ghidate de rezultatele anterioare).
Există şi versiuni mai complexe ale acestei probleme, de exemplu Problema celui de-
al n-lea element. Această problemă are ca date de intrare o secvenţă şi o variabilă n şi cere o
permutare a secvenţei astfel ca elementul aflat pe locul n (în secvenţa ordonată) să se afle pe
locul său, elementele din stânga sa să fie mai mici sau egale decât acesta şi elementele din
dreapta sa să fie mai mari sau egale cu acesta (figura 38). în cele ce urmează vom trata
versiunea simplă, enunţată la începutul acestui fragment.

Fig. 38. Rearanjarea secvenţei cu al 6-lea element corect poziţionat [16]

Exemplu
Pentru secvenţa (13 15 12 17 11 14 16) şij = 5, metoda de rezolvare furnizează x :
15. Problema nu are soluţie pentru j = 9 sau j = 0.

61
 Algoritmul secvenţial pentru rezolvarea acestei problerr.i r - : a i :—- - are
stocată în secvenţă şi construieşte sub-secvenţele Al şi A2. alean.;:; : - ; : - ; ; —ici
sau egale, respectiv mai mari decât x. Rangul lui x este chiar n u r r J r . i ; Al.
Dacă numărul de elemente din Al este chiar j, atunci algoritmul '. . I .. - * de
elemente din Al este mai mare decât j, atunci se reia căutarea c_ _- ; ac ?: se
reţine faptul că valoarea căutată este mai mică decât x. Dacă n u i r ă r - ae t z-'tra - este
mai mic decât j, atunci se reia căutarea cu un element din AS >: se iic» - -I - ..rea
căutată este mai mare decât x. La căutările ulterioare se aleg - : r - s l : :acâ şi
informaţiile memorate. O altă versiune ar fi marcarea valorilor însoeraoe r e t e r - a nu se
repeta căutările. Dacă valorile lui / sunt în afara mulţimii { 1 . 2 . . . izjzc- r r : e ensţ r.u are
soluţie.

if ( (j <= 0) or (j > n)) then STOP

x = a[1]
mark (a[1])
p = position_marked()
while (true) do
list Al, A2
for (i = 1; i <= n; i++)
if (i != P )
if (a[i] <= x) then append (Al, a
else append(A2, a[i])
k = length(Al)
if (k = j) then
write (x)
STOP
if (k > j) then x = primul_element_neciarcat Al
else x = primul_element_nemarcat(A2)
mark(x)
p = position_marked()

Observăm că în algoritm s-au folosit metodele: position_-2r< ^ : p e t n r . rre _area

poziţiei ultimului element marcat, append(lista, elemer.r peccr_ a c ă j g t e a unui
element la sfârşitul unei liste, length (lista) pentru aflarea f — r . r n — ic clemente
dintr-o lista, mark (element) pentru marcarea unu: t-kt-s-- şi
primul_element_nemarcat (lista) pentru preluarea primului [Link]".er' dmtr-o
lista.
La fel că în cazul precedent, pentru rezolvarea paralelă a p r : r l e m e ^ e c r e i . vom
folosi un model de tip master-slave, în care procesul maşter (Po) aleg; a ; r _"JL -.orile
pentru x şi distribuie proceselor slave (Pi-Pk) valoarea x curentă ş: sub-sec- [Link] oe ungimi
aproximativ egale. Fiecare proces P, calculează rangul r, al lui x şi apoi procesul P execută
pe tot grupul o comandă Reduce cu sumă, obţinând valoarea r. Dacă _ • . a r ^ r e'.or; ş i r
sunt egale, atunci algoritmul se opreşte. Dacă r > j , atunci proces-. P - . n a r e mai
mică decât precedenta valoare a lui x. Altfel, se alege o valoare ma: rr-are La :a r s:r_aţia
secvenţială, se poate folosi intervalul de valori posibile, sau marcarea : r ie;a testate,
pentru a scădea timpul de execuţie.

5.2.4. Problema interclasării

Problema interclasării presupune existenţa a două secvenţe - : r_a:e ? ;ere construirea

unei noi secvenţe sortate, alcătuită din toate elementele celor c : _ ă secvenţe iniţiale.
Interclasarea este o problemă care apare des în practică. începând r.e - f_nuelor. care

62
doresc să-şi centralizeze stocurile sau vânzările şi mergând până la situaţii complexe, de
statistici multinaţionale sau interconectări de baze de date.
Versiunea secvenţială presupune existenţa a trei indici, fiecare alocat unei secvenţe,
compararea elementelor indicate de indicii secvenţelor iniţiale, alimentarea secvenţei finale
cu elementul cel mai mic şi avansarea indicelui secvenţei care a trimis valoarea în secvenţa
finală. Dacă acest indice nu mai poate avansa, atunci se transferă toate elementele rămase în
cealaltă secvenţă şi algoritmul se încheie.

i = 1 // indicele secvenţei A, care are lungimea n

j = 1 // indicele secvenţei B, care are lungimea m
k = 1 // indicele secvenţei C
while ((i <= n) and (j <= m)) do
if (a [i] <= b[j]) then
c[k] = a[i]
i++
else
c[k] = b[j]
j++
k++
if (i > n) then
for (i = j; i <= m; i++)
c [i] = b[i]
else
for (j = i; j <= n; j++)
c[j ] = a [j ]

Pentru paralelizarea folosind trei procesoare se poate folosi strategia producător-

consumator: fiecare secvenţă se stochează local şi datele se transferă de la procesul Pi sau Pj
(producătorii) la procesul P3 (consumatorul).
O altă posibilitate speculează prezenţa masivă a resurselor de calcul şi aplică
problema găsirii rangului. Dacă avem la dispoziţie un număr mare de procesoare şi secvenţele
de interclasat sunt foarte lungi, atunci putem aplica următoarea metodă de rezolvare:
• procesul Po (maşter) trimite fiecărui proces P, (slave) elementul de pe poziţia i din
A şi toată secvenţa B;
• fiecare proces Pi (slave) calculează în paralel = rangul în B al elementului aflat
pe poziţia im A;
• procesul Po (maşter) colectează valorile (prin comenzi Gather);
• procesul Po (maşter) construieşte secvenţa C pe baza celor două secvenţe iniţiale
şi ale valorilor colectate. Se vor prelua blocuri din B şi câte un element din A, în
mod repetat, ca în exemplul următor.

Exemplu de construire a secvenţei C

Presupunem că avem la dispoziţie 6 procesoare şi că se interclasează secvenţele
A=(3 6 8 9 10)
B = (2 4 5 7 11)
Procesele P1-P5 vor returna valorile ni = 2, nj = 4, n? = 5, n4 = 5 şi «5 = 5, care vor fi folosite
astfel de procesul Po pentru construirea secvenţei C:
• prima valoare (ni = 2) arată că pe prima poziţie în C se aduce prima valoare din B,
urmată de prima valoare din A: C = (2 3...
• a doua valoare (n? = 4), fiind cu 2 mai mare decât precedenta, arată că în C se
aduc următoarele 2 elemente din B şi apoi următorul element din A: C = (2 3 4
5 6...

63
 • a treia valoare («? = 5), fiind cu 1 mai mare decât precedenta, arată că in C se
aduce următorul element din B şi apoi următorul element din C = (2 3 4 5
6 7 8...
• a patra valoare ( i î j = 5), fiind egală cu precedenta, arată că in C se ac-ce -rmătorul
element din A: C = (2 3 4 5 6 7 8 9...
• a cincea valoare {ns = 5), fiind egală cu precedenta, arată că :n C se aduce
următorul element din A: C = (2 3 4 5 6 7 8 9 10...
• nu mai există alte valori, astfel că în C se aduc toate elementele rămase din B şi
algoritmul se încheie: C= (2 3 4 5 6 7 8 9 10 11).

Această metodă este interesantă deoarece permite execuţie paralelă masivă şi

construieşte secvenţa C numai pe baza informaţiilor privind poziţia. în ordine crescătoare, a
unui singur element din A în secvenţa B.
Eficienţa aplicaţiei de granularitate mare (folosind doar trei procesoare) este mare.
fiind dată de o descompunere naturală a domeniului (descompunere în date). Dacă însă
dispunem de multe procesoare şi secvenţele de sortat sunt lungi, atunci putem alege o
descompunere funcţională, cum este cea din exemplul anterior. Această descompunere este
eficientă, deoarece procesele sunt independente, deci şablonul comunicaţiilor nu induce
întârzieri.

5.2.5. Problema sortării

Problema sortării înseamnă a reordona o secvenţă astfel încât componentele sale să

fie într-o anumită ordine (crescătoare sau descrescătoare). Şi în acest caz, pentru a păstra
coerenţa rezolvărilor, vom prezenta sortarea crescătoare.
Una dintre metodele interesante de paralelizare a sortării porneşte de la reţeaua de
comparatoare [5]. Un comparator este un instrument care realizează ordonarea a două valori,
prin interschimbarea lor. Comparatorul poate fi imaginat ca un dispozitiv fizic, în care datele
circulă pe orizontală, în sensul indicat în desen (figura 39). Reprezentarea unui comparator se
face printr-un segment vertical, iar valorile prelucrate sunt specificate la intrare şi la ieşire.
Ieşirea dintr-un comparator se face ordonând valorile crescător, de sus în jos.

timp

Fig. 39. Ordonarea valorilor (8 4) folosind un comparator

Reţeaua de comparatoare este o structură de astfel de comparatoare conectate.

Evoluţia temporală se face de la stânga la dreapta, datele se schimbă la fiecare unitate de timp
şi după mai multe astfel de etape se obţine sortarea datelor care au intrat în reţea.
Dacă reţeaua reuşeşte sortarea oricărei secvenţe, atunci este o reţea de sortare. Dacă
toate comparatoarele lucrează pe elemente adiacente, atunci reţeaua este simplă. In figura 40
este prezentată o reţea simplă de sortare pentru 6 elemente, care sortează în 6 unităţi de timp
valorile [9 8 7 6 5 4 ] ,

64
 9 8 6 4

8 9 6 8 4 6 5

7 6 9 4 8 5 6

6 7 4 9 5 8 ( 7

5- 4 , 7 5 1
9 7 , 8

4, 5 7 9

•
1 2 3 4 5 6 timp

Fig. 40. Reţea simplă pentru sortarea a 6 elemente

O reţea de sortare simplă care permite la intrare o secvenţă de n valori necesită cel

puţin C] = ~~ ~ comparatoare (deoarece un comparator poate produce cel mult o

inversiune - atunci când secvenţa este privită ca o permutare; datele descrescătoare, ca în

exemplul din figura 40, necesită numărul maxim de inversiuni). Din acest punct de vedere,
reţeaua din fig. 40 este optimă, având exact C62 =15 comparatoare.
Eficienţa reţelei simple de sortare cu un număr minim de comparatoare este mare,
deoarece:
• transferul de date se face în proximitate, consumul de resurse fiind minimal;
• dispozitivele hardware (comparatoarele) sunt în număr minimal;
• comparările se pot realiza în paralel - acesta fiind singura caracteristică unde
intervin cunoştinţele programatorului şi unde se pot obţine execuţii mai scurte.
Exemplul următor ilustrează cum organizări diferite conduc la timpi diferiţi de
execuţie.

Exemplu de sortare folosind reţea de comparatoare: Metoda Bubble-sort

Paralelizarea sortării prin reţea de comparatoare este o problemă dificilă, în general. O
idee de paralelizare este abordarea individuală, speculând ideea de bază a metodei de sortare
avută în vedere. O altă abordare este tratarea recursivă la nivelul unei clase de metode,
folosind de exemplu formulele:
x = max(a,,a2,...,a„)
sort(ax, a2,..., an) = (sort(delete(x, a^,a1,...,an)'),x)
valabile în cazul sortării crescătoare.

Aceste formule arată că procesul de sortare a n valori se face aşezând pe ultima

poziţie cea mai mare valoare dintre cele n valori intrate în procesul de sortare, extrăgând
această valoare şi sortând cele n - 1 valori rămase. Reţeaua de comparatoare care
implementează recursiv abordarea globală a sortării este reprezentată în figura 41.

65
 Timpul necesar pentru implementarea sa secvenţială este dat de urmă: -elaţie de
recurenţă:
T(n) = (« -1) + T(n -1)

şi cum T(2) = 1, avem că T(n) = (n -1) + (n - 2) + . . . +1 = — — —

1
K
<D
-<2-> c<D
O G
sx JZ
o OJ

Bk

1 2 3 ... n- 1 timp

Fig. 41. Model de reţea recursivă pentru sortarea secvenţială a n elemente

Dacă, însă, metoda de sortare permite utilizarea simultană a mai multor comparatoare,
atunci timpul de sortare poate scădea. De exemplu, prima comparare aferentă Blocului pentru
sortarea a n - 1 elemente se poate realiza la momentul 3, nu se aşteaptă până la momentul n.
Sunt necesare 9 unităţi de timp, nu 15 cum ar rezulta din formula de mai sus pentru n = 6
(figura 42).

1 2 3 4 5 6 7 8 9 timp

Fig. 42. Reţea pentru sortarea a 6 elemente prin metoda Bubble-sort

66
 Reţeaua din figura 42 este simplă, optimă din punct de vedere al numărului de
comparatoare (15), dar are nevoie de mai mult timp decât sortarea din fig. 40, care este mai
compactă. Gradul de paralelizare al sortării din ultima figură este mai scăzut.
O altă idee de paralelizare este găsirea în paralel a optimului (valorii maxime) din
secvenţa de n elemente, folosind metoda turneului, prezentată deja în acest subcapitol.
Relaţia de recurenţă pentru timpul de sortare în paralel devine astfel:

T(n) = log(/i) + T(n -1)

şi cum T(2) = 1, avem că:

T(n) = logO?) + log(/7 - 1 ) + . . . + 1 = log(«!) « n log(«)

conform aproximării Ramanujan [14].

Iată cum, deşi procesele sincronizează la fiecare trecere la o secvenţă mai scurtă
(producând întârzieri inerente), paralelizarea produce o scădere semnificativă a timpului de
sortare.
La nevoie, dacă problema are restricţii semnificative de timp, atunci aceste două idei
se pot combina. Algoritmul rezultat este mult mai complex, dar asigură un timp de execuţie
extrem de scăzut.

în acest capitol am prezentat câteva probleme pentru care rezolvările concurente au

fost discutate. După cum am văzut, nu există soluţii unice de paralelizare, fiecare având
avantajele sau dezavantajele sale. Dezvoltările tehnologice sau noile limbaje concurente pot
oricând recomanda noi descompuneri sau noi şabloane de comunicaţie între procese.

67
 Capitolul 6

Probleme actuale ale calculului paralel

Complexitatea situaţiilor actuale impune utilizarea calculului paralel pentru obţinerea

la timp a rezultatelor. Conducerea unor procese industriale (procese tehnologice robotizate),
managementul activităţilor ştiinţifice (realizate de reactoare, urmărite de sateliţi) sau a celor
cu impact major (baraje, centrale atomice) nu se mai pot realiza cu succes fără sisteme de
calcul extrem de puternice şi rapide, capabile să exploateze şi să întreţină cât mai eficient
instalaţiile/procesele respective.
Teoreticienii preiau în mod continuu provocările vieţii reale, le modelează folosind
aparatul matematic, realizează simulări ale fenomenelor reale şi încearcă mereu să
îmbunătăţească metodele şi algoritmii incluşi în aplicaţiile aflate în industrie, logistică sau
comunicaţii. Evoluţia unei astfel de probleme este prezentată în subcapitolul următor. Cel de-
al doilea subcapitol prezintă câteva domenii moderne ale informaticii şi matematicii aplicate,
în care calculul paralel se aplică acum cu succes.
Avansul tehnologic face ca aplicaţiile paralele să fie din ce în ce mai rapide şi
costurile lor să devină din ce în ce mai scăzute. Parallela face parte din categoria
calculatoarelor multi-procesor ieftine, care se pot asambla acasă şi care pot fi folosite pentru
învăţarea limbajelor paralele şi pentru dezvoltatorii de tip freelancer [27], Calculatoarele de
tip mainframe sunt destinate instituţiilor, firmelor sau băncilor şi oferă resurse puternica la
preţuri din ce în ce mai mici - de exemplu seria Intel z9 a fost lansată la aproximativ jumătate
din preţul seriei anterioare. Supercalculatoarele sunt sistemele aflate în prima linie a puterii
de calcul. Centrele de calcul de înaltă performanţă, universităţile, companiile transnaţionale
sunt cele care le achiziţionează şi care oferă locuri de muncă specialiştilor în calcul paralel.

6.1. De la TSP la MDPVRPTW

Problema comis-voiajorului (Traveling Salesman Problem - TSP) este una dintre cele
mai vechi probleme de optimizare, care (într-o formă oarecum asemănătoare) 1-a preocupat
pe Leonhard Euler [6]:

Un comis-voiajor trebuie să construiască un ciclu hamiltonian de cost minim

într-un graf ponderat (fiecare nod cu excepţia celui de start este vizitat o singură
dată, iar nodul de start este vizitat de două ori).

TSP are un set infinit de instanţe; când se rezolvă o instanţă, datele sunt complet
specificate şi soluţiile posibile se pot măsura (figura 43). Problema este deterministă; pentru
rezolvarea sa nu s-au găsit algoritmi polinomiali de rezolvare şi nici nu s-a demonstrat că
(«-!)!
astfel de algoritmi nu există. Algoritmul exhaustiv, care inspectează toate cele ~ cicluri
hamiltoniene (dacă instanţa are n noduri) este deci supra-polinomial.

69
 Figura 43. O instanţă TSP şi o soluţie [22]

Se consideră că algoritmii de acest tip nu sunt „folositori", deoarece instanţele mari nu

se pot rezolva în timp util. De exemplu, doar în anul 2009 s-a rezolvat o instanţă cu 85.900 de
noduri [1],
Pentru evitarea lor există următoarele alternative, care oferă în timp polinomial o
soluţie apropiată de soluţia optimă:
• Algoritmii euristici: dau rezultate bune în majoritatea cazurilor, adică produc
soluţii apropiate de optim în timp rezonabil, fără să asigure întotdeauna găsirea
unei soluţii şi fără a se putea prognoza cât de bună este soluţia (dacă este găsită).
• Algoritmii aproximativi: dau întotdeauna rezultate de o calitate minimală fixată, în
timp rezonabil [17]. Istoria algoritmilor aproximativi începe în anii '60, odată cu
dezvoltarea tehnicilor de optimizare combinatorie. La sfârşitul secolului trecut,
teoria acestor algoritmi a devenit bine fundamentată şi a permis abordarea
problemelor cu adevărat dificile (de exemplu, Proiectul Genomului Uman [20]).
în situaţia în care există incertitudine în date, TSP devine mai dificilă. Una dintre
versiunile sale este Problema cu intervale de date a comis-voiajorului. Deosebirea faţă de
TSP constă în faptul că fiecare muchie are un cost aflat într-un anumit interval, specific
muchiei respective (figura 44). Parcurgerea muchiei (0 1) costă între 1 şi 3; când algoritmul
se lansează în execuţie se precizează exact costul muchiei (la fel şi pentru celelalte muchii)
[12].
[1, 31

Figura 44. O instanţă TSP cu intervale de date pentru costurile muchiilor [12]

Algoritmul care rezolvă această problemă trebuie să fie capabil să rezolve instanţa cât
mai aproape de optim, oricare ar fi costurile muchiilor (în intervalele specificate). O instanţă
are deci o infinitate de realizări efective (scenarii), fiecare furnizând o soluţie care poate fi
evaluată.

70
 O altă versiune a TSP este Problema probabilistă a comis-voiajorului [8]. Faţă de
varianta deterministă, se consideră că fiecare dintre cele n noduri emite (cu probabilitatea
Pi,\<i<n) comenzi zilnice. La momentul plecării în cursă, comis-voiajorul află care sunt
nodurile de vizitat. Soluţia problemei este un ciclu a priori, din care comis-voiajorul elimină
nodurile care nu se vizitează la execuţia curentă a algoritmului. De exemplu, în Figura 45
sunt reprezentate a) soluţia unei instanţe probabiliste cu 10 noduri şi b) drumul curent, atunci
când nu se vizitează nodurile 3, 7, 8.

1 1

a) b)

Figura 45 [8]. a) Soluţia instanţei TSP probabilistă b) Drumul curent

Graful incomplet al unor instanţe TSP face ca uneori să nu existe soluţii, sau costul
acestora să fie mare, fată de situaţia în care ar fi fost permise muchii între orice două noduri.
Un exemplu este prezentat în figura 46. Pentru vizitarea localităţilor Slănic Moldova şi
Agigea, este necesară parcurgerea de două ori a muchiilor Slănic Moldova - Târgu-Ocna şi
Agigea - Constanţa.
Pentru abordarea acestui caz, noţiunea de soluţie se va relaxa, astfel că algoritmul de
rezolvare va fi nevoit să lucreze cu un spaţiu mult mai mare de soluţii posibile. Conceptul de
relaxare este general şi se referă la aproximarea unei probleme printr-o problemă
asemănătoare, care se poate rezolva mai uşor. De exemplu, se renunţă la constrângerea ca
soluţiile unei probleme să fie numere întregi şi se rezolvă în cazul numerelor reale.

71
 Figura 46. O instanţă TSP fară soluţie în sens clasic [3]

La nivelul actual, există preocupări ale cercetătorilor pentru investigaţii

interdisciplinare. Un exemplu în acest sens este utilizarea serviciilor GIS (Geographic
Information Systems) pentru elaborarea cu acurateţe a hărţilor pentru instanţe TSP reale, care
ar putea folosi în Geoinformatică, Logistică, Comunicaţii, Ingineria Mediului. In figura 47 se
află reprezentarea primei instanţe naţionale TSP care utilizează date vectoriale
(,[Link]), iar în figura 48 este prezentată soluţia exactă a acesteia.

72
 Figura 47. Instanţă TSP cu date vectoriale

J~~i Jî S . MoUe
^ V î V D ^ r - e s ^

% K >, r v >

« j , V "} -
Roiii-itua
H"4
1 ?SSY •-1 >
hi
X rv\1

ir
C<l L IM
-!' X ^ iviili*
V ? V i v n K i j v v j ţ ^ V T *" " V P - C y
/-) -
Ştffefl
u j ) ţ t y " *f•
' r

Figura 48. Soluţia exactă a instanţei [Link]

Soluţia din figura 48 a fost obţinută folosind o aplicaţie paralelă pe 2 procesoare Intel
Xeon la 2,2 GHz şi 64 MB RAM (aflată la adresa [24]).

73
 O generalizare a TSP, abordată şi formalizată de cercetători ca răspuns la cerinţele
vieţii reale este Problema rutării vehiculelor (Vehicle Routing Problem - VRP):

Se cere servirea cu costuri minime a unor clienţi aflaţi în diverse puncte geografice,
utilizând un set de camioane care la începutul zilei sunt parcate într-un depou şi care
la sfârşitul zilei se întorc la depou [4].

f N«

V 4 1 . .
V ; 1/ / " V
Depot
/
ET7m>
E >
". Depot '•i'-

• • . • { * i .
• V1 \
• • • • ^ «
a) b)
Figura 49 [19] a) O instanţă VRP b) o soluţie

VRP este o problemă extrem de importantă prin aplicaţiile sale: aproape că nu există
mărfuri care să nu includă costuri de transport, iar cum resursele neregenerabile (derivaţii
petrolului) se împuţinează, este evidentă preocuparea specialiştilor pentru rezolvarea cât mai
eficientă a situaţiilor specifice de transport mărfuri. Au apărut versiuni tot mai complexe ale
VRP:
• CVRP (Capacitated VRP) - camioanele au capacităţi fixate de transport, care nu pot
fi depăşite la nici un moment; mai există şi versiunea în care aceste capacităţi sunt
diferite, sau fiecare camion are compartimente, în care se pot transporta anumite
categorii de produse (de exemplu lichide care trebuie refrigerate, etc.);
• VRPTW (VRP with time windows) - clienţii au un program fix din zi când pot fi
aprovizionaţi; de exemplu, parcarea camionului în zonă poate fi făcută până la ora 9.
• MDVRP (mulţi depot VRP) - există mai multe depouri, fiecare camion se întoarce la
depoul de unde a plecat;
• PVRP (periodic VRP) - se consideră mai multe zile succesive şi fiecare client
specifică un şablon propriu de aprovizionare (de exemplu o dată la 3 zile).

Aceste versiuni se pot combina, astfel că există, de exemplu, MDPVRPTW. Această

problemă este dificilă deoarece orice metodă de rezolvare s-ar implementa, se consumă
resurse majore pentru verificarea tuturor restricţiilor (de capacitate, de interval orar şi de
şablon de aprovizionare, de testare a celui mai convenabil depou). De aceea, numai aplicaţiile
paralele, cu module complexe de construire şi evaluare a soluţiilor pot acum să furnizeze
soluţii eficiente [2].

74
 6.2. Potenţialul actual al calculului paralel

Calculul paralel reprezintă viitorul aplicaţiilor eficiente şi puternice, dezvoltate

calculatoare mulţi-procesor. Următoarele domenii oferă un mare potenţial specialiştilor în
calcul paralel, fiind demne de luat în considerare de către tinerii specialişti.

6.2.1. Criptologia modernă

Criptologia este ştiinţa comunicării sigure. Cele două subdomenii ale criptologiei
sunt:
• Criptografia - se ocupă cu asigurarea securităţii comunicării;
• Criptologia - încearcă depăşirea barierelor criptografice de securitate.

Dezvoltarea fără precedent a metodelor de comunicaţie electronică a dus la un progres

pe scară largă a modelelor criptografice, la noi reglementări legislative internaţionale şi deci
la un avânt deosebit în cercetarea şi aplicaţiile legate de criptologie.
Algoritmul de factorizare a întregilor stă la baza sistemelor moderne de
criptografie/criptanaliză. Factorizarea unui număr întreg înseamnă descompunerea acestuia
într-un produs de două numere. Cea mai dificilă factorizare are loc atunci când numărul
întreg este semi-prim, adică este produs de două numere prime, problema având deci o
singură soluţie.
La ora actuală nu există o metodă eficientă (de complexitate polinomială) pentru
problema factorizării, ceea ce este speculat de algoritmii de criptare. Dacă se va găsi o astfel
de metodă, atunci toate metodele moderne de criptare vor deveni vulnerabile şi vor trebui
urgent schimbate.
Primul algoritm modern de criptare care a fost aplicat cu succes la nivel internaţional
este RSA (Rivest-Shamir-Adleman). Acum există algoritmi mai complecşi, care elimină
aproape în totalitate şansa decriptării prin forţa brută a unui mesaj (SHA-384, ECDH-384,
etc.). Având în vedere marea miză a domeniului, aplicaţiile eficiente sunt cele paralele.

6.2.2. Moneda virtuală

Moneda virtuală (virtual currency) este un concept modern, implementat şi

recunoscut de instituţiile financiare.
Prima monedă virtuală de succes a fost bitcoin, care şi la nivelul anului 2014 este cel
mai răspândit şi cel mai folosit astfel de mijloc de plată [30]. Banca Centrală a Europei
recunoaşte puterea circulatorie a monedei virtuale, definind-o în 2012 ca „o monedă digitală,
lipsită de un control instituţional, care este emisă şi controlată de dezvoltatorii săi şi folosită
de membrii unei comunităţi virtuale".
Ideea bitcoin este interesantă din punctul de vedere al calculului paralel: moneda se
creează prin mining - găsirea soluţiei prin forţa brută la o problemă dificilă - deci sunt
avantajaţi cei care posedă resurse consistente de calcul şi le folosesc în acest scop. Faptul că
este convertibilă îi asigură şi o altă posibilitate de dobândire: prin schimb.
Tehnologia actuală şi faptul ca bitcoin a fost concepută cu o viteză de creare în
scădere, face ca acum costul energiei folosite să depăşească valoarea produsă pe un sistem de
calcul obişnuit, astfel că se folosesc alte soluţii (de exemplu, plăci grafice).

75
 6.2.3. Calculul cuantic

Calculul cuantic este un model bazat pe bitul cuantic (quantic bit - qubit). Acum nu
există calculatoare cuantice, dar modelul este intens studiat de cercetători, existând
preocupări la nivel teoretic - spre deosebire de moneda virtuală care există şi funcţionează.
Un qubit generalizează noţiunea de bit: aşa cum un bit poate lua doar două valori (0 sau 1),
un qubit poate fi orice combinaţie liniară a valorilor 0 şi 1 (în care ponderile sunt numere
complexe).
Dacă notăm cu | 0} (ket-0) qubitul care stochează valoarea 0 şi cu j 1 )(ket-\) qubitul
care stochează valoarea 1, atunci un qubit poate stoca orice valoare
V | 0 ) + z2-|l>
unde z,,z 2 e C , | z , | 2 |2=1.
Deci un qubit poate stoca orice pereche de numere complexe care au suma normelor
1, având deci o putere (teoretic) infinită de stocare. Modelul calculatorului cuantic este
extrem de interesant, iar încercările actuale de simulare sunt doar începutul unei noi
paradigme de calcul [15].

Calculul paralel se referă la rezolvarea de probleme complexe folosind calculatoare

multi-procesor. Centrele de cercetare, marile instituţii sau corporaţii investesc tot mai mult
în capacităţi evoluate de calcul. Piaţa muncii în acest domeniu este la început, având o
dezvoltare spectaculoasă; specialiştii în calcul paralel sunt cei de la care se aşteptă
exploatarea eficientă a resurselor puternice de calcul, care devin din ce în ce mai
disponibile.

76
 Capitolul 7

Probleme actuale ale calculului distribuit

Calculul distribuit cunoaşte în zilele noastre o dezvoltare nemaiîntâlnită: reţelele de

calculatoare sunt o prezenţă obişnuită în companii, în instituţii sau la domiciliu. Suntem
posesori de telefoane inteligente, sau de alte dispozitive electronice (smart TV, router, GPS
pentru autovehicul, etc.) care ne fac viaţa mai confortabilă, preluându-ne problemele şi
rezolvându-le.
Modelul distribuit nu este nou: reţeaua de cale ferată, de exemplu, manifestă
concurenţă (mai multe trenuri se află pe acelaşi tronson), latenţă (trenurile întârzie), toleranţă
la erori (un tren întârziat nu are impact major asupra celorlalte), partajarea datelor
(evenimentele se anunţă în reţea).

La nivelul reţelelor de calcul, programatorii de aplicaţii distribuite au tendinţa de a

ignora unele aspecte care pot influenţa calitatea produsului software. De exemplu, se
consideră în mod eronat că:
• reţeaua este securizată
• latenţa este zero
• costul de transfer este zero
• lărgimea de bandă este infinită
• reţeaua este omogenă
• componentele nu se defectează
• topologia este fixă
• există un singur administrator, care are o strategie constantă de gestionare.
Toate aceste presupuneri trebuiesc ignorate de un programator bun de aplicaţii
distribuite.

Reţelele eterogene sunt cele care pun cele mai mari probleme dezvoltatorilor de
aplicaţii; eterogenitatea se poate referi la:
• arhitectura sistemelor de calcul
• formatul local al datelor
• încărcarea locală
• viteza de calcul
• dinamica încărcării reţelei
şi se tratează diferit, în funcţie de situaţia la care se referă.
De exemplu, dacă sistemele cad şi aplicaţia nu este proiectată să recupereze datele,
utilizatorul trebuie să o re-lanseze de la început; o bună abordare ar fi să se proiecteze puncte
de întrerupere şi salvare, astfel încât să se poată relua fără pierderea rezultatelor intermediare.
In cazul aplicaţiilor mobile (apps) se realizează versiuni dedicate tuturor sistemelor majore de
operare (cel puţin Android, iOs, Windows Mobile OS). In cazul aplicaţiilor de căutare, se pot
implementa funcţii de interogare a unor baze de date diverse - de exemplu, pentru proiectele
software dedicate călătoriilor de persoane, se pot realiza aplicaţii multi-modale pentru
conexiuni avion - cale ferată - autocar.

77
 Exemplu de aplicaţie eterogenă distribuită: Intelligent Transportation System

Un sistem inteligent de transport (Intelligent Transportation System - ITS) este un

sistem integrat de calcul care foloseşte datele primite de la utilizatori şi pe cele captate din
mediu cu ajutorul senzorilor pentru a optimiza şi gestiona traficul şi pentru a oferi sfaturi
celor interesaţi. ITS integrează date diverse, pe care le exploatează în funcţie de natura lor:
• date GPS (Global Positioning Sv.s7em)/GLONASS (sistemul rusesc de poziţionare
globală)/Galileo (sistemul european)/! RNSS (sistemul indian)/Bei-Dou-2
(versiunea chineză);
• date specifice telefoanelor inteligente, pe care le folosesc de exemplu pentru
aplicaţiile turistice dedicate marilor oraşe (London Bus Checker, etc.);
• date de tip GIS (Global Information System) referitoare la poziţionarea exactă pe
suprafaţa globului;
• date în format VT (Vehicle Telematics) care descriu vehiculele participante la
trafic, de exemplu în caz de accident, computerul de bord poate realiza
independent un apel de urgenţă, dacă are instalat un sistem de tip eCall;
• date în format TSM ( T r a f f i c Signal Monitors) care se preiau prin senzori statici,
amplasaţi pe şosele şi care realizează statistici de trafic sau colectarea automată a
taxelor de autostradă.

Sistemele inteligente de trafic sunt proiectate pentru comunicaţii ad-hoc, realizate la

nevoie şi fară coordonare; aceste comunicaţii pot fi de următoarele tipuri:
• V2I (vehicle-to-infrastructure) de exemplu pentru aplicaţiile de semnalare
accidente;
• V2V (vehicle-to-vehicle) când două autovehicule participante la trafic comunică
pentru evitarea unui potenţial eveniment.

Deşi sistemele inteligente de trafic oferă un ajutor preţios, şoferul este cel care îşi
asumă responsabilitatea deplasării şi deţine controlul asupra autovehiculului. Vehiculele
autonome (conduse de calculator) se află încă la stadiul de teste, iar legislaţia care să le
permită accesul pe şosele este în vigoare în 4 state din SUA, în Singapore şi în Marea
Britanie.

Sistemele de calcul distribuit sunt prezente sub forma cloud computing (calcul
folosind resurse stocate distribuit în reţea), mobile computing (aplicaţii de telefonie mobilă),
etc. Toate formele de calcul distribuit sunt acum în dezvoltare accelerată, oferind
specialiştilor posibilităţi diverse de angajare.

78
Bibliografie

1. Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W., Espinoza, D.G., Goycoolea, M.,
Helsgaun, K. - Certification of an optimal TSP tour through 85,900 cities, Operations
Research Letters, 37, 1, 11-15, 2009
2. Crainic, T.G., Crişan, G.C., Gendreau, M., Lahrichi, N., Rei, W. - Multi-thread
Cooperative Optimization for Rich Combinatorial Problems, IEEE International
Parai lei & Distributed Processing Symposium, Rome, Italy, 2284-2291, 2009
3. Crişan G.C., Nechita E., Talmaciu M., Pătruţ B. - Using Centrality Indices in Ant
Systems, Proceedings of the International Conference on Computers, Communication
and Control ICCC2006, Oradea, 146-149, 2006
4. Dantzig, G.B., Ramser, J.H. - The Truck Dispatching Problem, Management
Science, 6, 1, 80-91, 1959
5. Dumitrescu B.A. - Algoritmi de calcul paralel, note de curs, Universitatea Politehnica
Bucureşti, 2001
6. Euler, L. - Solution d'une question curieuse qui ne paraît soumise â aucune analyse,
Memoire de 1'Academie des Sciences de Berlin 15, 310-337, 1759, publicată în
Opera Omnia 1, 7, 26-56, 1766
7. Grama, A. Gupta, A., Karypis, G., Kumar, V. - Introduction to parallel computing,
Addison-Wesley; 2nd Ed., 2003
8. Jaillet, P. - Probabilistic Traveling Salesman Problem, Teză de Doctorat, MIT,
Cambridge, 1985
9. Knuth, D.E. - The Art of Computer Programming, Volume 3: Sorting and Searching.
2 n d Ed., 1998
10. Kung, H.T., Leiserson C.E. - Algorithms for VLSI processor arrays - Introduction to
VLSI systems, Addison-Wesley, 271-292, 1980
11. Mayer-Schonberger, V., Cukier, K. - Big Data: A Revolution That Will Transform
How We Live, Work, and Think, Eamon Dolan/Houghton Mifflin Harcourt, 2013
12. Montemanni, R., Barta, J., Mastrolilli, M., Gambardella, L.M. - The Robust Traveling
Salesman Problem with Interval Data, Transportation Science, 41, 3, 366-381, 2007
13. von Neumann, J. - First Draft of a Report on the EDVA, Pennsylvania University,
USA, 1945
14. Ramanujan, S. - The lost notebook and other unpublished papers, Springer Berlin,
1988
15. Stolze J., Suter, D. - Quantum Computing. Wiley-VCH, 2004
16. Tikhonova, A., Tanase, G., Tkachyshyn, O., Amato, N., Rauchwerger, L. - Parallel
Algorithms in STAPL: Sorting and the Selection Problem, Technical Report, TR05-
005, Parasol Laboratory, Department of Computer Science, Texas A&M University,
2005
17. Vazirani, V.V. - Approximation Algorithms. Berlin: Springer, 2003
18. [Link]
19. [Link]
20. [Link]
21. [Link]
22. [Link]
23. [Link] ; Inv

j„ VASILE A L E C S A N D R I
79 din D a c ă u
Bibliotecă
j Cotă fi/ 3 %cH
24. [Link]
25. [Link]
26. [Link]
27. [Link]
28. [Link]
29. [Link]
[Link]
30. [Link]
31. [Link]
32. [Link]

80