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

L’ordine può rallentare il tempo esecuzione, a causa della cache che si ottengono più cache miss, quindi

riordiniamo per ottenere più cache hit.

Optimization flags

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

-O0, -O1, -O2, -O3

Tiling

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

2. Multicore

OpenMP

2.1.

-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 eseguiro 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 iterazione 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.

Scoping

2.2.

di default le variabili dichiarate fuori le 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à riportata 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);

Cache

2.3.

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.

-