Prof. Almerico Murli. Corso di Calcolo Parallelo e Distribuito II. a.a Progettare un algoritmo per il calcolo della somma di N numeri :

1

Prof. Almerico Murli

Corso di Calcolo Parallelo e Distribuito II a.a. 2005-2006

Problema

in ambiente di calcolo distribuito

a

a a

S =

+

+ ... +

Progettare un algoritmo per il calcolo della somma di N numeri :

3

Quali sono le caratteristiche dell’ambiente di calcolo

?

Requisiti fondamentali

• le risorse di calcolo sono distribuite geograficamente

•i dati risiedono nella memoria locale di tali risorse

(ovvero sono già distribuiti)

5

ESEMPIO 1

Calcolo della somma di 2 numeri utilizzando 2 risorse di calcolo connessi mediante una rete LAN

Caratteristiche dell’ambiente

P 1 P ₂

potenza di calcolo : 4 GFLOPs

7

Caratteristiche dell’ambiente

rete LAN : Bandwidth=100 Mbit/sec

latenza= 0.01sec

P 1 P ₂

I dati sono già distribuiti

P 1 P ₂

a

a

9

I dati sono già distribuiti

P 1 P ₂

a

a

Come sommare

a

a

?

? +

Algoritmo

I passo: comunicazione

P 1 P ₂

a

a

a

11

Algoritmo

I passo: comunicazione

P 1 P ₂

a

a

a

Algoritmo

II passo: calcolo

P 1 P ₂

a

a

a

+ + a

13

Quanto tempo impiega l’algoritmo ( T

)?

I passo: comunicazione Æ T

II passo: calcolo Æ T

T

= t

+ m t

T

= N

t

Quanto tempo T

impiega l’algoritmo?

T

= T

+ T

Risposta

Poiché T

>> T

Il tempo di esecuzione dell’algoritmo è dello stesso ordine di grandezza

di T

OSSERVAZIONE

15

1 word=32 bit

I passo: calcoliamo T

T_com = t _lat + m x t _word =

0.01 sec ?

m=1 ^Poiché

bandwidth= 100 Mbit/sec

t _word = 0.32 x 10 ^-6 sec

Calcolo di T

= T

+ T

1 word=32 bit

I passo: calcoliamo T

T_com = t _lat + m x t _word =

Calcolo di T

= T

+ T

Tcom = t _lat + m x t _word = sec₋₆

17

II passo: calcoliamo T

Ogni processore effettua 4 x 10 ⁹ flops

) 10 4 /(

1 × ⁹

t _calc= ^sec

T_calc = N _op x t_calc= 0.25 x 10 ^-9 sec

Calcolo di T

= T

+ T

T_calc= N_op t_calc

1 somma

T

= T

+ T

=

9 6

2

0 . 32 10 0 . 25 10

10

+ ×

+ ×

=

Calcolo di T

= T

+ T

≈

p = 2

il tempo necessario per sommare 2 numeri è dominato dal tempo di latenza

t_lat

19

Quindi ….

T

= T

+ T

=

= ( t

+ m x t

) + N

x t

poichè

t

>> t

t

>> t

Il tempo di latenza può influenzare in maniera significativa il tempo di

esecuzione dell’algoritmo

ESEMPIO 2

calcolo della somma di N numeri

distribuiti su risorse di calcolo

situate in due siti geograficamente distribuiti

21

Sito 2 Sito 1

Rete geogr.: lat. = 0.3 sec

LAN: lat. = 0.01 sec LAN: lat. = 0.01 sec

Caratteristiche dell’ambiente di calcolo

Sito 2 Sito 1

Rete geogr.: lat. = 0.3 sec

LAN: lat. = 0.01 sec LAN: lat. = 0.01 sec

Caratteristiche dell’ambiente di calcolo

a2

a1

I dati sono già distribuiti

23

Problema

ridurre “al minimo possibile”

le comunicazioni sulla rete con tempo di latenza più alto

Ovvero

Ridurre le comunicazioni tra un sito e l’altro

(intra – sito)

Una soluzione..

Riorganizzare il calcolo in modo da effettuare solo 1 comunicazione sulla rete intra – sito

Rete geogr.: lat. = 0.3 sec

IDEA

Sito 1 Sito 2

rete intra – sito

25

I passo: 4 comunicazioni inter-sito

Calcolo somma parziale S₁nel Sito 1

Sito 1 Sito 2

a4 a₅ a3

a2

Rete geogr.: lat. = 0.3 sec

a1

I passo: 4 comunicazioni inter-sito

Calcolo somma parziale S₁nel Sito 1

Sito 1 Sito 2

Rete geogr.: lat. = 0.3 sec

27

I passo: 2 comunicazioni inter-sito

Calcolo somma parziale S₂nel Sito 2

Sito 1 Sito 2

s1 a₆ a₈

Rete geogr.: lat. = 0.3 sec

5 1

1

a ... a s = + +

a7

I passo: 2 comunicazioni inter-sito

Calcolo somma parziale S₂nel Sito 2

... a a

s = + +

Sito 1 Sito 2

Rete geogr.: lat. = 0.3 sec

29

II passo

Sito 1 Sito 2

calcolo S = s₁+s₂

1 comunicazione intra-sito

s2

Rete geogr.: lat. = 0.3 sec

2

1 s

s S = +

s2

II passo

Sito 1 Sito 2

calcolo

2

1 s

s S = +

1 comunicazione intra-sito

Rete geogr.: lat. = 0.3 sec

31

III passo: 6 comunicazioni inter-sito

Sito 1 Sito 2

S

S S

Spedire Sagli altri nodi del sito

S S S S S

Rete geogr.: lat. = 0.3 sec

Quindi:

• I passo:

– 6 comunicazioni inter-sito 1

• II passo:

- 1 comunicazione intra-sito

• III passo:

33

ESEMPIO 3

calcolo della somma di N numeri

distribuiti su risorse di calcolo

situate in due siti geograficamente distribuiti dove in uno dei due siti

c’è un cluster a rete locale veloce

Sito 2 Caratteristiche risorse di calcolo:

nel sito 1 c’è un cluster a rete locale veloce

Switch: lat. = 0.001 sec LAN: lat. = 0.01 sec

Rete geogr.: lat. = 0.3 sec

LAN: lat. = 0.01 sec

ESEMPIO 3:

35

I dati sono già distribuiti

a1

a4

a6

a5

a3

a2

a8

a7 Switch: lat. = 0.001 sec

LAN: lat. = 0.01 sec

Rete geogr.: lat. = 0.3 sec

LAN: lat. = 0.01 sec

Sito 1

Sito 2

PROBLEMA

4 nodi beowulf Switch: lat. = 0.001 sec LAN: lat. = 0.01 sec

PC

Sito 1

Nel Sito 1 ci sono 2 reti di comunicazione

cercare di usare il meno possibile

37

Idea

fare il “massimo possibile” di comunicazioni sulla rete con

tempo di latenza più basso

…in che modo?

Una Soluzione

Calcolare prima

5 2

) (

1 a ... a s^b = + +

)

(b4 nodi beowulf Switch: lat. = 0.001 sec LAN: lat. = 0.01 sec

PC

Sito 1

)

(b (b) (b)

Successivamente

) (b

(2= log (p) comunicazioni)

(1 comunicazione)

39

In GENERALE

Latenza elevata

Latenza bassa

Livello 1

Livello 2

Livello 3

Ogni livello individua

un tipo di rete in base al tempo di latenza

Switch LAN

Rete geogr.

LAN

Idea

sfruttare quanto più è possibile i livelli più bassi perché relativi

alle reti veloci

Procedere nel calcolo dal basso verso l’alto calcolo

41

successivamente

Distribuire i risultati

procedendo dall’alto verso il basso

distribuzione risultati

parziali

algoritmo topology-aware

In generale: calcolo della somma

43

I passo: Somma locale nel livello 3

Cioè….

s₁ s₁ s₁ s₁ s₂

45

Somma con il livello 2

Cioè…

s₁+s₂

s₁+s₂ s₃ s₃ s₃

47

Somma al livello 1

Cioè….

s₁+s₂+s₃ s₁+s₂+s₃

49

Distribuzione al livello 2

S S

S= s₁+s₂+s₃

Distribuzione al livello 3

S S S S

S S= s₁+s₂+s₃

51

osservazione

Lo schema dell’algoritmo della somma nella formulazione standard

presuppone un

ambiente di calcolo omogeneo

(soprattutto rispetto al tempo di comunicazione) perché gestisce uniformemente le comunicazioni

tra processori (

albero binario

Aspetti algoritmici

53

Struttura del livello 1: cid(livello)= risorsa

Ad ogni livellole reti connettono 2 o piu’ risorse

Switch

LAN LAN

cid(1)=0

cid(1)=1

Struttura del livello 2

Switch cid(2)=0

cid(2)=1

cid(2)=0cid

(2)=1 cid (2)=2

Ogni risorsa e’ suddivisa in 2 o piu’ sottorisorse ….

cid(1)=0

55

Struttura del livello 3

cid(3)=0cid (3)=1cid

(3)=2cid (3)=3

… fino al livello piu’ basso

problema

Come identificare i processi delle varie

risorse?

57

Identificativo dei processi delle risorse al livello 1

In ogni clusteri processi hanno un differente identificativo (pid) 0

1 2 3 4

0 1 2

Identificativo dei processi nei cluster al livello 2

0

0 1 2 3

0 0 0

Il pid cambia da ogni livello

59

Identificativo dei processi nei cluster al livello 3

0 0 0 0

Ai livelli piu’ bassi i processi hanno pid =0

Riassumendo….

Livello 1

Livello 2

Livello 3 cid(1)=0 cid(1)=1

cid(2)=0 cid(2)=1

Ogni processo e’ cosi’ identificato da una profondità (prof)e da un identificativo di cluster(cid)ad ogni livello

prof=2 cid(1)=1 prof=2

cid(1)=0 cid(2)=0

prof=3 cid(1)=0

cid(2)=0 cid(2)=1 cid(2)=2

cid(3)=0 cid(3)=1cid(3)=2 cid(3)=3

61

Inoltre …

Livello 1

Livello 2

Livello 3 Ogni processo e’ identificato da un

identificativo di processo (pid) ad ogni livello

prof=2 pid(1)=0

pid(2)=0 prof=3

pid(1)=4 pid(2)=3 pid(3)=0

prof=2 pid(1)=2 pid(2)=0

Somma al livello 3

cid(1)=0 cid(2)=1 cid(3)=0 pid(1)=1

cid(1)=0 cid(2)=1 cid(3)=1 pid(1)=2

cid(1)=0 cid(2)=1 cid(3)=2 pid(1)=3

cid(1)=0 cid(2)=1 cid(3)=3 pid(1)=4

stesso cid(2) e pid(3)=0 !!!!

63

Somma al livello 2

cid(1)=0 cid(2)=1 cid(3)=0 pid(1)=1 pid(2)=0 pid(3)=0 cid(1)=0

cid(2)=0 pid(1)=0 pid(2)=0

cid(1)=1 cid(2)=0 pid(1)=0 pid(2)=0

cid(1)=1 cid(2)=1 pid(1)=1 pid(2)=0

cid(1)=1 cid(2)=2 pid(1)=2 pid(2)=0

stesso cid(1) e pid(2)=0 !!!!

Somma al livello 1

cid(1)=1 cid(2)=0 pid(1)=0 pid(2)=0 cid(1)=0

cid(2)=0 pid(1)=0 pid(2)=0

stesso cid(0) e pid(1)=0 !!!! …

65

Distribuzione al livello 2

cid(1)=0 cid(2)=1 cid(3)=0 pid(1)=1 pid(2)=0 pid(3)=0 cid(1)=0

cid(2)=0 pid(1)=0 pid(2)=0

cid(1)=1 cid(2)=0 pid(1)=0 pid(2)=0

cid(1)=1 cid(2)=1 pid(1)=1 pid(2)=0

cid(1)=1 cid(2)=2 pid(1)=2 pid(2)=0

stesso cid(1) e pid(2) =0 !!!!

S S

Distribuzione al livello 3

cid(1)=0 cid(2)=1 cid(3)=0 pid(1)=1

cid(1)=0 cid(2)=1 cid(3)=1 pid(1)=2

cid(1)=0 cid(2)=1 cid(3)=2 pid(1)=3

cid(1)=0 cid(2)=1 cid(3)=3 pid(1)=4

stesso cid(2) e pid(3) =0 !!!!

S S S S

S

67

FINE LEZIONE