Calcolo parallelo

Calcolo parallelo - Appunti

Università degli Studi di Napoli Parthenope, CdS in Informatica

Camilla De Martino

A.A. 2022/2023

Indice

1 Introduzione 4

1.1 Lezione 0 - Introduzione al corso . . . . . . . . . . . . . . . . . . 4

1.2 Lezione 1 - Motivazioni del parallelismo . . . . . . . . . . . . . . 4

2 Tipi di parallelismo 6

2.1 Lezione 2 - Classificazione di Flynn . . . . . . . . . . . . . . . . 6

2.1.1 Parallelismo temporale . . . . . . . . . . . . . . . . . . . 8

2.1.2 Parallelismo spaziale . . . . . . . . . . . . . . . . . . . . 8

2.1.3 Parallelismo asincrono . . . . . . . . . . . . . . . . . . . 9

2.1.4 Calcolo parallelo vs calcolo distribuito . . . . . . . . . . 11

3 Somma di N numeri su architetture MIMD 13

3.1 Lezione 4 - Parallelismo delle architetture MIMD-SM . . . . . . . 13

3.1.1 Somma tra vettori . . . . . . . . . . . . . . . . . . . . . . 16

3.1.2 Somma di elementi dello stesso vettore . . . . . . . . . . . 18

4 Parametri di valutazione di un algoritmo - pt1 22

4.1 Lezione 5 - Introduzione all’efficienza di un algoritmo parallelo . 22

4.1.1 Cosa si intende per efficienza di un algoritmo? . . . . . . 22

5 Parametri di valutazione di un algoritmo - pt2 36

5.1 Lezione 6 - Legge di Ware-Amdahl . . . . . . . . . . . . . . . . . 36

5.1.1 Analisi asintotica dello speed-up . . . . . . . . . . . . . . 38

5.1.2 Legge di Ware (Amdahl) . . . . . . . . . . . . . . . . . . 42

6 Isoefficienza e scalabilità di un algoritmo parallelo 47

6.1 Lezione 8 - I parametri di valutazione di un algoritmo parallelo: isoefficienza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.1.1 Somma di due vettori . . . . . . . . . . . . . . . . . . . . 48

6.1.2 Somma di N numeri in parallelo . . . . . . . . . . . . . . 48

6.1.3 Stime e calcoli sui due nuclei computazionali . . . . . . . 53

1 Capitolo 0 – Indice

7 Stima metriche algoritmi paralleli per la somma 60

7.1 Lezione 11 - Calcolo di speedup, overhead ed efficienza (def classica) Ware-Amdahl . . . . . . . . . . . . . . . . . . . . . . . . . . 60

7.1.1 Somma di due vettori di dimensione N . . . . . . . . . . . 62

7.1.2 Somma di N numeri . . . . . . . . . . . . . . . . . . . . . 63

7.1.3 Somma vettori N non esattamente divisibile . . . . . . . . 70

7.1.4 Somma N numeri non esattamente divisibile . . . . . . . . 71

7.1.5 Calcolo dell’isoefficienza . . . . . . . . . . . . . . . . . . . 72

7.2 Esercitazione aggiuntiva: W-A generalizzata, nei casi della non divisibilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

7.2.1 Somma 2 vettori . . . . . . . . . . . . . . . . . . . . . . . 73

7.2.2 Somma N numeri I strategia . . . . . . . . . . . . . . . . 75

7.2.3 Somma N numeri II strategia . . . . . . . . . . . . . . . . 77

8 Prodotto scalare 83

8.1 Lezione 14 - Prodotto scalare in ambiente multicore - Strategie di parallelizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.1.1 Calcolo di speed-up, overhead ed efficienza (def classica) . 85

8.1.2 Isoefficienza . . . . . . . . . . . . . . . . . . . . . . . . . . 90

8.1.3 Speedup usando la legge di Ware-Amdahl generalizzata . 92

9 Algoritmi full-parallel per dati 2D (matrici) 96

9.1 Lezione 16 - Prodotto scalare per matrice . . . . . . . . . . . . . 96

9.1.1 I strategia - blocchi righe . . . . . . . . . . . . . . . . . . 97

9.1.2 II strategia - blocchi colonne . . . . . . . . . . . . . . . . 98

9.1.3 III strategia - blocchi righe/colonne . . . . . . . . . . . 98

9.1.4 Strategie di parallelizzazione per problemi di tipo element-wise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

9.2 Lezione 17 - Valutazione strategie . . . . . . . . . . . . . . . . . 100

9.2.1 Calcolo di speedup, overhead ed efficienza (def classica) . 100

10 Prodotto matrice per vettore 103

10.1 Lezione 19 - MatriceXvettore, strategie standard di parallelizzazione in ambiente multicore . . . . . . . . . . . . . . . . . . . . . 103

10.1.1 I strategia - blocchi righe . . . . . . . . . . . . . . . . . 104

10.1.2 II strategia - blocchi colonne . . . . . . . . . . . . . . . 105

10.1.3 III strategia - blocchi righe/colonne . . . . . . . . . . . 107

10.2 Lezione 20 - Approfondimenti matrice per vettore I e II strategia 108

10.2.1 I strategia - blocchi righe . . . . . . . . . . . . . . . . . 109

10.2.2 II strategia - blocchi colonne . . . . . . . . . . . . . . . 111

10.3 Lezione 22 - Approfondimenti matrice per vettore 3 strategia . . . 118

10.3.1 Osservazioni . . . . . . . . . . . . . . . . . . . . . . . . 123

10.4 Lezione 25 - Matrice per vettore 3 strategia - caso della non esatta divisibilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

10.4.1 Righe non esattamente divisibili . . . . . . . . . . . . . 124

10.4.2 Colonne non esattamente divisibili . . . . . . . . . . . . 126

2 Capitolo 0 – Indice

10.4.3 Righe e colonne non esattamente divisibili . . . . . . . . 127

10.4.4 Isoefficienza - I strategia . . . . . . . . . . . . . . . . . 129

10.4.5 Isoefficienza - II strategia . . . . . . . . . . . . . . . . . 129

10.5 Lezione 27 - Matrice per vettore 3 strategia - legge di Ware-Amdahl 130

10.5.1 I strategia . . . . . . . . . . . . . . . . . . . . . . . . . . 132

10.5.2 II strategia . . . . . . . . . . . . . . . . . . . . . . . . . 134

3

Capitolo 1

Introduzione

1.1 Lezione 0 - Introduzione al corso

Il calcolo ad alte prestazioni (HPC, High Performance Computing) è quella branca dell’informatica che realizza infrastrutture in grado di realizzare enormi quantità di calcoli in brevi tempi.

Il vero scopo di un super computer è quello di risolvere problemi. È detto “super” in quanto si tratta del sistema che fornisce le prestazioni più elevate, in quel momento.

In particolar modo, potrei volere una macchina ad alte prestazioni per risolvere problemi in “tempo reale (utile)” (es. previsioni meteo), o per risolvere problemi di grandi dimensioni.

Lo sviluppo tecnologico di una nazione può essere misurata attraverso la potenza dei suoi sistemi HPC.

Con benchmark si intende un insieme di test software utilizzati per misurare le prestazioni di un sistema. Con un Linpack benchmark si risolve un sistema denso di equazioni lineari.

1.2 Lezione 1 - Motivazioni del parallelismo

In generale, il tempo richiesto per l’esecuzione di un software (τ) è:

τ (1.1)

* *

τ = k T (n) μ

dove:

• K: rappresenta il “tempo sprecato” dalla macchina per fare altre cose. È una costante moltiplicativa aleatoria che rappresenta ad esempio i tempi di I/O o ritardi relativi alla scrittura in memoria, dunque un valore fisso. Si tratta dell’elemento più imprevedibile;

4 Capitolo 1 – Introduzione

• T(n): rappresenta la complessità computazionale dell’algoritmo, inteso come numero di operazioni da fare. Dipende dall’algoritmo;
• μ: rappresenta il tempo di esecuzione di una operazione floating point. Dipende dal calcolatore.

n.b: T(n) non deve essere confuso con τ, solo quest’ultimo rappresenta il tempo effettivo.

L’obiettivo sarà quello di avere un τ quanto più ridotto possibile al fine di ridurre il tempo di esecuzione del software, e per far ciò si deve cercare di ridurre k, T (n) e μ quanto più possibile:

• K: si deve cercare di tenere la macchina quanto più “libera” possibile (modificando la tecnologia). Computer con una diversa rappresentazione numerica nella memorizzazione dei dati (accesso più rapido alla memoria). Si ottengono algoritmi quantistici. È comunque in fase ancora embrionale.
• T(n): ottimizzando l’algoritmo. Da notare che esiste, per ogni problema, un algoritmo di complessità minima (algoritmi ottimali) sotto del quale non si può andare. Quindi è possibile ridurre T (n) solo fino ad un certo punto. Inoltre, il compito del Calcolo Numerico non è solo quello di trovare l’algoritmo più veloce ma anche quello più efficiente dal punto di vista dell’accuratezza (riducendo l’errore quanto più possibile). Infatti nel Calcolo Parallelo vogliamo fare “presto, ma bene”.
• μ: si devono ridurre le distanze fra la CPU e la memoria. Il processo di miniaturizzazione ha portato a distanze sempre inferiori, che tuttavia stanno trovando oggigiorno limiti fisici come per esempio problemi di surriscaldamento.

Dunque è possibile ridurre τ solo fino ad un certo punto, per questo motivo abbiamo bisogno del calcolo parallelo. Fondamentalmente, decomponiamo il problema in più sottoproblemi di dimensione inferiore, e li risolviamo contemporaneamente con più unità processanti.

Il prezzo da pagare è il tempo richiesto per unire i risultati.

5

Capitolo 2

Tipi di parallelismo

2.1 Lezione 2 - Classificazione di Flynn

Nel 1945 Von Neumann inventò il primo schema del computer che sarà poi utilizzato come modello generale.

In origine, secondo questo modello, un calcolatore eseguiva tutte le sue azioni sequenzialmente, su un dato alla volta. Dunque, non veniva applicato alcun tipo parallelismo.

Si tratta dell’architettura SISD (Single Instruction Single Data). Essa si componeva di:

• Memoria
• CPU che a sua volta contiene una:
  • Unità di controllo: esegue le operazioni riguardo il trasferimento di dati o al controllo dell’esecuzione di programmi. Dà i comandi.
  • Unità logico aritmetica (ALU): si occupa di eseguire le operazioni logiche ed aritmetiche.
• Unità I/O

6 Capitolo 2 – Tipi di parallelismo

Figura 2.1: Macchina di Von Neumann

È chiaro che oggi questo schema è stato modificato, ma viene usato sempre come modello generale.

Nel corso del tempo si sono diffusi vari tipi di parallelismo, la cui implementazione avviene a livello hardware.

Flynn dunque distinse varie architetture di calcolo, individuati dalla tassonomia di Flynn.

Distinguiamo 3 tipologie principali di parallelismo: temporale, spaziale e asincrono.

Inoltre, distinguiamo due tipi di parallelismo on-chip, in base a se il parallelismo è effettuato su unico chip (temporale, spaziale) oppure su più chip (asincrono).

Attualmente, tutti i microprocessori utilizzano forme diverse di parallelismo, e nessun sistema in commercio si può definire puramente sequenziale.

Figura 2.2: Tipi di Parallelismo

7 Capitolo 2 – Tipi di parallelismo

2.1.1 Parallelismo temporale

Il parallelismo temporale è la prima modifica che viene apportata al modello di Von Neumann, realizzato attraverso la tecnica della catena di montaggio, detto anche parallelismo pipeline. È ottenuto aggiungendo delle funzionalità all’unità aritmetico logica.

Consiste nel suddividere un lavoro in più fasi semplici ed affidare ogni fase ad una specifica unità che eseguono il proprio lavoro contemporaneamente.

Questa tipologia di architetture prende il nome di MISD (Multiple Instruction Single Data).

Un esempio: l’operazione di addizione floating point è divisa in 4 segmenti, dove ciascun segmento è preposto all’esecuzione di una fase dell’operazione:

• 1. Confronto degli esponenti (per vedere quale numero è più grande);
• 2. Shift della mantissa (per portare il tutto ad un’unica dimensione);
• 3. Somma delle mantisse;
• 4. Normalizzazione.

Nella somma di N numeri “tradizionale” (cioè senza parallelismo), solo un segmento alla volta è attivo mentre gli altri rimangono inattivi.

Nella somma di N numeri “pipelined”, a regime tutti i segmenti sono attivi contemporaneamente (cioè quando arriva per la prima volta alla quarta fase).

Nel primo caso avrò un tempo 4Ntu, nel secondo caso avrò un tempo < 4Ntu (dove 4 sono il numero di fasi).

L’uso di unità funzionali pipelined è anche alla base dei processori vettoriali, capaci di operare efficientemente su dati strutturati sotto forma di vettori.

Attualmente tutti i microprocessori utilizzano una struttura pipeline per migliorare le loro prestazioni.

2.1.2 Parallelismo spaziale

La seconda modifica apportata, consiste nel mettere all’interno di un’unica CPU, per un’unica Unità di Controllo, più ALU.

All’interno delle singole ALU si preservano le proprietà del parallelismo temporale.

Il parallelismo spaziale consiste quindi nel far eseguire contemporaneamente la stessa istruzione su dati diversi.

8 Capitolo 2 – Tipi di parallelismo

Figura 2.3: Parallelismo Spaziale

Questa tipologia di architetture prende il nome di SIMD (Single Instruction Multiple Data). Si pensi ad un gruppo di operai che costruiscono un muro: ogni operaio si occupa di mettere la calce, mettere un mattone e livellarlo. Abbiamo più operai che eseguono lo stesso lavoro.

Le architetture SIMD sono nate proprio grazie alla miniaturizzazione (più ALU sulla stessa CPU). Inoltre, siccome abbiamo una sola Unità di Controllo, tale parallelismo è anche detto parallelismo sincrono.

2.1.3 Parallelismo asincrono

Il parallelismo asincrono consiste nel far eseguire contemporaneamente azioni diverse su parti diverse.

È realizzato utilizzando più CPU (ognuna con una sola Unità di Controllo).

Figura 2.4: Parallelismo Asincrono

Questa tipologia di architetture prende il nome di MIMD (Multiple Instruction Multiple Data). Si pensi ad un gruppo di operai che costruiscono una casa: in questo caso ogni operaio penserà e agirà liberamente in quanto dovrà risolvere uno specifico problema. (ALU + CU).

9 Capitolo 2 – Tipi di parallelismo

In particolar modo, possiamo distinguere due tipologie di calcolatori MIMD: Distributed Memory e Shared Memory.

• DM (Distributed Memory): i calcolatori DM sono costituiti da più CPU ognuna delle quali ha una propria memoria. Si parla di “cluster” di processori. Distinguiamo due categorie di MIMD DM:
  • MPP (Massive Parallel Processors): architettura con CPU in PC indipendenti che lavorano in parallelo. Presenta però il problema della memoria;
  • DSM (Distributed Shared Memory): architettura con CPU in PC indipendenti che lavorano in parallelo, ma dove uno dei PC ha una memoria condivisa virtuale.
• SM (Shared Memory): i calcolatori SM sono costituiti da più CPU connesse ad una singola memoria principale in un’unica macchina. Ne distinguiamo due categorie:
  • SMP (Symmetric Multiprocessor): tutti i microprocessori sono identici, in quanto tutti i core hanno la stessa funzione (multicore Intel);
  • ASMP (Asymmetric Multiprocessor): i microprocessori sono diversi, in quanto NON tutti i core hanno la stessa funzione (PS5).

Parliamo dunque di un ambiente multicore.

Siamo così al secondo tipo di parallelismo ON-CHIP.

Sul chip quindi abbiamo il secondo tipo di parallelismo

Figura 2.5: SM e DM

10 Capitolo 2 – Tipi di parallelismo

Nelle macchine MIMD, CPU e memorie possono essere collegate in diverso modo a seconda del tipo di problema e applicazione della macchina.

In un calcolatore MIMD SM, la memoria e le CPU possono essere collegate con un bus singolo, bus multipli oppure in modo indiretto.

In un calcolatore MIMD DM, la memorie e le CPU possono essere collegate anche con schemi di connessione più complessi, come:

Le GPU rappresentano la più sofisticata forma di macchina parallela.

Se in un normale processore multicore abbiamo per ogni core 1 CU + 1 ALU, in una GPU abbiamo per ogni core 1 CU + 1 stream di ALU.

Sono specializzate in eseguire calcoli semplici ma su un’enorme quantità di dati, e infatti si occupano di risolvere sistemi di equazioni lineari.

2.1.4 Calcolo parallelo vs calcolo distribuito

I sistemi MIMD-DM rappresentavano quindi un cluster multiprocessore.

La gestione di un cluster è però complicata perché ha bisogno di un sistemista per poter funzionare.

Il problema è dunque la necessità di comunicazione tra i processori.

La libreria e/o lo standard che permette di fare ciò è l’MPI, il quale utilizza delle routine predefinite che stabiliscono compiti per ogni CPU.

L’idea di unire più calcolatori con cavi è stata superata dall’idea di unire più calcolatori sulla rete Internet.

Parliamo dunque di Cloud Computing, cluster eterogenei (distributi nel mondo, non sono macchine vicino a noi fisicamente).

11 Capitolo 2 – Tipi di parallelismo

Un ambiente di calcolo parallelo è un sistema di unità processanti strettamente collegate che comunicano per risolvere problemi su larga scala in maniera efficiente.

Un ambiente di calcolo distribuito è un sistema di unità processanti autonome e indipendenti, fisicamente distribuite che comunicano per risolvere problemi su larga scala in maniera efficiente.

La differenza è nella rete di connessione. Ci sono vantaggi nell’uno o nell’altra ma non in termini di performance.

L’obiettivo principale di un calcolatore parallelo sono le performance, e infatti si cerca di ridurre il tempo necessario alla risoluzione computazionale di un problema reale.

L’obiettivo principale di un sistema ad architettura distribuita è il riuso delle risorse esistenti, e infatti si cerca di riutilizzare “efficacemente” le risorse hardware e software distribuite geograficamente sul territorio.

Infatti il calcolo parallelo mira ad eseguire prima l’algoritmo, mentre il calcolo distribuito mira ad abbassare i costi (le performance peggiorano perché si perde tempo per l’invio di dati, in quanto aumenta la distanza).