Costurile de comunicare in masini paralele Importanta modelelor de cost pentru operatiile de comunicare

Sizin üçün oyun:

Google Play'də əldə edin


Yüklə 530 b.
tarix30.01.2018
ölçüsü530 b.


Curs 3 Comunicarea in masini paralele Modele si costuri Operatii de comunicare colectiva


Costurile de comunicare in masini paralele

  • 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

  • Rutarea Store-and-forward utilizeaza ineficient resursele retelei

  • 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)

  • Dimensiunea mica a unui Flit => obligatia de minimizare a header-ului

  • 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.

  • Minimizarea volumului datelor transmise



Modelul liniar al costului comunicarii

  • Tcomm=ts+l*th+m*tw

  • ts >> tw , si th≈ neglijabil

  • Tcomm=ts+m*tw



Modelul liniar al costului comunicarii (cont)



Modelul liniar al costului comunicarii (cont)

  • 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:

  • Tmem=ts+m*tw

  • Particularitate : ts << tw



Operatii de comunicare colectiva



Tipuri de comunicatii prin mesaje

  • One to One

  • Operatii de comunicatii colective:

    • One to All Broadcast
    • All to One Reduction
    • All to All Broadcast
    • All to All Reduction
    • All-Reduce &prefix Sum
    • Scather and gather
    • All to All Personalized Communication
  • Mai multe detalii: Cap 4 / [GGKK]



Importanta operatiilor de comunicare colectiva

  • 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)



One to all broadcast pe inel



All to one reduction pe inel



One-to-all broadcast pe mesh



One-to-all broadcast pe hipercub



One-to-all broadcast pe arbore



Algoritmi pentru one-to-all broadcast

  • 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 si gather

  • 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




Dostları ilə paylaş:
Orklarla döyüş:

Google Play'də əldə edin


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2017
rəhbərliyinə müraciət

    Ana səhifə