Calcolo Parallelo - Riassunto Sbobbinato Slide.

8/19/2019 Calcolo Parallelo - Riassunto Sbobbinato Slide.

1/25

C e r r o n e M a r i a r o s a r i a

2014/2015

Appunti di Calcolo

Parallelo eDistribuito mod A


2/25

INTRODUZIONE

Il termine supercalcolatore si riferisce ad un sistema che fornisce le prestazioni più elevate. La

prestazione è misurata dal tempo necessario per risolvere un particolare applicazione. La TOP500

è la lista dei calcolatori più veloci nel mondo. Il calcolo ad alte prestazioni serve a risolvere

problemi in "tempo reale" ( tempo utile ) e a risolvere problemi di grandi dimensioni ( a larga

scala).Il tempo di esecuzione di un software è: τ = k T(n) μ. Dove k è una costante T(n) è il numero di

operazioni effettuate dall'algoritmo ossia la complessità di tempo dell'algoritmo ( tecnologia in

senso lato ) e μ è il tempo di esecuzione su un calcolatore di una operazione floating point (

tecnologia in senso stretto ). Per diminuire τ possiamo pensare di diminuite T(n) e μ, ma in

entrambi i casi ci sono dei vincoli perchè da un lato meglio degli algoritmi ottimali non posso

andare e dall' altro pur volendo ridurre le distanze non posso costruire calcolatori di dimensioni

troppo piccole. Se ancora τ non ci soddisfa possiamo pensare al calcolo parallelo. Ho un problema

di dimensione N, lo decompongo in P sottoproblemi di dimensione più piccola N/P e li risolvo

contemporaneamente su diversi processori.

CLASSIFICAZIONE DI FLYNNAlla classificazione di Flynn ( 1965) appartengono le seguenti classi di architetture parallele:

SISD è l'acronimo di Sigle Istruction Single Data, e si usa per intendere la classe delle architetture in

cui si possono eseguire singole istruzioni su singoli dati. A questa categoria appartengono i

monoprocessori.

MISD è l’acronimo di Multiple Istruction Single Data, e si usa per intendere la classe delle

architetture in cui si possono eseguire flussi di istruzioni diversi sullo stesso dato

contemporaneamente. Presa la definizione alla lettera, sembra non esistere né essere

immaginabile un’architettura reale che appartenga a questa classe, ma molti fanno rientrare in

questa categoria quelle architetture che implementano la pipeline: questo significa che con questo

tipo di architetture si può realizzare un parallelismo di tipo temporale, ovvero quello che si puòesemplificare in una catena di montaggio. Un esempio di implementazione della pipeline in

architettura lo troviamo spesso (oggi ormai possiamo dire sempre) a livello di unità aritmetiche

(ALU) del processore: l’ALU è generalmente divisa in segmenti, ognuno preposto ad una specifica

operazione elementare, e quindi in grado di lavorare concorrentemente agli altri.

SIMD è l’acronimo di Single Istruction Multiple Data, e si usa per intendere la cla sse delle

architetture in cui si può eseguire lo stesso flusso di istruzioni contemporaneamente su dati

diversi. Dunque, a questa categoria appartengono quelle architetture in cui ad una sola unità di

controllo (CU) corrispondono più unità aritmetiche (ALU), che agiscono su dati diversi: l’istruzione

decisa dalla CU viene eseguita contemporaneamente dalle diverse ALU, ognuna sul proprio

insieme di dati. Dunque con questo tipo di architetture si può realizzare un parallelismo di tipospaziale. Eventualmente le macchine pipelined possono essere fatte rientrare anche in questa

categoria, ed se teniamo conto di questo con le architetture SIMD possiamo realizzare anche

parallelismo di tipo temporale.

MIMD è l'acronimo di Multiple Istruction Multiple Data, e si usa per intende la classe delle

architetture in cui si possono eseguire contemporaneamente diverse istruzioni su dati diversi.

Dunque, a questa categoria appartengono quelle architetture in cui differenti processori ( CPU )

cooperano eseguendo istruzioni diverse su dati diversi in parallelo. Con questo tipo di architetture

si può realizzare un parallelismo di tipo asincrono. In un calcolatore MIMD, CPU e memorie

possono essere collegate in due diversi modi: si parla di shared memory e distrubuited memory.

I calcolatori MIMD-SM ( a memoria condivisa ) hanno un unica memoria a cui attingono diverseCPU. Il vantaggio di questo tipo di architettura è che le informazioni sono a disposizione di tutte le


3/25

CPU quindi non c'è necessità di scambio di dati ma c'è la necessità di soncronizzare l'accesso ai

dati.

I calcolatori MIMD-DM ( a memoria distribuita ) hanno più CPU e ognuna di queste ha la sua

memoria. Il vantaggio è che non c'è necessità di sincronizzare l'accesso ai dati ma c'è lo svantaggio

di doversi scambiare le informazioni.

Noi lavoreremo sia su memoria distribuita che su memoria condivisa per risolvere alcuni problemi.SOMMA DI N NUMERI

Voglio calcolare al somma di N numeri reali su un calcolatore di tipo MIMD con p processori. Su un

calcolatore monoprocessore la somma è calcolata eseguendo N-1 addizioni ( algoritmo parallelo ).

In parallelo suddivido il problema in N/p sottoproblemi ognuno dei quali è assegnato ad uno dei p

processori che lavorano in parallelo e poi occorre mettere insieme in qualche modo il risultato.

Cominciamo a lavorare con un calcolatore di tipo MIMD a memoria distribuita. Esistono 3 strategie

per il calcolo della somma di N numeri.

I STRATEGIA

Nella prima strategia dopo che ogni processore ha calcolato la propria somma parziale , ad ogni

passo ciascuno di essi invia la propria somma parziale ad un unico processore prestabilito. Taleprocessore sarà quello che conterrà la somma totale. In tale strategia vengono poco sfruttati i

processori perchè dopo il primo passo ne lavorerà uno solo.

II STRATEGIA

Nella seconda strategia dopo che ogni processore ha calcolato la propria somma parziale, ad ogni

passo coppie distinte di processori comunicano contemporaneamente e uno dei due invia all’altro

la sua somma parziale. Alla fine il risultato si troverà in unico processore prestabilito.

III STRATEGIA

Nella terza strategia, dopo che ogni processore ha calcolato la propria somma parziale, ad ogni

passo coppie distinte di processori comunicano contemporaneamente ma, a differenza dellaseconda strategia, in ogni coppia i processori si scambiano le proprie somme parziali. Sebbene farò


4/25

più operazioni il vantaggio è che alla fine il risultato si troverà in tutti i processori e quindi se a uno

di queste servisse non c'è necessità di comunicazione ( che sappiamo pesare molto sull'efficienza).

Vedremo che lo strumento software utilizzato per lo sviluppo di algoritmi in ambiente di calcolo

MIMD-DM è il Message Passing Interface ( MPI ).

VALUTAZIONE EFFICIENZA DI UN ALGORITMO PARALLELO

Sappiamo che per valutare l'efficienza di un algoritmo sequenziale ( monoprocessore ) valutazione

la complessità di tempo ( T(n) numero di operazioni eseguite dall'algoritmo ) e la complessità di

spazio ( S(n) numero di variabili utilizzate ) . In un algoritmo sequenziale il numero di operazioni

determina anche il numero di passi temporali in un algoritmo parallelo non è così perchè ci sono

operazioni effettuate contemporaneamente dai diversi processori. In generale con p processori ci

aspettiamo che T(1) sia p volte T(p) ovvero ci aspettiamo di ridurre di p volte il tempo di

esecuzione quando passiamo da 1 a p processori.

Per l'algoritmo della somma di n numeri posto p=2k

( per semplicità) T(p)= ( -1 log2p ) tcalc DEFINIZIONE Si definisce Speed-up il rapporto: . Lo Speed up misura la riduzione deltempo di esecuzione su p processori rispetto a quello impiegato su 1 processore. In generale

S(p)


5/25

E' comune usare al posto di Ts e Tc la notazione α e 1-α, dove α indica la parte sequenziale (

frazione di operazioni eseguite in sequenziale) . Posto T(1)= 1, Ts=α, Tc=1-α l'Overhead totale

sarà: Oh=(p-1)α ossia cresce al crescere di p e di α. Quindi l'efficienza:

La LEGGE DI WARE o AMDAHL dice che:

Se la dimensione del problema è n fissato, al crescere di p non otteniamo speed up vicini a quello

ideale ma in più le prestazioni peggiorano perchè l'efficienza diminuisce e quindi non conviene

utilizzare un maggior numero di processori.

Fissando il numero di processori p e aumentando la dimensione N del problema ( la parte

sequenziale diminuisce ) si possono ottenere speed up prossimi a quello ideale ma non è possibileaumentare in maniera indefinita la dimensione del problema ( le risorse hardware sono limitate ).

Aumentando sia N che p le prestazioni dell' algoritmo parallelo non degradano e ci aspettiamo

che: T(1,N)=T(2,2N)=.......=T(p,pN) dove T(p,pN) è il tempo impiegato da p processori per eseguire

la somma di pN numeri. Pertanto se si assume pT(1,n)=T(1,pn): Ovvero se si assume che T(1,pN) è uguale al tempo che si ottiene moltiplicando per p il tempo per

risolvere su un processore il problema di dimensione N otteniamo lo Speed up ideale che si chiama

più correttamente speed up scalato.

DEFINIZIONE Nell'algoritmo della somma lo speed uo scalato è : DEFINIZIONE Si definisce efficienza scalata il rapporto tra Speed up scalato e p.Un algoritmo si dice SCALABILE se l'efficienza rimane costante o non degrada al crescere dei

processori e della dimensione del problema.

E' possibile ottenere speed up scalati prossimi allo speed up ideale?

Il tempo T(p) si può decomporre in due parti: una parte relativa alle operazioni che sono eseguite

in sequenziale( Ts ) e una parte relativa alle operazioni che sono eseguite in parallelo ( Tc' ).

T(p)= Ts+ Tc' .

Il tempo impiegato dall'algoritmo sequenziale, tenendo presente che le operazioni relative alla

parte parallela sono ora eseguite sequennzialmente è : T(1)= T s+ pTc'. Si assume T(p) come tempo

unitario ossia T(p)= Ts+ Tc'=1 e quindi Tc' = 1 - Ts allora T(1)= Ts+ p(1-Ts).Posto Ts=α

' , la LEGGE DI GUSTAFSON ( reintrerpretazione della legge di ware) dice che:

Si possono ottenere speed up prossimi a quello ideale. Nell'algoritmo della somma abbiamo

calcolato speed up ed efficienza scalata aumentando la complessità di tempo del problema in

maniera proporzionale al numero di processori ovvero nel passare da p0 a p1 processori con p1=kp0

siamo passati da T(p0,n

0) a T(p

1,n

1) con n

1=kn

0. Ovvero

T(1,n1)=I(p0,p1,n0) cioè


6/25

La funzione I esprime la legge secondo cui deve aumentare la complessità di tempo dell'algoritmo

sequenziale con dimensione n1 su p1 processori a partire da p0 e da T(1,n0) affinchè l'efficienza

scalata non degradi. I è detta ISOEFFICIENZA. L'isoefficienza è calcolata:

Nell'algoritmo della somma nel passare da p0 a p1 la complessità di tempo del problema deve

aumentare rispetto alla dimensione iniziale del fattore . L'algoritmo della somma èscalabile.

Se si esegue l'algoritmo su un calcolatore MIMD-DM il tempo di esecuzione dipende non solo dal

numero di operazioni eseguite ma anche dal tempo di comunicazione che in genere è molto più

grande di quello di calcolo perchè richiedere la velocità della rete etc.

Per l'algoritmo della somma di n numeri posto p=2k ( per semplicità) considerando le

comunicazioni T(p)= ( -1 log2p ) tcalc + (log2p)tcom In generale il tempo di esecuzione di un algoritmo parallelo, distribuito su p processori,

comprende 3 componenti:

Ts tempo per eseguire la parte sequenziale

Tc/p tempo per eseguire la parte parallela

T0 costo di comunicazione che è maggiore o uguale a 0

T(p)= Ts + Tc/p + T0

L'Overhead di comunicazione unitario è dato da:

dove

è il tempo di

comunicazione di un dato e è il tempo di esecuzione di una operazione floating point.L'overhead di comunicazione fornisce una misura del peso della comunicazione sul tempo diesecuzione dell'algoritmo.

IL PROBLEMA DEL BILANCIAMENTO

Una cattiva ripartizione del carico di lavoro tra i processori induce un tempo di attesa o tempo di

sincronizzazione e quindi un aumento del tempo di esecuzione quindi il tempo di esecuzione può

dipendere del bilanciamento del carico computazionale tra i processori.

In generale il tempo di esecuzione di un algoritmo parallelo, distribuito su p processori,

comprende 3 componenti:

Ts tempo per eseguire la parte sequenziale

Tc/p tempo per eseguire la parte parallela

T0 costo di comunicazione e sincronizzazione che in genere è sempre maggiore di 0.

T(p)= Ts + Tc/p + T0

Lo Speed up misura la riduzione del tempo di esecuzione su p processori rispetto aquello impiegato su 1 processore. Come possiamo scegliere T(1)?

Possiamo scegliere T(1) come il tempo di esecuzione dell'algoritmo parallelo su un processore

anche se potrebbe richiedere più operazioni oppure come il tempo di esecuzione del migliore

algoritmo sequenziale ma nasce di problema di capire chi è il migliore algoritmo.


7/25

SPEED UP ED EFFICIENZA PER L'ALGORITMO DELLA SOMMA

I STRATEGIA

Dati n ( maggiore o uguale a 2 ) numeri e p processori con p < 2n+1, il numero di dati che diamo ad

ogni processo è :

T(1)=(n-1)tcalc ; T(p)=(r-2+p)tcalc

Considerando i passi di comunicazione abbiamo: T(1)=(n-1)tcalc ; T(p)=(r-2+p)tcalc+(p-1)tcom Si

calcola speed up ed efficienza tenendo conto che tcom=htcalc ( in realtà noi lo facciamo per h=2 ).

II STRATEGIA

Dati n ( maggiore o uguale a 2 ) numeri e p=2k processori con k


8/25

per un totale di operazioni eseguite in paralleloSeguono altre p -1 fasi di calcolo, in tutte queste fasi un solo processore compie un unica

operazione di somma quindi: operazioni eseguite da un solo processore. In totalevengono eseguite

operazioni.

Per la legge di Ware-Admahl: Nel nostro caso:

Per la legge di Ware-Amdahl generalizzata:

dove è la frazione di operazioni eseguite con k processori.Nel nostro caso:

Tutti gli altri sono nulli. In questo caso il risultatocorrisponde a quello trovato con la legge precedente.

II STRATEGIADati n ( maggiore o uguale a 2 ) numeri e p=2

k processori con k


9/25


Tutti gli altri sono nulli. In questo caso il risultato non corrisponde a quello trovato con la legge

precedente.

III STRATEGIA

Nel caso della terza strategia per la legge di Ware α=0 perchè in sequenziale non è eseguita

nessuna operazione. Nel caso della legge di Ware generalizzata solo =1.MPI

MPI è lo strumento software utilizzato per lo sviluppo di algoritmi in ambiente di calcolo MIMD-

DM, è un ambiente standard che è stato creato per il paradigma del message passing per i sistemi

a memoria distribuita ossia:

ogni processore ha una prorpia memoria locale alla quale accede direttamente in maniera

esclusiva

ogni processore può conoscere i dati in memoria di un altro processore o far conoscere i propri

attraverso il trasferimento di dati ed è per questo che si chiama message passing. Per renderlo

portabile si è sviluppato lo standard e quindi abbiamo il message passing interface.

In ambiente MPI un programma è visto come un insieme di componenti ( o processi ) concorrenti.

L'MPI li prende, li lancia e li collega attraverso diverse categorie: gruppo, contesto e

communicator. Ogni componente concorrente del programma ( pezzo di codice ) viene affidata ad

un gruppo di processori. In ciascun gruppo ad ogni processore è associato un identificativo.

L'identificativo è un intero, compreso tra 0 e il numero totale di processori appartenenti ad un

gruppo decrementato di un unità. Processori appartenenti a uno o più gruppi possono avere

identificativi diversi, ciascuno relativo ad uno specifico gruppo.

A ciascun gruppo di processori viene attribuito un identificativo detto contesto. Il contestodefinisce l'ambito in cui avvengono le comunicazioni tra processori di uno stesso gruppo. Se la

spedizione di un messaggio avviene in un contesto, la ricezione deve avvenire nello stesso

contesto. Ad un gruppo di processori appartenenti ad uno stesso contesto viene assegnato un

identificativo: il communicator.Il communicator racchiude tutte le caratteristiche dell'ambiente di

comunicazione. A seconda del problema che ho da risolvere mi costruisco il communicator più

comodo. Esistono due tipi di communicator. L'intra-communicator in cui le comunicazioni

avvengono all'interno di un gruppo di processori.

L'inter-communicator in cui le comunicazioni avvengono tra gruppi di processori.

Tutti i processori fanno parte di un unico communicator detto MPI_COMM_WORLD in cui tutti

comunicano con tutti.L'MPI è una libreria che comprende:

funzioni per definire l'ambiente

funzioni per comunicazioni 1 a 1

funzioni per comunicazioni collettive

funzioni per operazioni collettive

FUNZIONI D'AMBIENTE

Nel programma .c occorre includere la libreria mpi.h perchè contiene alcuno direttive necessarie al

preprocessore per l'utilizzo dell' MPI ( #include "mpi.h" )

MPI_Init(&argc,&argv)

Deve essere chiamata una sola volta prima di ogni altra routine MPI. Inizzializza l'ambiente diesecuzione MPI, definisce l'insieme dei processori attivati ( il communicator MPI_COMM_WORLD).

argc è il numero di stringhe che ci sono nella riga di comando e argv è il vettore di stringhe che


10/25

contiene tutte le stringhe della riga di comando e sono gli argomenti del main( sono passate per

indirizzo ).

MPI_Finalize()

Determina la fine del programma MPI e dopo questa routine non è possibile richiamare nessun

altra routine di MPI.

MPI_Comm_rank(MPI_COMM_WORLD,&menum)Questa routine permette al processore chiamante, appartenente al communicator

MPI_COMM_WORLD, di memorizzare il proprio identificativo nella variabile menum

MPI_Comm_size(MPI_COMM_WORLD,&nproc)

Questa routine permette al processore chiamante di memorizzare nella variabile nproc il numero

totale di processori concorrenti appartenente al communicator MPI_COMM_WORLD.

FUNZIONI DI COMUNICAZIONE

Per comunicare un dato in ambiente MPI occorre specificare: l'indirizzo in memoria del dato, la

dimensione del dato e il tipo del dato (MPI_INT, MPI_FLOAT....).

La spedizione o la ricezione di un messaggio da parte di un processore può essere bloccante o non

bloccante. Se un processore esegue una comunicazione bloccante si arresta fino a conclusionedell'operazione. Se un processore esegue una comunicazione non bloccante presegue senza

preoccuparsi della conclusione dell' operazione.

COMUNICAZIONI BLOCCANTI IN MPI

MPI_Send(&n,1,MPI_INT,1,tag,MPI_COMM_WORLD)

Con questa routine un processore spedisce l'indirizzo di n di dimensione 1, di tipo intero al

processore 1 il cui identificativo di comunicazione è tag nel communicator comm world.

MPI_Recv(&n,1,MPI_INT,0,tag,MPI_COMM_WORLD,&info)

Con questa routine un processore riceve l'indirizzo di n, di dimensione1, di tipo intero, dal

processore 0, il cui identificativo di comunicazione è tag, nel communicator comm world. La

variabile info che è tipo MPI_status contiene tutte le informazioni sulla comunicazione. MPI_Status info

E' un tipo di dato strutturato, composto da tre campi: identificativo del processore da cui

ricevere, identificativo del messaggio, identificativo di errore.

Se devo comunicare più informazioni userò un for per le send in cui cambia a chi mandare

l'informazione e il tag. La recv la fanno tutti una sola volta e cambia solo il tag che deve essere,

se in send metto tag+i in recv mi serve tag+menum.

MPI_Get_count(&info,MPI_INT,&num)

Questa routine permette di conoscere il numero, num, di elementi ricevuti, di tipo MPI_INT,

nella spedizione individuata da info.

FUNZIONI NON BLOCCATI PER LA SPEDIZIONE

MPI_Isend(&n,1,MPI_INT,1,tag,MPI_COMM_WORLD,&rqst)

Analogo a quello bloccante. Il parametro rqst di tipo MPI_rqst è simile a info, contiene le

informazioni dell'intera spedizione. Dopo che il processore ha inviato il parametro n è libero di

procedere nelle successive istruzioni senza aspettare l'ok. La comunicazione termina quando

chi ha inviato svuota il suo buffer e chi ha ricevuto lo riempie.

MPI_Irecv(&n,1,MPI_INT,1,tag,MPI_COMM_WORLD,&rqst)

Analogo a quello bloccante. Il parametro rqst di tipo MPI_rqst è simile a info, contiene le

informazioni dell'intera spedizione. Dopo che il processore ha inviato il parametro n è libero di

procedere nelle successive istruzioni.


11/25

Le operazioni non bloccanti utilizzano l'oggetto request di tipo MPI_request che collega

l'operazione che inizia la comunicazione in esame con l'operazione che la termina.

MPI_Test(&rqst,&flag,&info)

Il processore che riceve verifica se la ricezione di n, individuata da rqst, è stata completata; intal caso flag=1 altrimenti flag=0.

MPI_Wait(&rqst,&info)

Il processore controlla lo stato della comunicazione non bloccante identificata da rqst, e si

arresta sl quando l'operazione in esame si è conclusa. In info ci sono informazioni sul

completamente dell'operazione di Wait.

Le comunicazioni di tipo non bloccante hanno due vantaggi:

1) il processore non è obbligato ad aspettare in stato di attesa2)Più comunicazioni possono avere luogo contemporaneamente sovrapponendosi almeno in parte

tra loro.

FUNZIONI PER COMUNICAZIONI E OPERAZIONI COLLETTIVE

Per comunicazioni che coinvolgono solo due processori si considerano le funzioni MPI per

comunicazioni uno a uno. Esistono, però, modi per fare comunicazioni collettive.

Le operazioni collettive sono eseguite da tutti i processori appartenenti ad un communicator.

Possono richiedere una sincronizzazione e tutte queste operazioni sono bloccanti. Le operazioni

collettive permettono: la sincronizzazione dei processi, l'esecuzione di operazioni globali e una

gestione ottimizzata degli input/output seguendo uno schema ad albero.

MPI_Barrier (MPI_COMM_WORLD)

Questa routine fornisce un meccanismo di sincronizzazione per tutti i processori del

communicator: ogni processore si ferma fin quando tutti i processori del communicator non la

eseguono.

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

Il processore con identificativo 0 spedisce n di dimensione 1 di tipo MPI_INT a tutti i processori

del communicator.

MPI_Gather(&n, num, MPI_INT, &N, NUM, MPI_INT, 1, MPI_COMM_WORLD)

Il processore 1 riceve da tutti gli altri processori del comunicator dei dati n che concatena in N.

num contiene il numero di dati da spedire da ciascun processore e NUM contiene il numero di

dati da ricevere.

MPI_Scatter(&n, num, MPI_INT,&N, NUM, MPI_INT,0,MPI_COMM_WORLD)

Il processore 0 distribuisce a tutti gli altri processori ( se stesso compreso ) del comunicator, i

dati contenuti in n. Il contenuto di n viene suddiviso in nproc segmenti ciascuno di dimensione

num. Il primo segmento viene affidato al processore 0, il secondo al processore 1 e così via.


12/25

MPI possiede una classe di operazioni collettive chiamate operazioni di riduzione. In ciascuna

operazione di riduzione tutti i processori di un communicator contribuiscono al risultato di

un'operazioone. Sono operazioni che da più dati in input otteniamo solo un dato in output (

somma, max,min...)

MPI_Reduce(&sum,&sumtot,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD)

Il processore 0 ottiene la somma degli elementi sum, di tipo MPI_INT, di dimensione 1,

distribuiti tra tutti i processori del communicator. Il risultato lo pone nella propria variabile

sumtot.

MPI_Wtime()

E' una funzione di MPI che restituisce un tempo in secondi ( double ).

es: double t0t0=MPI_Wtime()

LE TOPOLOGIE E LE GRIGLIE

Una topologia è la geometria virtuale in cui si immaginano disposti i processori, può non avere

alcun nesso con la disposizione reale.

Una griglia è un comunicator e la dichiaro:

MPI_Comm comm_grid

Per creare questa griglia virtuale che serve a facilitare le comunicazioni nel caso in cui si lavora con

le matrici userò i seguenti comando MPI.

MPI_Cart_Create(MPI_COMM_WORLD,dim,ndim,period,reorder,&comm_grid)

Operazione collettiva che restituisce un nuovo communicator comm_grid. Ogni processo

dell'ambiente MPI_COMM_WORLD ( di partenza ) definisce la griglia che si chiama comm_grid

di dimensione dim ( supponiamo 2 ) e non periodica lungo le due componenti ( period[i]=0 per

ogni i ). Il numero di righe e di colonne sono memorizzare nel vettore ndim, i processi non sono

riordinati secondo un particolare schema ( non è permesso riordinare i menum , reorder[i]=0

per ogni i )

MPI_Cart_coords(MPI_Comm comm_grid,menum, dim,coordinate)

Operazione collettiva che restituisce a ciascun processo di comm_grid con identificativo

menum le sue coordinate all'interno della griglia predefinita. Coordinate è un vettore di

dimensione dim i cui elementi rappresentano le coordinate di un processo all'interno della

griglia predefinita.

OPEN MP

Se il sistema è tale che diverse CPU sono collegate alla stessa memoria fisica è opportuno un

parallelismo a memoria condivisa. Cosa cambia rispetto ad un parallelismo di tipo distribuito?

Per un sistema operativo moderno, l'unità di base della CPU è il thread ( è un flusso di istruzioni

indipendente da altri che deve essere eseguito sequenzialmente su una CPU).

Un processo di definisce come un programma in esecuzione, è costituiti da almeno un thread.

Threads diversi possono essere eseguiti indipendentemente su CPU/core diversi. Anche se i core

sono collegati fisicamente alla stessa memoria processi diversi non condividono le stesse aree di


13/25

memoria ( che vengono assegnate dal sistema operativo). Perchè lavorino insieme bisogna gestire

una comunicazione esplicita. I threads di uno stesso processo condividono la stessa area di

memoria. Si può pensare di dividere il lavoro tra i threads di uno stesso processo. I threads sono

coordinati attraverso la sincronizzazione degli accessi alle variabili condivise. Ogni thread ha una

locazione privata ma per la comunicazione è necessario avere alcune variabili condivise quindiabbiamo quest'area di memoria condivisa e per accedervi bisogna sincronizzare.

SOMMA

Tutti i threads leggono in contemporanea i numeri da sommare ognuno fa la prorpia somma

parziale e la salva in una variabile diversa. Per fare la somma totale ogni thread aggiorna sumtot

con la propria somma parziale ma bisogna sincronizzare gli accessi a tale variabile con il

meccanismo dei semafori. Quando un thread lavora su sumtot mette un semaforo ( rosso ) agli

altri threads.

#pragma omp parallel for reduction(+: sumtot)

for i=0;i


14/25

Variabili d'ambiente

Per modificare il valore delle variabili di controllo interne prima dell'esecuzione.

Il primo passo per parallelizzare un codice sequenziale con Open Mp consiste nell'individuare quali

istruzioni possono essere eseguire in parallelo. Una volta individuate le porzioni di codice cheposso essere parallelizzate si introducono opportune direttive con le relative clausole.

Le direttive si applicano al costrutto seguente:

#pragma omp direttive [clausole]

Il costrutto parallel forma un team di thread ed avvia un'esecuzione parallela.

#pragma omp parallel [clausole]

{

blocco istruzioni }

Le clausole possono essere:

if(espressione scalare) può comparire più di una volta

num_thread(espressione intera) può comparire al più una volta

default(shared| none )

private (list)

first private(list)

shared(list)

copyin(list)

reduction(operator:list) equivalente a MPI_Reduce

Non è considerato l'ordine delle clausole.

Alla fine del blocco di istruzioni è sottintesa una barriera di sincronizzazione: tutti i threads

aspettano che tutti gli altri abbiano completato prima di tornare all'esecuzione sequenziale ( qui

non c'è la clausola nowait perchè dopo devono morire). Tutto quello che segue questa direttiva è

eseguito da ogni thread. Dopo aver generato i threads è necessario stabilire anche una

distribuzione del lavoro tra i thread del team per evitare ridondanze.

Quali sono le direttive di WorkSharing?

Ci sono tre tipi di costrutti detti WorkSharing perchè si occupano della distribuzione del lavoro al

team di threads : FOR, SECTIONS, SINGLE.

Anche all'uscita di un costrutto WorkSharing è sottintesa una barriera di sincronizzazione, se non

diversamente specificato dal programmatore.

Il costrutto FOR specifica che le iterazioni del ciclo contenuto devono essere distribuite tra i thread

del team.

#pragma omp for [clausole]

{

ciclo for }



15/25

private (list)

first private(list)

last private(list)

schedule(kind[,chunck_ size])

collapse(n)ordered

nowait esclusione della barriera in uscita

reduction(operator:list) equivalente a MPI_Reduce

Perchè usiamo il for e non il while? perchè il while vuole una condizione per terminare ma non la

conosciamo a priori e nel for sono sicura di sapere quante sono le iterazioni fatte.

Il costrutto SECTIONS conterrà un insieme di costrutti section ognuno dei quali verrà eseguito da

un thread del team.

#pragma omp sections [clausole]

{

[#pragma omp section [clausole]

blocco]

[#pragma omp section [clausole]

blocco]

}


private (list)

first private(list)

last private(list)

nowait

reduction(operator:list)

Le diverse sezioni devono poter essere eseguite in ordine arbitrario ( devono essere indipendenti

tra loro ). C'è rischio di sbilanciamento del carico se una sezione è più lunga di un ' altra.

Il costrutto SINGLE specifica che il blocco di istruzioni successivo verrà eseguito da un solo thread

qualsiasi del team. Gli altri attendono che questo termini la sua porzione di codice.

#pragma omp single [clausole]

{

blocco di istruzioni

}



16/25

private (list)

first private(list)

copyprivate(list)

nowait elimina la barriera sottintesa alla fine del costrutto

I costrutti WorkSharing possono essere combinati con il costrutto parallel e le clausole ammesse

sono l'unione di quelle ammesse per ognuno.

Il costrutto MASTER specifica che il blocco di istruzioni successivo verrà eseguito dal solo master

thread. Non sono sottintese barriere di sincronizzazione nè all'ingresso nè all'uscita del costrutto

perchè il master thread vive a se stante.

#pragma omp master

{

blocco istruzioni

}

Il costrutto CRITICAL forza l'esecuzione del blocco successivo ad un thread alla volta: è utile per

gestire regioni critiche. Si può assegnare un nome alla regione che sarà globale al programma.

#pragma omp critical [(nome)]

{

blocco istruzioni

}

Il costrutto BARRIER forza i thread di uno stesso task ad attendere il completamento di tutte leistruzioni precedenti da parte di tutti gli altri. Al momento del barrier ( implicito o esplicito ) si crea

una lista consistente dei dati dei thread.

#pragma omp barrier

Non tutte le clausole sono valide per tutte le direttive.

-default(shared| none )

Controlla gli attributi di data-sharing delle variabili in un costrutto. Se non specificata questa

clausola, il compilatore stabilisce quali variabili devono essere private per ogni thread. In genere

tutti i dati sono condivisi da tutti i thread.shared: tutte le variabili saranno considerate condivise

none: decide tutto il programmatore

- shared(list)

gli argomenti contenuti in list sono condivisi tra i thread del team

- private (list)

gli argomenti contenuti in list sono privati per ogni thread del team. Le variabili private hanno un

valore indefinito all'entrata e all'uscita della regione parallela perchè devono essere variabili che

non contengono info importanti.

- first private(list)


17/25

gli argomenti contenuti in list sono privati per i thread e vengono inizializzate con il valore che

avevano prima di incontrare la regione parallela.

- last private(list)

gli argomenti contenuti in list sono privati per i thread e all'uscita le variabili manterranno l'ultimo

valore della sezione parallela.- reduction(operator:list)

Gli argomenti contenuti in list verranno combinati utilizzando l'operatore associativo specificato.

Al termine la variabile sarà condivisa.

-nowait

elimina la barriera implicita alla fine del costrutto ( non della regione parallela ). I thread non

aspettano gli altri e continuano.

-schedule(kind[,chunck_ size])

esiste solo per la for, specifica il modo ( kind ) di distribuire le iterazioni del ciclo seguente;

chunk_size è il numero di iterazioni contigue da assegnare allo stesso thread, mentre kind puòessere:

static: secondo uno scheduling round-robin

dynamic:assegnati su richiesta, quando un thread termina il proprio chiede un altro chunk.

guide: variante del dynamic

runtime:decisione presa a runtime attraverso la variabile d'ambiente OMP_SCHEDULE (stabilisce

lo scheduling di defoult da applicare nei costrutti for)

Il modo consigliato per verificare il tempo di esecuzione del programma è utilizzare la funzione

int gettimeofday(timeval *tp, NULL) cotenuta in . La funzione va chiamata subito

dopo e subito prima la regione parallela.

PRODOTTO MATRICE-VETTORE a memoria distribuita

Quali sono i sotto problemi indipendenti?

In generale il prodotto di una matrice A per un vettore x dà luogo ad un vettore le cui componenti

sono i prodotti scalari tra la i-esima riga di A e il vettore x. i prodotti scalari possono essere

calcolati indipendentemente gli uni dagli altri. Ci sono varie strategie!

I STRATEGIA

Suddividiamo la matrice A in blocchi di righe ( in genere il numero di processori è più piccolo del

numero di righe quindi partizioniamo la matrice in blocchi di righe così da sfruttare il parallelismo

a blocchi ) e assegniamo ogni blocco a ciascun processore. Assegniamo interamente il vettore x a

tutti i processori. Ciascun processore è in grado di calcolare n/p componenti del vettore soluzione.

Non sono richieste interazioni tra i processori se non alla fine per ottenere il risultato finale ma il

vettore x è assegnato interamente a tutti i processori.


18/25

II STRATEGIA

Suddividiamo la matrice A in blocchi di colonne e assegniamo ogni blocco a ciascun processore.

Distribuiamo le componenti del vettore x tra i processori ( tanti elementi quante sono le colonne

di A assegnate ). Ciascun processore è in grado di calcolare tutte le componenti parziali del vettore

soluzione. Per ottenere il vettore soluzione bisogna far interagire i processori facendo la somma inparallelo in modo che tutti i processori hanno il risultato( analogo a quello della somma).

III STRATEGIA

Suddividiamo la matrice A in blocchi quadrati ( di colonne e di righe ) e assegniamo ogni blocco a

ciascun processore. Distribuiamo le componenti del vettore x tra i processori ( tanti elementi

quante sono le colonne di A assegnate ). Ciascun processore è in grado di calcolare una parte delle

componenti parziali del vettore soluzione. Per ottenere il vettore soluzione bisogna far interagire i

processori facendo la somma in parallelo in modo che tutti i processori hanno il risultato( analogo

a quello della somma).


19/25

Matrice vettore a memoria condivisa

#pragma omp parallel for defoult(none)shared(A,m,n,x,b)private(i,j)

for i=0;i


20/25

SPEED UP ED EFFICIENZA PER L'ALGORITMO DEL PRODOTTO MATRICE - VETTORE

I STRATEGIA

Ax=b AєRnxm

xєRm

b єRn

Suddividiamo la matrice A in blocchi di righe e assegniamo ogni blocco a ciascun processore . Il

vettore x è dato intero a tutti i processori. Ogni processore calcola un prodotto matrice vettore più

piccolo e non si deve ricompilare il risultato.

Dati p processori distribuiti sulle righe della griglia

T(1)=n(2m-1)tcalc ; T(p)=r(2m-1)tcalc

Considerando i passi di comunicazione abbiamo: T(1)=n(2m-1)tcalc ; T(p)=r(2m-1)tcalc +log2p tcom

Si calcola speed up ed efficienza tenendo conto che tcom=htcalc ( in realtà noi lo facciamo per h=2 ).

II STRATEGIA

Ax=b AєRnxm

xєRm

b єRn

Suddividiamo la matrice A in blocchi di colonne e assegniamo ogni blocco a ciascun processore . Il

vettore x è distribuito tra i processori. Ogni processore calcola le componenti parziali del vettore

soluzione si. Si deve ricompilare il risultato : b è la somma di s i.

Dati q processori distribuiti sulle colonne della griglia

T(1)=n(2m-1)tcalc ; T(p)=r(2c-1)tcalc+nlog2q tcalc

Considerando i passi di comunicazione abbiamo: T(1)=n(2m-1)tcalc ; T(p)=r(2c-1)tcalc+nlog2q

tcalc+nlog2q tcom Si calcola speed up ed efficienza tenendo conto che tcom=htcalc ( in realtà noi lo

facciamo per h=2 ).

III STRATEGIA

Ax=b AєRnxm

xєRm

b єRn

Abbiamo processori idealmente disposti in una griglia pxq, distribuiamo la matrice per blocchi

rettangolari. Il vettore x viene distribuito tra i processori sulla stessa colonna della griglia. Bisogna

ricompilare il risultato solo lungo le righe della griglia.

Dati pxq processori

T(1)=n(2m-1)tcalc ; T(p)=r(2c-1)tcalc+rlog2q tcalc


21/25

Considerando i passi di comunicazione abbiamo: T(1)=n(2m-1)tcalc ; T(p)=r(2c-1)tcalc+rlog2q

tcalc+rlog2q tcom+ rlog2p tcom Si calcola speed up ed efficienza tenendo conto che tcom=htcalc ( in

realtà noi lo facciamo per h=2 ).

SPEED UP ED EFFICIENZA PER L'ALGORITMO DELLA SOMMA CON LA LEGGE DI WARE-AMDAHL

I STRATEGIA

Ax=b AєRnxm

xєRm

b єRn

Suddividiamo la matrice A in blocchi di righe e assegniamo ogni blocco a ciascun processore . Il

vettore x è dato intero a tutti i processori. Ogni processore calcola un prodotto matrice vettore più

piccolo e non si deve ricompilare il risultato.

Dati p processori , le righe del processore i saranno:

per un totale di .Per la legge di Ware-Admahl: Nel nostro caso:


dove è la frazione di operazioni eseguite con k processori.Nel nostro caso: Tutti gli altri sono nulli. In questo caso il risultatocorrisponde a quello trovato con la legge precedente.

II STRATEGIA

Ax=b AєRnxm

xєRm

b єRn

Suddividiamo la matrice A in blocchi di colonne e assegniamo ogni blocco a ciascun processore . Il

vettore x è distribuito tra i processori. Ogni processore calcola le componenti parziali del vettore

soluzione si. Si deve ricompilare il risultato : b è la somma di s i.

Dati q processori , le colonne del processori i sono:


22/25

per un totale di

Per la legge di Ware-Admahl: Nel nostro caso:



Tutti gli altri sono nulli. In questo caso il risultato corrisponde aquello trovato con la legge precedente.

III STRATEGIA

Nel caso della terza strategia per la legge di Ware α=0 perchè in sequenziale non è eseguita

nessuna operazione. Nel caso della legge di Ware generalizzata solo =1.


23/25

PRODOTTO MATRICE-MATRICE A·B=C

Quali sono i sotto problemi indipendenti?

In generale gli elementi di C sono calcolati effettuando i prodotti scalari di ciascuna riga di A per

ciascuna colonna di B e tali prodotti scalari Cij=AiB j sono calcolati in maniera indipendente l'uno

dall'altro.Ci sono varie strategie!

I STRATEGIA

Decomponiamo A per blocchi di righe e B per blocchi di colonne e li assegniamo a ciascun

calcolatore.

Ciascun calcolatore può calcolare p prodotti matrice matrice di dimensione più piccola ottenendo

solo alcune componenti della matrice C. Per calcolare le altre devono interagire scambiandosi i

blocchi di colonne della matrice C. In tal modo siamo riusciti a calcolare le componenti mancanti di

C.

II STRATEGIA

Decomponiamo A per blocchi di colonne e B per blocchi di righe e li assegniamo a ciascun

calcolatore.

Ciascun calcolatore può calcolare un contributo di ciascun elemento della matrice C: C1...C

p. Per

ottenere C i risultati parziali vanno sommati. In paralleo tutti i processori faranno la somma deicontributi parziali.


24/25

III STRATEGIA

Suddividiamo entrambe le matrici in blocchi di colonne e assegniamoli ai processori. Ciascun

processore può calcolare un contributo di una parte della matrice C. Per completare i contributi

calcolati devono scambiarsi i blocchi di colonne della matrice A. Dopo lo scambio ciascun

processore ha un blocco di C e basta ricomporli per ottenere C.

IV STRATEGIA - Broadcast Multiply Rolling

Decomponiamo le matrici in blocchi quadrati. I processori vengono disposti in una griglia

cartesiana e le matrici vengono distribuite in modo che al processore Pij vengono assegnati i

blocchi Aij e Bij

La strategia è costituita da p passi. Si parte dalla diagonale principale della griglia di processori, ad

ogni passo k, si considera la k-esima diagonale situata al di sopra di quella principale. I processori

situati lungo la diagonale effettuano una comunicazione collettiva dal blocco di A in loro possesso

a tutti i processori della medesima righa. Inoltre ad ogni passo ciascun processore effettua una

comunicazione del proprio blocco di B al processore situato nella stessa colonna e nella righa

precedente.


25/25

BITONIC SORT

E' un algoritmo che non è di algebra lineare. Vogliamo ordinare un vettore su un calcolatore

MIMD-DM con p processori.

Dobbiamo analizzare 3 punti:

1)Algoritmo per l'ordinamento di un vettore bitonico mediante il bitonic sort

DEFINIZIONE s=(s1 s2 .........sn) è un vettore bitonico se e solo se esiste un indice kє[1,n] tale che: s1≥s2≥......≥sk e sk+1≤....sn oppure s1≤s2≤.....≤sk e sk+1≥....sn ossia sk è l'elemento di separazione

tra le due parti del vettore una ordinata in modo crescente e l'altra in modo decrescente. Se k =n il

vettore è detto MONOTONICO.

Ordinare un vettore bitonico. A partire dalle due metà già ordinate si confrontano gli elementi

omologhi scambiando gli elementi di ciascuna coppia che non si trovano nell'ordine desiderato. Si

ripete questo procedimento applicandolo separatamente a ciascuna metà. Si prosegue fino a

quando si arriva ad applicarlo a coppie di elementi. Ad ogni passo e per ogni coppia si effettuano

operazioni di COMPARE-EXCHANGE ( confronta e scambia ) che viene applicata ricorsivamente ai

sottovettori di lunghezza uguale alla metà di quella precedente. Ci sono due tipo di COMPARE-EXCHANGE: Co-Ex-Lo se si vuole ordinare la coppia in senso crescente e Co-Ex-Hi se si vuole

ordinare la coppia in senso decrescente.

Complessità di tempo: Ad ogni passo si dimezza la lunghezza del vettore, l'algoritmo è costituito da

log2n passi ad ogni passo si effettuano n/2 Co-Ex allora la complessità di tempo è O(n log 2n)

confronti che è migliore di algoritmi con complessità n2 ma il vettore di partenza deve essere

bitonico.

2) algoritmo per ordinare un vettore qualsiasi mediante il general bitonic sort

L'idea è quella di trasformare il vettore qualsiasi in un vettore bitonico e applicare il bitonic sort.

Partizioniamo il vettore in coppie e ordiniamo le coppie prima a 2 a 2 poi 4 a 4 ....etc con BBS fino

ad avere 2 sottosequenze ordinate in modo bitonico di lunghezza n/2. Ordiniamo ciascuno dei duesottovettori in modo da avere un unico vettore bitonico a questo punto applico il bitonic sort e

ottengo il vettore ordinato.

Complessità di tempo: l'algoritmo è costituito da log2n passi, ad ogni passo si utilizza l'algoritmo

BBS su sequenze di lunghezza minore di n la cui complessità di tempo è O(n log2n) allora la

complessità di tempo di GBS è O ( nlog22n )

3) algoritmo parallelo per l'ordinamento di un vettore qualsiasi ( parallel general bitonic sort )

L'operazione di confronto-scambio che nell'algoritmo sequenziale è applicata a due elementi viene

ora applicata ad una coppia di processori.

DEFINIZIONE p0

Calcolo Parallelo - Riassunto Sbobbinato Slide.

Documents

Transcript of Calcolo Parallelo - Riassunto Sbobbinato Slide.