Domande e risposte esame Calcolo parallelo

Domande e risposte calcolo parallelo

Autori

Vincenzo Longobardo
Prof.ssa Livia Marcellino
Prof. Pasquale De Luca

Private, first private e last private

• Private (list): Gli argomenti contenuti in List sono privati per ogni thread che li utilizza. Ciò significa che ogni thread avrà la propria copia delle variabili private, che saranno tutte inizializzate a 0.
• First private (list): Come Private, ma le variabili mantengono il valore che avevano prima di entrare nella regione parallela (solo per parallel).
• Last private (list): Come Private, ma il valore delle variabili verrà aggiornato una volta usciti dalla regione parallela (solo per for).

Reduction

Reduction (operatore: list): Gli argomenti contenuti in list verranno combinati utilizzando l'operativo associativo specificato. Ogni Thread avrà una copia privata delle variabili in list, e al termine del costrutto la variabile sarà condivisa. È utile perché evita il verificarsi di race condition sulla variabile.

Thread vs processo

• Un thread: È un flusso di istruzioni indipendente che deve essere eseguito sequenzialmente su una CPU.
• Un processo: È un programma in esecuzione. Un processo è costituito da almeno un thread (può contenerne più di uno).

Il costrutto che sposa la formula fork-join

In OpenMP il modello d'esecuzione parallela è quello fork-join, tutti i processi cominciano con un solo thread (master thread) che esegue in maniera sequenziale. Fork: comincia una regione parallela, viene quindi creato un team di thread che procede parallelamente. Join: tutti i thread del team hanno terminato le istruzioni della regione parallela, si sincronizzano e terminano, lasciando proseguire solo il master thread. Il costrutto che sposa questa formula fork-join è il FOR che ci permette di distribuire le iterazioni tra i thread del team.

Speed Up, Overhead, Efficienza

• Speed Up: Siano T1 e Tp il tempo di esecuzione di un algoritmo in un ambiente di calcolo dotato rispettivamente di 1 e di p processori/core, lo speed up Sp indica di quanto si riduce il tempo d'esecuzione di un algoritmo su p processori rispetto alla versione sequenziale ed è definito come il rapporto di T1 su Tp. Sp= T1/Tp. Un algoritmo parallelo, è tanto più veloce quanto più lo speed up si avvicina allo speed up ideale ovvero Sp=p.
• Overhead: L'overhead totale Oh(p) misura la differenza fra lo speed up ottenuto e lo speed up ideale Oh= pTp-T1. In una situazione ideale Oh = 0. Sebbene usare più processori comporta una riduzione del tempo di esecuzione, comporta anche maggior overhead, e dunque l'algoritmo risulta meno efficiente.
• Efficienza: L'efficienza Ep di un algoritmo parallelo è definita come il rapporto fra lo speed up e il numero di processori Ep= Sp/p e quantifica lo sfruttamento del parallelismo del calcolatore da parte dell'algoritmo. Tanto più l'efficienza di un algoritmo si avvicina ad 1, tanto più l'algoritmo parallelo sfrutta le risorse di calcolo (cioè, è efficiente). Un'efficienza ideale sarebbe uguale a 1, ma nella realtà avremo sempre un numero < 1.

Legge Amdahl base e generalizzata

Legge di Amdahl base

Esempio, 1 strategia
Supponiamo di avere: p=8, N=32, nloc=4 (n/p, ie quanti numeri deve sommare ogni proc). La prima domanda che devo pormi è: “questa strategia prevede una netta distinzione fra la parte sequenziale e parallela”. Se sì, non ho bisogno della WAG ma posso usare la più semplice WA.

Infatti, in questo caso ho una netta distinzione e dunque possiamo usare direttamente la WA. In sequenziale, T(1) = N-1= 32-1 = 31 somme.

• Fase 1: Si tratta di una fase tutta parallela, in quanto ogni unità processante effettuerà le proprie somme. In particolare, ogni p farà nloc-1 somme, cioè 4-1= 3 somme. Siccome ogni processore effettua 3 somme, ed abbiamo 8 processori, nella prima fase effettuiamo 3x8=24 somme delle 31 totali. Dunque, la parte parallela (1-a) = 24/31. Possiamo già calcolare (1-a)/p = 3/31.
• Fase 2: Si tratta di una fase tutta sequenziale, in quanto il processore Master si occupa di effettuare la somma totale. Essendo i processori 8, significa che avremo 8 somme parziali. Il processore Master dovrà effettuare la somma totale a partire dalle somme parziali. In particolare, dovrà effettuare p-1 somme (7 somme). Dunque, la parte sequenziale a = 7/31.

È importante che dalla somma della parte sequenziale e della parte parallela otteniamo 1. Infatti, 24/31 + 7/31 = 31/31 = 1. Dunque abbiamo fatto bene i conti. Adesso ci rimane da calcolare lo Speed Up con WA: NB: in effetti 7 somme sequenziali sono un po’ tante.

Legge di Amdahl Generalizzata

La formula di Ware Amdahl Generalizzata (WAG) viene in nostro soccorso per quegli algoritmi che non hanno una netta separazione fra la parte sequenziale e la parte parallela.

Dove:
- a1 rappresenta le operazioni eseguite in sequenziale;
- ak rappresenta le operazioni eseguite con parallelismo medio, cioè quelle operazioni eseguite parallelamente su k processori (con k < p), ovvero solo su una porzione di questi;
- ap rappresenta le operazioni eseguite con parallelismo totale, cioè su tutti i p.

ak parte da 2 e termina a p-1 perché a1 sarebbe la parte sequenziale e ap sarebbe la parte completamente parallela.

• Esempio, 2/3 strategia: nb: i risultati per la 2 e 3 strategia sono gli stessi nel calcolo di WA perché le somme uguali non sono considerate (infatti la 3 strategia fa più somme, ma servono solo per avere lo stesso risultato in tutti i processori e non fare il broadcast dopo, e non porta alcun vantaggio in termini di velocità dell’algoritmo). Supponiamo di avere: p=8, N=32, nloc=4.