CP_Cap1_Arhitecturi_pentru_calculul_paralel.pdf

Calcul paralelCalcul paralel

Curs Anul IV Specializarea Ingineria Informaiei (INF)

Facultatea de Electronic, Telecomunicaii i Tehnologia Informaiei

Prof. Felicia Ionescu

Prof. Felicia Ionescu Calcul paralel - Cap. 1 2

Capitolul 1Capitolul 1-- Arhitecturi pentru calculul paralelArhitecturi pentru calculul paralel1.1 Introducere1.2 Clasificarea calculatoarelor dup mecanismul de control (clasificarea Flynn) 1.3 Clasificarea calculatoarelor paralele dup organizarea memoriei

1.3.1 Arhitecturi cu memorie partajata1.3.2 Arhitecturi cu transfer de mesaje

1.4 Clasificarea calculatoarelor MIMD1.5 Granularitatea calculatoarelor paralele1.6 Sisteme paralele i distribuite

1.6.1 Clustere de calculatoare1.6.2 Sisteme Grid1.6.3 Sisteme Cloud Computing

1.7 Scurt istoric al dezvoltarii sistemelor paralele i distribuite1.7.1 Prototipuri de calculatoare paralele destinate cercetrii1.7.2 Primele generaii de calculatoare paralele1.7.3 Generaia actual de sisteme paralele i distribuite

1.8 Reele de interconectare n calculatoarele paralele1.8.1 Reele dinamice de interconectare1.8.2 Reele statice de interconectare

1.9 Reele de interconectare n clustere de calculatoare1.9.1 Reteaua Gigabit Ethernet1.9.2 Reteaua Infiniband1.9.3 Reteaua Myrinet


1.1 Introducere1.1 Introducere Exist numeroase aplicaii cu cerine de calcul foarte mari (intens

computationale) provocari ale stiintei n diferite domenii: Domeniul stiintific: fizica nucleara, studierea fenomenelor naturale (meteorologice,

fizica pamantului), biologie(genom), biochimie (proiectarea de noi medicamente) etc. Domeniul ingineresc: proiectare n mecanic, electronic, arhitectur etc. Domeniul economic: previziuni financiar-bancare, modelri macro-economice etc.

Pentru astfel de aplicatii calculatoarele secventiale (tradiionale) nu au performane suficiente si sunt necesare calculatoare paralele, constnd din multiple procesoare, care ofer performane de calcul ridicate

Calculatoarele secveniale: sunt bazate pe modelul von Neumann (1945); constau dintr-o unitate de prelucrare (procesor), o unitate de memorie (M) i un canal

de comunicaie;

Creterea performanelor calculatoarelor secveniale se obine prin: Creterea vitezei de operare a memoriei i a vitezei de transfer a datelor ntre

procesor i memorie Creterea performanelor procesoarelor prin:

Creterea vitezei de operare a procesoarelor Introducerea paralelismului n interiorul procesoarelor


CreCreterea performanterea performanelor calculatoarelor secvenelor calculatoarelor secvenialeiale

Creterea vitezei de operare a memoriei i a vitezei de transfer a datelor intre procesor i memorie: Memorii intreesute (crete banda de comunicaie) Memorii cache (scade latena de comunicaie)

Processor Memorie

Arhitectura von Neumann

Processor Memorie

Memorie

Memorie

Memorii ntreesute

Cache Memorie

Memorie

Memorie

Processor

Memorii cache


CreCreterea vitezei de operare a procesoarelorterea vitezei de operare a procesoarelor Creterea vitezei de operare a procesoarelor:

Creterea frecvenei ceasului procesorului (clock rate) Introducerea paralelismului n interiorul procesorului

Creterea frecvenei ceasului procesorului -> cresterea IPS (Instructions Per Second): numrul de operaii cu numere ntregi (operaii netiintifice) pe secund. Multipli: kIPS = 103 IPS i MIPS = 106 IPS.

IPS executate de procesoare a crescut n permanen, prin cresterea frecvenei de ceas (clock rate). De exemplu: IBM System/370 (1972) la o frecven de ceas de 1 MHz obtine 1 MIPS; Intel 8080 (1982 ) la o frecven de ceas de 12 MHz obtine 2.66 MIPS; Intel 486DX (1992) la o frecven de ceas de 66 MHz obtine 54 MIPS; Intel Core 2 Extreme QX9770 (2008) la frecventa de ceas de 3.2 GHz obtine ~ 60000

MIPS.

Frecvena de ceas nu poate crete la infinit, datorit limitrii fizice fundamentale, prin care viteza de propagare a semnalelor n interiorul chipului este limitat la valoarea vitezei luminii n vid (3x108 m/s)

De aceea, pentru creterea mai puternic a performanelor procesoarelor se adopt diferite soluii arhitecturale din ce n ce mai complexe, n principal prin introducerea paralelismului n interiorul procesoarelor


Introducerea paralelismuluiIntroducerea paralelismului n interiorul proceson interiorul procesoarelorarelor Introducerea paralelismului (concurenei) n interiorul procesoarelor

(paralelism implicit): mai multe ci de date, mai multe etaje de prelucrare Ca urmare crete complexitatea circuitelor VLSI ale procesoarelor Cresterea complexitii (numr de componente) circuitelor VLSI este descris

empiric de lege a lui Moore: complexitatea circuitelor VLSI se dubleaz n fiecare an (n 1965); n 1975, Gordon Moore a ajustat durata estimat de dublare a complexitatii circuitelor VLSI la 1,5 ani

Exist controverse privind evoluia n viitor a complexitii circuitelor VLSI Actualmente sunt combinate diferite tehnici de proiectare a procesoarelor:

Tehnica pipeline Prelucrarea vectorial pipeline Procesoare VLIW (Very Long Processor Word) Procesoare superscalare Procesoare multi-core Procesoare SCMP (Single Chip Message Passing) Acceleratoare hardware - procesoare GPU (Graphical Processing Unit)

Calculatoarele paralele actuale constau din multiple procesoare performante (zeci, sute, mii, sute de mii etc.)


Tehnica pipeline (1)Tehnica pipeline (1) Tehnica pipeline: divizarea fiecrei instruciuni ntr-un numr de etape, fiecare

etap fiind executat de o unitate funcional a procesorului (segment pipeline) Segmentele pipeline S0, S1, , Sd-1 sunt conectate ntre ele, formnd o

conduct (pipe) de execuie a fiecrei instruciuni Segmentele pipeline tipice:

extragerea (F fetch ) decodarea (D decode) execuia operaiei (E execute) scrierea rezultatului (W write-back)

n acelai moment de timp, mai multe instruciuni (maximum d) se afl n diferite stadii de execuie n unitile pipeline ale procesorului

Execuia pipeline: nu reduce timpul de executie al unei instruciuni individuale dar reduce timpul mediu de execuie a unui numr oarecare (suficient de mare) de

instruciuni, producnd o accelerare de calcul, numit accelerare pipeline (pipeline speedup)


Tehnica pipeline (2)Tehnica pipeline (2) Accelerarea pipeline este raportul dintre timpul de execuie a instruciunilor fr

pipeline i timpul de execuie a instruciunilor cu pipeline Pentru un procesor pipeline cu d segmente pipeline cu durate de execuie egale

cu unitatea de timp: TS (timpul de execuie secvenial a n instruciuni: TS = n x d TP (timpul de execuie pipeline a n instruciuni): TP = n + d -1 AP (accelerarea pipeline): AP = TS / TP = n x d / (n + d 1) =~d (dac n >> d)

Accelerarea pipeline este limitat la numrul de segmente pipeline (d) Exemplu: Intel Pentium 4 are 20 etape pipeline la 2GHz

TimpF D E W

F D E W

F D E W

F D E W

F D E W

F D E W

I1

I2

I3

I4

I6

I5

Instruciuni


Procesarea vectorialProcesarea vectorial pipelinepipeline Un procesor sau un calculator vectorial pipeline const dintr-o unitate

de procesare i registre vectoriale i posed instruciuni vectoriale de operare asupra vectorilor de date

Fie, de exemplu, doi vectori x i y de dimensiune n, i o bucl de calcul:for (i = 0; i < n; i++)

y[i] = a*x[i] + y[i]; n procesarea vectorial pipeline, aceast bucl se poate nlocui cu o

singur instruciune vectorial: Y = a*X + Y. Datele vectorilor sunt memorate n registre vectoriale i sunt procesate

succesiv n unitatea de procesare n acest fel se elimin costul operatiilor de extragere (F) i decodare (D)

repetate la fiecare iteraie Exemplu:

Execuia a n instruc. cu cte 4 etaje pipeline (F,D,E,W): TS = n(F) + n(D) + n(E) + n(W) =4n

Execuia unei instruct. vectoriale pentru n elemente: TV = 1(F) + 1(D) + n(E) + n(W) = 2(n+1)

TV < TS pentru n > 2


Procesoare VLIWProcesoare VLIW

ntr-un procesor VLIW (Very Long Instruction Word) o instruciune codeaz mai multe operaii care se pot executa concurent, pe unitti de prelucrare multiple, dac nu exist dependene ntre operaii n acest fel se reduce numrul operaiilor de fetch (F) i decode (D) Exemplu: arhitectura procesorului Intel IA64 este VLIW

n VLIW dependenele de date sau de resurse se pot rezolva: Static (naintea execuiei) de ctre compilatoare care planific ordinea de execuie a

operaiilor, astfel nct s respecte dependenele existente ntre operaiile unei instruciuni lungi dar nu toate dependenele pot fi cunoscute n timpul compilrii (dependene care apar n

funcie de rezultatul unei instruciuni conditionale)

Dinamic (n cursul execuiei) de hardware specializat, care detecteaz dependenele i planific corespunztor operaiile instruciunii lungi, dar atunci crete complexitatea hardware (volumul circuitelor neceasare)


Procesoare superscalareProcesoare superscalare Un procesor superscalar are mai multe uniti de prelucrare (n general

pipeline) i poate executa mai multe instruciuni n acelasi ciclu (exemplu procesorul superscalar Sun UltraSPARC) Ex.: execuie superscalar pe dou ci pentru adunarea a 4 numere:

1. load R1, @1000 2. load R2, @1008 3. add R1, @1004 4. add R2, @100C 5. add R1, R26. store R1, @2000

Dou sau mai multe instruciuni se pot executa simultan (dac nu existdependene ntre ele (ex: nu sunt dependene ntre instr. 1 i 2 sau 3 i 4)

Dependenele se rezolv static (la compilare), dar nu pot fi detectate toate dependenele, sau dinamic (n cursul execuiei), de hardware specializat, dar aceasta crete volumul circuitelor

Cicli instruciune0 2 4 6 8

load R1, @1000load R2, @1008

add R1, @1004add R2, @100C

add R1, R2

IF ID OF

IF ID OF

IF ID OF E

IF ID OF E

IF ID NA E

IF ID NA WB

IF: Instruction FetchID: Instruction DecodeOF: Operand FetchE: Instruction ExecuteWB: Write-BackNA: No Action

store R1, @2000


Procesoare multiProcesoare multi--corecore Un procesor multicore conine mai multe procesoare interne (cores) n acelai

chip, care execut secvena de instruciuni (programul) Schema generic a unui procesor dual-core (dat n figura) conine cte o memorie

cache local pentru fiecare procesor (nivel L1) i o memorie cache partajat de ambele procesoare (nivel L2)

Exemple: Intel Core Duo E6750, An AMD Athlon X2 6400+ dual-core processor. Procesoarele multi-core:

omogene (conin uniti de acelai fel) heterogene (conin uniti diferite)

Comunicaia ntre cores n interiorul chipului: prin partajare

cache partajat memorie partajat

prin transfer de mesaje, folosind o reea de interconectare intern; acestea se mai numesc SCMP (Single Chip Message Passing)

Creterea performanelor unui procesor multicore este semnificativ dac executalgoritmi paraleli

CPU &Cache L1

CPU &Cache L1

Cache L2 &Interfaa memorie

Memorie


Procesoare SCMP (Single Chip Message Passing)Procesoare SCMP (Single Chip Message Passing) Procesoarele SCM conin uniti de prelucrare multiple conectate printr-o reea

de interconectare intern Fiecare unitate de prelucrare este un procesor RISC (Reduced Instruction Set

Chip) cu o unitate ALU (Arithmetic Logic Unit) i o unitate FPU (Floting Point Unit), memorie local

Procesoarele se conecteaz printr-o reea de conectare; de exemplu reeauastatic gril bidimensional, n care fiecare procesor se conecteaz cu 4 vecini


Acceleratoare hardwareAcceleratoare hardware Procesoare GPU Procesoare GPU (Graphical Processing Unit)(Graphical Processing Unit)

Procesoarele sau sistemele de calcul pot include acceleratoare - implementeaz direct n hardware operaii critice, necesare n anumite aplicaii; de exemplu: Uniti aritmetice cu virgul mobil Uniti de calcul FFT (Fast Fourier Transform ) incluse n procesoare de semnal Procesoare grafice pentru accelerarea operaiilor grafice

Actualmente, procesoarele grafice (GPU Graphical Processing Unit) GPUs - compuse din mai multe (zeci, sute, mii) uniti de prelucrare performante,

folosite nu numai pentru grafic, ci i pentru calcule generale GPGPU (General Purpose GPU); produse de: Nvidia, Intel, AMD

In fig.: chipul Nvidia GT200: cluster de 10 procesoare (TPC), fiecare cu 3 uniti SM (Streaming Multiprocesor), alctuite din cte 8 SP (Streaming Procesor)


EvoluEvoluia performania performaneleloror procesoarelor procesoarelor Folosind diferite tehnici, viteza de calcul a procesoarelor i a calculatoarelor

secveniale a crescut continuu, de la apariia lor i pn n prezent: de la ~ 50 operaii n virgula mobila / sec. (50 FLOPS) la calculatorul ENIAC din 1950 pn la valori de 1TFLOPS la procesoarele actuale:

procesorul AMD x86_64 Opteron Quad Core: 8.4 GFLOPS (la 2.1 GHz) procesorul Intel POLARIS: 1 TFLOPS (la 3.2 GHz).

Un FLOPS (FLoating point Pperaions Per Second) - msur a performanelor de calcule n virgul mobil; multiplii cei mai folosii ai FLOPS sunt:

MFLOPS (megaFLOPS) = 106 FLOPS; GFLOPS (gigaFLOPS) = 109 FLOPS; TFLOPS (teraFLOPS)= 1012 FLOPS; PFLOPS (petaFLOPS) = 1015 FLOPS; EFLOPS (exaFLOPS) = 1018 FLOPS.

Reprezentarea performanelor proc. n funcie de cost arat c: la nceputul fiecrei curbe (costuri mici),

perf. cresc aprox. linear cu costul peste un anumit punct, creteri mici ale

perf. necesit creteri mari ale costului Deci este mai economic utilizarea mai

multor procesoare cu perf. moderate dect a unui singur procesor cu performane foarte mari

2000

19901980

1970

Performane

Cost


Calculatoare paralele (1)Calculatoare paralele (1) Definitie: Un calculator paralel (main paralel) este un calculator care

conine multiple uniti de procesare (procesoare, core) i este capabil s prelucreze informaia prin manevrarea concurent a datelor, asigurnd, n general, scderea timpului de execuie a aplicaiilor (accelerare paralel) Accelerarea paralel (S Speedup) este raportul dintre timpul de execuie secvenial

i timpul de execuie paralel a unei aplicaii

Calculatoarele paralele satisfac cerinele mereu n cretere de putere de calcul, prin obinerea unor performane pe care un calculator secvenial nu le poate atinge, datorit limitrilor existente

Calculatoarele paralele cu cele mai mari performane de calcul sunt numite supercalculatoare n perioada de timp respectiv

Performanele supercalculatoarelor au crescut n permanen: Ceea ce n deceniile trecute era considerat un supercalculator, este astzi depait de

un simplu PC sau dispozitiv mobil; Primul supercalculator, ILLIAC IV (Illinois University, 1968), cu 64 de procesoare

specializate de 64 bii la 13 MHz, a atins performanta de 200 MFLOPS (proiectul intialprevedea 256 de procesoare i performana de 1 GFLOPS);

Actualmente (2012), primele 10 supercalculatoare depesc 10 PFLOPS


Calculatoare paralele (2)Calculatoare paralele (2)

Din punct de vedre hardware: se pot construi maini paralele cu sute de mii de noduri de calcul puternice, legate prin reele de interconectare la un pre relativ sczut

Din punct de vedere software apar numeroase probleme dificile ca: descompunerea aplicaiilor n sute i mii de pri (task-uri), care s fie executate

concurent; coordonarea activitatii tuturor task-urilor pentru realizarea unei aplicaii (comunicarea

i sincronizarea ntre task-uri).

n plus, se resimte lipsa de maturitate a instrumentelor soft (limbaje, biblioteci, sisteme de dezvoltare) necesare pentru calculul paralel, precum i lipsa de experien a programatorilor n programarea paralel

Clasificri ale calculatoarelor paralele: Clasificarea n funcie de mecanismul de control (taxonomia Flynn) Clasificarea n funcie de organizarea spaiului de adres al memoriei Clasificarea n funcie de granularitate


1.2 1.2 Clasificarea calculatoarelorClasificarea calculatoarelor dup mecanismul de control dup mecanismul de control

Clasificarea calculatoarelor propus de Michael Flynn (1972), n funcie de numrul fluxurilor de instruciuni i de date (unice sau multiple): Calculatoare SISD - cu flux unic de instruciuni i de date (Single Instruction

Stream, Single Data Stream) Calculatoare MISD - cu fluxuri multiple de instruciuni, flux unic de date

(Multiple Instruction Stream, Single Data Stream) Calculatoare SIMD - cu flux unic de instruciuni, fluxuri multiple de date (Single

Instruction Stream, Multiple Data Stream) Calculatoare MIMD - cu fluxuri multiple de instruciuni i de date (Multiple

Instruction Stream, Single Data Stream)

Aceast clasificare este o clasificare foarte general, care nu difereniaz calculatoare din punct de vedere al structurii

Cu toate acestea, clasificarea (taxonomia) lui Flynn este frecvent utilizat i aceste clase arhitecturale vor fi analizate n continuare


Calculatoare SISDCalculatoare SISD

Un calculator SISD const dintr-un procesor (P), (compus din unitatea de procesare - UP i unitatea de control - UC) i o unitate de memorie (M);

n fiecare pas de calcul, UC lanseaz o instruciune, UP executa acea instruciune aupra unei date din fluxul de date (FD), obinut din unitatea de memorie (M) i trimite rezultatul napoi n memorie

Un astfel de calculator este un calculator secvenial, care respect modelul de execuie introdus de John von Neumann n perioada anilor 1945

FDFIUnitate deControl (UC)

Unitate de Memorie (M)

Unitate deProcesare (UP)

Procesor


Calculatoare MISDCalculatoare MISD n calculatoarele MISD, exist N uniti de procesare (UP), fiecare primete un

flux de instruciuni (FI) de la propria lui unitate de control (UC), i executoperaii asupra datelor dintr-un flux unic de date (FD), primit de la o unitate de memorie (M)

La fiecare ciclu de execuie, fiecare unitate de procesare UPi execut operaii diferite (n funcie de instruciunea din fluxul FIi pe care o primete de la propria unitate de control - UCi) asupra aceleiai date (din fluxul de date FD) extrase din memorie

Arhitecturile MISD (denumite i tablourile sistolice) sunt utilizate pentru aplicaii specializate

FI1

FI0

FD Unitate de Memorie (M)

Unitate de Procesare (UP0)

Unitate de Control (UC0)



FIN-1Unitate de Control (UCN-1)

Unitate de Procesare (UPN-1)


Calculatoare SIMDCalculatoare SIMD Un calculator SIMD const dintr-un numr N de uniti de procesare (UPi,

0 i < N ), care opereaz sub controlul unui flux unic de instruciuni (FI) lansat de o unitate de control global (UC)

Unitatile de procesare lucreaz sincron: la fiecare pas de calcul, fiecare unitate UPi execut aceeai instruciune (extras din fluxul FI) asupra unei date diferite, extrase din propriul fluxul de date (FDi)

Calculatoarele SIMD mai sunt cunoscute sub numele de tablouri deprocesoare (processor arrays)

Comunicaiile ntre procesoare se fac prin memorie partajat i/sau reea de interconectare

FDN-1

FD1

FD0

FIUnitate de Control (UC)


Unitate de Procesare (UPN-1)


Memorie

i/sau

Reea de Interconectare


Calculatoare MIMDCalculatoare MIMD Un calculator MIMD const dintr-un numr N de uniti de procesare (UPi

0 i < N), fiecare cu propria lui unitate de control (UCi) i memorie local Fiecare unitate de procesare UPi execut instruciuni din fluxul de instruciuni FIi

lansat de unitatea de control proprie UCi, asupra datelor din fluxul de date propriu FDi

In calculatoarele MIMD fiecare un procesor (compus din UC i UP) poate executa un program diferit de programul executat de celelalte procesoare

Clasa de calculatoare MIMD este cea mai general i cea mai flexibil dintre toate clasele de calculatoare paralele

FI0 Unitate de Procesare (UP0)


FD0

FI1Unitate de Control (UC 1)


FD1

FIN-1Unitate de Control (UC N-1)

Unitate de Procesare (UP N-1)

FDN-1

Memorie

i/sau



ComparaComparaie SIMD ie SIMD -- MIMDMIMD Construcia calculatoarelor SIMD i MIMD

MIMD utilizeaz procesoare de uz general SIMD utilizeaz procesoare proiectate special, mai compacte -o singur unit. central

Calculatoarele SIMD: sincronizare automat ntre procesoare la fiecare ciclu de instruciune execut eficient programe care implic operaii identice asupra unor masive de date,

programe care sunt cunoscute sub numele de programe data paralele Calculatoarele MIMD:

pot fi folosite pentru rezolvarea oricrui tip de problem, inclusiv cele care prezint masive de date regulate i operaii identice executate de toate procesoarele n aceleai momente de timp (programe data-paralele)

dat fiind c procesoarele lucreaz asincron, algoritmii implementai sunt algoritmi asincroni, care sunt dificil de proiectat, de implementat, de testat i de evaluat.

n evoluia calculatoarelor paralele se observ variaia tendinelor arhitecturale, n funcie de nivelul de dezvoltare a tehnologiilor microelectronice n primele faze de dezvoltare (1970 - 1990) s-au realizat mai ales calculatoare SIMD,

mai compacte i mai ieftine pentru acea perioad n perioada urmtoare (1990 2010) s-au realizat mai ales calculatoare MIMD, care

folosesc procesoare de uz general, ieftine datorit produciei mari Actualmente (2010-2013) asistm la reluarea arhitecturii SIMD n procesoarele GPU,

(Graphical Processing Unit), incluse n calculatoarele paralele


1.3 Clasificarea calculatoarelor paralele1.3 Clasificarea calculatoarelor paraleledupdup organizarea memorieiorganizarea memoriei

Din punct de vedere al modului cum comunic procesoarele ntre ele, exista dou tipuri de arhitecturi paralele: arhitecturi cu memorie partajat arhitecturi cu transfer de mesaje (fara memorie partajat)

Arhitecturi cu memorie partajat (strns cuplate tightly coupled): modelul cu acces uniform la memorie (Uniform Memory Access UMA) (a) modelul cu acces neuniform la memorie (NonUniform Memory Access NUMA

P0 P1 PN-1

Reea de interconectare

MP0 MP1 MPM-1

(a)


Modele cu acces neuniform la memorie (NUMA)Modele cu acces neuniform la memorie (NUMA)

Modelul NUMA cu memorie local (nepartajat) i memorie global partajat

P0 ML0 P1 ML1 PN-1 MLN-1


MGP0 MGPM-1MGP1

Modelul NUMA cu memorie partajat distribuitP0 MPD0 P1 MPD1 PN-1 MPDN-1



ArhitecturArhitecturaa cu transfer de mesajecu transfer de mesaje

Aceast arhitectur const din mai multe noduri conectate printr-o reea de interconectare

Fiecare nod din reea conine o unitate format din procesor (P) i memorie (M) local (care nu poate fi accesat de alte procesoare din sistem)

Nu exist memorie partajat, comunicaia se face numai prin transfer de mesaje Se mai numesc sisteme slab cuplate (loosly coupled)


P0 M0

P1M1

PN-1MN-1


1.4 1.4 Clasificarea calculatoarelor MIMDClasificarea calculatoarelor MIMDCalculatoare MIMD

MultiprocesoareSpaiu unic de adrese al

memoriei partajate

MulticalculatoareSpaii multiple de adrese ale

memoriei i transfer de mesaje

Multiprocesoarecu memorie partajatcentralizat (UMA)(SMP Symmetric Multi-Processor)

Multiprocesoarecu memorie partajatdistribuit (NUMA)

Multicalculatoarecu memorie

distribuit

Multicalculatoarecu memorie

centralizat (?)

Slab cuplatePuternic cuplate

Arhitecturile actuale ale calculatoarelor paralele sunt hibride: MPP (Massively Parallel Processsing): multicalculatoare n care nodurile sunt compuse din multiprocesoare (CPU) multicore, n combinaie cu procesoare GPU


1.1.55 Granularitatea calculatoarelor paraleleGranularitatea calculatoarelor paralele Granularitatea calculatoarelor paralele:

Granularitate mare: numar mic de procesoare puternice; exemplu: Cray Y-MP, compus din16 procesoare puternice, cu o vitez de procesare de 10 Gflops

Granularitate fina: numar mare de procesoare slabe; de exemplu: Connection Machin 1 (CM-1) conine 65536 (64k) procesoare de un bit

Granularitate medie: numar mediu de procesoare cu capacitate de procesare moderata

Valorile care definesc granularitatea (numr de procesoare, viteza de procesare) variaz (cresc) ncontinuu, odat cu dezvoltarea tehnologic

Diferite aplicaii de calcul paralel sunt adecvate pentru calculatoare paralele cu diferite valori ale granularitii Aplicaii cu grad limitat de paralelism nu pot beneficia de un numr foarte mare de

procesoare dintr-un calculator cu granularitate fin, i sunt mai potrivite execuiei pe calculatoare cu granularitate medie sau grosier

Pentru execuia eficient a programelor paralele trebuie s existe o potrivire(matching) ntre granularitatea calculatorului paralel i gradul de paralelism al algoritmului


1.1.66 Sisteme paralele Sisteme paralele i distribuitei distribuite Sisteme paralele i distribuite - conin mai multe (posibil sute de mii) procesoare:

Sisteme (calculatoarele) paralele uniti la distante mici (aceeasi incinta), comunica prin memorie partajata sa prin reea rapida de interconectare cu transfer de mesaje

Sisteme distribuite unitati la distante mari, comunica prin reea de interconectare cu transfer de mesaje

n general se consider c noiunea de sistem distribuit nglobeaz i pe aceea de calculator (sistem) paralel i deci sistemele distribuite cuprind: Calculatoare paralele (multiprocesoare, multicalculatoare, MPP) Sisteme distribuite bazate pe reele de calculatoare:

Reele LAN (Local Area Network) suport pentru clustere de calculatoare Retele WAN (Wide Area Network - cum este reeaua Internet) suport pentru sisteme de

calcul distribuit cum sunt sistemul Web, Grid-uri, sisteme Cloud Computing n nodurile reelei unui sistem distribuit pot fi folosite calculatoare secveniale sau paralele

HPC - High Performance Computing - www.top500.org public lista celor mai performante 500 de sisteme paralele i distribuite (supercalculatoare), ncepnd din anul 1993; listele sunt actualizate o dat la 6 luni

n momentul de fa (conform listei top500/noiembrie 2012) supercalculatoarele se ncadreaz ntr-una din dou clase arhitecturale: MPP (Massively Parallel Processing) - 17.8 % Clustere de calculatoare - 82.2 %


Calcul paralel Calcul paralel i distribuiti distribuit Calcul (procesare) concurent mai multe sarcini de calcul (task-uri) se

executa concurent pe mai multe procesoare ntr-un sistem paralel sau distribuit: Calcul paralel (aplicaie paralel) rezolv o problema intens computational,

partiionat n mai multe sarcini de calcul care se execut concurent ntr-un sistem paralel sau distribuit; comunicaie prin memorie partajata sau transfer de mesaje

Calcul distribuit (aplicaie distribuit) execuia concurent a mai multor programe de calcul inerent distribuite (plasate) n unitati distincte ale unui sistem distribuit; comunicatie prin transfer de mesaje

Algoritmi concureni: Algoritmi paraleli algoritmi care definesc aplicaii paralele Algoritmi distribuiti - algoritmi care definesc aplicaii distribuite

Programare concurent: Programare paralel dezvoltarea algoritmilor paraleli Programare distribuit dezvoltarea algoritmilor distribuii

Convergena (ntreptrunderea) noiunilor paralel-distribuit: Calculul paralel se poate desfura atat n calculatoare (sisteme) paralele ct i n

sisteme distribuite Componentele unei aplicatii distribuite pot fi task-uri intens computationale (paralele) Calculatoare paralele pot fi folosite ca servere n aplicaii distribuite Se folosete termenul general calcul de inalt performan HPC (High Performance

Computing)


Clustere de calculatoareClustere de calculatoare

Un cluster de calculatoare este compus dintr-un grup de calculatoare independente, conectate printr-o reea local (LAN Local Area Network) care poate oferi (n funcie de numrul i capacitatea calculatoarelor conectate) performante foarte ridicate, pn la nivel de supercalculatoare.

~82 % din supercalculatoarele actuale (2013) sunt clustere De ex., clusterul Fujitsu cu 705024 procesoare SPARC64 la 2.0 GHz instalat n

Japonia atinge 10510 TFLOPS (10.510 PFLOPS); a fost #1 n lista top500/nov 2011 i #3 n lista top500/nov.2012

Un cluster este un sistem local, n care controlul (proprietatea, administrarea) aparine unui singur domeniu administrativ (intreprindere, laborator).

Clusterele se pot clasifica n: Clustere nededicate, compuse din calculatoarele conectate n reea ale unei

ntreprinderi, pe care se pot executa aplicatii individuale (ale celor ce detin aceste calculatoare) concomitent cu aplicaiile paralele care necesit puterea de calcul a tuturor, sau a unui mare numr din calculatoarele conectate n reea; sunt primele care s-au dezvoltat

Clustere dedicate, care sunt clustere special construite, folosite pentru execuia aplicaiilor paralele, fr utilizatori individuali ai fiecarui calculator din cluster;


Avantajele clusterelor de calculatoareAvantajele clusterelor de calculatoare Apariia clusterelor:

Determinat de faptul c timpul de calcul al calculatoarelor existente intr-o ntreprindere este n general utilizat parial (editare de documente, e-mail-uri, sau dezvoltare de programe)

Resursa de calcul format din timpul de calcul ramas neutilizat al calculatoarelor din reea poate fi organizat ca un cluster nededicat care s execute aplicaii intens computaionale

Ulterior s-a trecut la construirea clusterelor dedicate, deosebit de puternice, care concureaz cu succes calculatoarele paralele (multiprocesoare i multicalculatoare)

Avantajele clusterelor: Riscuri de dezvoltare sczute Costuri sczute, datorit posibiltaii de a folosi calculatoare din productia curenta

(COTS Commodity Of the Shelfs marfa de pe raft) Suporta arhitecturi heterogene, ceea permite extinderea treptata a sistemului, fara

costuri exagerate n faza initiala (asa cum se intampla la achizitia unui calculator paralel performant)

Clusterele pot urmri cu usurin progresul tehnologic, fiecare nou calculator performant achizitionat de ntreprindere poate fi nglobat n cluster.


Arhitectura clusterelor de calculatoareArhitectura clusterelor de calculatoare Componentele clusterelor: hardware i software

Hardware: un cluster este compus din noduri (host-uri) conectate printr-o reea de comunicaie, fiecare nod este un calculator independent, secvenial sau paralel: COP (Cluster of PCs) COW (Cluster of Workstations) CLUMP (Cluster of Multiprocessors).

Reea de interconectare

PC/Workstation

Interfata reea

PC/Workstation

Interfata reea

PC/Workstation

Interfata reea

Cluster Middleware

Aplicii secvenialeAplicii secvenialeAplicii secveniale Medii de programare paralel

Aplicii secvenialeAplicii secvenialeAplicii paralele


Componentele hardware ale clusterelorComponentele hardware ale clusterelor Procesoarele utilizate n nodurile clusterelor sunt procesoarele din producia

curent a marilor producatori (Intel, Motorola, AMD etc.) Sistemele de stocare a datelor constau din:

memoria principal RAM (Random Access Memory), cu capaciti ce depasesc n general 4 GByte/nod);

memorii cache; memoria secundar, compus din hard-disk-uri de mare capacitate.

Retelele de interconectare utilizate n clustere sunt n general reele dinamice de mare vitez standardizate: Gigabit-Ethernet Infiniband Myrinet

Fiecare nod se conecteaz la reea prin module de interfa, compuse din plci de reea (Net. Interface HW) i driverele software de comunicaie aferente (Comm SW)


Componentele software ale clusterelorComponentele software ale clusterelor

Componentele software ale clusterelor: sisteme de operare, middleware, biblioteci, toolset-uri de dezvoltare, programe de aplicaii

Sistemele de operare ruleaz n fiecare nod din cluster, asigurnd: gestiunea resurselor locale ale nodului respectiv Interfaa cu middleware-ul i aplicaiile din cluster

Sistemele de operare folosite n supercalculatoarele din top500/nov. 2011 (dintre care majoritatea de 83.4% sunt clustere): Sisteme de operare Linux (91.2% din sisteme, dintre care majoritatea sunt clustere) Sistemele de operarte Unix sunt folosite ntr-o proporie mult mai mic (6 %) Sistemele de operare Windows au o utilizare sub 1%

Middleware-ul este un nivel software folosit n sistemele distribuite ca intermediar ntre sistemele de operare (locale din fiecare nod) i programele de aplicaii distribuite

n clustere, middleware-ul are, n general, rolul de a asigura o imagine de sistem unic (Single Sistem Image SSI)


Imagine de sistem unicImagine de sistem unic SSI (Single Sistem Image)SSI (Single Sistem Image) Imaginea de sistem unic (SSI) - asigur transparenta localizarii diferitelor sarcini

i resurse, adic utilizatorul nu trebuie s precizeze sau s cunoasc n ce nod anume se afla o resurs sau se execut un job

Serviciile oferite de SSI: Punct unic de intrare (Single Point of Entry) utilizatorul se poate conecta la cluster

ca la un sistem unic, n loc s se conecteze la fiecare calculator n parte Ierarhie unica de fisiere (Single File Hierarchy) - utilizatorul vede toate fisierele din

cluster intr-o singura ierarhie, cu radacina unic Un singur punct de management i control (Single Point of Management and

Control) intregul cluster poate fi monitorizat dintr-un singur punct (host) Spaiu de memorie unic (Single Memory Space) aparena unui spatiu unic de

adrese ale memoriei, construit peste memoriile componente ale nodurilor clusterului Un singur sistem de gestiune a job-urilor (Single Job Management System) -

utilizatorul poate lansa un job n orice nod al clusterului n mod transparent Spatiu unic de I/O (Single I/O Space) fiecare nod poate executa operaii de

intrare/iesire att ctre periferice locale ct i ctre perifericele la distan (remote) Spatiu unic al proceselor (Single Process Space) procesele au identificatori care

sunt unici n intreg clusterul.


Categorii de middleware Categorii de middleware n clusteren clustere

Categorii de middleware folosite n clustere: Sistemele middleware de comunicatie, sunt biblioteci de transfer de mesaje cum

sunt MPI (Message Passing Interface) i PVM (Parallel Virtual Machines)

Sisteme middleware de management a resurselor (Resourse Manager) -au rolul de a primi cererile de execuie a job-urilor i de a le planifica i executa n nodurile de calcul; cele mai cunoscute planificatoare pentru clustere sunt: LSF, TORQUE, Condor, PBS, SGE.

Sisteme middleware de echilibrare a utilizarii resurselor (Workload Manager) -permit o planificare avansat a resurselor i a proceselor; cele mai cunoscute planificatoare avansate sunt Moab i Maui.

Aplicaiile care se pot executa n clustere sunt: Aplicatii obisnuite (secveniale) Aplicatii paralele, compuse din mii (sau mult mai multe) task-uri care se execut

coordonat n nodurile clusterului pentru rezolvarea unor probleme intens computationale

Aplicatii distribuite, care permit colaborarea ntre diferii utilizatori din cluster.


Sisteme Grid Sisteme Grid Definitie concisa a Grid-urilor data n lucrarea "The Anatomy of the Grid" (Ian

Foster, Carl Kesselman, Steven Tuecke, 1999): Grid-ul este o infrastructur distribuit i reconfigurabil, care ofer o modalitate flexibil i securizat de a coordona partajarea resurselor de calcul a diverselor colective dinamice formate din persoane i institutii, numite Organizatii Virtuale (VO).

Analogia cu reelele electrice (power grids), care furnizeaz energie electricconsumatorilor, independent de locul de producere a acesteia (centralele electrice) prin transportul ei prin reelele de distribuitie

Spre deosebire de Internet, care este unul singur, exista numeroase Grid-uri, ca organizatii virtuale construite pentru rezolvarea anumitor probleme, n principal stiintifice, dar i financiare, comerciale etc.

Sistemele Grid permit calculul de nalt performan (HPC) n medii distribuite, i includ resurse cum sunt: Calculatoare performante (supercalculatoare), reele de comunicaie Baze de date Instrumente stiintifice Licene software etc.


Sisteme Sisteme Cloud ComputingCloud Computing Sistemele Cloud Computing sunt sisteme distribuite n care se folosesc servicii

i resurse de calcul externe (remote - la distan) nchiriate (de la furnizori centre de date), atunci cnd sunt necesare (on-demand computing)

Sistemele distribuite cloud computing sunt rezultatul combinaiei mai multor tehnologii pre-existente: Internet, virtualizare, servicii.

Virtualizare: emularea uneia sau mai multor staii sau servere pe un singur calculator fizic Virtualizarea asigur scalabilitatea, flexibilitatea i reutilizabilitatea resurselor fizice

datorit posibilitii de adaptare a resurselor existente la cerinele unor aplicaii diverse si expandabile

Sistemele cloud computing se mpart n trei mari categorii: Software-as-a Service (SaaS) sau Application-as-a-Service (AaaS): aplicaii gzduite

pe servere la distan i accesate de utilizatori distribuii n Internet; utilizatorul nu cumpr softul, ci pltete pentru utilizarea lui (modelul pay-per-use).

Platform-as-a-Service (PaaS) furnizorul (provider) ofer platforma hardware i instrumentele software de dezvoltare a unor aplicaii de ctre utilizatori.

Infrastructure-as-a-Service (IaaS) furnizorul ofer resurse de calcul (capacitate de procesare sau spaiu de stocare), pe care utilizatorii le pot accesa prin Internet.

Furnizori de servicii i resurse cloud computing: Amazon, Google, IBM, Microsoft Tehnologii de dezvoltare a aplicaiilor n cloud: Hadoop, Microsoft Dryad etc.


1.1.77 Scurt istoric al dezvoltarii Scurt istoric al dezvoltarii sistemelor paralele sistemelor paralele i distribuitei distribuite

Mai multe etape (generaii) n dezvoltarea calculatoarelor paralele i a sistemelor distribuite, prezentate n tabelul urmator:

Generaia Caracteristici Cteva exemple

Prototipuri de cercetare timpurii

Procesoare special proiectate Illiac, PASM, MPP, NYU Ultra, HEP, TRAC, Cosmic Cube, RP3

Primele generaii de calculatoare paralele

Procesoare specializate sau din productia curent; retele de interconectare statice sau dinamice nestandardizate (proprietar)

Sequent Balance, Sequent SymmetryNCUBE-1, NCUBE-2CM-1, CM-2, CM-5iPSC/1, iPSC/2

Generatia actualde sisteme paralele i distribuite

Sisteme paralele i distribuite cu performante ridicate (folosind numar mare de procesoare puternice i reele de interconectare rapide)

Sisteme MPP: IBM BlueGene, Cray XT5-HE Clustere: HP, IBM, FujitsuSisteme GridCloud Computing


Primele calculatoare paralelePrimele calculatoare paralele Prototipuri de calculatoare paralele destinate cercetrii:

pentru studierea problemelor de baz teoretice ale calculului paralel; nu au avut succes comercial, dar au pregtit sisteme paralele i distribuite actuale. Exemplu: primul calculator paralel, Illiac IV:

finalizat n anul 1968 la Universitatea din Illinois, proiectat pentru 256 proc. specializate; avea att funcionare sincron (mod SIMD), ct i functionare asincron (mod MIMD); proiectat pentru performane de 1 GFLOPS, nu a atins decat 200 MFLOPS (cu 64 procesoare)

Primele generaii de calculatoare paralele (ultimele decenii ale secolului trecut): Cuprind att calculatoare SIMD cat i MIMD, produse de mari companii (IBM, Sun, HP

etc.) i disponibile comercial; exemplu: firma TMC Thinking Machines Corpoation Danny Hillis a produs:

Calculatoarele CM1 (Connection Machine 1, 1985), CM2- (1887) arhitectura SIMD compus din 64 k elemente de procesoare pe 1 bit, respectiv 4 biti, reea de interconectare hipercub; Performana atins: 5 GFLOPS, respectiv 20 GFLOPS.

Calculatorul CM5 (1993): calculator cu functionare dual, MIMD i SIMD compus din 16 384 noduri de procesare (procesoare SPARC, apoi SuperSPARC) trei reele de interconectare (reeaua de date, de control i de diagnoz) performana posibil n configuraia maxim: 2 TFLOPS


GeneraGeneraia actualia actual de sisteme paralele de sisteme paralele i distribuite i distribuite ((11))Lista primelor 5 supercalculatoare din top500/noiembrie 2012


GeneraGeneraia actualia actual de sisteme paralele de sisteme paralele i distribuite i distribuite ((22)) Performanele supercalculatoarelor (conform statisticilor top500):

#1 din 1993 (CM-5 cu 1024 procesoare SPARC-32) avea performana maxim de 60 GFLOPS

#1 din noiembrie 2012 (sistem Cray XK7 cu 560640 core procesoare Opteron) are performana maxim de 17.59 PFLOPS

Productorii de supercalculatoare sunt marii producatori de calculatoare comerciale: IBM (~38% n top500/nov.2012), HP, Cray, SGI, Dell, Fujitsu etc.

Numrul de procesoare n supercalculatoare (top500/iunie 2011): Granularitate mare: 1k-2k procesoare/sistem (0.4 %) Granularitate fina: > 128k procesoare/sistem (2 %) Granularitate medie: 4k-128k procesoare/sistem (97.6%), dintre care majoritatea sunt

cu 4k-8k (39%) sau 8k-16k (44.6%)

Sisteme de operare (lista top500/nov.2012): Linux (~ 94% din lista top500/nov. 2013), celelalte sisteme (Unix, Windows) cu procente mult mai mici

Reele de interconectare n sistemele paralele i distribuite actuale: n calculatoarele paralele: reele nestandardizate (custom, proprietary) n clustere de calculatoare: reele standardizate (Ethernet, Infiniband, Myrinet)


GeneraGeneraia actualia actual de sisteme paralele de sisteme paralele i distribuite i distribuite ((33)) Procesoarele folosite n MPP i clustere: CPU, GPU

CPU (n general multicore): Intel (Xeon ~ 44% in top500/nov.2013), AMD (Opteron), Motorola (Power), SPARC64 etc.

GPU - compuse din sute sau mii de uniti de prelucrare (cores) se folosesc ca i co-procesoare pentru accelerarea operaiilor paralele n combinaie cu CPUs

Cel mai mare productor de GPU: Nvidia, cu modelele GeForce, Quadro, Tesla GPU - model SIMT Single Instruction Multiple Thread), asem. sistem SIMD Fiecare core din GPU poate executa thread-uri multiple prin time-sharing, cu

control hardware, echivalent SO hardware Supercomputerul Titan Cray XK7

conine perechi de procesoare CPU (Opteron) i GPU (Nvidia Tesla)

Programarea GPU - biblioteci speciale CUDA (Compute Unified Device

Architecture) - pentru procesoare Nvidia

OpenCL (Open Computing Language) platform pentru programare paralel pe arhitecturi heterogene (CPU, GPU, DSP)


1.1.88 ReReele de interconectare ele de interconectare n calculatoarele paralelen calculatoarele paralele n multiprocesoare, multicalculatoare i MPP se folosesc reele statice i dinamice

nestandardizate (custom, proprietary ~ 17% n lista top500/nov. 2013) Reelele statice (directe): constau din conexiuni fixe (invariante n timp), punct-la-punct,

ntre noduri; folosite n general n calculatoare cu transfer de mesaje; Reelele dinamice (indirecte): constau din comutatoare (switch-uri) i conexiuni (link-

uri), care asigur ci de comunicatie n mod dinamic n funcie de pozitia comutatoarelor

Carecteristicile generale ale reelelor de interconectare: Lrgimea canalului (channel width, b): numrul de bii care pot fi transferai simultan

pe canal; este dat de numrul de fire fizice din care este compus un link. Viteza canalului (channel rate, v - msurat n numr de bii / secund): viteza cu care

se pot transmite datele pe un fir fizic al unui canal (link). Lrgimea de band a canalului (channel bandwidth, w): viteza cu care se pot

transmite datele pe un canal de comunicaie; w = v * b [ bii / secunda] Lrgimea biseciei (bisection width, B): numrul minim de link-uri care trebuie tiate

pentru a mpri reeaua n dou pri aproximativ egale. Lrgimea de band a biseciei (bisection bandwidth, W): viteza de comunicaie a

datelor ntre dou jumti ale reelei: W = B * w [ bii / secunda] Costul (C): se pot folosi mai multe criterii: numrul de comutatoare, numrul de module,

numrul de link-uri, volumul (spatiul ocupat de reea).


ReReele de interconectare dinamiceele de interconectare dinamice Reele dinamice: crossbar, magistral (bus), multietaj. Reeaua crossbar (reea de comutatoare): conecteaz p proc. cu n blocuri de memorie

Este neblocant: o conexiune intre 2 elemente nu interzice alt conexiune (intre alte perechi de procesoare-module de memorie)

are nr total de comut. (costul) C = (p * n); dac p = n, C = (n2), deci este nescalabil punct de vedere al costului

Este scalabil ca performane: B = n, W = B x w = n x w = O (n) (w constant) Este utilizat n multiprocesoare (de ex. Fujitsu VPP-500, Sun Enterprise-1000)

Element de comutare

Pp-1

P0

P1

M1M0 Mn-1


ReReeua magistraleua magistral (bus)(bus) O magistral (bus) este alctuit din fire, conectori i circuite de arbitrare, pentru

transferul datelor ntre procesoare, module de memorie i dispozitive periferice Realizeaz un singur transfer de date la un moment de timp, ntre surs i destinaie Este o reea blocanta: dac sunt mai multe cereri simultane de transferuri de date,

logica de arbitrare a magistralei secveneaz n timp transferurile Performanele sistemului se limiteaz chiar dac numrul de procesoare creste (este

nescalabil ca i performane) deoarece B = 1, W = B x w = O(1) (w constant) Costul crete proportional cu numrul de module conectate: C = O(n), deci reeaua

magistral este scalabil ca i cost

Reeaua magistral este folosit n multiprocesoare (de ex. IBM RS/6000)

Bloc de Memorie

Magistrala

Procesor Procesor Procesor

Bloc de Memorie

SubsistemIntrare/Ieire


Retele multietaj Retele multietaj Reelele multietaj au o comportare intermediar intre:

reeaua crossbar care este neblocanta i scalabil ca performante, dar nescalabil ca i cost (performant, dar scump);

reeaua magistral, care este scalabil ca i cost, dar este blocant i nescalabil ca performane (ieftin, dar performane se limiteaz atunci cnd crete nr de procesoare).

Crossbar Multietaj MagistralCost

Numr de procesoare

Magistral

Multietaj

Crossbar

Performae

Numr de procesoare

Reelele multietaj sunt, n general, parial blocante: admit mai multe interconexiuni simultane; exist i interconexiuni care nu pot fi realizate simultan; n acest caz, transferurile de

date sunt distribuite n dou sau mai multe treceri.

Reelele multietaj sunt realizate ca reele custom (de ex. reeaua Omega) sau standardizate (Ethernet, Infiniband, Myrinet)


Exemplu: Exemplu: rereeauaeaua dinamicdinamic multietaj Omegamultietaj Omega O reea Omega de dimensiune n x n este constituit din:

k = log n etaje, fiecare etaj compus din n/2 comutatoare 2 x 2 fiecare conexiune inter-etaje este o reea de permutare cu intercalare perfect

Din totalul de n! permutri, nn/2 se pot realiza ntr-o singur trecere; toate celelalte necesit maximum log n treceri; deci reeaua Omega este partial blocant

Exemplu: reea Omega de dimensiune 8 x 8 (n = 8, k = 3)Etaj 1Etaj 2 Etaj 0

76

5

4

3

2

10

76

5

4

3

2

10

7 (111)6 (110)

5 (101)

4 (100)

3 (011)

2 (010)

1 (001)0 (000)

(111) 7(110) 6

(101) 5

(100) 4

(011) 3

(010) 2

(001) 1(000) 0 c20

c21

c22

c23

Intrri Ieiri

c10

c11

c12

c13

c00

c01

c02

c037 6

5

4

3

2

1 0

7 6

5

4

3

2

1 0

7 6

5

4

3

2

1 0

7 6

5

4

3

2

1 0


ReReeleele statice de interconectarestatice de interconectare Reelele statice de interconectare utilizeaz conexiuni (link-uri) directe i invariante

n timp ntre noduri Fiecare nod dintr-o reea static este compus dintr-un procesor, un modul de

memorie local i un circuit de rutare (router) O reea static se reprezint printr-un graf G = (V, E), unde:

V = {vi | 0 | 0


ReReeaua complet conectateaua complet conectat i rei reeaua steaeaua stea Reeaua complet conectat (a):

Rutarea datelor: direct, intre fiecare 2 noduri Gradul nodurilor: g = n 1 Diametrul reelei: D = 1 Largimea bisectiei: B = (n/2)*(n/2) = n2/4 Cosul (nr.link-uri): C = n * (n-1)/2 Reteaua complet conectat este similara

reelei dinamice crossbar

Reeaua stea (b): Rutarea datelor: prin intermediul nodului

central, care produce congestie n comunicaiile din reeaua stea

Gradul nodurilor: g = 1, n 1 Diametrul reelei: D = 2 Lrgimea biseciei; B = ? Costul (nr. link-uri): C = n 1 Reeaua stea este similar reelei dinamice

de tip magistral

(a)

(b)


ReReelele lanelele lan i ineli inel Reeaua lan (linear array) (a)

Rutarea datelor: prin naintarea repetat ctre un nod vecin pn la destinaie Gradul nodurilor: g = 1, 2 Diametrul reelei: D = n 1 Lrgimea biseciei: B = 1 Costul (nr. link-uri): C = n 1

Reeaua inel (ring) (b) Rutarea datelor se face la stnga sau la dreapta; se poate alege drumul cel mai scurt

ntre noduri Gradul nodurilor: g = 2 Diametrul reelei: D ~= n/2 Largimea biseciei: B = 2 Costul (nr. link-uri): C = n

(b)(a)


ReReelele grilelele gril i tor (1)i tor (1) Se poate defini o reea gril (grid) sau tor (thorus) cu k dimensiuni Dac n fiecare dimensiune sunt m noduri, grila (torul) are n total n = mk noduri Pentru k = 2:

Gril bidimensional (a) extensia n dou dimensiuni a reelei lan Tor bidimensional (b) extensia n dou dimensiuni a reelei inel

Dac cele dou dimensiuni ale grilei sunt egale, atunci grila se numete gril ptrat, altfel se numete gril rectangular; la fel pentru tor

(a) (b)


ReReelele grilelele gril i tor (2)i tor (2) Reeaua gril bidimensional cu n noduri (m linii x m coloane, m = n):

Rutarea datelor: prin naintarea datelor dintr-un nod n nodul vecin, mai nti pe una din dimensiuni (de exemplu, pe linie), apoi pe cealalt dimensiune (pe coloan), pn se atinge nodul destinaie (rutare XY ordonata dup dimensiuni)

Gradul nodurilor: g = 2, 3, 4 Diametrul reelei: D = 2(m 1) Lrgimea biseciei: B = m = n Costul (nr. link-uri): C = 2 m (m 1) = 2(n n)

Reeaua tor bidimensional cu n noduri (m linii x m coloane, m = n) Rutarea datelor: prin naintarea datelor dintr-un nod n nodul vecin, mai nti pe una

din dimensiuni (de exemplu, pe linie), apoi pe cealalt dimensiune (pe coloan), pn se atinge nodul destinaie, folosindu-se i link-urile de nchidere ale inelelor

Gradul nodurilor: g = 4 Diametrul reelei : D = m/2 + m/2 = m = n Lrgimea biseciei : B = 2 m = 2 n Costul (nr. link-uri): C = 2 m x m = 2n

Reelele gril i tor au fost folosite n construcia multor calculatoare paralele (de exemplu: Intel Paragon, Cray T3D).

n


ReReeaua arbore (1)eaua arbore (1) ntr-o reea arbore k-ar (k-ar tree), fiecare nod este conectat la alte k noduri:

acestea se numesc noduri descendeni sau fii (children); nodurilor terminale (nodurile frunz leaves) nu au descendeni; nodul iniial (nodul rdcin root sau printe parent) nu are nici un ascendent

Pentru k = 2 arbore binar; un arbore binar complet cu d niveluri are: pe nivelul j (unde 0 j < d) 2j noduri; n total: n = 20 + 21 + + 2d-1 = 2d 1 noduri; 1 nod rdcin, 2d-1 noduri frunz, 2d-1 2 noduri intermediare numrul de niveluri: d = log (n + 1).

Nivel 313 14121110987

6543

21

0Nivel 0

Nivel 1

Nivel 2


ReReeaua arbore (2)eaua arbore (2) Caracteristicile reelei arbore binar complet:

Rutarea datelor: n reeaua arbore se execut prin naintarea acestora de la nodul surs n sus, ctre rdcin, pn ce este ntlnit un nod care este printe al subarborelul care conin nodul surs i nodul destinaie; de la acest nod, datele sunt rutate n jos, pn la nodul destinaie

Gradul nodurilor: G = 1, 2, 3 Diametrul reelei: D = 2(d 1) = 2(log (n + 1) 1) Lrgimea biseciei: B = 1 Costul (nr. link-uri): C = 2(2d-1 1) = 2d 2 = n 1 deoarece din 2d 1 noduri (nodul

rdcin i nodurile intermediare) pornesc cte 2 link-uri

Dezavantajul reelei arbore: aglomerare a mesajelor pe link-urile nodurilor din nivelurile mai apropiate de nodul rdcin (congestie)

nlturarea acestui dezavantaj: arbore gras (fat tree - Leiserson, 1985) ntr-un arbore gras, lrgimea canalului link-urilor crete de la frunze ctre rdcin Reeaua arbore gras a fost folosit n construcia multor calculatoare paralele (de

exemplu: calculatorul CM-5)


Reteaua hipercub (1)Reteaua hipercub (1) Un hipercub d-dimensional const din n = 2d noduri Fiecare nod are o etichet care se reprezint binar cu d bii Dou noduri sunt conectate ntre ele printr-un link dac i numai dac etichetelor

lor difer exact ntr-o singur pozitie a unui bit; deci nodurile a i b:a = ad-1 ad-2 ..ai aj..a1a0b = bd-1 bd-2 ..bi bj..b1b0sunt conectate ntre ele pe dimensiunea i (unde 0 i < d ) dac:ai bi i aj = bj , pentru orice j i i 0 j < d

Construcie recursiv a hipercubului: hipercubul (d + 1)-dimensional se construiete prin conectarea nodurilor corespondente (cu etichetele egale) a dou hipercuburi d-dimensionale

00

10

01

11

Hipercub0-D

0 1

Hipercub1-D

Hipercub2-D

010

001

101

000

100

011

111110

Hipercub3-D

Dim 0

Dim 1

Dim 2

Dim 0

Dim 1

Dim 0


ReReeaua hipercub (2)eaua hipercub (2)

Caracteristicile reelei hipercub: Rutarea datelor: de la nodul s la nodul t se face prin naintarea acestora, succesiv, pe

fiecare din cele d dimensiuni ale hipercubului care au valoarea 1 a bitului corespunztor din distana Hamming dintre cele dou noduri (H = s xor t)

Gradul nodurilor: G = d = log n Diametrul: D = d = log n Largimea bisectiei: din construcia recursiv rezult ca un hipercub d-dim. se poate

mpari n dou hipercuburi (d 1)- dim. prin elim. a 2d-1 muchii; rezulta: B = 2d-1 = n/2 Costul (nr. link-uri): C = (n log n)/2

Reeaua hipercub a fost folosit n multe calculatoare paralele: CM-1, 2, Intel iPSC, n-Cube, Cray (Cray Interconnect) etc.

0010

0101

0000

0100

0011

01110110

1010

1001

11011100

11111110

0001 1000

0111

1011

Constructia hipercubului 4-dimensional din 2 hipercuburi 3-dimensionale


1.9 1.9 ReReele de interconectare ele de interconectare n clustere de calculatoaren clustere de calculatoareReteaua Ethernet: standard IEEE 802.3 (1975, firma Xerox) pentru LAN Toate variantele folosesc acelai protocol CSMA/CD (Carrier Sense Multiple

Access with Collision Detection) permite interoperarea ntre diferite tehnologii Este #2 n lista top500/nov. 2012 (37.8 % din sisteme) Tipuri de reele dinamice realizate n tehnologia Ethernet:

Conexiuni prin cablu coaxial sau cabluri torsadate cu concentrator (hub) reea bus Conexiuni prin cabluri torsadate cu switch-uri reele dinamice crossbar (1 switch) sau

multietaj (mai multe switch-uri) Evoluie ca tehnologie i performante:

Ethernet 10 Mbit/sec mai multe variante i standarde: 10Base2 10 Mbit/sec pe cablu coaxial de cupru; 10Base-T: hub sau switch, patru perechi de fire torsadate de tipul Cat.3 sau Cat. 5.

Fast Ethernet - 100 Mbit/sec: perechi de fire torsadate, cu mai multe variante: 100Base-TX: 100Mbit/sec pe dou perechi de fire dintr-un cablu Cat.5. 100Base-FX: 100 Mbit/sec pe fibr optica.

Gigabit Ethernet 1 Gbit/sec: cabluri torsadate cu variantele: 1000BASE-T: 1 Gbit/s pe cablu de cupru Cat.5; 1000BASE-SX: 1 Gbit/s pe fibr optic;

10-Gigabit Ethernet 10 Gbit/sec cu mai multe variante: 10GBASE-SR: proiectata pentru transmisia pe fibr, pana la max. 300 m; 10GBASE-LX4: 240-300m pe fibra multi-node (multiplexare) pana la 10 km pe fibra single-mode 10GBASE-LR i 10GBASE-ER: suport 10km, respectiv 40 km pe fibre single mode.


ReReeaua Infiniband eaua Infiniband Standardul Infiniband (2002) pentru comunicaia pe cablu de cupru i fibr, cu

viteze pn la 96 Gigabit/sec Reeua Infiniband n listele top500/nov.2012:

2003 cu un procent de utilizare de 0.2% (1 sistem din primele 500) 2012 #1 ca numar de sisteme (44.8%)

Reteua Infiniband este o reea dinamica multietaj n care nodurile se conecteza intre ele prin intermediul unor module de comutatie (switched fabric): Un nod poate fi un nod de procesare (server host), sau un dispozitiv de I/O; Un modul de comutatie: compus dintr-unul sau mai multe comutatoare i routere (fig); Pe 1 fir se pot transmite date cu diferite viteze:

2.5 Gigabit/sec (single data rate SDR); 5 Gigabit/sec (double data rate DDR); 10 Gigabit/sec (quad data rate QDR).

La o codare 8B/10B se obtin viteze: 2 Gigabit/sec (SDR); 4 Gigabit/sec (DDR); 8 Gigabit/sec (QDR).

Se pot agrega 1, 4 sau 12 fire ntr-un link La agregare de 12 fire ntr-un link viteza maxim de 12 x 8 = 96 Gigabit/sec;

Nod

Switch

Switch Switch

Switch

Nod

Nod

Nod

Nod

Nod

Nod

Nod

Nod

Nod

Nod


ReReeaua Myrineteaua Myrinet Reteaua Myrinet (firma Myricom): standard ANSI n anul 1998 Dezvltare remarcabila intre anii 2002-2004, dup care a fost depait de reelele

Gigabit-Ethernet i Infiniband (datorit costurilor ridicate ale dispozitivelor sale) n anul 2004 reeaua Myrinet era pe primul loc n top500 (37.6% ca nr. de sisteme); n anul 2012 ea a ajuns la un procent de numai 0.6% ca numar de sisteme din top500

Reteaua Myrinet este o reea dinamic multi-etaj de tip Clos, cu mai multe niveluri de comutatoare (switch-uri), porturi de conexiune pentru noduri (host-uri) i conexiuni intre niveluri

Variante: Myrinet Myri-10G (10Gigabit/sec) i Myrinet-2000 (2Gigabit/sec)

Capitolul 1- Arhitecturi pentru calculul paralel1.1 IntroducereCreterea performanelor calculatoarelor secvenialeCreterea vitezei de operare a procesoarelor Introducerea paralelismului n interiorul procesoarelorTehnica pipeline (1)Tehnica pipeline (2)Procesarea vectorial pipelineProcesoare VLIWProcesoare superscalareProcesoare multi-coreProcesoare SCMP (Single Chip Message Passing)Acceleratoare hardware Procesoare GPU (Graphical Processing Unit)Evoluia performanelor procesoarelor Calculatoare paralele (1)Calculatoare paralele (2)1.2 Clasificarea calculatoarelor dup mecanismul de controlCalculatoare SISDCalculatoare MISDCalculatoare SIMDCalculatoare MIMDComparaie SIMD - MIMD1.3 Clasificarea calculatoarelor paraleledup organizarea memorieiModele cu acces neuniform la memorie (NUMA)Arhitectura cu transfer de mesaje 1.4 Clasificarea calculatoarelor MIMD1.5 Granularitatea calculatoarelor paralele1.6 Sisteme paralele i distribuiteCalcul paralel i distribuitClustere de calculatoareAvantajele clusterelor de calculatoareArhitectura clusterelor de calculatoareComponentele hardware ale clusterelorComponentele software ale clusterelorImagine de sistem unic SSI (Single Sistem Image)Categorii de middleware n clustereSisteme Grid Sisteme Cloud Computing 1.7 Scurt istoric al dezvoltarii sistemelor paralele i distribuitePrimele calculatoare paraleleGeneraia actual de sisteme paralele i distribuite (1)Generaia actual de sisteme paralele i distribuite (2)Generaia actual de sisteme paralele i distribuite (3)1.8 Reele de interconectare n calculatoarele paraleleReele de interconectare dinamiceReeua magistral (bus)Retele multietaj Exemplu: reeaua dinamic multietaj OmegaReele statice de interconectareReeaua complet conectat i reeaua steaReelele lan i inelReelele gril i tor (1)Reelele gril i tor (2)Reeaua arbore (1)Reeaua arbore (2)Reteaua hipercub (1)Reeaua hipercub (2)1.9 Reele de interconectare n clustere de calculatoareReeaua Infiniband Reeaua Myrinet

CP_Cap1_Arhitecturi_pentru_calculul_paralel.pdf

Documents

Transcript of CP_Cap1_Arhitecturi_pentru_calculul_paralel.pdf