Calcul Paralel si

Distribuit
Introducere

Cosmina Ivan
[Link]@[Link]
[Link]@[Link]
Departamentul de Calculatoare
UNIVERSITATEA TEHNICA CLUJ NAPOCA
 Conţinut (1)
Concepte introductive

– Introducere în procesarea paralelă şi distribuită . Taxonomii în calculul

paralel şi distribuit. Modele şi paradigme ale procesării paralele şi
distribuite

II. Calcul paralel

– Scalabilitate şi performanţă in sisteme cu procesoare multiple. Legile

accelerării performanţei. Scalabilitate algoritmică şi arhitecturală.
– Tehnici şi paradigme pentru proiectarea algoritmilor paraleli.
• tehnici de paralelizare, dependenta datelor, descompunerea datelor, tehnici de
mapare statica/dinamica
– Algoritmi paraleli fundamentali (sortare, cautare, pe matrici, pe grafuri)

– Modele de calcul paralel si comunicatie. Sisteme de [Link]

statice si dinamice. Comunicaţiile şi rutarea in sisteme multiprocesor .
Topologii, canale şi reţele virtuale , tehnici de transmisie pentru
operaţiuni de comunicatie de grup.
2
 Conţinut (2)
III. Calcul distribuit

– Modele fundamentale în calculul distribuit : interactiune,

comunicare, procesare, cadere .Principii .Caracteristici .
– Timp și Sincronizare :ceasuri fizice si logice
– Excludere mutuala distribuita , snapshot distribuit
– Ordonare cauzala a evenimentelor
– Stări gobale
– Alegere leader (proces)
– Alti algoritmi distribuiti

Auxiliar
– Consistenţă şi replicare: modele si protocoale .
– Toleranta la erori in sisteme distribuite.

Sisteme cu memorie partajata distribuita, Structuri P2P

Clustere şi griduri computaţionale

3
 Organizatoric
 Metode de evaluare

4 teme de laborator – notate ca activitate practica individuala – trimise pe e-mail, nu se

accepta decat deadline-ul specificat.
Proiect individual - prezentat public
Referat individual – prezentat public

 Teme 20% (6 sapt)

 Proiect 30% (4 sapt )
 Referat 20% (2 sapt)
 Examen 30%

 toate modalitatile de evaluare sunt obligatorii

 ponderea specificata, notare distincta, 50%

4
 5 generaţii de arhitecturi
• prima generaţie (1956) - CPU, VF, PC, CPU implicată în toate operaţiile de acces la
memorie şi de I/O, masini cu acumulator, limbaj de asamblare (Eniac, IBM701)
• a doua generaţie (1967) - registre index, aritmetica virgula flotantă,multiplexare
memorie,procesoare de I/O, limbaje de nivel inalt, procesare batch, compilatoare,
biblioteci (IBM 7030,CDC1604)
• a treia generaţie (1978)- control microprogamat, pipelining şi memorii cache , SO
time- sharing ce folosesc memoria virtuală (IBM 360, CDC 6600 PDP8).
• a patra generaţie (1989) - calculatoare paralele si sisteme distribuite, în diverse
arhitecturi cu memorie partajată sau distribuită, VLSI, SO pentru multiprocesare,
limbaje, biblioteci şi compilatoare speciale pentru paralelism, tools-uri software
(VAX9000, CrayX-MP, IBM 4090)
• a cincea generaţie (Tflops - Pflops realizează procesare masiv-paralelă,arhitecturi
scalabile şi heterogene de calculatoare cu memorie partajată sau sisteme cu transfer
de mesaje , Java, microkernel/ multithreading, S paralele si distribuite (Fujitsu,
CrayMachine, Intel-Paragon, Dash, KSR, SGI Origin)
(K Hwang, Scalable parallel computing, 1998)

5
 Paralel vs distribuit
Sisteme de calcul cu mai multe elemente de procesare

• Procesare paralela – executia rapida (t<<<) a unor probleme de calcul pe

masini cu mai multe procesoare ce lucreaza in maniera bine coordonata

– Sisteme cuplate strans (distanţa între procesoare este redusa,

multiprocesoare)

• Procesare distribuita - rezolvarea unor probleme de calcul prin partajarea

resurselor in sistem, oferind fiabilitate, toleranta la erori, procesoarele unui
astfel de sistem sunt distribuite fizic

– Sisteme cuplate larg (reţele de calculatoare, multicalculatoare)

Procesare concurenta
la nivel de instructiune , pipeline in procesoare
vectoriale, multiprocesare bazata pe M partajata sau
distribuita, sisteme distribuite/Internet
Aplicatii ale calculului paralel şi distribuit
Simularea informatiei
Dinamica fluidelor, Dinamica structurala – industrie automobilistica, civil
Simulari electromagnetice - radar
Planificare sisteme de control aviatice
Modelare mediu ,Simulari integrate complexe ( climat, date seismice)
Modelare biologie/sanatate, Chimie – stare solida/tranzitii
Dinamica moleculara, astrodinmica
Modelare economica/financiara
Simulari in retea, griduri, Simulari ale fluxurilor particulelor nucleare
Prelucrari grafice, procesare de imagini
Containere informationale de stocare
Analiza statistica : sanatate/asigurari
Data mining
Acces la informatie
Procesare tranzactii online/banci asigurari
Sisteme colaborative (WWW, proprietar)
Planificare piete bursiere
Integrare Informatie
Sisteme suport de decizie
Sisteme de control in timp real
E-........ Bancar, comert,.....
Educatie – e-learning , sisteme de asistare

7
 Complexitate....
Alocarea resurselor
dimensionarea colectiei de elemente de procesare,
elementelor de memorie
parametrii de performanta in accesul la resurse

Accesul la date, comunicatia si sincronizarea

cum comunica si coopereaza elementele de procesare?
cum sunt datele transmise intre procesoare?
setul de abstractiuni si primitive necesare cooperarii intre
elementele de procesare?

Performanta si scalabilitatea
translatarea cerintelor in termeni de performanta
arhitectura ofera scalabilitate?

8
 Evoluţie
Architectura de sistem
arhitecturală
•transfera oferta tehnologica in performanta si capabilitati de
procesare
•rezolva diferentele generate de heterogeneitate si cerintele de
localitate a datelor, modificabile ca urmare a scalarii sistemului
sau evolutiei tehnologice

• Evolutia arhitecturilor

 initial , programarea asociata unei anumite arhitecturi fizice

limitari: lipsa portabilitatii, scalabilitatii,
problema “ grefata” pe o anumita arhitectura

 ulterior - programe proiectate specific anumitor categorii de

algoritmi/probleme (stiluri) , compilatorul a devenit responsabil cu
maparea/translatarea specifica arhitecturii

 curent – convergenta arhitecturala, diverse instrumente

standardizate pentru programarea paralela si distribuita
9
 Evolutie arhitecturi
• Era calculatoarelor seriale (IBM Mainframe)
• Calculatoare vectoriale (Cray)
• Paralelism SIMD ( o instructiune mai multe fluxuri de date, Thinking Machines ,Maspar)
• Paralelism MIMD ( mai multe instructiuni, mai multe fluxuri, Transputere / alte tehnologii on
chip)
• statii de lucru (Workstations-Sun)
• Sisteme de procesare masiv paralela (topologii diverse hipercub, tor, mesh)
• Calculatoare Personale (IBM, Intel, Microsoft, Apple)
• Sisteme MPP comerciale
• Retele de statii de lucru (NOW)
• Servere Enterprise implementeaza tehnologii specifice partajarii memoriei
• Calculul paralel larg raspandit
• Paralelism de date (SPMD MPI/ HPF) modele paralele acceptate
• WAN in universitati (ATM)
• Masini cu M distribuita – retele dinamice cu comutare inlocuiesc retelele statice
• Calcul bazat pe modelul Client/Server

• Calculul distribuit inlocuieste calculul paralel ca domeniu de interes major

• Obiecte distribuite, modele noi Agenti/Servlet
• PC/ retele rapide, Linux ca sistem de operare - clustere Beowulf
• Internet computing
• Internet de banda larga ( modemuri de cablu,ASDL, sateliti, comunicatii wireless, etc.)
• Calcul mobil, senzitiv la context
• Griduri/metacomputing: calcul distribuit si de inalta performanta pentru aplicatii complexe , pe
scara larga
10
 Calcul paralel
Procesare paralela - o forma de procesare a informatiei ce
utilizeaza evenimente concurente si necesita suport de limbaj
(biblioteci) si/sau hardware.

Algoritm paralel = algoritm care permite efectuarea simultana a

mai multor operatii/taskuri.
Descompunerea unei probleme in subprobleme care se
executa in paralel pe mai multe procesoare

Calculator paralel - o colectie de elemente de procesare utilizate

pentru a rezolva mult mai rapid probleme de procesare de
dimensiuni mari (Almasi& Gottlieb, 1989)

Supercalculatoare paralele, statii de lucru multiprocesor,

clustere bazate pe retele locale de calculatoare.

11
 Calcul paralel
Arhitecturile paralele :
oferă o soluţie de crestere a performanţei
sistemelor de calcul (clasic, bazat doar pe evolutia
la nivelul procesoarelor)

procesarea paralela este aplicabila la toate

nivelurile in proiectarea de sistem, utila in
procesarea unor volume mari de date

permit stabilirea unor relatii logice intre diverse

forme de manifestare a paralelismului : paralelismul
la nivel de instructiune/ thread , la nivel de task/
element de procesare

12
 Motivatie
• “Mai repede, mai mult” Problemele de rezolvat necesita
cresterea puterii de calcul

Probleme de rezolvat Putere de calcul,

Aplicatii Tehnologie

Cresterea puterii de calcul permite

punerea de noi probleme

• Nu conteaza cat de rapid este calculatorul cel mai

performant de la un moment dat, cineva va dori sa utilizeze
unul mai rapid
• Exista intotdeauna probleme importante care cer mai mult
decat puterea de calcul disponibila la un moment dat
• Cu cat puterea de calcul creste mai mult ,cu atat mai multe
probleme nerezolvate apar la orizont
13
 Programare paralela
• Algoritm secvential: specifica executia secventiala a unui set
de instructiuni
• Proces: executia unui program secvential
Algoritm paralel: specifica mai multi algoritmi secventiali care
pot fi executati simultan ,ca procese paralele

• Paralelism logic: 1 procesor – N procese.

– La un moment dat se executa fizic o actiune
corespunzatoare unui singur proces.
– Procesele se desfasoara concurent: se lanseaza
instructiunile unui proces inainte de a se fi terminat
executia tuturor instructiunilor corespunzatoare
celorlalte procese

• Paralelism fizic: mapare procesor – proces.

14
 Clasificari arhitecturale (3)
Influenta aplicatiei asupra arhitecturii
A – nivelul de paralelism permis de aplicatie
L – nivelul de paralelism permis de limbajul de programare
C – nivelul de paralelism permis de compilator
H – nivelul de paralelism permis de structura hardware

• Minimizarea timpului de rulare a aplicatiei necesita :

A≤L≤C≤H

15
 Caracterizarea aplicatiilor
• Compuse din taskuri.
• In aplicatii cu grad nenul de paralelism unele taskuri ruleaza
in paralel.
• Caracteristici
– granularitate
– grad de paralelism
– nivelul de paralelism
– interdependenta datelor

16
 Granularitatea unui task
Granularitatea unui task
• Dependenta de:

R – durata de executie (runtime)

C – durata comunicarii

• Granularitate grosiera: R>>C

• Granularitate fina: R<<C
• Granularitate medie: R si C – comparabile

17
 Gradul de paralelism
• Gradul de paralelism

• Masura numarului de fire (threads) executate simultan.

• Nivelul de paralelism:
– la nivelul procedurii
– la nivelul taskului
– la nivelul instructiunii
– la nivelul operatiei
– la nivelul microoperatiei (microcode)

18
 Modele de procese
Aplicatie seriala
Modul 1

Modul 2
Modul 1

Modul 3

Single task
Multiple tasks
 Modele de procese (2)

Modul 1

Modul 2 Modul 3 Modul P - 1

Aplicatie serie - paralel Modul P

20
 Modele de procese (3)

Modul 1

Modul 2 Modul 3 Modul P - 1

Aplicatie serie – paralel Modul P

cu dependenta datelor

21
 Taxonomii
• Obiectivele clasificarilor ( taxonomiilor) :

– Sa ofere posibile configuratii ce ar putea fi omise de catre

arhitectii de sistem. Sa permita o examinare formala a
posibilelor variante de arhitectura.

– Sa permita construirea de modele utile de evaluare a

performantei, evidentiind potentialul unei anumite
arhitecturi pentru imbunatatirea performantelor.

– Sa ofere raspunsuri la intrebari privind tipul paralelismului,

arhitectura cu cele mai bune perspective de viitor,
realizarile la zi privind o anume arhitectura.
22
 Taxonomii
• Control – driven:
– Activitatea de prelucrare este dictata de secventa de
instructiuni. Datele sunt preluate de procesor cand este
nevoie de ele.
• Data – driven:
– Activitatea de prelucrare dictata de disponibilitatea
datelor necesare efectuarii unei instructiuni.
• Demand – driven:
– Executia unei instructiuni este activata atunci cand
rezultatul executiei ei este cerut de o instructiune deja
activata pentru executie.

23
 Structura multiprocesor

Procesoare P1 P2 P3 Pn

Retea
interconectare

Memorie M1 M2 Mm

24
 Structura multicomputer

Retea
interconectare

P1 Pn P2

Calculatoare

M1 Mn M2

25
Structura multi-multiprocesor

Retea interconectare

26
 Taxonomia Flynn
 SISD – mainframe-uri, statii de lucru, PC (Single Instruction stream -Single
Data stream), masini conventionale secventiale,ce utilizeaza diverse
tehnici pentru cresterea performantelor uniprocesorului.

 SIMD – (Single Instruction stream over Multiple Data streams) ,

 memorie partajata - calculatoare vectoriale -tablouri de elemente de
procesare sincronizate (seria Cray CM-2).

 MISD – (Multiple Instruction streams & Single Data stream),

 Memoria partajata tablouri sistolice pentru executie pipeline,
(Sequent, KSR, Terra, SGI, SUN)

 MIMD - (Multiple Instruction streams Multiple data)Memoria distribuita

si/sau partajata sisteme complexe tip cluster (Cray T3D, CM-5, Intel,
Transputere IBM SP2, DEC, Sun, HP)

27
 Avantajele MIMD
• Viteza mare de prelucrare, daca prelucrarea poate fi
descompusa in fire paralele, TOATE procesoarele
prelucrand simultan

• Intrucat procesoarele si blocurile de memorie sunt

resurse de tip general, defectarea unei unitati se poate
compensa prin alocarea sarcinii de prelucrare altei
unitati (grad ridicat de toleranta la erori)

• Se poate utiliza reconfigurarea dinamica pentru a face

fata gradelor variabile de incarcare a procesoarelor

28
 Cerinte - MIMD (1)
1. Planificarea procesoarelor: alocarea eficienta a taskurilor la
procesoarele din sistem intr-o maniera dinamica, pe durata
evolutiei prelucrarii

2. Sincronizarea procesoarelor: prevenirea situatiilor de tentativa

simultana de schimb de date intre doua procesoare si
respectarea restrictiilor de precedenta in manipularea datelor.

3. Proiectarea retelei de interconectare: retelele de

interconectare procesor – memorie si procesor – procesor
sunt, probabil, cele mai costisitoare elemente ale sistemului.
De aici dedicarea de I/O procesoarelor si NU utilizarea unei
retele de interconectare procesor – I/O
29
 Cerinte - MIMD (3)
4. Overhead: in mod ideal, un sistem cu n procesoare ar trebui
sa ofere o viteza de prelucrare (throughput) de n ori mai
mare decat un sistem cu un unic procesor.

In realitate, consumul suplimentar de resurse (overhead) pentru

coordonarea activitatii procesoarelor si solutionarea
competitiei pentru resurse comune (memorie, reteaua de
interconectare) nu permite atingerea acestui deziderat.

5. Partitionarea: identificarea paralelismului in algoritmii de

prelucrare si invocarea prelucrarii concurente nu este o
problema triviala

30
Taxonomia Hwang

 Calculatoare vectoriale (PV) - sisteme proprietar, initial

dezvoltate pentru stiinte computationale

 Multiprocesoare simetrice (SMP) nescalabile, suport simplu ,

ieftin pentru procesare paralela

 Sisteme masiv paralele (MPP)- sisteme proprietar, performante

deosebite in procesarea paralela insa la costuri ridicate

 Sisteme distribuite (SD) - complexe , o colectie de resurse de

calcul autonome ce coopereaza

 Clustere/Griduri – ofera suport pentru calcul de inalta

performanta , definesc sisteme cuplate larg, de mare
disponibilitate (sisteme critice, sisteme tolerante la erori)

31
 Modele (1)
PVP - procesoare vectoriale
Arhitectură tip “shared Memory”, module de memorie partajate ce
oferă acces rapid la date, procesoare puternice proprietar , nu integreaza
cacheuri , doar registre vectoriale si buffere de instructiuni
Reteaua de interconectare proprietar (crossbar ) (Cray C90, T90)
 SMP - multiprocesoare simetrice
sistem bazat pe procesoare echivalente conectate folosind memoria
partajată şi protocoale pentru coerenta datelor
arhitectură simetrică (tip Shared-everything ) , procesoarele partajează
resursele globale disponibile, RI mag./crossbar
rulează o singura copie a SO
Limitari – reteaua de interconectare (magistrala) greu de scalat odata
proiectata(SGI, DEC Alpha, IBMR50)

32
 Modele (2)
MPP – procesoare masiv paralele
sistem de procesare paralela de dimensiuni mari, procesoare clasice
şi memoria distribuită nodurilor de procesare
arhitectură shared-nothing
scalabil ( sute de noduri de procesare)
maşină asincronă MIMD, cuplat strans , folosind retele de
interconectare de înaltă performanţă (B>> , L<<)
programul conţine procese multiple, fiecare cu spaţiul privat de
adrese, interacţiune prin transfer de mesaje
procese sincronizate (operaţii de transfer de mesaje)
 in anumite sisteme e posibil un singur kernel
pentru aplicaţii complexe ce posedă grad ridicat de paralelism(Intel
Paragon)

33
 Modele (3)
DSM (Distributed Shared Memory)
memoriile distribuite nodurilor de procesare devin memorie globală
partajată, creand un spaţiu unic de adrese
 arhitectura ce integreaza structuri d ecoerenta a datelor tip
directoare de cacheuri
necesită suport HW/SW - pentru a implementa conceptul SSI (Single
system image) (Stanford Dash - structuri de directoare,CrayT3D- suport
HW ,Treadmarks- extensii SW )
Sistem distribuit
 calculatoare independente , conectate bazat pe retele convenţionale
 maşinile individuale pot fi combinaţii MPP,SMP, clustere, sisteme
individuale
 posedă imagini multiple de sistem (fiecare nod rulează propriul SO)

34
 Modele (4)
COW –Cluster of workstation (Digital Trucluster IBM SP2, Berkeley NOW)
fiecare nod e o staţie completă (disc, mai puţin periferie), poate reprezenta
SMP sau PC
noduri conectate folosind reţea convenţională (Ethernet, FDDI, FC, switch
ATM) sau retele proprietar
interfaţa de reţea cuplată larg magistralei I-O
fiecare nod rulează propriul sistem de operare- microkernel
 sistemul de operare integreaza Sw special pentru implementarea imaginii
unice de sistem (SSI)
echilibrarea încărcării, suport pentru paralelism şi comunicaţie
 nodurile lucreaza colectiv asemeni unei resurse unice integrate
 masina ofera disponibilitate ridicata si performanta crescuta
 avantaje de cost in implementarea de masini scalabile
35
 Maşini hibride tip cluster
 Cluster de statii SMPs (CLUMP ) (ASCI Red (Intel), ...

 sistemele SMP, cele mai rapide solutii de procesare paralela pot fi

integrate intr-o structura tip cluster

 Memoria partajata in structura SMP, dar transfer de mesaje intre noduri

masina privita unitar, intotdeauna se foloseste transfer de mesaje (si la
nivelul nodului SMP
 expune doua niveluri / memoria partajata si transferul de mesaje (creste
performantele dar si complexitatea programarii).

36
 Modele de acces la memorie
Modelul UMA(UniformMemory Access)
•memoria fizică e uniform partajată de
toate procesoarele

•procesoarele au acelaşi timp de acces la

memorie

Modelul NUMA( NonUniform Memory Access)

P1 PE1 P2 PE2
•memoria partajată e distribuită fizic ...
Pn PEn

procesoarelor , este creat un spaţiu de M1 M2 Mn

adresare comun

•tipuri de accese la memorie : acces la RETEA DE INTERCONECTARE

memoria locală, acces la memoria locală a

altui procesor, acces la memoria globală
partajată.

37
 Modele de acces la memorie
Modelul CC-NUMA (Cache Coherent
NUMA) - toate datele partajate sunt
echidistante accesului procesoarelor

Modelul COMA ( Cache Only Memory

Acces)
P1 P2 Pn
M principale devin cache, coerenţa prin PE1 PE2 ... PEn
structuri de “directoare cache” C1 C2 Cn
distribuite

Retea de interconectare

38
Niveluri si tipuri de paralelism

39
40
41
 Calcul distribuit
Def1. (Tannenbaum) - o colectie de computere independente ce apare ca
un sistem unic, coerent utilizatorilor sai – greu de realizat

Def2. (Coulloris) - o colectie de resurse de calcul heterogene

interconectate folosind o retea / infrastructura ce ofera suport pentru
dezvoltarea de aplicatii si servicii . Resursele distribuite sunt autonome ,
comunica si coopereaza prin schimb de mesaje pentru a rezolva o
sarcina comuna sau un serviciu.

Def3. (Lamport) – acel sistem in care nu se poate atinge un anumit scop

deoarece o masina fizica despre care nici nu s-a auzit a cazut.

 slab corelat fizic, strans corelat logic

 Bazat pe schimb de mesaje – transfer de mesaje necesar cooperarii
pentru o stare comuna
 Presupune integrarea unui suport software (de nivel SO/Middleware)
ce permite independenta masinilor si utilizatorilor sistemului
distribuit , cat si interactiunea lor.

42
 Sistem distribuit cu elemente mobile

Internet

Host intranet WAP

Wireless LAN gateway Home intranet

Mobile
phone
Printer Laptop
Camera Host site

(G. Coulouris, Distributed systems)

Exemple de SD : Web, Intranet,

infrastructuri mobile, etc.
43
 SD caracteristici
SD acceptiune HW
un calculator virtual, existenta nodurilor autonome e transparenta,
implementarea transparentei prin algoritmi de control distribuit.

SD acceptiune SW
aplicatii bazate pe cooperare intre procesoare/ hosturi

Caracteristici
 resurse fizice si logice multiple
 distributia resurselor e transparenta
 independenta si cooperare intre componente
Host - componente operationale HW şi SW
Middleware – nivel intermediar , rezolva
heterogeneitatea si distribuirea entitatilor in sistem
Resurse –abstractiuni HW/SW, resurse distribuite : fizice,
date , control
44
 Argumente
• Economice
– Partajarea resurselor- BD/HW costisitoare, control remote laboratoare
speciale, etc.

– Relativ simplu de expandat/scalat

– Viteza /puterea de calcul oferita este posibil mai mare chiar decat a unui
mainframe.

– Rata cost/performanta ( retele Gb procesoare de viteza)

• Informatie/utilizatori inerent distribuiti

• Expandabilitate/flexibilitate in reconfigurarea de sistem pentru a indeplini

cerintele utilizatorilor

• Disponibilitate si siguranta functionarii - daca o masina cade, sistemul rezista.

• Scalabilitate buna determinata de conectivitatea slaba

45
Ipoteze false =>complexitate
 In dezvoltarea de sistem => set de false ipoteze

Reteaua este sigura pentru transmisie

Reteaua este securizata
Reteaua este omogena
Topologia retelei nu se modifica
Latenta de transmisie este nula
Latimea de banda este infinita
“Costul de transport “( performanta) este zero
Un singur domeniu administrativ

46
 Avantaje /dezavantaje
Avantaje/popularitate
• Disponibilitatea sistemelor de calcul si retelelor de
comunicatie
• Partajarea resurselor
• Scalabilitate
• Toleranta la erori

Dezavantaje:
• Puncte de cadere multiple: caderea nodurilor/ sau legaturilor
de comunicatie.
• Aspecte de securitate : mai multe oportunitati pentru atacuri
neautorizate.
47
 Proprietati
 Descentralizare /distributie

 Non-centralizarea datelor /serviciilor (server) , controlului (algoritmi distribuiti)

 nici un host nu detine starea completa a sistemului
 nu exista ceas global in sistem
 integreaza mecanisme tolerante la caderea nodurilor/ legaturilor de
comunicatie
 nodurile pot lua decizii functie de info locala

 Paradigme (clase de sisteme distribuite)

DSM,
agenti ( cod mobil),
coordonare distribuita,
documente partajate,
sisteme publish&subscribe,
obiecte distribuite,servicii web

48
 Sistem deschis
Sistem deschis - poate interactiona cu servicii ( interfete) oferite de alte sisteme
deschise, indiferent de infrastructura, independent de heterogeneitatea
HW/SW sau de limbaj.

Caracteristici:
 Sistemul este conform unor interfete predefinite, publice
 Este asigurata conformitatea componentelor sale cu standarde publice
(implementat folosind componente testate pentru conformanta)
 suporta portabilitatea aplicatiei, ofera interoperabilitate
 poate fi usor extins/ modificat/reimplementat
 Concept corelat cu cele de interoperabilitate/portabilitate

Standardizare ( ISO/ ITU – RM-ODP )

 permite interoperabilitate ( integrare componente Sw/HW)
 ofera suport pentru portabilitate
 standarde de facto ( OMG, TINA) , de jure, etc.

49
 Heterogeneitate/flexibilitate
Heterogeneitate
 generata de varietatea tehnologiilor utilizate pentru implementarea
platformelor, managementului datelor si aplicatiilor
 heterogeneitatea platformelor (retelelor, SO, hw) , a limbajelor a
componentelor implementate de catre dezvoltatori diferiti
 rezolvata de un nivel intermediar – middleware, masini virtuale

Flexibilitate
solutie clasica - kernel monolitic - nonflexibila , sistem de fisiere/ sistem
de directoare, management complex al proceselor,
noi solutii - microkernel - servere de nivel utilizator pentru servicii sistem,
(mecanism IPC, MM, management/planificare de procese redusa)

= extensibilitate simpla ( modificare componente

/servicii),interoperabilitate, interfete publice, standardizate

Performanta - integrare suport pentru paralelism, abilitatea migrarii

entitatilor, securitate, etc

50
 Toleranta la erori/ partajare
resurse
Toleranta la erori- sistemul va opera chiar in prezenta erorilor =>determina
modalitatea de proiectare a sistemului distribuit
 solutii de management – identifica si inlocuiesc componentele ce
genereaza erori. Sisteme HW – redundanta fizica, Sisteme SW –
replicari de servere, de date, tranzactii specializate

Partajarea resurselor - un sistem distribuit ofera suport pentru cooperare -

aplicatii de grup ce necesita partajarea resurselor logice/fizice

 aspecte complementare/complexe de securitate

 componente secializate pentru managementul resurselor – autorizare
acces, autentificare
Securitate
 lipsa unui punct unic de control
 Mesaje furate, modificate, serviciile interzise =>solutii criptografice
51
 Transparente
Transparenta – sistemul se prezinta unitar fata de utilizatori si aplicatii
(nivel inalt se ascunde distributia fata de utilizatori, nivel scazut
ascunderea distributiei fata de programe)
Transparenta Descriere
Ascunde diferente in reprezentarea datelor si modul
Accesului
in care e accesata o resursa similar local si remote
Locatiei Ascunde locatia resursei
Ascunde faptul ca o resursa se poate muta la o alta
Migrarii
locatie
Ascunde faptul ca o resursa poate/se poate muta in
Relocarii/mobilitatii timp ce este utilizata fara a afecta utilizatorii
/programele
Pot fi utilizate mai multe instante ale resursei fara a
Replicarii
sti care replica este utilizata
Ascunde partajarea concurenta a resursei de mai
Concurentei
multi utilizatori, procesele opereaza fara interferente
Ascunde caderea si refacerea accesului la o resursa,
Caderii/defectarii
astfel taskurile pot fi finalizate
Ascunde locatia unei resurse software (in M sau pe
Persistentei
disc)
Middleware (1)
Motivare – aplicatii in retea greu de integrat
 sisteme de operare in retea diferite
 sisteme informationale federalizate
 combinare de BD diferite, sisteme de
procesare a tranzactiilor)
 servicii Internet pe scara larga
 extensibilitatea unor servicii /complexe
– mobilitate, teleworking, aplicatii
colaborative

Definitie – set de API uri independente de

sistem pentru integrare programare
distribuita

Caracteristici
 independenta de L, SO, retea
 utilizeaza functionalitatea de baza oferita de
sistemele de operare existente ( RPC, NFS ,
DCOM)
 protocoalele / interfetele utilizate la fiecare
nivel middleware sunt identice
 Middleware -caracteristici
 Servicii middleware

 Servicii de comunicatie - apeluri de proceduri remote, invocari de obiecte la distanta,

sisteme de cozi de mesaje, sisteme de streamuri, servicii de notificare evenimente

 Servicii pentru sisteme informationale - servicii de numire entitati, servicii de

directoare (masini de cautare) servicii de localizare entitati mobile, facilitati de stocare
distribuita, managementul datelor

 Servicii de control - refera controlul modului de acces la date – persistenta, procesarea

tranzactiilor, migrarea proceselor, planificarea taskurilor

 Servicii de securitate - utile in procesare si comunicatie sigura - de

autentificare/autorizare, de criptare, de audit.

 Tipuri de middleware
 orientate tranzactii(TP)- procesare tranzactii distribuite in BD multiple
 orientate mesaj (MOM)- trafic sigur de mesaje intre resursele SD
 orientate apel remote de proceduri (RMI)
 orientate obiectual – invocari remote de obiecte(DOM)

54
 Caracteristici/ cerinte pentru sisteme distribuite
 heterogeneitate ( HW, SW)/ numar de procesoare ( noduri in sistem)
 concurenta accesului la diverse resurse (partajarea resurselor, retele de
interconectare stari partajate )
 cooperare/comunicare, gradul de sincronizare
 inexistenta unui mecanism de coordonare globala
 Implementarea de mecanisme de tolerare a diverselor tipuri de caderi
in sistem

 Dificultati de proiectare/ implementare/ management :

 scalabilitate, pierderea controlului in anumite parti in sistem,
transfer de mesaje nesigur, caderi independente in sistem

55
 Scalabilitatea
Scalabilitatea – defineste modul in care sistemul suporta cresterea numarului de utilizatori,
hosturi, domenii administrative, volumului datelor, tranzactiilor efectuate, distantei intre
noduri etc. (multe sisteme suporta doar scalabilitatea dimensiunii)

 Tehnici de scalare
• Distributie - partitionare date/procesare pe mai multe sisteme ( ex. Apeti Java,
DNS, WWW)
• Replicare – copii ale datelor pe diverse masini (servere de fisiere, BD replicate,
site-uri replicate)
• Cachare - procese client pot accesa copii locale ale datelor: cache web, (browser,
proxy) , cache fisiere(la client/server)
• Utilizarea de comunicatii cu predilectie asincrone

Probleme in asigurarea scalabilitatii de sistem

Complexitate in aplicarea tehnicilor de scalare datorate inconsistentei datelor (copii

cachate sau replicate ) si sincronizarilor globale greoaie

Existenta unor servicii centralizate – server unic pentru utilizatori, date centralizate,
algoritmi centralizati - Solutie – algoritmi decentralizati – nici un host nu detine starea
sistemului, hosturile iau decizii bazat pe info locale, caderea unei masini nu “ distruge”
algoritmul.

56
 Modele in sisteme distribuite
• Modelul de interactiune procese : modelul client-server si variatii (servere
multiple cooperante ce ofera un serviciu, cod mobil, agenti mobili), respectiv
modelul peer-to-peer (procesele pereche coopereaza si implementeaza
mecanisme de notificare evenimente sau comunicatii de grup).
– Factori ce afecteaza interactiunea : performanta canalelor,solutiile de
comunicare alese: tranzient/persistent , sincron/ asincron

• Modelul de comunicatie - socketuri / RPC/invocari de metode/transfer de

mesaje / bazat pe evenimente/ streamuri
• Modelul de cadere - procesele si canalele de comunicatie comporta caderi,
diverse tipuri de interactiune/ cadere (fail-stop, crash, omisiune ,caderi
arbitrare)

• Modelul de securitate - presupune securizarea proceselor si a canalelor de

comunicatie utilizate in interactiuni, prin protejarea acestora la accese
neautorizate (orientate client , respectiv server)

• Modelul de programare (calcul ) - a evoluat paralel cu limbajele de

programare si cu diversele mecanisme specifice sistemelor de operare/
middleware 57
 Modele de comunicatie
Comunicatia – caracteristica importanta in proiectarea unui SD (HW/SW), Protocol – un
set de reguli ( specifica secventa de mesaje schimbate) si formate de date utilizate
pentru a implementa comunicatia intre procese, se regasesc in emitator/receptor
IPC : socketuri, invocari remote, mesaje, streamuri ( pentru fiecare exista protcoale
specifice, diferite semantici) terminal virtual, transfer
Host A Host B fisiere(FTP,SMTP,RPC)
ISO/OSI
1 Aplicatie Mesaj criptare, compresie,
interfete conversie (XDR)
2 Prez. Mesaj
interfata utiliz:directoare, dr.
acces, sincro, SO diferite
3 Sesiune Mesaj
creare pachete, mux/demux,
4 Transport Mesaj [Link] cap la cap
rutare, control congestie,
Subretea 5 Retea Pachet internetwork, Ip, X25

Frame limitare frame, control flux,

6 Leg. date
detectare erori( HDLC, Eth)
58
7 Fizic Bit semnale fizice, cablare
 Modele de cadere
Model de cadere - definirea modalitatilor de aparitie a defectelor pentru a
intelege efectele lor
caderi de procese, canale de comunicatie
 pot fi benigne, arbitrare, de timp
caderi tip crash - oprirea unui host
caderi prin omisiune (canal ) - serverul nu raspunde, timeout nu anunta daca
procesul/canalul a cazut , omisiune la emisie/receptie ( procese)
cadere proces tip fail –stop = procese cad, raman oprite ,alte procese pot
detecta caderea
caderi arbitrare ( proces/canal) - manifestari aleatoare transmitere aleatoare de
mesaje, opriri de procese, pasi eronatim , caderi datorate unor raspunsuri eronate
caderi datorate depasirii limitei de timp de executie ( de performanta a
procesului /canalului)
Tehnici de detectare/mascare/tolerare ( redundanta) /recuperare
59
 Modele de programare
 Model de programare - conceptualizarea masinii fizice utilizata de
programator la nivel de aplicatii
 modul in care elementele fizice coopereaza si isi coordoneaza
activitatile
 specificarea activitatilor de comunicare si sincronizare

 Model clasic de programare : multiprogramare – concept ce reflecta

inexistenta comunicarii sau sincronizarilor la nivel de program

 Modele de programare actuale:

 Spatiu de adrese partajat – acces partajat la date

 Transfer de mesaje - comunicare explicita punct la punct

60
Modelul spaţiului de memorie
•
partajat
set de adrese de memorie partajate de procesoare
• comunicatie Implicita bazata pe Memorie
• orice procesor poate referi direct orice locatie de M
• scrierile in spatiul de adrese partajat sunt vizibile
celorlalte procese/threaduri
• operatii speciale , atomice pentru sincronizare si
comunicare
• arhitecturi cuplate strans

Limitari :
cresterea numarului de procesoare conduce la
necesitatea implementarii unori mecanisme
complexe care sa rezolve accesele concurente la
acceasi locatie de memorie

61
 Modelul transferului de
mesaje…
– comunicatie bazata pe operatii I/O explicite
– usor de proiectat , mult mai scalabile
• Modelul de programare
– acces direct doar la spatiul de adrese private (M locala)
– comunicatia bazata pe mesaje explicite (send/receive)

• bazat pe biblioteci (MPI, PVM)

62
Abstracţiunea Message-Passing

Match t Receive
, Y, P,t
Adresa Y
Send X, Q, t

Spatiu de
Adresa x Spatiu de adrese local
adrese local

Pr oces P Pr oces Q

 primitiva Send specifica buferul pentru transmisie si procesul receptor

 primitiva Recv specifica procesul emitator si spatiul de stocare la nivel
aplicatie
 copie memorie-memorie, procesele necesita numire
 Tag optional in procesul emitator si regula de “matching” la receptor
 procesele utilizator numesc datele locale si entitatile in procese.
 potrivirea send/receive realizeaza si sincronizarea

63
 Modele de interactiune
Modelul obiectual
 Obiect = resursa partajata , poseda identitate unica, se afla in server si
ofera facilitati de acces la distanta
 obiectul client poseda un proxy – implementarea interfetei obiectului
 pot fi colocate in alte hosturi mentinand identitatea ( migrare obiecte)
Observatii
 distinctie minimalista intre servere - clienti , reflecta modelul de
interactiune “ peer to peer” ( un obiect poate fi client/server,
solicita servicii altor obiecte)
 nivelul middleware implementeaza mecanisme de localizare a
obiectelor si de comunicare/interactiune

Modelul cod la cerere

 clientul poseda resursele si va efectua procesarea , serverul detine
codul/aplicatia ( Know-how , ex. appleti Java) pe care il transfera la cerere
clientului

Modelul agenti mobili

 ofera flexibilitate crescuta in implementarea aplicatiilor distribuite
 orice nod in sistem poseda resursele/ aplicatia (componente) , agentii
mobili - refera cod disponibil oriunde in retea.
64
 Modele de platforme
• Modelul minicomputer
• Modelul workstation
• Modelul workstation-server
• Modelul processor-pool
• Modelul cluster
• Modelul grid computing

65
 Modelul minicomputer

Mini-
computer

ARPA
Mini- net Mini-
computer computer

 reprezintă o extensie a sistemelor clasice cu partajarea timpului

 după logarea pe sistemul propriu, e posibil şi accesul remote la alte
procesoare (telnet)
 resursele partajate reprezintă baze de date sau dispozitive de mare
performanţă.

66
 Modelul Workstation
Workstation

Workstation 100Gbps Workstation

LAN

Workstation Workstation

 bazat pe migrarea proceselor în sistem

 anumite joburi pot migra de pe staţiile încărcate pe alte staţii
 modelul ridică o serie de probleme între care identificarea unei
staţii neocupate, mecanisme necesare migrării, etc.

67
 Modelul Workstation-Server
• presupune existenţa unor staţii simple
pentru procesare locală a aplicaţiilor
interactive , iar operaţii de acces la
Workstation fişiere, tipărire, http sunt transferate
unor servere specializate.
Workstation Workstation
• Serverele sunt sisteme puternice fiecare
dedicat unui anumit tip de serviciu.
100Gbps
LAN
• Modelul de comunicaţie client - server -
tip apel de procedură la distanţă sau
invocare remote de obiecte .
Mini- Mini- Mini-
Computer Computer Computer
file server http server ... server • Modalitatea de interacţiune este
realizată prin apelul procesului server de
către procesul client, fără a presupune
migrare.

68
 Modelul Ferma de procesoare
 terminale diskless

 toate serviciile oferite în sistem sunt

distribuite tuturor serverelor existente

100Gbps
LAN
 pentru fiecare utilizator va putea fi
alocat numărul necesar de procesoare.

 asigură o mai bună utilizare însă cu

Server 1 Server N preţul reducerii interactivităţii.

69
 Modelul Cluster
 serverul conţine staţii sau sisteme
Workstation
personale conectate printr-o reţea de mare
viteză, având drept scop performanţă
Workstation Workstation oferită aplicaţiilor - pot procesa cereri în
paralel.
100Gbps
LAN
http server2
http server1 http server N

Master Slave Slave Slave

node 1 2 N

1Gbps SAN

70
 Modelul grid
 a apărut în intenţia de a colecta puterea
de calcul a sistemelor tip supercomputer,
Workstation
şi a clusterelor distribuite cu scopul de a
le oferi ca o resursă unitară de calcul.

Super- Mini-  oferă

computer computer  calcul distribuit de performanţă
Cluster (pentru probleme complexe),
Retea de mare performanta
 debit de procesare ridicat prin
integrarea diverselor resurse
disponibile de procesare
Super-  calcul ştiinţific bazat pe date
Cluster
computer distribuite
 calcul colaborativ .

Workstation Workstation

71
Modele computationale - Modelul Client-Server

File server
DNS server

Client invocation HTTP server invocation Server

result result
Server

Client
Key:
Process: Computer:

Workstation

Workstation Workstation

100Gbps
LAN

Mini- Mini- Mini-

Computer Computer Computer
file server http server cycle server

72
 Structuri de servere
Service

Server
Client Replication
• Availability
• Performance
Server

Client
Workstation
Server
Workstation Workstation

100Gbps
LAN

Master Slave Slave Slave

node 1 2 N

Ex. [Link] DB server

1Gbps SAN

73
 Servere proxy si cache

Client Web
server
Proxy
server

Client Web
Ex. Internet Service Provider server

Workstation

Workstation Workstation

100Gbps
LAN

Master Slave Slave Slave

node 1 2 N

1Gbps SAN

74
 Procese peer

Application Application

Coordination Coordination
code code

Application

Coordination
Distributed whiteboard application
code

Workstation

Workstation 100Gbps Workstation

LAN
Workstation Workstation

75
 Cod mobil , agenti

a) client request results in the downloading of applet code

Client Web
Applet code server

b) client interacts with the applet

Web
Client Applet server

Workstation

Workstation Workstation

100Gbps
LAN

Mini- Mini- Mini-

Computer Computer Computer
file server http server cycle server

76
 Clienti Thin

X11 Compute server

Network computer or PC Diskless workstations

Thin network Application

Client Process

Workstation

Workstation Workstation

100Gbps
100Gbps
LAN
LAN

Master Slave Slave Slave

node 1 2 N
Server 1 Server N

1Gbps SAN

77
 “The Power of the Internet “
(Source: [Link])/2012
• DOMAIN NAMES: There are 12,844,877 unique domain names (e.g. [Link]) registered
worldwide, with 428,023 new domain names registered each week. (NetNames Statistics
12/28/1999).
• BACKBONE CAPACITY: The capacity of the Internet backbone to carry information is doubling every
100 days. (U.S. Internet Council, Apr. 2004).
• DATA TRAFFIC SURPASSING VOICE: Voice traffic is growing at 10% per year or less, while data
traffic is conservatively estimated to be growing at 125% per year, meaning voice will be less than
1% of the total traffic by 2007. (Technology Futures, Inc March 2000).
• HOST COMPUTERS: In July 1999 there were 56.2 million "host" computers supporting web pages.
In July 1997 there were 19.5 million host computers, with 3.2 million hosts in July 1994, and a
mere 80,000 in July 1989. (Internet Software Consortium – Internet Domain Survey).
• TOTAL AMOUNT OF DATA: 1,570,000,000 pages, 29,400,000,000,000 bytes of text, 353,000,000
images, and 5,880,000,000,000 bytes of image data. (The Censorware Project, Jan. 26, 1999).
• EMAIL VOLUME: Average U.S. consumer will receive 1,600 commercial email messages in 2005, up
from 40 in 1999, while non-marketing and personal correspondence will more than double from
approximately 1,750 emails per year in 1999 to almost 4,000 in 2005 (Jupiter Communications,
May 2000).
• 159 million computers in the U.S., 135 million in EU, and 116 million in Asia Pacific (as of April
2000).
• WEB HITS/DAY: U.S. web pages averaged one billion hits per day (aggregate) in October 1999.
(eMarketer/Media Metrix, Nov. 1999).

78
 Google
• the Google cluster has the following stats:

359 racks

31,654 machines

63,184 CPUs

126,368 Ghz - processing power

63,184 Gb of RAM

2,527 Tb of Hard Drive space

sursa [Link]/2012

79
 “The network really is the computer.”

Tim O’Reilly, in an address at 6/2000 Java One:

“By now, it's a truism that the Internet runs on open source. Bind, the
Berkeley Internet Name Daemon, is the single most mission critical
program on the Internet, followed closely by Sendmail and Apache, open
source servers for two of the Internet's most widely used application
protocols, SMTP and HTTP.”

Early “killer apps”:

- usenet: distributed bulletin board
- email
- talk
Recent “killer apps”:
- the web
- collaborative computing
80
 Facebook
The new Facebook data
center in Prineville, Oregon.
The new servers have been
redesigned are networked,
for energy efficiency, speed-
up and for fault-tolerance.
user
The set up mimics client-
server kind of operation, with
the servers having a high
level of parallelism.
user
However, the network of
servers may also be viewed
user as a distributed system.

30,000 servers

17
 Exemplu

A record of email communication among 4360 employees of one of

the Hewlett Packard Research Labs during the completion of a
project. It is a trivial example of a distributed system.

2
 Paralel vs distribuit

Sisteme paralele Sisteme distribuite

Memoria Sisteme cuplate strans Sisteme cuplate larg ,memoria

distribuita,transfer de
mesaje,paradigme RPC/RMI
sisteme de obiecte, DSM)
Control Control unic Nu există control unic

Interconectare Tbps Gbps

(Bus, mesh, tree, Ethernet, token ring ,SCI ,
hipercub) Myrinet)
Scop Performanta Disponibilitate/siguranta
Calcul stiintific functionarii , partajare info si
resurse , performanta

83
 Concluzii
Calcul paralel Calcul distribuit

Procese cooperante în rezolvarea numar arbitrar de sisteme si procese,

unui obiectiv comun - task, fie comunică prin mesaje
acestea implementate pe sistem de control deschis
procesoare virtuale sau separate Scop – partajarea resurselor şi
fizic. reducerea costurilor pentru
probleme complexe, pe retele de
 Scop : obtinerea performantei calculatoare
 Performanta – timp de
raspuns al sistemului la un Pentru ca un sistem sa fie distribuit e
anumit grad de incarcare necesar ca toate dimensiunile sa
comporte distributie =>
complexitate
 Dificultati de abstractizare a
conceptelor de paralelism -
la nivelul unui program, • Dimensiunile distributiei
procedura, instructiune  poate reflecta distribuirea aplicatiei
 Paralelizare – automat prin sau descompunerea functionala a
compilatoare sau/si la sistemului (resursele fizice sau logice
pot fi distribuite)
nivelul algoritmului
 strategia de control poate fi
centralizata sau distribuita
 datele (controlate de sistem /
84
aplicatie ) distribuite
 Bibliografie
Introduction to Parallel Computing: Design and Analysis of Algorithms,
[Link], A. Grama, A. Gupta, G. Karypis,
Ed. Addison Wesley , 2009
Building parallel programms,
A Kaminsky
Ed Cengage, 2011

Distributed Algorithms .An algoritmic approach,

Wan Fokkink ,
MIT press 2013

Distributed systems,principles,algorithms, systems,

M. Singhal,
Ed. Cambridge University press, 2008

... ftp- materiale ( carti, note de curs in romana, slideuri, laburi, resurse
referate/proiecte)
85