Calcolo Parallelo

Università degli Studi di MessinaFacoltà di Scienze MM.FF.NN.Corso di Laurea Specialistica in Informatica

A cura di Biagio BonaseraCarmelo Rudipelli

Corso di Calcolo ParalleloCorso di Calcolo ParalleloProf.ssa L. PuccioProf.ssa L. Puccio

Anno accademico 2004/2005Anno accademico 2004/2005

2

Introduzione al calcolo parallelo Calcolo sequenziale:

Risolve un problema tramite un algoritmo, le cui istruzioni sono eseguite in sequenza.

Modello computazionale caratterizzato da un singolo processore.

Calcolo parallelo: Risolve lo stesso problema tramite un algoritmo le cui istruzioni sono eseguite in

parallelo. L’algoritmo deve sfruttare in maniera effettiva il parallelismo esplicitabile nel

problema, per rendere più veloce l’esecuzione. Modello computazionale che prevede processori multipli e relativi meccanismi di

cooperazione.

Metodologia generale per esplicitare il parallelismo: Dividere il problema tra processori (decomposizione). I vari processori lavorano sui propri pezzi del problema, e comunicano se

necessitano di cooperare.

3

Programmare in Parallelo Un programma sequenziale può essere suddiviso in due tipi di sezioni:

sezioni inerentemente sequenziali sezioni potenzialmente parallelizzabili

E’ bene che le parti inerentemente sequenziali siano piccole

Scopo di una buona parallelizzazione: mantenere tutti i processori (equamente) occupati (load balancing) minimizzare le comunicazioni inter-processor evitare che i processori rimangano in attesa di sincronizzazioni o I/O

associare ad ogni processore task multipli indipendenti (eccesso di parallelismo) per nascondere idle times

4

A che serve il parallelismo?

Alcune applicazioni richiedono maggiore velocità di esecuzione di quanto i computer sequenziali attuali possono fornire.

Le esigenze applicative sono ottenere computazioni che terminano in un tempo ragionevole. eseguire nello stesso tempo e con lo stesso algoritmo problemi più complessi.

Esempi di problemi che non possono essere oggi risolti in tempi

ragionevoli: Modellare grandi strutture di DNA. Prevedere in maniera globale i fenomeni meteorologici e quelli correlati. Modellare il movimento di corpi celesti.

Spesso, di pari passo con l’incremento delle prestazioni dei computer, si cerca di risolvere problemi con dati di dimensioni maggiori

computer sequenziale, anche se più veloce, NON sufficiente

5

HPC HPC (High Performance Computing) offre un nuovo modo di fare scienza:

Sperimentare Teorizzare/Modellare Computare

Il modello computazione è principalmente usato per approssimare sistemi fisici

Tra i vantaggi Giocare con i parametri della simulazione per studiare nuove soluzioni La possibilità di ripetere particolari eventi simulati Studiare sistemi quando non esistono teorie esatte

6

Un esempio: Previsioni del tempo L’intera atmosfera è modellata dividendola in regioni o celle tridimensionali, il

calcolo su ogni cella è ripetuto diverse volte per modellare il passaggio del tempo.

L’atmosfera è suddivisa in celle di dimensioni 1 Km ×1 Km ×1 Km per un’altezza di 10 km (per un’altezza di 10 celle) per un totale di circa 5 ×108 celle.

Supponiamo che il calcolo associato a ciascuna cella richiede 200 FP ops, in un passo sono necessari 1011 FP ops

Per una previsione meteo su 10 giorni, usando intervalli di tempo di simulazione di 10 minuti, sono necessari 6 passi di simulazione all’ora, per un totale di 1440 passi (circa 1,4 1014 FP ops)

Un computer che operasse a 100 Mflops (108 FP ops/sec) impiegherebbe più di 106 secondi (circa 16 giorni !!!!).

Per eseguire lo stesso calcolo in 10 minuti ci vorrebbe un computer in grado di eseguire 0,2 Tflops (0,2 × 1012 FP ops/sec)

Cosa succede se aumentiamo i passi o rimpiccioliamo le celle?

7

Calcolatori paralleli Sistemi a memoria condivisa SHARED

MEMORIA

CPU 1 CPU 2 … CPU N

Sistemi a memoria distribuitaDISTRIBUITED

CPU 1

MEMORIA 1

CPU 2 … CPU N

MEMORIA 2 … MEMORIA N

8

L’operazione di Somma

Calcolo della somma S di N=16 numeri a0,a1,…,a15

Calcolatore monoprocessore S= a0+a1+…+a15 (N-1 addizioni)

Calcolatore multiprocessore (shared) 4 processori Pi ,i=0,1,2,3 Pi calcola Si = ai*4 + ai*4+1 + ai*4+2 + ai*4+3

1 caso - il processore P0 accede in memoria e calcola S=S0+S1+S2+S3

2 caso – P0: S=S+S0, P1:S=S+S1, P2:S=S+S2, P3:S=S+S3

senza sincronizzazione S può non assumere il valore corretto, per risolvere il problema si usano i semafori (ogni processore accede in maniera esclusiva ad S)

9

Algoritmo

BeginS := 0Forall Pi, 0 ≤ i ≤ 3 do

SP:= 0for j = i*4 to i*4+3 do

SP:= SP+aj

endfor lock (S)

S:= S+SPunlock (S)

EndForallEnd

10

Computer paralleli e loro programmazione

Negli scorsi anni abbiamo assistito al proliferare di architetture parallele diverse, associati con paradigmi di programmazione differenti e specializzati

A causa di ciò, programmare in parallelo è stata considerata un’attività complessa, che richiede l’uso di strumenti di programmazione a basso livello, e un’elevata attività di tuning dei programmi per ottenere alte prestazioni

11

Classificazione di calcolatori paralleli Tipo e numero di processori

Sincronismo

Interconnessione dei processori

Presenza o assenza di un meccanismo globale di controllo, Flynn ha introdotto la seguente tassonomia dei computer, dove le classi interessanti di computer paralleli sono:

MIMD (Multiple Instruction stream-Multiple Data stream) SIMD (Single Instruction stream - Multiple Data stream)

SISTEMICALCOLO

SINGLEINSTRUCTION

MULTIPLEINSTRUCTION

SISD SIMD MISD MIMD

12

Flynn - 4 modelli di computer

Modello di Von Neumann

Array processors, Pipeline processors

Processori indipendenti con unità di controllo indipendenti

Riconducibile a SISD

13

SIMD

L’array di processori opera in modo sincrono, ovvero a ogni passo tutti i processori eseguono la stessa istruzione su dati differenti

Macchine SIMD adatte per risolvere problemi data parallel regolari, dove la stessa istruzione può essere applicata a partizioni distinte dei dati

14

MIMD (Multiprocessor / Multicomputer)Ogni processore opera in modo asincrono sotto il controllo di un proprio programma e su dati diversi

Come nel caso SIMD, la comunicazione dei dati e dei risultati può avvenire attraverso memoria condivisa o rete

Computer MIMD con memoria condivisa sono conosciuti come multiprocessors o tightly coupled machines. Tutti i costruttori hanno oggi in listino multiprocessori a vari livelli di scala.

Computer MIMD con rete di interconnessione sono conosciuti come multicomputers o loosely coupled machines.

15

Interconnessione dei processori:shared memory vs message passing Sia nel caso SIMD e sia nel caso MIMD per cooperare è necessario

scambiare dati tra processori. Questo può essere fatto in due modi Usando SHARED MEMORY (SM) e SHARED VARIABLES Usando DISTRIBUTED MEMORY (DM) e MESSAGE PASSING

Nel caso SM abbiamo un unico spazio di indirizzamento a cui i vari processori possono accedere

problemi legati alla scalabilità, parzialmente risolvibile tramite cache modalità di cooperazione adatta per piccoli numeri di processori (multiprocessor

MIMD a 2-32 vie)

Nel caso DM abbiamo uno spazio di indirizzamento privato a ciascun processore, per cui per comunicare i processori devono scambiarsi messaggi via rete

modalità tipica di molti MPP di tipo MIMD e dei cluster di WS con rete veloce un unico spazio di indirizzamento può essere emulato a software Virtual Shared

Memory (VSM)

16

Interconnessione dei processori: esempi di networks

Array lineare monodimensionale

Mesh

4×4.

Albero di base 8

4-cubo

17

Modello di programmazione Controllo

Come il parallelismo viene creato Qual è e come viene garantito l’ordine corretto tra le operazioni Come thread di controllo differenti si sincronizzano

Naming Quali dati sono private e quali shared Come i dati shared sono acceduti/comunicati dal punto di vista logico

Insieme di operazioni e costi Quali sono le operazioni di base Qual è il loro costo

Storicamente Ciascuna macchina parallela era unica, e caratterizzata da una specifico modello

architetturale Aveva il proprio modello di programmazione e un linguaggio associato

18

Modelli di programmazione 1 (SM) Shared Memory (SM). Nel modello shared-memory i processi (thread)

condividono uno spazio comune, sul quale leggono/scrivono in maniera asincrona. Meccanismi vari come lock e semafori possono essere usati per controllare gli accessi alla SM.

Un vantaggio dal punto di vista del programmatore è che non esiste la nozione di “ownership” dei dati, e quindi non c’è bisogno di comunicare dati. Comunque, dal punto di vista della programmazione efficiente, gestire la località può diventare complesso.

Il modello shared memory è in un certo senso primitivo su macchine SM MIMD, ma un ambiente SM può essere realizzato anche su un DM MIMD (Virtual SM).

Ancora una volta il modello non mette vincoli alla fantasia del programmatore (unrestricted model) ed è di basso livello. Un ambiente di programmazione tipico sono le librerie portabili per la programmazione multi-threading (es.: pthread) da linkare con codice sequenziale.

Parallelismo di tipo esplicito: il programmatore è responsabile delle suddivisione del programma in task, e della cooperazione tra i task via SM

19

Modello di programmazione 2 (MP) Message passing (MP). Il modello message-passing è basato sull’astrazione di

task (processi) multipli, creati staticamente o dinamicamente.

Ogni task è caratterizzato da uno specifico codice e incapsula dati privati.

Le primitive send/receive nominano direttamente i task (tramite degli identificatori/nomi unici) o delle astrazioni di canali di comunicazione che collegano i task.

Modello di basso livello, che permette qualsiasi tipo di decomposizione e struttura di comunicazione

Il modello message passing è in un certo senso primitivo su macchine DM MIMD, ma può essere realizzato efficientemente anche su un SM MIMD.

Esistono linguaggi message passing, anche se oggi l’ambiente di programmazione tipico fa uso di librerie portabili, facili da usare, e efficienti da linkare con codice sequenziale (MPI, PVM)

Parallelismo di tipo esplicito: il programmatore è responsabile delle suddivisione del programma in processi, e della cooperazione tra i processi via MP

20

Modelli di programmazione Storicamente, tutte le architetture parallele avevano caratteristiche uniche

(ciascuna con il proprio modello di programmazione e linguaggio associato)

Necessario riprogettare il sw parallelo per ogni macchina

Attualmente, distinguiamo il modello di programmazione dall’architettura sottostante

Il modello di programmazione visto come una concettualizzazione della macchina parallela che il programmatore usa per le sue applicazioni (possiamo scrivere codice corretto e portabile, che esegue su più macchine )

MPI (modello MP) è oggi l’opzione più portabile Ma cosa possiamo dire per le prestazioni? Purtroppo scrivere codice portabile ma veloce richiede ancora il tuning per ogni

specifica architettura

La sfida è rendere semplice questo processo di programmazione parallela portabile ed efficiente

21

Valutazione delle prestazioni: Speedup

Massimo speedup Sp(n)=n con n processori: speedup lineare

Speedup superlineare se Sp(n) > n può essere dovuto all’uso di un algoritmo sequenziale sub-ottimo può essere dovuto a caratteristiche dell’architettura che favoriscono la

versione parallela.

Una ragione comune dello speedup superlineare è la maggiore quantità di memoria disponibile sulle architetture parallele, che permette di mantenere in memoria più dati del problema rispetto al caso sequenziale (senza quindi coinvolgere il disco … swapping).

Speedup su n processori

22

Valutazione delle prestazioni: Efficienza

L’efficienza dà una misura della frazione del tempo totale durante il quale i vari processori sono efficacemente usati per effettuare la computazione.

Un’efficienza uguale a 1 (Sp(n)=n) significa che tutti i processori prendono parte in maniera proficua all’esecuzione dell’algoritmo

Un’efficienza molto minore di 1 testimonia il fatto che carico sbilanciato processori idle lavoro extra nella versione parallela dell’algoritmo overhead legati alle comunicazioni/sincronizzazioni

Efficienza

23

Valutazione delle prestazioni: Costo Il prodotto processor-time o Costo (o Work) di una computazione è definita

come Costo= (tempo di esecuzione) x (no. Totale di processori usati)

Il Costo di una computazione sequenziale è semplicemente ts .

Il Costo di una computazione parallela è tp x n.

Poiché tp = ts / Sp(n) il Costo può essere formulato come Costo= ts / E(n)

Un algoritmo parallelo è Cost-Optimal se il costo per risolverlo in parallelo è simile al costo per risolverlo in sequenziale (Efficienza ottima = 1)

24

Valutazione delle prestazioni: Scalabilità Il termine scalabilità si usa per indicare un progetto hardware che può

essere incrementato (aggiungendo processori, memoria, rete, I/O) per aumentare le prestazioni

Esiste anche il concetto di scalabilità algoritmica

Un algoritmo parallelo è scalabile se è possibile a causa di un incremento della dimensione dei dati incrementare il livello di parallelismo (usare più processori) con un basso o limitato incremento del tempo di esecuzione

25

PVM & MPI

Librerie di software alla base del paradigma “message passing”

Insieme di funzioni che consentono ai processori di scambiarsi informazioni

PVM è l’acronimo di Parallel Virtual Machine consente di vedere una rete di calcolatori UNIX come un singolo calcolatore

parallelo a memoria distribuita (la macchina virtuale). Lo sviluppo di PVM è iniziato nel 1989 all’Oak Ridge National Laboratory (ORNL).

MPI è l’acronimo di “Message Passing Interface” nasce dalla necessità di definire uno standard unico per le librerie di message

passing. il 5 Maggio 1994, la versione 1.0 fu distribuita su Internet. Negli anni successivi sono state rilasciate nuove versioni

26

MPI Lo standard MPI comprende:

comunicazioni punto-punto operazioni collettive gruppi di processori domini di comunicazione topologie di processori gestione dell’ambiente chiamate al Fortran e al C.

Lo scambio di informazioni tra processori avviene attraverso la comunicazione di messaggi:

comunicazioni “uno a uno” comunicazioni “collettive “

comunicazione di uno a più di uno (broadcast); scambio di informazioni tra più processori

27

Il modello Message-Passing Ad un processo sono associati

program counter address space.

I processi possono avere threads multipli (program counters & private stacks) singolo address space

Le versioni correnti di MPI supportano la comunicazione tra processi, non tra thread

Interprocess communication (message-passing) Sincronizzazione Movimento di dati dall’address space di un processo (mittente), all’address

space di un altro processo (destinatario)

28

Operazioni di base #include “mpi.h”

Inizializzazione di MPI: MPI_Init() deve essere chiamata prima di ogni altra routine MPI. Definisce l’insieme dei processori attivati (contesto).

Termine di un programma MPI: MPl_Finalize() Determina la fine del programma MPI. Dopo questa routine non è possibile richiamare nessuna altra routine MPI

Esempio di codice

29

Comunicatori I processi MPI possono essere organizzati in gruppi

Ogni messaggio è inviato in un gruppo all’interno di uno specifico contesto Il msg deve anche essere ricevuto nello stesso contesto

Gruppo e Contesto insieme formano un comunicatore per lo stesso gruppo potremmo così avere comunicatori diversi

Un processo è identificato dal suo rank nel gruppo associato con un comunicatore

MPI_COMM_WORLD è il comunicatore di default

30

Informazioni sull’ambiente a run-time Ogni processo può avere necessità di chiedere :

Quanti processi partecipano in questa computazione? Chi sono io?

MPI fornisce funzioni per rispondere a questi quesiti: MPI_Comm_size() restituisce il numero di processi MPI_Comm_rank() restituisce il rank, un numero tra 0 e size-1,che identifica il processo

chiamante

Esempio di codice:#include <mpi.h>

#include <stdio.h>

int main( int argc, char *argv[] ){

int rank, size;

MPI_Init( &argc, &argv );

MPI_Comm_rank( MPI_COMM_WORLD, &rank );

MPI_Comm_size( MPI_COMM_WORLD, &size );

printf( “Io sono %d di %d\n", rank, size );

MPI_Finalize();

return 0;}

31

Datatypes

Un’implementazione MPI permette comunicazioni tra processi allocati su macchine eterogenee, i cui datatype elementari hanno :

rappresentazione in memoria lunghezze differenti

Con i datatype si possono specificare layout application-oriented dei dati

Tabella dei datatypes MPI

32

Tags I messaggi sono inviati accompagnati con un tag intero user-defined

Questo serve al processo ricevente per identificare il messaggio I messaggi possono essere selezionati dal ricevente specificando il tag I messaggi possono non essere scelti dal ricevente sulla base del tag

Specificando MPI_ANY_TAG come tag nella receive.

I tag sono considerati come message type in alcuni sistemi messagepassing, ma non in MPI

MPI li chiama semplicemente tag per evitare confusione con i datatypes.

33

Send/Receive MPI_SEND (start, count, datatype, dest, tag, comm)

Comunicazione standard, Asincrona/Buffered/Bloccante Il buffer del messaggio è descritto da : start, count, datatype Il processo destinazione è specificato da dest, che è il rank del processo target nel

comunicatore specificato da comm. Quando la funzione ritorna, i dati sono già stati consegnati al sistema e il buffer può essere

riusato Il messaggio può non essere stato ricevuto dal processo ricevente

MPI_RECV(start, count, datatype, source, tag, comm, status) Comunicazione standard, Asincrona/Buffered/Bloccante Attende fino a quando un matching message (rispetto a comm, source etag) è ricevuto dal

sistema, e copiato nel buffer utente (start,count, datatype) source è il rank nel comunicatore specificato da comm, oppure MPI_ANY_SOURCE. tag è il tag atteso e associato al messaggio, oppure MPI_ANY_TAG status è un parametro in output, e conterrà informazioni sulla comunicazione Si possono ricevere meno di count occorrenze di un datatype, ma riceverne di più è un errore

34

Broadcast e Reduce MPI_Bcast(void* message, int count, MPI_Datatype datatype, int root,

MPI_Comm comm) Effettua il broadcasting dei messaggi Come la MPI_Send ma invia il messaggio a tutti i processi appartenenti al

comunicatore MPI_Comm

MPI_Reduce(void* operand, void* result, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

combina gli operandi memorizzati in *operand usando l’operatore op e memorizza il risultato in *result nel processo root.

deve essere chiamata da tutti i processi appartenenti al comunicatore comm, ed inoltre count, datatype, e op devono essere gli stessi in ogni processo.

l’ argomento op può essere preso da una tabella predefinta è anche possibile definire operatori aggiuntivi

35

Status Status è una struttura dati allocata nello user’s program, che conterrà

informazioni sulla receive appena conclusa:int recvd_tag, recvd_from, recvd_count;

MPI_Status status;

MPI_Recv(..., MPI_ANY_SOURCE, MPI_ANY_TAG, ..., &status )

recvd_tag = status.MPI_TAG;

recvd_from = status.MPI_SOURCE;

MPI_Get_count( &status, datatype, &recvd_count );

36

E’ noto che l’area del cerchio è r2 π, per cui l’area del semicerchio con

r=1 è: π/4 Curva cerchio (teorema di Pitagora):

x2 + y2 = 1y = √(1-x2)

L’area del semicerchio corrisponde al calcolo del seguente integrale:

Possiamo calcolarlo numericamente.Maggiore è il numero di intervalli in cui suddividiamo [0..1], maggiore è la precisione del calcolo dell’integrale

Calcolo di PI greco

1

0

21 x

37

Esempio: PI greco in C (1/2)#include <mpi.h>

#include <math.h>

int main(int argc, char *argv[]) {

int done = 0, n, myid, numprocs, i, rc;

double PI25DT = 3.141592653589793238462643;

double mypi, pi, h, sum, x, a;

/* inizializza l’ambiente MPI */

MPI_Init(&argc,&argv);

/* ottiene il numero dei processi */

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

/* ottiene l’id del processo chiamante */

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

if (myid == 0) {

printf(“Inserisci il numero di intervalli: (0 fine) ");

scanf("%d",&n);

}

/* manda &n in broadcast a tutti i processi di MPI_COMM_WORLD */

/* &n di tipo MPI_INT, 1 un solo MPI_INT, 0 processo root */

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

38

Esempio: PI greco in C (2/2) if (n != 0) {

h = 1.0 / (double) n;

sum = 0.0;

for (i = myid + 1; i <= n; i += numprocs) {

x = h * ((double) i - 0.5);

sum += 4.0 / (1.0 + x*x);

}

mypi = h * sum;

/* ricompone il risultato in &pi sommando &mypi (MPI_SUM)*/

/* 1 un solo MPI_INT, 0 processo root */

/* il processo root rimane in attesa fino a quando non riceve tutti i &mypi del MPI_COMM_WORLD */

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,MPI_COMM_WORLD);

if (myid == 0)

printf("pi is approximately %.16f, Error is %.16f\n",pi, fabs(pi - PI25DT));

}

MPI_Finalize();

return 0;

}