Appunti di Parallel Computing

Parallel Computing

2023-2024

Indice

1 INTRODUZIONE 2

1.1 Tipi di parallelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Tassonomia di Flynn . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Architetture di parallelizzazione . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Metriche per la valutazione delle prestazioni . . . . . . . . . . . . . . . . 10

1.3.1 Legge di Amdahl . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.3.2 Legge di Gustafson . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.3.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.4 Creare un programma parallelo . . . . . . . . . . . . . . . . . . . . . . . 23

2 PARALLELIZZAZIONE 28

2.1 Modelli di progettazione per programmi paralleli . . . . . . . . . . . . . 28

2.1.1 Decomposizione dei task . . . . . . . . . . . . . . . . . . . . . . . 28

2.1.2 Decomposizione dei dati . . . . . . . . . . . . . . . . . . . . . . . 29

2.1.3 Design data-oriented . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.1.4 Comunicazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.2 Esempi di strutture dati . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.3 Proprietà importanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4 Design patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.4.1 Sequenza superscalare . . . . . . . . . . . . . . . . . . . . . . . . 39

2.4.2 Parallelismo a livello di loop . . . . . . . . . . . . . . . . . . . . . 40

2.4.3 Parallelismo dei task . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.4.4 Fork-Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.4.5 SPMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.4.6 Master-Worker . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.4.7 Client-Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.4.8 Task pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.4.9 Producer-Consumer . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.4.10 Work Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.4.11 Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.4.12 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.4.13 Riduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2.4.14 Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.4.15 Stencil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.4.16 Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.5 Scambio di informazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.6 Regole per la progettazione di applicazioni multi-thread . . . . . . . . . . 52

2.7 Metodologie di progettazione . . . . . . . . . . . . . . . . . . . . . . . . 54

i

INDICE ii

3 THREADS 55

3.1 Processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2 Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2.1 Stati di un thread . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2.2 Visibilità dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.2.3 Meccanismi di sincronizzazione . . . . . . . . . . . . . . . . . . . 57

3.2.4 Controllo dell’esecuzione dei thread . . . . . . . . . . . . . . . . . 59

3.2.5 Numero di thread e sequenzializzazione . . . . . . . . . . . . . . . 59

3.2.6 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.2.7 Accesso alla memoria . . . . . . . . . . . . . . . . . . . . . . . . . 60

4 TIMING & PROFILING 63

4.1 Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.2 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.2.1 Google Perftools . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.2.2 Callgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.2.3 VTune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.3 Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5 CPU MODERNE 72

6 VETTORIZZAZIONE 80

7 OpenMP 88

7.1 Consistenza della memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.1 Coerenza sequenziale . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.2 Coerenza rilassata . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.1.3 Coerenza della memoria in OpenMP . . . . . . . . . . . . . . . . 91

7.2 Panoramica di OpenMP in e . . . . . . . . . . . . . . . . . . . . . 95

C C++

7.3 Direttive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

parallel

7.3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

for

7.3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

sections

7.3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

task

7.3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

single

7.3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

master

7.3.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

critical

7.3.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

atomic

7.3.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

barrier

7.3.10 Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

7.3.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

flush

7.3.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

threadprivate

7.4 Producer/Consumer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

7.5 Thread sanitizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

7.6 Ottimizzazione in OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . 125

7.6.1 Processo di ottimizzazione . . . . . . . . . . . . . . . . . . . . . . 129

INDICE 1

8 GPU E CUDA 135

8.1 Modello di programmazione GPU . . . . . . . . . . . . . . . . . . . . . . 150

8.2 CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

8.2.1 Gestione della memoria . . . . . . . . . . . . . . . . . . . . . . . 164

8.2.2 Organizzazione dei thread . . . . . . . . . . . . . . . . . . . . . . 166

8.2.3 Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

8.3 Memoria CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

8.3.1 Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

8.3.2 Coalescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

8.3.3 Sovrapposizione nel trasferimento dei dati . . . . . . . . . . . . . 208

8.4 Atomic CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

8.5 Privatizzazione CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

8.6 Pattern CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

8.6.1 Convoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

8.6.2 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

8.6.3 Gather . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

8.6.4 Scatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

8.6.5 Riduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

8.6.6 Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

8.7 Librerie CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

8.7.1 Thrust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

8.7.2 CuBLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

8.7.3 Fast Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

8.7.4 NVIDIA libcu++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

Capitolo 1

INTRODUZIONE

concorrente

Un sistema si dice se può supportare due o più azioni allo

in progresso

stesso momento. Ovvero, un’applicazione concorrente avrà due o più thread in pro-

gresso in un determinato momento (ad esempio, due thread vengono continuamente

scambiati dal sistema operativo su un processore a singolo core per avanzare progressi-

vamente). parallelo

Un sistema si dice se può supportare due o più azioni allo stes-

in esecuzione

so momento. Ovvero, un’applicazione parallela avrà due o più thread in esecuzione si-

multanea se il calcolatore possiede più core disponibili (ad esempio, due o più thread

vengono assegnati a core separati per essere eseguiti contemporaneamente).

N.B: possiamo considerare il parallelismo come un sottoinsieme della concorrenza,

ovvero Parallelismo Concorrenza.

⊆ core

Un programma concorrente diventa parallelo se sono disponibili abbastanza (unità

per eseguire thread (o processi multipli) simultaneamente.

di elaborazione)

Quindi, la programmazione concorrente è caratterizzata dalla composizione di pro-

cessi in esecuzione indipendente. Invece, la programmazione parallela è caratterizzata

dall’esecuzione simultanea di calcoli.

Sotto questo aspetto, la concorrenza rappresenta la gestione di molte azioni contempo-

raneamente. Invece, il parallelismo consiste nel fare molte azioni allo stesso momento.

Quindi, la concorrenza fornisce un modo di strutturare la risoluzione di un problema

che può essere parallelizzabile (ma non necessariamente).

Un algoritmo concorrente è un algoritmo strutturato in modo tale da poter eseguire i

suoi passaggi in modo indipendente. Un algoritmo concorrente può essere eseguito in

serie. Tuttavia, è necessaria una comunicazione per coordinare le esecuzioni indipenden-

ti.

Un algoritmo parallelo è progettato per eseguire più operazioni nello stesso momento. Il

parallelismo di un algoritmo può migliorare le prestazioni su diversi tipi di computer.

N.B: il termine indica la traduzione di un codice seriale in un codice

parallelizzazione

concorrente. 2

CAPITOLO 1. INTRODUZIONE 3

Per sviluppare un’applicazione, il calcolo parallelo richiede una comprensione dell’hard-

ware, del software e del parallelismo. Queste opzioni possono essere combinate per

ottenere un’efficienza e una velocità ancora maggiori.

Lo sviluppatore è responsabile del che include il codi-

livello software dell’applicazione,

ce sorgente. Nel codice sorgente, il programmatore sceglie il linguaggio di programma-

zione e le interfacce software parallele da utilizzare per sfruttare l’hardware sottostante.

Inoltre, il programmatore decide come suddividere il lavoro in unità parallele. Il com-

è progettato per tradurre il codice sorgente in una forma che l’hardware possa

pilatore

eseguire. Con queste istruzioni a disposizione, un gestisce l’esecuzione

sistema operativo

sull’hardware del computer.

Figura 1.1: La parallelizzazione si esprime in un livello di software applicativo che viene mappato

sull’hardware del computer attraverso il compilatore e il sistema operativo.

Non è detto che un algoritmo parallelo comporti dei vantaggi. Gli obiettivi della paral-

lelizzazione riguardano due aspetti principali:

• Elaborare la stessa quantità di dati in meno tempo.

• Elaborare più dati nella stessa quantità di tempo.

ES:

Consideriamo una CPU a core con hyperthreading e unità vettoriale a

16

bit. Un programma seriale che utilizza un singolo core utilizza solo lo

256 della capacità di elaborazione di questo processore. Infatti:

0.8% bit

256

cores hyperthreads possibili parallelizzazioni

× ×

16 2 = 128

bit (double)

64

Utilizzando un solo bus seriale su percorsi paralleli significa che stiamo

128

utilizzando (ovvero delle capacità di calcolo disponibili.

1 = 0.008 0.8%)

128

N.B: la larghezza in bit dell’unità vettoriale specifica il numero di istruzioni

che possono essere eseguite contemporaneamente. Pertanto, un’unità vetto-

riale di bit può eseguire contemporaneamente quattro istruzioni a bit

256 64

(double-precision) o otto istruzioni a bit (single-precision).

32

Il consumo energetico di una CPU è diventato un aspetto sempre più importante. In

una CPU la maggior parte dell’energia viene consumata per commutare gli stati dei

transistor. Questa energia è proporzionale al quadrato del valore della tensione e del-

V

la frequenza , quindi il consumo di potenza sarà . Tuttavia, la tensione

2

∝ ·

f P f V

CAPITOLO 1. INTRODUZIONE 4

necessaria per far funzionare la CPU ad una determinata frequenza è approssimativa-

mente proporzionale alla frequenza (ovvero ). Perciò, il consumo di potenza di

∝

V f

una CPU sarà proporzionale al cubo della frequenza, cioè .

3

∝

P f

Quindi, aumentando la frequenza, possiamo elaborare in un tempo minore la stessa

quantità di lavoro, ma l’energia richiesta dal sistema di calcolo dipenderà in modo qua-

dratico dalla frequenza, ovvero (questa energia verrà dissipata sotto forma di

2

∝

E f

calore).

Il parallelismo, può essere utilizzato per conservare l’energia richiesta dalla CPU. L’idea

è quella di incrementare il numero di core disponibili, ognuno dei quali opera ad una

frequenza minore. In questo modo, ogni singolo core può eseguire un numero di istru-

zioni minore in un’unita temporale, ma essi opereranno simultaneamente riducendo il

tempo di esecuzione dei task.

Le GPU hanno bisogno di molta potenza, ma grazie al parallelismo possiamo ridurre il

consumo.

ES:

Il processore Xeon E5-4660 a core di Intel ha una potenza termica di

16

W. Supponiamo che l’applicazione venga completata utilizzando pro-

120 20

cessori di questo tipo per ore. Il consumo energetico stimato per l’esecu-

24

zione dell’applicazione sarà: W

CPU) kWh

× ×

= (20 120 (24ore) = 57.60

P CPU

Supponiamo adesso di eseguire l’applicazione su quattro GPU NVIDIA Te-

sla V100 per ore. Una GPU Tesla V100 di NVIDIA ha una potenza ter-

24

mica di W. Il consumo energetico stimato per l’esecuzione dell’applica-

300

zione sarà: W

GPU) kWh

× ×

= (4 300 (24ore) = 28.80

P GPU

In generale, le GPU hanno una potenza termica superiore alle CPU, ma

possono potenzialmente ridurre il tempo di esecuzione o richiedere solo po-

che GPU per ottenere lo stesso risultato.

Osserviamo che alcuni programmi paralleli possono essere peggiori delle loro contropar-

ti sequenziali. Questo è dovuto principalmente a due fattori:

• Rallentamenti causati dall’overhead della comunicazione tra le unità di elabora-

zione.

CAPITOLO 1. INTRODUZIONE 5

• Alcuni algoritmi paralleli sono più veloci solo quando le dimensioni del problema

sono molto grandi.

1.1 Tipi di parallelismo

Analizziamo i principali tipi di parallelismo:

Bit-Level:

• rappresenta la forma di calcolo parallelo che si basa sull’aumento del-

la dimensione delle parole del processore. In questo tipo di parallelismo, l’aumen-

to della dimensione della parola riduce il numero di istruzioni che il processore

deve eseguire per compiere un’operazione su dati di grandi dimensioni (ovvero, le

cui dimensioni sono maggiori della lunghezza della parola).

Ad esempio, consideriamo uno scenario in cui un processore a bit deve calcolare

8

la somma di due numeri interi a bit. A tale scopo è necessario effettuare una

32

sequenza di operazioni ad bit, richiedendo quindi quattro istruzioni per eseguire

8

l’operazione (si sommano in modo sequenziale parti di bit dei due numeri). Al

8

contrario, un processore a bit può eseguire la somma in un solo passaggio.

32

Instruction-Level:

• rappresenta la forma di calcolo parallelo che si basa sull’e-

secuzione simultanea di più istruzioni di un programma. Alcune soluzioni che

implementano questo tipo di parallelismo sono:

– Pipelining: le istruzioni vengono eseguite in modo sovrapposto (si eseguono

istruzioni diverse in modo simultaneo, ciascuna in una fase diversa).

– Esecuzione Out-of-Order (O-o-O): le istruzioni vengono eseguite in qual-

siasi ordine che non violi le dipendenze dai dati.

– Esecuzione speculativa: le istruzioni vengono programmate prima di de-

terminare la necessità della loro esecuzione. Deve tenere conto della possibi-

lità che il comportamento previsto non sia corretto.

Data-Level:

• rappresenta la forma di calcolo parallelo che si basa sull’esecuzio-

ne simultanea della stessa istruzione su un insieme di dati (ovvero, si esegue una

singola istruzione su una grande quantità di dati in parallelo). Questo tipo di pa-

SIMD Instruction Multiple

rallelizzazione è conosciuta anche come (Single

Data).

Task-Level:

• rappresenta la forma di calcolo parallelo che si basa sulla scompo-

sizione di un task in sotto-task. Ciascuno di essi viene allocato per essere ese-

guito in modo simultaneo. Esistono due varianti importanti, legate al modello

di memoria sottostante:

– Memoria Condivisa: i processori condividono lo stesso spazio degli indiriz-

zi (ovvero, ogni CPU accede a qualsiasi posizione di memoria), semplificando

la programmazione. In questo caso, la (Inter-

comunicazione tra i processi

Process Communication IPC)

o avviene attraverso la memoria e quindi

risulta essere rapida. Tuttavia, questa soluzione introduce potenziali conflitti

di memoria, con conseguenti problemi di correttezza e prestazioni (infat-

ti, sincronizzare l’accesso alla memoria e i valori tra le CPU è complicato e

CAPITOLO 1. INTRODUZIONE 6

costoso). Inoltre, questa soluzione risul