Appunti di Parallel Computing

T

1

soddisfatta una determinata condizione. Questa condizione potrebbe basarsi su

variabili condivise che devono avere un valore specifico o uno stato specifico, come

ad esempio un buffer condiviso che deve contenere almeno un elemento.

3.2.5 Numero di thread e sequenzializzazione

A seconda della progettazione e dell’implementazione, il tempo di esecuzione di un pro-

gramma parallelo basato su thread può variare significativamente. Nella progettazione

di un programma parallelo, è fondamentale:

• Utilizzare un numero adeguato di thread, da selezionare in base al grado di paral-

lelismo fornito dall’applicazione e al numero di risorse di esecuzione disponibili.

• Evitare, quando possibile, la sequenzializzazione mediante operazioni di sincro-

nizzazione. Quando la sincronizzazione è necessaria (ad esempio, per evitare race

conditions) è importante che la sezione critica risultante, eseguita in modo se-

quenziale, sia mantenuta più piccola possibile per ridurre al minimo i tempi di

attesa.

Un programma parallelo dovrebbe creare un numero di thread sufficiente per sfruttare

tutti i core disponibili sulla piattaforma di esecuzione. Tuttavia, se il numero di thread

è troppo elevato, si può incorrere in overhead aggiuntivi dovuti alla creazione, gestione

e terminazione dei thread, nonché all’accesso alle risorse condivise, come la cache. Inol-

tre, l’uso eccessivo della sincronizzazione può comportare la sequenzializzazione delle

operazioni, vanificando l’obiettivo del parallelismo.

3.2.6 Deadlock

Le problematiche legate al comportamento non deterministico e alle race conditions

possono essere mitigate attraverso l’uso di meccanismi di sincronizzazione. Tuttavia, è

deadlock,

importante sottolineare che l’impiego dei lock può condurre a situazioni di

una condizione in cui l’esecuzione del programma si trova in uno stato nel quale ogni

thread attende un evento che può essere causato solo da un altro thread, che a sua

volta è in attesa. In generale, si verifica una deadlock per un insieme di task quando

ciascuno di essi attende un evento che può essere causato solo da uno degli altri task,

creando così un ciclo di attesa reciproca.

CAPITOLO 3. THREADS 60

Un esempio di deadlock può verificarsi quando due thread, denominati e , utilizza-

T T

1 2

no due lock distinti e :

s s

1 2

Thread Thread

T T

1 2

lock(s ); lock(s );

1 2

lock(s ); lock(s );

2 1

do work (); do work ();

unlock (s ); unlock (s );

2 1

unlock (s ); unlock (s );

1 2

In questa situazione, è bloccato da , mentre è bloccato da . Entrambi i thread

s T s T

1 1 2 2

e attendono che l’altro thread rilasci il lock mancante. Tuttavia, questo rilascio

T T

1 2

non può verificarsi, poiché ciascun thread è in una fase di attesa.

Esistono quattro condizioni fondamentali associate alla creazione di una situazione di

deadlock:

Mutua esclusione:

• condizione in cui una risorsa può essere accessibile solo da

un thread o processo alla volta. In altre parole, quando una risorsa è stata acqui-

sita da un thread, altri thread devono attendere che questa risorsa venga rilascia-

ta prima di poterla utilizzare.

Hold and wait:

• si verifica quando i thread mantengono alcune risorse e, contem-

poraneamente, ne richiedono altre. Questo significa che un thread può trattenere

risorse mentre aspetta di ottenere ulteriori risorse di cui ha bisogno.

No preemption:

• tale condizione indica che una risorsa può essere rilasciata so-

lo volontariamente dal thread che la detiene. In altre parole, un thread non può

essere interrotto o privato delle risorse che detiene in modo forzato da parte del

sistema.

Attesa circolare:

• si verifica quando c’è un ciclo di attesa tra due o più thread,

ognuno dei quali attende il rilascio di una risorsa detenuta da un altro thread nel

ciclo. Questo ciclo di attesa impedisce che qualsiasi thread rilasci le risorse che

detiene, poiché ciascun thread attende che un altro rilasci una risorsa necessaria.

N.B: livelock

il è una situazione simile al deadlock, ma con una differenza significati-

va. Mentre in un deadlock i processi sono completamente bloccati, nel livelock gli sta-

ti dei processi coinvolti cambiano costantemente, ma nessuno di essi fa effettivamente

progressi.

3.2.7 Accesso alla memoria

I tempi di accesso alla memoria possono costituire una parte significativa del tempo di

esecuzione di un programma parallelo. Quando un programma effettua l’accesso alla

memoria, causa il trasferimento di dati dalla memoria principale alla gerarchia di cache

del core responsabile dell’accesso alla memoria. Questo trasferimento di dati è causato

dalle operazioni di lettura e scrittura effettuate dai core.

A seconda del particolare schema di accesso alla memoria, non solo si verifica un trasfe-

rimento di dati dalla memoria principale alle cache locali dei core coinvolti, ma può an-

che verificarsi un trasferimento tra le cache locali dei core stessi. Il comportamento pre-

ciso di questi trasferimenti è controllato dall’hardware e non è influenzato direttamente

dal programmatore.

CAPITOLO 3. THREADS 61

False Sharing

Il fenomeno di si verifica quando due thread e , in esecuzione su

T T

1 2

core diversi, accedono a posizioni di memoria diverse che si trovano nella stessa linea

di cache. In questo caso, è necessario eseguire le stesse operazioni di memoria come se

stessero accedendo alle stesse locazioni di memoria. Questo accade perché la linea di

cache rappresenta la più piccola unità di trasferimento nella gerarchia della memoria.

Il False Sharing può comportare un considerevole numero di trasferimenti di memoria e

un significativo degrado delle prestazioni complessive del programma parallelo. Una so-

luzione per evitare il False Sharing consiste nell’allineare le variabili o gli oggetti in me-

moria ai confini delle linee di cache. In questo modo, è possibile garantire che le varia-

bili utilizzate da thread diversi non condividano la stessa linea di cache e, quindi, non

siano soggette a False Sharing. Alcuni compilatori supportano direttive di allineamento.

Per mitigare il problema del False Sharing, è importante prestare attenzione a diverse

situazioni in cui due oggetti vengono acceduti (in lettura o in scrittura) frequentemente

da parte di thread diversi, almeno uno dei quali sta effettuando operazioni di scrittu-

ra. Questi oggetti o campi di dati possono essere così vicini in memoria da finire sulla

stessa linea di cache. Le situazioni da tenere in considerazione includono:

• Oggetti vicini nello stesso array: se due oggetti o campi sono parte dello stesso

array e sono frequentemente acceduti da thread diversi, potrebbero condividere

una linea di cache.

• Campi vicini nello stesso oggetto: campi di dati adiacenti all’interno dello stesso

oggetto possono essere soggetti a False Sharing se vengono frequentemente letti o

scritti da thread diversi.

• Oggetti allocati vicini nel tempo o dallo stesso thread: alcuni linguaggi di pro-

grammazione allocano oggetti in modo contiguo in memoria. Se oggetti allocati

CAPITOLO 3. THREADS 62

consecutivamente sono frequentemente accessibili da thread diversi, potrebbero

finire sulla stessa linea di cache.

• Oggetti statici o globali disposti vicini in memoria dal linker: in alcuni casi, il

linker potrebbe disporre oggetti statici o globali vicini in memoria, portando a

False Sharing se questi oggetti sono frequentemente acceduti da thread diversi.

• Oggetti che diventano vicini in memoria in modo dinamico, come durante la com-

pattazione della garbage collection: in linguaggi con garbage collection, l’alloca-

zione e la compattazione dinamiche della memoria possono portare a oggetti che

diventano vicini in memoria e soggetti a False Sharing.

Per mitigare la False Sharing, è possibile seguire alcune buone pratiche:

• Ridurre il numero di scritture nella linea di cache. I thread che effettuano scrittu-

re possono temporaneamente scrivere i risultati intermedi in una variabile scratch

e aggiornare la variabile nella linea di cache solo occasionalmente, quando è stret-

tamente necessario. In questo modo, si riduce la competizione per la stessa linea

di cache.

• Separare le variabili in modo che non condividano la stessa linea di cache. Possia-

mo assicurarci che ogni oggetto abbia una linea di cache dedicata e non condivisa

con altri dati. Ciò può essere realizzato garantendo che nessun altro oggetto si

trovi prima o dopo i dati nella stessa riga di cache, allineando gli oggetti all’inizio

della riga di cache o aggiungendo del padding prima e dopo l’oggetto se necessa-

rio. Alcuni compilatori supportano direttive di allineamento per facilitare questa

pratica.

Capitolo 4

TIMING & PROFILING

4.1 Timing

Per profilare il codice e misurare il tempo di esecuzione delle diverse parti di un pro-

gramma, un approccio comune consiste nell’aggiungere timer al codice. Consideran-

do un esempio in linguaggio e utilizzando la libreria standard, è possibile valuta-

C

re quanto tempo è necessario per eseguire sia le versioni sequenziali che parallele del

codice.

La libreria offre diverse funzioni per misurare il tempo. Tra queste:

C

• La funzione della libreria restituisce il numero di cicli di clock

clock() <time.h>

del processore trascorsi dal momento in cui il programma è stato avviato. Questo

valore rappresenta una misura approssimativa del tempo di utilizzo della CPU da

parte del processo, conteggiando dall’inizio di un’epoca definita dall’implementa-

zione relativa all’esecuzione del programma.

Per ottenere il tempo in secondi, è necessario dividere il valore restituito da clock()

per una costante CLOCKS_PER_SEC.

N.B: solo la differenza tra due valori restituiti da chiamate diverse a clock()

è significativa per misurare il tempo trascorso, poiché l’inizio dell’era del clock

potrebbe non coincidere con l’inizio effettivo del programma. Pertanto, dobbia-

mo utilizzare prima e dopo l’esecuzione di una parte specifica del codice

clock()

che desideri profilare, quindi calcolare la differenza tra i due valori per ottenere il

tempo di esecuzione di quella parte specifica.

N.B: in un programma sequenziale il tempo del processore è approssimativamen-

te uguale al tempo di esecuzione complessivo del programma. Tuttavia, lo stesso

non vale per un programma parallelo. Infatti, in un programma parallelo, la fun-

zione restituisce il tempo totale trascorso nella CPU da tutti