1

1

Calcolo Parallelo

Efficienza e Scalabilitàdi algoritmi e software

in ambienti di Calcolo Parallelo

Laura Antonelli

EfficienzaEfficienza 2

Problema

Valutare l’efficienza di un algoritmo

in ambiente di calcolo parallelo

Cosa si intende per “EFFICIENZA” ?

Efficienza 3

Efficienza di un algoritmo sequenziale

COMPLESSITA’ di TEMPO T(n)Numero di operazioni eseguite dall’algoritmo

COMPLESSITA’ di SPAZIO S(n)

Numero di variabili utilizzate dall’algoritmo

Efficienza 4

Esempio: calcolo della somma di n=16 numeri

ALGORITMO SEQUENZIALE1 studente

Passi temporali

numero di addizioni = 15

passi temporali = 15

complessità di tempo

T(n)=n-1 addizioni

tcalc= tempo di esecuzione di 1 addizione

T1=15 tcalc

1234

56789

1011121314

15

2

Efficienza 5

In un algoritmo sequenziale

Il numero complessivo di operazioni

determina anche

il numero dei passi temporali

(tempo di esecuzione dell’algoritmo)

Efficienza 6

In un algoritmo parallelo

Si può ancora legare

il tempo di esecuzione al numero delle operazioni

che costituiscono l’algoritmo

?

Efficienza 7

Esempio: calcolo della somma di n=16 numeri

ALGORITMO PARALLELO2 studenti

Passi temporali

numero di addizioni = 15

MA

passi temporali = 8

12

34

56

7

8

• 1addizione

14 addizioni

(7 per ciascuno studente)

Passi temporali 1-7:

Passo temporale 8:

T2=8 tcalc

Efficienza 8

Esempio: calcolo della somma di n=16 numeri

ALGORITMO PARALLELO4 studenti

Passi temporali

numero di addizioni = 15

MA

passi temporali = 5

1 addizione

1

2

3

4

5

12 addizioni

2 addizioni

Passi temporali 1-3:

Passo temporale 4:

Passo temporale 5:

T4=5 tcalc

3

Efficienza 9

Esempio: calcolo della somma di n=16 numeri

ALGORITMO PARALLELO8 studenti

numero di addizioni = 15

MA

passi temporali = 4

Passo temporale 1: 8 addizioni

passitemporali

Passi temporali

1

2

3

4

Passo temporale 2: 4 addizioni

Passo temporale 3: 2 addizioni

Passo temporale 4: 1 addizione

T8=4 tcalc

Efficienza 10

Nell’algoritmo parallelo della somma

Il numero delle operazioni

dell’algoritmo Parallelo

NON è legato al

numero dei passi temporali

Efficienza 11

Infatti …

Un calcolatore parallelo è in grado di eseguire più operazioni

Il tempo di esecuzione non è proporzionale al numero di operazioni fl. p. effettuate

La sola complessità di tempo non è adatta a misurare l’efficienza di un algoritmo parallelo

nello stesso passo temporale(esecuzione parallela di più operazioni)

Efficienza 12

… e allora

Come misurare

l’efficienza

di un algoritmo parallelo?

4

13

OSSERVAZIONE

Sia Tp il tempo di esecuzione su p (p=1, 2, 3,…) processori

utilizzando p = 2

il tempo di esecuzione T1 dovrebbe essere il doppio di T2

2T

T

2

1

utilizzando p = 4

il tempo di esecuzione T1 dovrebbe essere il quadruplo di T4

4T

T

4

1

Efficienza 14

In generale

Utilizzando p processori

il tempo di esecuzione T1 dovrebbe essere p volte Tp,

cioè il loro rapporto vale:

pT

T

p

1

Utilizzando p processori

il tempo di esecuzione parallelo si dovrebbe ridurre di circa p volte

rispetto al tempo di esecuzione sequenziale

Efficienza 15

Speedup

Lo speedup misura la riduzione del tempo di esecuzione dell’algoritmo all’aumentare del numero di processori p, ovvero misura quanto aumenta la velocità di esecuzione rispetto ad 1 processore

in generale:

p

1p T

TS

Si definisce Speedup il rapporto

pSp

pSidealep

SPEEDUP IDEALE

Efficienza 16

Esempio: calcolo della somma di n=16 numeri

L’algoritmo su 8 processori è il più veloce.E’ più veloce di 3.75 volte di quello su 1 processore

(ma non di 8 volte come ci aspettavamo …)

3.75

3.00

1.88

1.00

4tcalc8

5tcalc4

8tcalc2

15tcalc1

Tppp

1p T

TS

Maggiore riduzione del tempo ovvero maggiore aumento della velocità di

esecuzione

Analizziamo lo speedup al variare di p

5

Efficienza 17

Domanda

p Tp

1 15tcalc

2 8tcalc

4 5tcalc

8 4tcalc

In generale quanto vale Tp?

2k ? tcalc

Perché Tp non si riduce proporzionalmente a p?

Efficienza 18

P3P0 P2P1

P5 P6 P7P4tcalc

1

2

3

4

n/p –1

Log p= max profondità dell’albero

Esempio: p=8, n=16

operazioniper ottenerela sommadei dati locali

Quanto vale Tp ? contiamo i passi temporali…

Efficienza 19

In generale: calcolo di Tp

ALGORITMO PARALLELO della somma di n numerisu p=2k processori

n = 16

tcalc= tempo di esecuzione di 1 addizione

p=1 T1=15 tcalc

p=2 T2=8 tcalc= (7+1) tcalc

p=4 T4=5 tcalc= (3+2) tcalc

p=8 T8=4 tcalc= (1+3) tcalc

………………

p=2kpn

Tp= ( -1 +log2 p) tcalc

20

Oh = pTp – T1

OVERHEAD totale

L’OVERHEAD totale misura quanto lo speedup differisce da quello ideale

Perché Sp non è proporzionale a p?

pT

TS

p

idealep 1

Tp = (Oh + T1) /p

1T

Op

TO

pT

)/pT (O

T

T

T(n)S

1

h1h

1

1h

1

p

1p

In generale l’overhead in informatica misura lo “spreco” di risorse per raggiungere un determinato obiettivo

Lo speedup effettivo dipende dal rapporto tra lo speedup ideale e l’overhead totale

6

Efficienza 21

T1 = n-1

Tp = n/p - 1 + log2 p

Oh = p Tp - T1 = p (n/p -1 + log2 p ) – (n-1) =

=O(p log2 p) ≈ n -p + p log2 p –n +1

p Oh

2 2

4 8

8 24

2k p log2 p

All’aumentare di p anche l’overhead aumenta!

Calcolo dell’overhead

ALGORITMO PARALLELO della somma di n numerisu p=2k processori

Efficienza 22

Riassumendo: calcolo della somma con n=16 numeri e p=8

Lo speedup misura la maggiore riduzione di tempo, all’aumentare delle risorse

MA….L’overhead misura il maggior scarto dallo speedup ideale

(ovvero il maggior “spreco” di risorse!!)

Come capire se la riduzione ottenuta dallo speedup produce un effettivo guadagno in efficienza?

(ovvero se il parallelismo è vantaggioso

rispetto all’inevitabile overhead introdotto?)

Efficienza 23

OSSERVAZIONE:calcolo della somma di n=16 numeri

p Speed-up ottenuto

Speed-up ideale

2 1.88 2

4 3.00 4

8 3.75 8

Lo speedup su 2 processori è

“il più vicino” allo speed-up ideale..

L’algoritmo parallelo su due processori

è quello più veloce in rapporto alle risorse utilizzate

(il guadagno ottenuto è commisurato alle risorse in uso)Efficienza 24

IDEA!calcolo della somma di n=16 numeri

… se si rapporta lo speedup al numero di processori

p Sp

2 1.88 0.94

4 3.00 0.75

8 3.75 0.47

Si ottiene una misura dello sfruttamento delle risorse

di calcolo

(il massimo per p=2)

p

Sp

Rapporto più grande

L’utilizzo di un maggior numero di processori NON è sempre garanzia di algoritmi paralleli efficienti

7

Efficienza 25

Efficienza

L’efficienza misura se e quanto l’algoritmo parallelo

sfrutta il parallelismo del calcolatore

p

SE p

p

1p

SE

idealepideale

p

EFFICIENZA IDEALE

Si definisce efficienza Ep il rapporto Sp su p

Efficienza 27

E’ possibile ottenerespeedup prossimi allo

speedup ideale ?

Domanda

Efficienza 28

una parte relativa alle operazioni che

sono eseguite (necessariamente) in sequenziale

Il tempo

di esecuzione sequenziale T1 si può decomporre in 2 parti:

Tseq =T1 Tpar =(1-)T1

T1 = +Tseq Tpar

una parte relativa alle operazioni che POSSONO essere eseguite in parallelo

OSSERVAZIONE:

una parte relativa alle operazioni che

sono eseguite (necessariamente) in sequenziale

Efficienza 29

Il tempo

di esecuzione sequenziale T1 si può decomporre in 2 parti:

Tseq =T1 Tpar =(1-)T1

T1 = T1 + (1-) T1

una parte relativa alle operazioni che POSSONO essere eseguite in parallelo

OSSERVAZIONE:

8

Efficienza 30

T1 = T1 + (1-) T1

Tp = T1 + (1-) T1p

Se

allora Tp il tempo impiegato dall’algoritmo parallelo con

p processori si può scrivere come:

Osservazione:

ovvero a partire da T1 possiamo ricavare Tp

dividendo le operazioni relative alla parte parallelaper il numero p di processori

Efficienza 31

Calcoliamo lo speedup:

Contributo relativo

all’esecuzione delle operazioni

sequenziali

Contributo relativo

all’esecuzione delle operazioni

in parallelo

p

)(11

p

)T-(1T

T

T

TS

11

1

p

1p

Lo speedup si può riscrivere come:

Efficienza 32

Legge di Ware (Amdahl)

p

)(11

p

)T-(1T

T

T

TS

11

1

p

1p

Tale legge esprime lo speedup in funzione delle frazioni sequenziali e parallelizzabili del tempo T1

ed il numero p di processori

Efficienza 33

Conseguenze della legge di Amdahl

p

)(1

Sp

1

Al crescere del numero p di processori…

1

Il valore asintotico di

Sp diventa costante!!

p

9

Efficienza 34

Esempio 1 (n fissato e p variabile)

p α1 αp Sp Ep

2 0,032 0,968 1,9 0,95

4 0,032 0,903 3,4 0,85

8 0,032 0,775 5,1 0,6

16 0,032 0,516 6,2 0,3

Fissiamo la dimensione n e aumentiamo il numero p di processori…

Speed up ed efficienzadegradano

perché la parte parallela

diminuisce!

Applichiamo la legge di Amdahl con n =32 e p =2, 4, 8, 16

Efficienza 35

Se la dimensione n del problema è fissata,

al crescere del numero p di processori,non solo non si riescono ad ottenere

speed up vicini a quello ideale

MA

Le prestazioni peggiorano!

(non conviene utilizzare un maggior numero di processori!!)

Prima conseguenza della legge di Amdahl

Efficienza 36

n α 1-α S2(n) E2(n)

8 0,14 0,86 1,75 0,875

16 0,06 0,93 1,8 0,9

32 0,03 0,96 1,9 0,96

64 0,01 0,98 1,96 0,99

La partesequenziale

tende a zero!

Applichiamo la legge di Amdahl con p =2 e n = 8, 16, 32, 64

Fissiamo il numero p di processori aumentiamo la dimensione n…

Esempio 2 (al contrario: n aumenta e p è fissato)

Efficienza 37

n α 1-α S2(n) E2(n)

8 0,14 0,86 1,75 0,875

16 0,06 0,93 1,8 0,9

32 0,03 0,96 1,9 0,96

64 0,01 0,98 1,96 0,99

La parte parallela è costante

Applichiamo la legge di Amdahl con p =2 e n = 8, 16, 32, 64

Esempio 2 (al contrario: n aumenta e p è fissato)

Fissiamo il numero p di processori aumentiamo la dimensione n…

10

Efficienza 38

Speed up ed efficienza sono

pressoché “costanti”!

Applichiamo la legge di Amdahl con p =2 e n = 8, 16, 32, 64

n α 1-α S2(n) E2(n)

8 0,14 0,86 1,75 0,875

16 0,06 0,93 1,8 0,9

32 0,03 0,96 1,9 0,96

64 0,01 0,98 1,96 0,99

Esempio 2 (al contrario: n aumenta e p è fissato)

Fissiamo il numero p di processori aumentiamo la dimensione n…

Efficienza 39

Seconda conseguenza della legge di Amdahl

p

)(1

Sp

1

Al crescere del numero n della dimensione del problema…

p

Il valore asintotico di

Sp è lo Speedup ideale!!

n

0 0

Efficienza 40

Fissando il numero p di processori e aumentando la dimensione del problema si possono ottenere

speedup prossimi a quello ideale

MA

Non è possibile aumentare in maniera indefinita la dimensione n

del problema: le risorse (hardware) sono limitate!

Seconda conseguenza della legge di Amdahl

Efficienza 41

Aumentando il numero p di processori e fissando la dimensione n del problema

si riesce ad utilizzare in maniera efficiente l’ambiente di calcolo parallelo,

se p ≤ p0

Sintesi

Secondo la legge di Amdahl-Ware…

Aumentando la dimensione n del problema e fissando il numero p di processori le

prestazioni dell’algoritmo parallelo non degradano se n ≤ n0

11

Efficienza 42

Cosa succede se

aumentiamo proporzionalmente

sia il numero p di processori

sia la dimensione n del problema

?

Domanda

Efficienza 43

Esempio: somma di n numeri in parallelo

n p α1 αp Sp(n) Ep(n)

8 2 0,14 0,86 1,75 0,875

16 4 0,06 0,8 3 0,75

32 8 0,03 0,77 5,1 0,64

64 16 0,01 0,76 9 0,56

La frazione di operazioni eseguite

in sequenziale

tende a zero!

Applichiamo la legge di Amdahl con p= 2, 4, 8, 16

è costante4p

n

Consideriamo quindi n= 8 , 16, 32, 64

Efficienza 44

Esempio: somma di n numeri in parallelo

La frazione di operazioni eseguite

in parallelo è “quasi costante”!

Applichiamo la legge di Amdhal con p= 2, 4, 8, 16

è costante4p

n

Consideriamo quindi n= 8 , 16, 32, 64

n p α1 αp Sp(n) Ep(n)

8 2 0,14 0,86 1,75 0,875

16 4 0,06 0,8 3 0,75

32 8 0,03 0,77 5,1 0,64

64 16 0,01 0,76 9 0,56

Efficienza 45

Esempio: somma di n numeri in parallelo

Lo speed up

aumenta!

Applichiamo la legge di Amdhal con p= 2, 4, 8, 16

è costante4p

n

Consideriamo quindi n= 8 , 16, 32, 64

n p α1 αp Sp(n) Ep(n)

8 2 0,14 0,86 1,75 0,875

16 4 0,06 0,8 3 0,75

32 8 0,03 0,77 5,1 0,64

64 16 0,01 0,76 9 0,56

12

Efficienza 46

Esempio: somma di n numeri in parallelo

L’efficienza

non degrada!

Applichiamo la legge di Amdhal con p= 2, 4, 8, 16

è costante4p

n

Consideriamo quindi n= 8 , 16, 32, 64

n p α1 αp Sp(n) Ep(n)

8 2 0,14 0,86 1,75 0,875

16 4 0,06 0,8 3 0,75

32 8 0,03 0,77 5,1 0,64

64 16 0,01 0,76 9 0,56

Efficienza 47

Aumentando sia n che p,

le prestazioni

dell’algoritmo parallelo non degradano:

l’efficienza esprime un buon guadagno

rispetto all’algoritmo sequenziale

Ma

come misurare le prestazioni

?

Scalabilità dell’algoritmo

Efficienza 48

•Raddoppiamo p ed n:

con p=2 posso calcolare la somma di 2n numeri nel tempo T1(n)

(2n)T(n)T 21

(4n)T(n)T 41

Sia T1(n) il tempo di esecuzione su un processoreper la somma di n numeri…

Esempio: somma di n numeri in parallelo

• Quadruplichiamo p ed n :

con p=4 posso calcolare la somma di 4n numeri nel tempo T1(n)

Efficienza 49

1)pn(T

)n(T

p

1

..se si assume

pT1(n) = T1(pn)

)pn(T...)n(T(2n)T(n)T p421 4

idealep

p

1 Sp)pn(T

)pn(Tp

)pn(T

)n(Tp

p

1

Pertanto...

Esempio: somma di n numeri in parallelo

Sia T1(n) il tempo di esecuzione su un processore per la somma di n numeri, in generale vale…

Si raggiunge lo speedup ideale!!

13

Efficienza 50

(*) la legge di proporzionalità dipende dal problema nel caso della somma essa è lineare, cioè

pT1(n) = T1(pn)

(np)T

(n)pT(n)SS

p

p1

SPEEDUP SCALATO

Speedup ScalatoUn algoritmo si dice scalabile se

aumentando il numero di processori

riusciamo ad aumentare proporzionalmente(*) la dimensione del problema mantenendo

il tempo parallelo costante, cioè vale:

Efficienza 51

(*) la legge di proporzionalità dipende dal problema nel caso della somma essa è lineare, cioè

pT1(n) = T1(pn)

Efficienza Scalata

(pn)T

(n)T

p

(n)SS(n)ES

p

1pp

EFFICIENZA SCALATA

Un algoritmo si dice scalabile se

aumentando il numero di processori

riusciamo ad aumentare proporzionalmente(*) la dimensione del problema mantenendo

l’efficienza scalata costante, cioè vale:

Efficienza 52

….. Misuriamo quanto impiegherebbe

un solo processore ad effettuare in sequenziale

le operazioni eseguite

concorrentemente da p processori:

cioè quanto impiegherebbe un solo processore

a risolvere un problema p volte più grande

(fixed-time model)

Osservazione

Efficienza 53

Osservazione

Se si esegue l’algoritmo parallelo su un

calcolatore MIMD a memoria distribuita,

il tempo di esecuzione dipende solo dal numero di operazioni eseguite in differenti

passi temporali?

14

Efficienza 54

Esempio: calcolo della somma di n=16 numeri

ALGORITMO PARALLELOp=2

L’algoritmo richiede lacomunicazione di 1 dato

tra 2 processori

tcom= tempo per comunicare un dato tra due processori

T2=8 tcalc +tcomcomunicazione

P0 P1tcom

1

tcom

Efficienza 55

Esempio: calcolo della somma di n=16 numeri

ALGORITMO PARALLELOp=4

tcom

T4=5 tcalc +2tcom

P3P0 P2P1

1

2

Efficienza 56

Esempio: calcolo della somma di n=16 numeri

ALGORITMO PARALLELOp=8

T8=4 tcalc +3tcom

tcalc P3P0 P2P1

P5 P6 P7P4

2

3

1

Efficienza 57

In sintesi …

p Tp

1 15tcalc

2 8tcalc + 1 tcom

4 5tcalc + 2 tcom

8 4tcalc + 3 tcom

In generale quanto vale Tp

considerando le comunicazioni?

?2k ? tcalc + ? tcom

15

Efficienza 58

In generale: calcolo di Tp considerando le comunicazioni

ALGORITMO PARALLELO della somma di n numerisu p=2k processori

n = 16

tcalc= tempo di esecuzione di 1 addizione

p=1 T1=15 tcalc

p=2 T2=8 tcalc= (7+1) tcalc + 1 tcom

p=4 T4=5 tcalc= (3+2) tcalc + 2 tcom

p=8 T8=4 tcalc= (1+3) tcalc + 3 tcom

………………

p=2k

pnTp= ( -1 +log2 p) tcalc + (log2 p) tcom

tcom= tempo di 1 comunicazioneEfficienza 59

Overhead di comunicazione

Tpcom = tempo di comunicazione dell’algoritmo

eseguito su p processori

Tpcalc = tempo di calcolo dell’algoritmo

eseguito su p processori

Fornisce una misura del “peso” della comunicazione sul tempo di esecuzione dell’ algoritmo

calcp

comp

p T

TOC

definiamo Overhead di Comunicazione totale, il rapporto:

Riferimenti Bibliografici

60

A. Murli, Lezioni di Calcolo Parallelo, cap 3

A.Y. Grama, A. Gupta, V. Kumar Isoefficiency: Measuring the Scalability of Parallel Algorithms and Architectures IEEE Parallel & Distributed Technology, 1993

A.Y. Grama, A. Gupta, G.Karypis, V. Kumar Introduction to Parallel Computing Second edition http://www-users.cs.umn.edu/~karypis/parbook/

J. L. Gustafson. Reevaluating Amdahl’s Law. Communications of the ACM, May 1988.

Efficienza 61

Fine Lezione