Resúmenes

Apuntes universitarios en formato Markdown desde Obsidian.

Performance (parte 2)

Legge di Amdahl

Bestia nera dei ricercatori nel campo del calcolo parallelo fino al 1988. Ha “limitato” la velocità di una macchina parallela a 20-50, indipendentemente dal numero di processori! Nel 1988, tuttavia, alcuni ricercatori dei Sandia National Labs ottennero una velocità di 1000 su una macchina da 1024 processori senza violare la legge di Amdahl. Come hanno fatto?

Speedup

Misura di quanto più velocemente viene eseguito il calcolo rispetto al miglior codice seriale: tempo seriale diviso per tempo parallelo.

ESEMPIO: dipingere una staccionata

30 minuti di preparazione (seriale)

1 minuto per dipingere un singolo picchetto

30 minuti di pulizia (seriale)

Quindi, 300 picchetti impiegano 360 minuti (tempo seriale)

Speedup di calcolo

Il potenziale aumento di speedup è limitato dalla parte seriale. E se il proprietario del recinto usasse una pistola a spruzzo per dipingere 300 picchetti in un'ora?

Migliore algoritmo seriale;
Se non sono disponibili pistole a spruzzo per più lavoratori, qual è l'accelerazione parallela massima?

Problema scalabile

I problemi che aumentano la percentuale di tempo parallelo con la loro dimensione sono più scalabili dei problemi con una percentuale fissa di tempo parallelo.

ESEMPIO: alcuni problemi dimostrano un aumento delle prestazioni aumentando la dimensione del problema

2D GRID CALCULATIONS - 85 sec - 85%

SERIAL FRACTION - 15 sec - 15%

Aumentare la dimensione del problema raddoppiando le dimensioni della griglia e dimezzando i tempi:

quattro volte il numero di punti della griglia

il doppio del numero di passi temporali

2D GRID CALCULATIONS - 680 sec - 97,84%

SERIAL FRACTION - 15 sec - 2,16%

Speedup massimo (Legge di Amdahl)

Speedup VS processori

Anche con un numero infinito di processori, velocità massima limitata a 1/f. Esempio: con solo il 5% del calcolo seriale, lo speedup massimo è 20, indipendentemente dal numero di processori.

Scalabilità

Come possiamo estrapolare le prestazioni da piccoli problemi e piccoli sistemi a problemi più grandi con configurazioni più grandi? L'esempio seguente mostra l'evoluzione dell'accelerazione di tre algoritmi per una FFT (Fast Fourier Transform) a n punti su 64 processori.

Per piccoli valori di n, sembrerebbe che gli algoritmi di scambio binario e di trasposizione 3D siano i migliori, ma per n > 18000, l'algoritmo di trasposizione 2D consente una migliore accelerazione. La morale è che è difficile dedurre la scalabilità dei dati da osservazioni e macchine "piccole".

L'efficienza di un programma parallelo può essere scritta come:

$E = \frac{S}{p} = \frac{T_{S}}{p T p}$

oppure, ricordando il concetto di overhead parallelo $T_{0} = p*T_{P} – T_{S}$ , si ha:

$E = \frac{1}{1 + \frac{T_{0}}{T_{S}}}$

Per un dato problema di dimensione (cioè il valore $T_{S}$ rimane costante), se aumentiamo il numero di processori p, $T_{o}$ aumenta. Al contrario, l'efficienza totale del programma diminuisce. Questo è il caso di tutti i programmi paralleli.

Esempio

Considera il solito problema di sommare n numeri su p processori (algoritmo di scala intelligente). Abbiamo visto che (evitiamo l'analisi asintotica, lavoriamo con le costanti):

$T_{p} = \frac{n}{p} + 2*\log p$

$S = \frac{n}{\frac{n}{p} + 2*\log p}$

$E = \frac{1}{1 + \frac{2*p*\log p}{n}}$

Se visualizziamo l'accelerazione per varie dimensioni di input, otteniamo:

L'accelerazione tende a saturare e l'efficienza diminuisce come conseguenza della legge di Amdahl.

Caratteristiche

La funzione di overhead totale $$T_0$$ è una funzione sia di $$T_S$$ (cioè la dimensione del problema) sia del numero di processori p.

In molti casi $$T_0$$ cresce in modo sub-lineare rispetto a $$T_S$$ . In tali casi, l'efficienza aumenta se aumentano le dimensioni del problema, mantenendo costante il numero di processori. Per questi sistemi, possiamo aumentare contemporaneamente le dimensioni del problema e il numero di processori per mantenere costante l'efficienza (ma come?).

Tali sistemi sono chiamati sistemi paralleli scalabili.

In un sistema scalabile, l'efficienza rimane costante con l'aumento sia di p che di n. Ad esempio, nel caso della somma di n numeri su p processori, l'efficienza rimane costante a 0,8 se:

$n = 8*p*\log p$

Conclusioni

Ricordiamo che i sistemi paralleli che sono ottimali in termini di costi hanno efficienza $\Theta(1)$ . Pertanto, la scalabilità e l'ottimizzazione dei costi sono strettamente correlate. Un sistema parallelo scalabile può essere ottimizzato in termini di costi se il numero di processori e la dimensione del problema sono scelti in modo appropriato.

In sintesi, per una data dimensione del problema, se aumentiamo il numero di processori, l'efficienza complessiva del sistema diminuisce (per tutti i sistemi) e, per alcuni sistemi, l'efficienza di un sistema parallelo aumenta se aumentano le dimensioni del problema mentre il numero di processi rimane costante.

Isoefficienza

I due concetti precedenti possono essere illustrati dalla seguente tabella:

Qual è il tasso di crescita della dimensione del problema rispetto al numero di processori per mantenere costante l'efficienza?

Questa velocità determina la scalabilità del sistema. Più piccolo è, meglio è. Prima di formalizzare questo concetto, dobbiamo definire formalmente quali sono le "dimensioni del problema".

Possibili soluzioni: dimensioni dell'input? Non bene!

Facciamo un esempio: sia n la dimensione dell'input di un problema di calcolo matriciale (es. somma di matrici, prodotto matrice-matrice). Se n viene raddoppiato, si avrà un incremento di 8 volte per un'operazione che coinvolge il prodotto matrice – matrice, mentre 4 volte se l'operazione è somma di matrici. Quindi, "dipende" dal problema. A tal fine, definiamo la dimensione del problema W il numero asintotico di operazioni associate al miglior algoritmo seriale per risolvere il problema (in pratica è il tempo sequenziale!).

Formalismo

Il tempo parallelo può essere scritto come (ricorda che $$W = T_S$$ ):

$T_p = \frac{W + T_0 (W, p)}{p}$

Quindi, lo speedup è:

$S = \frac{W}{T_p} = \frac{W_p}{W + T_0 (W, p)}$

Alla fine, l'espressione diventa:

$E = \frac{S}{p} = \frac{W}{W + T_0 (W, p)} = \frac{1}{1 + T_0 (W, p)/W}$

Per i sistemi paralleli scalabili, l'efficienza può essere mantenuta ad un valore fisso (tra 0 e 1), se il rapporto To/W è mantenuto costante. Per un dato valore ed efficienza:

$E = \frac{1}{1 + T_0 (W, p)/W}$

$\frac{T_0 (W, p)}{W} = \frac{1 - E}{E}$

$W = \frac{E}{1-E}T_0 (W, p)$

Se K = E/(1 - E) è una costante che dipende dall'efficienza da mantenere, dato che $$T_o$$ è una funzione di W e p, si ha:

$$W = KT_0 (W, p)$$

La formula precedente prende il nome di funzione isoefficienza.

Da questa formula risulta chiaro che le dimensioni del problema W possono essere ottenute in funzione di p tramite passaggi algebrici, in modo da mantenere costante l'efficienza.

Questa funzione determina la "facilità" con cui un sistema parallelo può mantenere un'efficienza costante e, di conseguenza, raggiungere uno speedup che aumenta proporzionalmente al numero di processori.

Esempio

La funzione di overhead per il problema di sommare n numeri su p processori è approssimata da 2plog p. Sostituendo $$T_0$$ con 2plog p, si ottiene:

$W = K*2*p*\log p$

Quindi, la funzione di isoefficienza asintotica per questo sistema parallelo è:

$\Theta(p*\log p)$

Se il numero di processori viene aumentato da p a p'(cioè di un fattore p'/p), la dimensione del problema (in questo caso, n) deve essere aumentata di un fattore (p'log p')/(plog p) per ottenere la stessa efficienza dei processori p. In questo modo l'accelerazione aumenta di un fattore p'/p.

Esempio (dal libro Pacheco)

Considera la versione sequenziale della regola trapezoidale:

h = (b - a) / n;
integral = (f(a) + f(b)) / 2.0;
x = a;
for(i = 1; i <= n-1; i++) {
    x = x + h;
    integral = integral + f(x);
}
integral = integral * h;

Il tempo di esecuzione può essere approssimato da:

$T_S (n) = c_1 + c_2 (n-1) = k_1 n + k_2 \approx k_1 n$

dove n è il numero del trapezio

Consideriamo la versione parallela della regola del trapezio:

h = (b - a) / n;
local_n = n / p;

local_a = a + my_rank * local_n * h;
local_b = local_a + local_n * h;
integral = Trap(local_a, local_b, local_n, h);

MPI_Reduce(&integral, &total, 1, MPI_FLOAT, MPI_SUM, 0, MPI_COMM_WORLD);

Il tempo di esecuzione può essere approssimato da:

$T_S (n, p) = k_1 n/p + k_2 \log_2 (p) + k_3$

Essendo:

$$T_0 = p * T_P - T_S$$

Abbiamo (trascurando $$k_3$$ ):

$T_0 = k_1 n + k_2 p \log_2 (p) - k_1 n = k_2 p \log_2 (p)$

Dalla definizione di efficienza:

$E = \frac{1}{1 + \frac{T_0}{W}} = \frac{1}{1 + \frac{k_2 p \log_2 (p)}{k_1 n}} \Rightarrow n = \frac{E}{1 - E} \frac{k_2}{k_1} p \log_2 (p)$

La formula:

$E = \frac{1}{1 + \frac{T_0}{W}} = \frac{1}{1 + \frac{k_2 p \log_2 (p)}{k_1 n}}$

ci dice che, per mantenere un'efficienza costante, n dovrebbe aumentare come $p \log_2 (p)$ .

Ad esempio, sia p=4 che n=512. Se vogliamo mantenere la stessa efficienza con 8 processori (cioè 2 p), dobbiamo imporre (invece di raddoppiare n come si potrebbe pensare):

$\frac{k_2 4 \log_2 (4)}{k_1 512} = \frac{k_2 8 \log_2 (8)}{k_1 n} \Rightarrow n = 1536$