Programare paralelă în sisteme distrbuite

Retelele de interconectare sunt de 2 tipuri:

a)retele statice la care conexiunile intre noduri sunt fixe si punct la punct-transferul informatiei in acest tip de retele este transmis prin mesaje.

b)retele dinamice- nodurile sunt conectate intre ele in mod dinamic prin comutare comandata

Retelele se utilizeaza in arhitecturile paralele cu memorie partajata.O retea poate fi reprez.matematic printr-o rel.de forma: G=(V,E)

V=mult a nodurilor,|V|=nr total noduri,

V={vi|0≤i≤v,v=|v|}

E+{eij|=<vi,vj>|0≤I,j<v}

E-multimea muchiilor unei retele

Parametri retelelor de interconectare

1)Gradul retelei=(not)q si este dat de numarul muchiilor incidente in nod.

Gradul unei retele este gradul maxim al acelei retele. Prin gradul retelei se def nr.porturilor dintr-un nod.

2)Dimensiunea retelei-dat de nr total al nodurilor din graf.

3)Diametrul retelei=(not)d sau D-se defineste ca distanta maxima dintre 2 noduri ale unei retele; 4)Largimea canalului-notata w este data de numarul de biti care se pot transfera prin acel canal.

5)Viteza canalului-este data de nr. de biti/sec care se pot transmite printr-o linie fizica;

6)Largimea de banda-se defineste ca nr biti/sec care se pot transmite prin canal si este egala cu produsul dintre viteza canalului si largimea canalului

7)Largimea bisectiei=not B – a unei retele de comunic.este data de nr.minim de legaturi care trebuiesc eliminate pentru a putea imparti reteaua in 2 parti egale sau cat mai apropiate intre ele;

Largimea de banda a bisectiei se def ca volumul de comunicatie ce poate avea loc intre cele 2 jumatati.Este data de produsul dintre largimea bisectiei si largimea de banda a canalului.

8)Costul retelei de interconectare =(not)C-pt evaluarea costului retelei se pot utiliza mai multi parametrii astfel:

-largimea bisectiei-deoarece prin ea se poate evalua limita inferioara a ariei sau a volumului in care se poate incapsula reteaua; - costul este dat de nr.de link-uri necesare pt constructia retelei; -lungimea legaturilor intre noduri ;

-omogenitatea si gradul nodurilor;

-simetria retelei

Retele dinamice de interconectare

Reteaua de tip magistrala : toate nodurile ei sunt conectate.La un mom. dat poate exista un singur transfer de informatii pe magistrala.Pentru evitarea conflictelor de retea se utilizeaza un bloc special care gestioneaza transferul.

Pentru a mari viteza de transfer se utilizeaza o structura de magistrala de acest fel. Transferul majoritar se face intre cache si processor. Transmisia pe magistrala are loc doar atunci cand cuvantul cautat nu se afla in mem cache locala. Reteaua tip magistrala este o retea blocanta de performante scazute,dar este cea mai simpla si de cost scazut.

Reteaua Crossbar-o retea dinamica

La o retea Crossbar de dim m*n se pot face simultan n transferuri de date. Costul acestei retele este foate mare .

Retea de tip multietaj imbina calitatile de scalabilitate a costurilor retelei magistrale cu calitatile de scalabilitate d.p.d.v.al performantelor pt retelele Crossbar. Reteaua de tip multietaj este formata din i etaje, numerotate de la 0 la i-1,incepand de la iesire. Etajele sunt formate din comutatoare dinamice Crossbar de dim a*b etaje.

Conexiunea intre etaje se face prin legaturi fixe notate C.D.E. Comutatoarele C.D.E. tb facute astfel incat sa permita legarea unei intrari la oricare iesire.Cele mai frecvente pernmutari sunt :

Perm. de baza consta in rotirea ciclica cu o singura pozitie la dreapta a reprezentarii binare a adresei sursei de intrare pt a determina adresa sursei de isire. Perm.baza(ai-1,ai-2,…,a1,a0)=a0ai-1ai-2…a2a1

Comutarea perfecta Shufle este asemanatoare comutarii de baza numai ca deplasarea ciclica se face la stanga. Perm.Shufle(ai-1,ai-2,…a1a0)=ai-2,ai-3,…,a0ai-1

Permutarea fluture-are loc interschimbarea b.c.m.p.s. cu b.c.m.s.Perm.bultertly : (ai-1,ai-2,…,a1,a0)=a0,ai-2…a1ai-1

Reteaua Omega -este un tip de retea multietaj. Este de dimensiuni nxn cu n=2i iar conexiunile CDE sunt de tip Shufle. si ese o retea blocata.Este formata din i etaje,fiecare etaj fiind format din cate n/2 comutatoare 2*2.

Rutarea datelor in reteaua Omega

Se considera ca etajele retelei sunt numerotate de la iesire catre intrare, astfel etajul de iesire va fi etjul 0,iar cel de iesire i-1,fiecare etaj se vor nota intre 0 si n/2-1.

Pt a conecta o intrare S-sursa si o iesire d-destinatie, pornind de la exprimarea binara a lui S si D. s=si-1si-2…s1s0

d=di-1di-2...d1d0

Reteaua BaseLine- se genereaza recursiv. In primul etaj,un bloc de dimensiunea n*n.Al 2-lea etaj este format din 2 blocuri 2*2,fiecare sub-bloc de dimens m*n este format la randul lui din m/2 comutatoare de dim 2*2.Reteaua CDE intre blocurile de dim m*n si blocurile de dim m/2*m/2 de la etajul urmator este realizata prin permutari de baza.

Analiza comparativa a retelelor dinamice de interconectare. : reteaua de tip magistrala este cea mai ieftina, dar lungimea de banda disponibila pt un procesor este mai scazuta.Reteaua crossbar este mai costisitoare dar are cea mai mare largime de banda, ceea ce o face cea mai indicata pt retelele de dim mari.Caracterul de blocat sau neblocat al retelei multietaj este dat de nu,marul si capacitatea conductoarelor folosite si de topologia CDE de conexiune intre etaje.

CURS 2

Retele statice de interconectare

In retelele statice legatura dintre noduri sunt fixe,necontrolabile. Nodurile sunt formate din:un procesor,un modul de memorie locala si un cerc de routare ce asigura interfata dintre procesor si link-urile de interconectare cu celelalte noduri.

Topologii ale retelelor statatice

Topologi in retele orientate complet

In aceasta retea fiecare nod este conectat direct cu toate celelalte noduri. Considerand cazul general in care numarul de noduri este n oarecare, parametrii principali ai unei retele sunt: a)gradul nodului:g=n-1

b)diametrul retelei:D=1, c)largimea bisectiei pentru impartirea retelei in doua parti egale sau aproape egale trebuie ca legatura din fiecare nod din cele n/2 noduri ale fiecarei jumatati sa fie eliminate.

Aceste legaturi sunt tot n/2. B=n/2*n/2=n2/4, d)costul retelei este dat de numarul total de link-uri C=n(n-1)/2. Transferul datelor are loc direct in oricare 2 noduri si se face intr-un singur ciclu.Ca acest tip de retea nu este blocanta,fiind similara retelei dinamice crossbar.

Topologia in stea

Aceasta topolgie este de tip centralizat deoarece contine un nod central la care sunt conectate toate celelalte noduri

Oricare legatura intre oricare 2 noduri se face prin modul central.Principalii parametrii: a)gradul nodurilor gc=n-1, g=1 ,g=1,n-1, b)diametrul D=2

c)largimea bisectiei find o structura centralizata,reteaua nu se poate imparti in 2 subretele egale. B=1. d)costul retelei:c=n+1. Reteaua este similara retelei dinamice de tip magistrala si ea este blocanta.Rolul magistralei este indeplinit de nodul central.

Topologia in lant si inele

Daca nodurile exteme nu sunt legate intre ele,reteaua este de tip lant si daca nu sunt legate este de tip inel.

Parcurgerea informatiei in retea se face in ambele sensuri in asa fel incat drmul parcurs sa fie cel mai scurt.

Parametrii : a)gradul nodurilor g=1, pentru noduri terminale, g=2, pentru celelalte noduri. b)diametrul retelei:Dl=n-1, Di=m/2

c)largimea bisectiei:o retea lant se poate imparti in 2 parti egale sau aproape egale avand fiecare cate n/2 noduri Bl=1, Bi=2

d)costul retelei:Cl=n-1, Ci=n

Topologia in retele grila si tor

Reteaua de tip grila bidimensionala este o extensie a retelei lant unidimens prin conectarea in paralel a mai multor retele de tip lant. Reteaua de tip tor este o extensie a retelei inel avand o legatura in ambele sensuri.Parametrii:

a)gradul nodurilor : gg=2 nodurile din colturi; gg=3 nodurile din lant marginal; gg=4 noduri din int.; gt=4

b)diametrul Dg=2(√n-1)

Pentru reteaua de tip grila este data de numarul de legaturilor dintre colturile opuse. Pentru reteaua de tip tor este data de numarul de legaturi dintre nodul din centru sau dintre nodurile din centru si un nod din coltul cel mai indepartat.

c)largimea bisectiei: Bg=√n, Bt=2*√n

Transferul datelor are loc ordonat pe linia p careia ai apartine nodul emitent pana in dreptul coloanei carei apartine nodul receptor.

d)costul: cg=2*√n*(√n-1),

ct=2*√n*√n=2n

Retea de tip arbore

La o retea de tip arbore k- fiecare nod este conctat la k noduri cu exceptia nodurilor frunza care nu au descendenti.

k=2 arbore binar

Arborele binar complet structurat in n nivele numerotate de la radacina la frunze n-1.

Fiecare nivel(0≤j≤l)are un numar de 2j noduri,deci numarul total de noduri este m=20+21+…+2l-1=2j+1-1.

Parcurgerea nodurilor ajuta la etichetarea nodurilor retelei. Aceasta poate fi printr-o parcurgere transversala sau prin alt tip de parcurgere.

Considerand etichetarea realizata prin parcurgere transversala se poate spune ca fiecare eticheta i are un parinte de adresa [i/2]-1 si orice nod de eticheta i are 2 descendenti de adrese (2*i+1) si (2*i+2). Parametrii retelei:

a)gradul nodurilor: gb=1,2,3, gk=1,k,k+1

b)diametrul retelei :D=2(l-1) = 2[log(n+1)-1]

c)largimea bisectiei : B=1

d)costul : Pentru arborii binari completi Cb=2(2l-1-1)=2l-2=2(lgn+1)

Ck=k(kl-1-1)/(k-1)