Importanta modelelor de cost pentru operatiile de comunicare:
Comunicarea intre procesoare este o sursa majora de overhead in executia algoritmilor paraleli => nu se poate face analiza alg paraleli fara a putea estima analitic timpul necesar comunicarii
Costul comunicarii depinde de:
Modelul de programare (memorie comuna sau comunicare prin mesaje)
Topologia retelei
Modalitatile de rutare
Costurile comunicarii prin transmitere de mesaje
Timpul de transmitere a unui mesaj intre 2 noduri in retea cuprinde:
Timpul de initializare (Startup time ts): pregatirea mesajului pentru transmisie (header, coduri corectoare de erori), rutare. Apare o data per mesaj.
Timpul per-hop (th): Timpul necesar header-ului mesajului sa ajunga la urmatorul nod, de care este direct conectat. Latenta nodului.
Timpul de transfer al unui cuvant (tw): Timpul necesar transferarii unui cuvant intre 2 noduri direct conectate. Depinde de latimea de banda a conexiunii.
Store-and-Forward Routing
Un mesaj care urmeaza o cale cu mai multe legaturi: la fiecare nod intermediar, mesajul trebuie receptionat in intregime, stocat si abia apoi transmis mai departe
Costul total de comunicare pentru un mesaj de dimensiune m pe l legaturi:
De obicei valoarea th este neglijabila si expresia se poate aproxima prin:
Packet routing: mesajul initial este impartit in pachete. Nodurile intermediare nu mai asteapta receptionarea intregului mesaj, ci doar a cate unui pachet.
Avantaje: Utilizeaza mai bine resursele retelei, exista posibilitatea ca pachetele sa urmeze rute diferite, pierderile de pachete nnu de mesaje
Dezavantaje: overhead mai mare deoarece fiecare pachet trebuie sa contine info de rutare, coduri detectoare de erori, info de secventa.
Packet routing (cont)
Transmiterea unui mesaj de lungime m in retea
In estimarea prezenta se presupune (simplificand!!) ca toate pachetele sunt rutate pe acelasi traseu
Timp de startup tS
Timpul de pachetizare = m tW1
Timpul de transmitere a unui cuvant tW2
Raportul informatia aditionala rezultata / informatia originala s/r
tW=tW1+tW2(1+s/r)
Timpul total de comunicare poate fi aproximat cu:
Cut-Through Routing
Unitatile transmise sunt pachete de dimensiune mica, fixa, denumite Flits (flow control digits)
Toti Flit ai umui mesaj urmeaza acelasi traseu -> nu e nevoie ca fiecare flit sa contina in header info de rutare
Exista un prim mesaj tracer care stabileste conexiunea
Toti Flits ai unui mesaj sunt transmisi in secventa -> nu mai e necesar ca header-ul sa contina info de secventa
Controlul erorilor se face per mesaj, nu per Flit
Stabilirea dimensiunii optime a unui Flit:
Daca e prea mica pentru o latime de banda data => rata de transfer prea mare pentru viteza circuitelor hardware
Daca e prea mare => buffere interne mari, creste latenta transmiterii mesajelor
Implementari curente: valori intre 1-32 octeti
Cut-Through Routing (cont)
Timpul de comunicare a unui mesaj de lungime l:
Imbunatatire fata de store-and-forward routing (twm nu se mai inmulteste cu l)
Formula e aceeasi ca la packet routing, dar tW este mai mic in cazul cut-through
Calculul timpului de comunicare
Datele problemei: mesaj de dimensiune m, trebuie sa traverseze l legaturi de la nodul sursa la nodul destinatie
Timpul de comunicare depinde si de mecanismul de rutare
Pentru cut-through routing (mecanism fara buffer-ari la nodurile intermediare):
Tcomm=ts+l*th+m*tw
Valorile pentru ts, th, tw:
sunt constante determinate de caracteristicile hardware-ului si a protocoalelor de comunicatie
De obicei: ts >> tw , si th≈ neglijabil
Optimizarea timpului de comunicare
Tcomm=ts+l*th+m*tw
Comunicare de tip “en-gros”: este mai eficient a transmite un singur mesaj mare decat multe mesaje mici, datorita ponderii importante a lui ts
Minimizarea distantei de comunicare: reducerea nr de link-uri l de parcurs; se poate face prin optimizarea asignarii proceselor pe procesoare. In practica, utilizand biblioteci de transmitere de mesaje, programatorul are un control redus asupra modului in care procesele sunt mapate pe procesoare.
Observatie importanta: expresiile timpilor de comunicare sunt valabile in absenta congestiilor in retea !
Pentru o topologie data, anumite tipare de comunicare pot sa duca la congestie
Exemplu: pe un masiv 2-dimensional:
Fiecare nod comunicacu un vecin -> fiecare legatura este utilizata de o singura operatie de comunicatie
Fiecare nod comunica cu un nod aleator -> exista legaturi care sunt utilizate de mai multe operatii de comunicare c -> mesajele trebuie serializate pe acea legatura Tcomm=ts+m*tw*c
Efectul congestiilor asupra costului comunicarii
Posibilitatea aparitiei congestiilor depinde de:
topologia retelei
tiparul de comunicare (cine cu cine comunica)
Effective bandwidth: se defineste ca fiind egal cu:
Link bandwidth, daca reteaua este fara congestii
Link bandwidth / c, unde c=gradul de congestie pentru cel mai incarcat link
Efectul congestiilor asupra costului comunicarii (cont)
Estimarea valorii c:
C=nr de procesoare p / latimea bisectiei b
Justificare:
Fiecare nod comunica cu un nod aleator => intre doua jumatati ale retelei exista p/2 comunicatii
Latimea bisectiei b => exista link-uri care trebuie sa duca cel putin p/(2*b) comunicatii
Exemplu: comunicarea dupa un tipar aleator in masiv 2D:
Latimea bisectiei b=sqrt(p)
Tcomm=ts+m*tw*sqrt(p)/2
Costurile comunicarii prin memorie partajata
Dificil de estimat:
Utilizarea memoriilor cache
Programatorul de obicei nu poate controla in ce adrese fizice se face stocarea anumitor date
Costul pentru acces read-only poate fi aproximat grosier prin aceeasi formula ca si in cazul transmiterii de mesaje:
Reprezinta tipare acceptate de comunicatii colective (de grup) utilizate in algoritmii paraleli
Colectiv: este implicat un grup de mai multe procesoare
Sunt utilizate in special in algoritmi data-paraleli
Eficienta algoritmilor paraleli depinde de implementarea eficienta a acestor operatii
Se aplica atat arhitecturilor cu memorie distribuita cat si celor cu memorie comuna
Majoritatea bibliotecilor de functii pentru calculul paralel le implementeaza
One-to-all Broadcast All-to-one Reduction
One-to-all broadcast: Un procesor detine un bloc de date de dimensiune m care va fi transmis celor p procesoare
All-to-one reduction: fiecare procesor detine cate un bloc de date. Acestea vor fi combinate utilizand un operator asociativ (ex: adunare, minim) iar rezultatul stocat la procesorul destinatie
Implementarea eficienta a acestor operatii de comunicare depinde de topologia retelei (exemple: inel, masiv, hipercub)
Pentru toate arhitecturile discutate, tiparul de comunicatii pentru one-to-all broadcast este similar(recursive doubling):
P procese => log p pasi, in fiecare pas au loc simultan mai multe comunicatii point-to-point
Tinand cont de formula modelului liniar al timpului de comunicatie, timpul pentru one-to-all broadcast este:
T one-to-all-broadcast=(ts+m*tw)*log p
Obs: fara utilizarea primitivei de tip one-to-all-broadcast, timpul de transmitere a p-1 mesaje independente este:
Tmesaje-independente=(ts+m*tw)*(p-1)
Operatia all-to-one reduction se implementeaza in mod simetric
Exemplu de utilizare
Inmultirea unei matrici A[n*n] cu un vector X[n*1] pe un masiv bidimensional de n*n noduri
Fiecare element al lui A se gaseste pe cate un nod; Elementele vectorului se gasesc pe nodurile din prima linie a masivului. Rezultatele vor fi generate pe nodurile apartinand primei coloane.
Exemplu (cont)
All-to-all broadcast si reduction
All-to-all broadcast:
Toate procesele realizeaza simultan un broadcast
Fiecare proces i transmite acelasi bloc de date Mi celorlalte procese. Procese diferite pot transmite date diferite.
All-to-all broadcast si reduction (cont)
All-to-all reduction:
Fiecare nod e destinatia unui all-to-one reduction
Fiecare nod i detine p mesaje, cate unul pentru fiecare nod destinatie; la nodul destinatie mesajele sunt insumate (sau alta operatie asociativa)
Implementare cu utilizarea eficienta a linkurilor retelei: toate operatiile de broadcast se efectueaza simultan in stil pipeline, astfel incat toate mesajele care traverseaza acelasi link in acelasi timp sunt concatenate (creste lungimea mesajelor transmise).
Algoritmii de implementare si performantele a acestui tip de comunicatie difera in functie de topologia retelei
All-reduce
Initial fiecare procesor detine cate un bloc de date de dimensiune m iar in final toate procesoarele detin un bloc identic de dimensiune m, obtinut prin combinarea celor p blocuri initiale printr-un operator asociativ
Acelasi efect ca si o operatie de all-to-one reduction urmata de o operatie one-to-all broadcast. Implementarea mai eficienta insa foloseste insa un tipar de tip all-to-all broadcast ion care in loc de concatenarea mesajelor se face insumarea (combinarea) lor
Prefix-sum
Fiecare procesor p detine initial cate un numar
In final fiecare procesor k detine suma numerelor de la procesoarele 0, 1, …, k
Scatter: un nod trimite cate un mesaj de dimensiune m tuturor celorlalte noduri (comunicatie de tip one-to-all personalized communication)
Gather: un nod colecteaza mesaje personalizate de la toate celelalte; este diferite de all-to-one reduction pentru ca NU combina mesajele !
Semantica lui scatter este total diferita de broadcast, dar implementarile sunt asemanatoare (la scatter lungimea mesajelor transmise scade pe masura ce nodurile de pe traseu receptioneaza datele care le sunt adresate)
Scatter si Gather (cont)
All-to-all personalized communication
Fiecare nod are un mesaj distinct pentru fiecare alt nod
Difera de all-to-all broadcast unde fiecare nod trimite acelasi mesaj tuturor celorlalte
Exemplu
Performantele operatiilor de comunicare colectiva
Functii MPI care implementeaza comunicatiile colective
