Appunti di Parallel Computing

Parallel Computing 2023-2024

Indice

1 Introduzione 21.1 Tipi di parallelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.1 Tassonomia di Flynn . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Architetture di parallelizzazione . . . . . . . . . . . . . . . . . . . . . . . 91.3 Metriche per la valutazione delle prestazioni . . . . . . . . . . . . . . . . 101.3.1 Legge di Amdahl . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.2 Legge di Gustafson . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.4 Creare un programma parallelo . . . . . . . . . . . . . . . . . . . . . . . 23

2 Parallelizzazione 282.1 Modelli di progettazione per programmi paralleli . . . . . . . . . . . . . 282.1.1 Decomposizione dei task . . . . . . . . . . . . . . . . . . . . . . . 282.1.2 Decomposizione dei dati . . . . . . . . . . . . . . . . . . . . . . . 292.1.3 Design data-oriented . . . . . . . . . . . . . . . . . . . . . . . . . 332.1.4 Comunicazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.2 Esempi di strutture dati . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.3 Proprietà importanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.4 Design patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.4.1 Sequenza superscalare . . . . . . . . . . . . . . . . . . . . . . . . 392.4.2 Parallelismo a livello di loop . . . . . . . . . . . . . . . . . . . . . 402.4.3 Parallelismo dei task . . . . . . . . . . . . . . . . . . . . . . . . . 412.4.4 Fork-Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.4.5 SPMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.4.6 Master-Worker . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.4.7 Client-Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.4.8 Task pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.4.9 Producer-Consumer . . . . . . . . . . . . . . . . . . . . . . . . . 442.4.10 Work Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.4.11 Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.4.12 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.4.13 Riduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.4.14 Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.4.15 Stencil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.4.16 Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.5 Scambio di informazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 492.6 Regole per la progettazione di applicazioni multi-thread . . . . . . . . . . 522.7 Metodologie di progettazione . . . . . . . . . . . . . . . . . . . . . . . . 54i

Indice ii3 Threads 553.1 Processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.2 Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.2.1 Stati di un thread . . . . . . . . . . . . . . . . . . . . . . . . . . 563.2.2 Visibilità dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.2.3 Meccanismi di sincronizzazione . . . . . . . . . . . . . . . . . . . 573.2.4 Controllo dell’esecuzione dei thread . . . . . . . . . . . . . . . . . 593.2.5 Numero di thread e sequenzializzazione . . . . . . . . . . . . . . . 593.2.6 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.2.7 Accesso alla memoria . . . . . . . . . . . . . . . . . . . . . . . . . 60

4 Timing & Profiling 634.1 Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.2 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.2.1 Google Perftools . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.2.2 Callgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.2.3 VTune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.3 Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5 CPU moderne 726 Vettorizzazione 807 OpenMP 887.1 Consistenza della memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 897.1.1 Coerenza sequenziale . . . . . . . . . . . . . . . . . . . . . . . . . 897.1.2 Coerenza rilassata . . . . . . . . . . . . . . . . . . . . . . . . . . 907.1.3 Coerenza della memoria in OpenMP . . . . . . . . . . . . . . . . 917.2 Panoramica di OpenMP in e . . . . . . . . . . . . . . . . . . . . . 95C C++7.3 Direttive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98parallel7.3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101for7.3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106sections7.3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107task7.3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108single7.3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109master7.3.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109critical7.3.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110atomic7.3.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112barrier7.3.10 Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1127.3.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115flush7.3.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119threadprivate7.4 Producer/Consumer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1207.5 Thread sanitizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1237.6 Ottimizzazione in OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . 1257.6.1 Processo di ottimizzazione . . . . . . . . . . . . . . . . . . . . . . 129

Indice 18 GPU e CUDA 1358.1 Modello di programmazione GPU . . . . . . . . . . . . . . . . . . . . . . 1508.2 CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1598.2.1 Gestione della memoria . . . . . . . . . . . . . . . . . . . . . . . 1648.2.2 Organizzazione dei thread . . . . . . . . . . . . . . . . . . . . . . 1668.2.3 Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1678.3 Memoria CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1838.3.1 Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1918.3.2 Coalescence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2008.3.3 Sovrapposizione nel trasferimento dei dati . . . . . . . . . . . . . 2088.4 Atomic CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2098.5 Privatizzazione CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2138.6 Pattern CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2168.6.1 Convoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2168.6.2 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2298.6.3 Gather . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2298.6.4 Scatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2298.6.5 Riduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2298.6.6 Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2328.7 Librerie CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2358.7.1 Thrust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2358.7.2 CuBLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2378.7.3 Fast Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2388.7.4 NVIDIA libcu++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

Capitolo 1 introduzione

Un sistema si dice concorrente se può supportare due o più azioni allo stesso momento. Ovvero, un’applicazione concorrente avrà due o più thread in progresso in un determinato momento (ad esempio, due thread vengono continuamente scambiati dal sistema operativo su un processore a singolo core per avanzare progressivamente).

Un sistema si dice parallelo se può supportare due o più azioni allo stesso momento. Ovvero, un’applicazione parallela avrà due o più thread in esecuzione simultanea 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.

Un programma concorrente diventa parallelo se sono disponibili abbastanza core (unità di elaborazione) per eseguire thread (o processi multipli) simultaneamente.

Quindi, la programmazione concorrente è caratterizzata dalla composizione di processi in esecuzione indipendente. Invece, la programmazione parallela è caratterizzata dall’esecuzione simultanea di calcoli.

Sotto questo aspetto, la concorrenza rappresenta la gestione di molte azioni contemporaneamente. 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 indipendenti.

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 parallelizzazione indica la traduzione di un codice seriale in un codice concorrente. 2

Capitolo 1. Introduzione 3

Per sviluppare un’applicazione, il calcolo parallelo richiede una comprensione dell’hardware, del software e del parallelismo. Queste opzioni possono essere combinate per ottenere un’efficienza e una velocità ancora maggiori.

Lo sviluppatore è responsabile del livello software dell’applicazione, che include il codice sorgente. Nel codice sorgente, il programmatore sceglie il linguaggio di programmazione e le interfacce software parallele da utilizzare per sfruttare l’hardware sottostante. Inoltre, il programmatore decide come suddividere il lavoro in unità parallele. Il compilatore è progettato per tradurre il codice sorgente in una forma che l’hardware possa eseguire. Con queste istruzioni a disposizione, un sistema operativo gestisce l’esecuzione 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 parallelizzazione 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 0.8% della capacità di elaborazione di questo processore. Infatti: bit 256 cores hyperthreads possibili parallelizzazioni × × 16 2 = 128 bit (double) 64

Utilizzando un solo bus seriale su percorsi paralleli significa che stiamo utilizzando 1 = 0.008 ovvero 0.8% delle capacità di calcolo disponibili. 128

N.B: la larghezza in bit dell’unità vettoriale specifica il numero di istruzioni che possono essere eseguite contemporaneamente. Pertanto, un’unità vettoriale di bit 256 può eseguire contemporaneamente quattro istruzioni a bit 64 (double-precision) o otto istruzioni a bit 32 (single-precision).

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 V e della frequenza f, quindi il consumo di potenza sarà ∝ f · V². Tuttavia, la tensione necessaria per far funzionare la CPU ad una determinata frequenza è approssimativamente proporzionale alla frequenza (ovvero V ∝ f). Perciò, il consumo di potenza di

Capitolo 1. Introduzione 4

una CPU sarà proporzionale al cubo della frequenza, cioè 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 quadratico dalla frequenza, ovvero E ∝ f² (questa energia verrà dissipata sotto forma di 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 istruzioni minore in un’unità 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 processori di questo tipo per ore. Il consumo energetico stimato per l’esecuzione dell’applicazione sarà: W CPU) kWh × × = (20 120 (24 ore) = 57.60 P CPU

Supponiamo adesso di eseguire l’applicazione su quattro GPU NVIDIA Tesla V100 per ore. Una GPU Tesla V100 di NVIDIA ha una potenza termica di 24 mica di W. Il consumo energetico stimato per l’esecuzione dell’applicazione sarà: 300 W GPU) kWh × × = (4 300 (24 ore) = 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 poche GPU per ottenere lo stesso risultato.

Osserviamo che alcuni programmi paralleli possono essere peggiori delle loro controparti sequenziali. Questo è dovuto principalmente a due fattori:

• Rallentamenti causati dall’overhead della comunicazione tra le unità di elaborazione.

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 della dimensione delle parole del processore. In questo tipo di parallelismo, l’aumento 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’esecuzione 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 qualsiasi ordine che non violi le dipendenze dai dati.
• Esecuzione speculativa: le istruzioni vengono programmate prima di determinare la necessità della loro esecuzione. Deve tenere conto della possibilità che il comportamento previsto non sia corretto.
• Data-Level: rappresenta la forma di calcolo parallelo che si basa sull’esecuzione 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 parallelizzazione è conosciuta anche come SIMD (Single Instruction Multiple Data).
• Task-Level: rappresenta la forma di calcolo parallelo che si basa sulla scomposizione di un task in sotto-task. Ciascuno di essi viene allocato per essere eseguito in modo simultaneo. Esistono due varianti importanti, legate al modello di memoria sottostante:
• Memoria Condivisa: i processori condividono lo stesso spazio degli indirizzi (ovvero, ogni CPU accede a qualsiasi posizione di memoria), semplificando la programmazione. In questo caso, la comunicazione tra i processi (Inter-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 (infatti, sincronizzare l’accesso alla memoria e i valori tra le CPU è complicato e

Capitolo 1. Introduzione 6 costo). Inoltre, questa soluzione risul