Appunti di Calcolo Parallelo e Distribuito

CALCOLO PARALLELO E DISTRIBUITO

ESAME

• PROVA SCRITTA (SCRITTURA CODICE PARALLELO)
• PROVA ORALE

RISOLVERE PROBLEMI TRAMITE IL CALCOLO PARALLELO

• QUALI SONO I PROBLEMI? → CON QUALE APPROCCIO VANNO RISOLTI?
• COME VANNO RISOLTI?

SUPERCOMPUTING → RISOLVERE PROBLEMI CON UN SUPERCOMPUTER

SUPERCOMPUTER → SUPERCALCOLATORE

SISTEMA CHE FORNISCE LE PRESTAZIONI PIÙ ELEVATE

TEMPO DI RISOLUZIONE DI UNA PARTICOLARE APPLICAZIONE

RMAX: BENCHMARK PER RISOLVERE A_x=b

1980

• 1 ANNO

1992

• 4 ORE

1997

• 2 ORE

2000

• 10 MIN

2021

• 10 SEC

LO STESSO CALCOLO, SVOLTO SUI DUE CALCOLATORI PIÙ VELOCI DEL RISPETTIVO ANNO, PRESENTANO TEMPI DI RISOLUZIONE NETTAMENTE DIVERSI.

LINPACK BENCHMARK

EQUAZIONI LINEARI SISTEMA DENSO DI EQUAZIONI LINEARI

HPC

• HIGH
• PERFORMANCE
• COMPUTING

LA POTENZA DEI SISTEMI HPC DI UNA NAZIONE È UNO DEI PARAMETRI PER VALUTARNE LO SVILUPPO TECNOLOGICO

È NECESSARIO USARE UN SUPERCOMPUTER?

AD OGGI NON ESISTE PIÙ LA MACCHINA DI VON NEWMAN (CALCOLATORE SEQUENZIALE).

SI MA NO

DIPENDE DAL CASO D'USO.

SUPERCOMPUTER

• + VELOCITÀ
• + AFFIDABILITÀ
• + SICUREZZA
• - GESTIONE
• - PREZZO ELEVATO

PC

• + ECONOMICA
• + FACILE GESTIONE

QUANDO PUÒ ESSERE NECESSARIO L'UTILIZZO DI MACCHINE HPC?

LA RICERCA WEB

PERMETTONO DI RIDURRE AL MINIMO IL TEMPO DI INTERROGAZIONE DEL SERVER.

Approccio Sequenziale: Somma F.P.

• Fase 1
  • Confronto degli esponenti
  • Individuare l'esponente maggiore
• Fase 2
  • Shift della mantissa
  • Adeguamento dell'esponente minore
• Fase 3
  • Somma delle mantisse
• Fase 4
  • Normalizzazione

Lo schema è il medesimo della lavanderia:

Complessità: T = [L_u + N - 1]E_u

Complessità in sequenziale: 4 N E_u

Il guadagno è strettamente legato a numero di unità processanti

Funzionalità pipelining → processi vettoriali

Evoluzione del parallelismo

• SISD (Monoprocessore)
• MISD
  • Mono processore + pipeline mono ALU: multi (U.F.)
• SIMD
  • Singol Instruction Multiple Data: multi ALU, Parallelismo spaziale
• MIMD
  • Multi Instruction Multiple Data: multi CPU, Parallelismo asincrono

Memoria distribuita

SIMD

1 istruzione, N dati

MIND = Multi Core

Threads

• Flusso di istruzioni indipendenti da eseguire sequenzialmente su una e solo una unità di controllo.
• Il thread deve essere una sequenza di istruzioni tra loro dipendenti.

Processo = programma che "gira", un software in esecuzione.

Processore = macchina che esegue processi, formato da una o più CPU.

Processo = uno o più threads (flusso di istruzioni dipendenti).

Processore = uno o più core -> CPU.

Processo gira su processore, che può essere:

• Multi-thread: algoritmo che gira su macchina multi-core.
• I threads di uno stesso processo condividono la stessa area di memoria e possono lavorare contemporaneamente.

Pro: leggerezza ed efficienza.

Contro: necessità di sincronizzazione degli accessi alle variabili condivise.

I threads possono essere creati dinamicamente in fase di scrittura del codice.

ROUTINE -> LIBRERIE CHE LAVORANO SULLE VARIABILI DI RUNTIME

• MODIFICA NUMERO THREADS, INFORMAZIONI SULLO SCHEDULING
• SONO CONTENUTE NEL FILE omp.h
• RUNTIME LIBRARY ROUTINES

VARIABILI D'AMBIENTE -> POSSIBILITÀ DI IMPOSTARE DELLE VARIABILI DA RIGA DI COMANDO PRIMA DI FAR PARTIRE L'ESECUZIONE

• COME UTENTE, NON COME SVILUPPATORE

=> OMP_NUM_THREADS: NUMERO DI THREAD DA UTILIZZARE DURANTE LE PROSSIME ESECUZIONI

• > OMP_NUM_THREADS = (NP) VALORE DI TIPO INT.
• > sh/bash: export OMP_NUM_THREADS = (NP)

OMP_DYNAMIC - TESTA IL PERMESSO O MENO DI MODIFICARE IL NUMERO DI THREADS UTILIZZATI

VERIFICA CARATTERISTICHE PROCESSORE:

• LINUX : CAT /PROC/CPUINFO
• MAC : sysctl -a|grep machdep.cpu

SI PUÒ MODIFICARE IL NUMERO DEI THREAD TRAMITE LE VARIABILI D'AMBIENTE STANDARD DELL'OPENMP TRAMITE:

export OMP_NUM_THREADS = numero

COMPILARE:

• gcc -fopenmp -o nome.exe nomefile.c
• ESEGUIRE: ./nome.exe

Il tempo dell'algoritmo sequenziale ed il tempo dell'algoritmo su p=1 sono la stessa cosa?

NO -> Il tempo dell'algoritmo su p=1 (1 solo processore) è sempre maggiore del tempo impiegato dall'algoritmo sequenziale (fa delle cose in più...)

Es.

• Divisione degli elementi sui p processori per p=1 è una divisione in più che distribuisce tutti gli elementi ad un singolo processore
• Interrogazione sul numero di processori è pur sempre un'operazione

Quale algoritmo scegliere per calcolare T(1)

T(1) = tempo di esecuzione dell'algoritmo parallelo su 1 processore

NB

S(p) dà informazioni su quanto l'algoritmo si presta all'implementazione dell'algoritmo parallelo ma potrebbe eseguire più operazioni del necessario!

La scelta migliore sarebbe dunque, scegliere il tempo d'esecuzione dell'algoritmo sequenziale. Per avere effettivamente idea di qual è il guadagno che si ottiene grazie alla parallelizzazione.

MA:

• Dovremmo sempre individuare ed utilizzare il "miglior" algoritmo sequenziale.
• Se pur individuato, non è detto che questo sia accessibile o disponibile.

Essendo entrambe le scelte non ottimali, per convenzione si sceglie il tempo di esecuzione su 1 processore (parallelo) mettendo al numeratore il numero di operazioni che si esegue in sequenziale ed al denominatore il numero di operazioni concorrenti quando l'algoritmo gira in sequenziale con p unità

Prima scelta con efficienza

Formula Generalizzata di Ware (Amdhal)

S(p) = ¹/_{α1 + ∑^n-1k=2 (Δυk/^{k + Δυk/}p)}

• α₁ parte sequenziale dell'algoritmo parallelo
• Δυ_k parte dell'algoritmo eseguita in parallelismo totale
• Δυ_k parte dell'algoritmo eseguita in parallelismo medio per k

Base: S(p) = ¹/_{α + 1 - α/p}

Per Δυ_k/p non possiamo dire che la parte parallelizzabile è il complemento α₁ di Δ₁

Ciò perchè non abbiamo potuto separare nettamente la parte sequenziale da quella parallela

Cosa succede se p ed n crescono contemporaneamente? Ed in che rapporto devono essere per aumentare?

Applichiamo la legge di Ware Amdahl

P = {2, 4, 8, 16}

h = {8, 16, 32, 64}   ^h/_P = 4 costante