High Performance Computing

2020/2021 High performance computing – appunti

Corso laurea magistrale – Cloud computing

Sommario

• 1. Introduzione .............................................................................................................................................. 3
• 2. Multicore ................................................................................................................................................... 4
• 2.1. OpenMP ............................................................................................................................................ 4
• 2.2. Scoping .............................................................................................................................................. 4
• 2.3. Cache ................................................................................................................................................. 5
• 2.4. Task .................................................................................................................................................... 6
• 2.5. Nested Parallelism ............................................................................................................................ 7
• 2.6. NUMA ................................................................................................................................................ 7
• 3. Vectorization ............................................................................................................................................. 8
• 3.1. AVX Intrinsic ...................................................................................................................................... 8
• 3.2. Data reorganization .......................................................................................................................... 9
• 3.2.1. Array of Structures (AoS) vs Structure of Arrays (SoA) ......................................................... 10
• 3.2.2. Intel AVX .................................................................................................................................. 10
• 3.3. Autovectorization and VLA Programming ..................................................................................... 10
• 3.4. Roofline Model ............................................................................................................................... 11
• 4. GPU (Graphics Processing Unit).............................................................................................................. 12
• 4.1. GPU memory ................................................................................................................................... 13
• 4.2. GPU Reduction ................................................................................................................................ 13
• 4.3. SYCL ................................................................................................................................................. 13
• 5. FPGA ........................................................................................................................................................ 13
• 6. Optimizing Compilers.............................................................................................................................. 14

1. Introduzione

Loop reordering

Loop Reordering. L’ordine può rallentare il tempo di esecuzione, a causa della cache che si ottengono più cache miss, quindi riordiniamo per ottenere più cache hit.

Optimization flags

Optimization flags. Chiediamo al compilatore di fare ottimizzazioni al posto nostro per velocizzare il programma.

• -O0, -O1, -O2, -O3

Tiling

Tiling. È una tecnica che aiuta il riutilizzo dei dati e con conseguente riduzione di accessi alla memoria.

2. Multicore

2.1. OpenMP

OpenMP.

-fopenmp per dire al compilatore che è un programma OpenMP.

#pragma omp parallel crea un blocco di codice parallelo.

Numero di threads:

• Environment variable: OMP_NUM_THREADS=...
• By adding num_threads(num) to the parallel construct.

#pragma omp for parallelizzare il for in una sezione già parallela, altrimenti si può usare #pragma omp parallel for se stiamo parallelizzando solo quel for.

#pragma omp single in una sezione parallela fa eseguire da un solo thread il blocco che segue.

#pragma omp master viene eseguito solo dal master thread del team.

For loop scheduling: OpenMP allows to influence how the iterations are scheduled among the threads of the team, via the schedule clause:

• Schedule(static): iterazioni divise in egual modo tra tutti i thread.
• Schedule(dynamic): le iterazioni del for vengono divise man mano che vengono concluse (utile per carichi di lavoro variabili).

Race condition: almeno due thread accedono alla stessa locazione di memoria e almeno uno scrive (accesso non protetto da locks). Una critical region viene eseguita da tutti i thread, ma solo da un thread contemporaneamente #pragma omp critical (nameLock).

Mutual exclusion: due thread non possono eseguire un costrutto critico con lo stesso nome allo stesso tempo.

Barrier i thread aspettano finché tutti i thread del team corrente hanno raggiunto la barriera.

In OpenMP, le barriere sono implicite o esplicite.

• Esplicite: #pragma omp barrier.
• Implicito: tutti i costrutti di condivisione del lavoro (omp for, omp sections, omp single) contengono una barriera implicita alla fine.

2.2. Scoping

Scoping.

Di default le variabili dichiarate fuori dalle regioni parallele diventano shared all’interno, le variabili dichiarate all’interno della sezione parallela sono private (per il singolo thread).

Come condizioni dell’istruzione di OpenMP per le regioni parallele possiamo specificare lo scope di ogni variabile:

• Shared: condivise tra i threads, responsabilità del programmatore evitare che si sovrascrivano tra loro;
• Private: variabili che appartengono e sono visibili solo al singolo thread (non è inizializzata);
• First-private: la variabile sarà privata all’interno della regione parallela, ma inizializzata con il valore che aveva prima di entrare nella regione stessa;
• Last-private: il valore che aveva all’ultima iterazione del loop sarà riportato all’esterno della regione parallela.

Reduction clause è un'operazione in cui l'operatore viene applicato a tutte le variabili della lista, le variabili devono essere condivise: reduction (operatore:lista).

Crea una copia locale per i thread e poi queste copie vanno a sovrascrivere la variabile shared.

Collective Patterns: le operazioni trattano un insieme di dati come un tutto, piuttosto che come elementi separati (reduce, partition, scatter, Gather, scan);

2.3. Cache

Cache: computer memory con breve tempo di accesso usata per la memorizzazione di istruzioni o dati usati frequentemente o di recente.

Locality: i programmi tendono a usare dati e istruzioni con indirizzi vicini o uguali a quelli che hanno usato di recente:

• Località temporale: gli elementi referenziati di recente hanno la probabilità di essere referenziati di nuovo nel prossimo futuro.
• -