Principi Di Parallelismo

1°edizione 7 - 18 luglio 2008 2°edizione 8 – 19 settembre 2008

Principi di parallelismo

Giovanni Erbacci - [email protected]

Gruppo Supercalcolo - Dipartimento Sistemi e Tecnologie

Giovanni Erbacci


1

Elaborazione

ParallelaElaborazione sequenziale

Pipelining

Elaborazione parallela

53

Giovanni Erbacci


2

Parallel Computing

Cosa si intende per parallel computing?

– Parallel computing è una tecnica di programmazione che coinvolge l’utilizzodi più processori che operano insieme su un singolo problema

– Il problema globale è suddiviso in parti, ciascuna delle quali viene eseguitada un diverso processore in parallelo.

Programma Parallelo

programma composto di tasks (processi) che comunicano tra loro per realizzare un obiettivo computazionale complessivo.

Giovanni Erbacci


3

Calcolatori Paralleli

P M

54

Giovanni Erbacci


4

P

M

P

MP

M

P

M

P

M

P

M

N

MP P

PP

M

P P

PP

Giovanni Erbacci


5

Un modello di programmazione è una collezione di astrazioni di programma che

fornisce una visione semplificata e trasparente del sistema hardware e software

nella sua globalità.

I processori di un calcolatore parallelo comunicano tra loro secondo 2 schemi di

comunicazione:

– Shared memory: I processori comunicano accedendo a variabili condivise

– Message-passing: I processori comunicano scambiandosi messaggi

Questi schemi identificano altrettanti paradigmi di programmazione parallela:

- paradigma a memoria condivisa o ad ambiente globale (Shared memoy)

i processi interagiscono esclusivamente operando su risorse comuni

- paradigma a memoria locale o ad ambiente locale (Messsage passing)

non esistono risorse comuni, i processi gestiscono solo informazioni locali e l'unica

modalità di interazione è costituita dallo scambio di messaggi (message passing)

55

Giovanni Erbacci


6

Paradigma Message Passing

A B

Giovanni Erbacci


7

Paradigma Shared Memory

……

56

Giovanni Erbacci


8

Esempio: Sort di n numeri

#define SWAP(a,b) { int t; t=a; a=b; b=t; }

void SORT( int a[], int n )

{

int i, j;

for(i=0;i<n;i++)

{

for(j=1;j<(n-i);j++)

{

if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);}

} }

Input: una sequenza di n numeri <a1, a2, a3, … an>

Output: una permutazione <a’1, a’2, a’3, … a’n> degli elementi,

tale che a’1!!!! a’2, !!!! a’3!!!! …!!!! a’n

Giovanni Erbacci


9

Sort di n numeri / 1

Idea: - si potrebbe dividere il vettore da ordinare in due vettori di n/2

elementi ciascuno,

- ordiare i due vettori separatamente

- richiamare una procedura di merge per ricomporre i due

vettori ordinati precedentemente

SORT(a[0 : n/2-1])

SORT(a[n/2 : n-1])

MERGE(a[0 : n/2-1], a[n/2 : n-1])

57

Giovanni Erbacci


10

Complessità

L’ algoritmo di sort richiede n-1 passi:

ogni passo pone un elemento nella sua corretta posizione

il passo imo fa n-I confronti e scambi.

Complessità: O(n2) .

L’ algoritmo di merge opera la fusione facendo n confronti:

Complessità: O(n) .

Giovanni Erbacci


11

Complessità / 1

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

0 10 20 30 40 50 60 70 80 90 100

(n**2 )/ 2

(n**2 )/ 4 + n

(n**2 )/ 8 + n

n**2

La procedura di sort nella versione modificata viene richiamata 2 volte e

ogni volta ordina n/2 elementi mentre la procedura merge è richiamata

una sola volta ed esegue n confronti.

Nella versione modificata vengono eseguiti 22

2 4

2

2

" + = +

n

nn

n confronti.

58

Giovanni Erbacci


12

Sort su k Processori

P0 P1 P2 …….. Pk-1

Giovanni Erbacci


13

Problema

Lettura dati da ordinare

SORT(a[0 : n/2-1])

SORT(a[n/2 : n-1])

MERGE(a[0 : n/2-1], a[n/2 : n-1])

Scrittura del vettore ordinato

59

Giovanni Erbacci


14

Indirizzamento Locale o Globale

s ∑ ∑ m

Giovanni Erbacci


15

Indirizzamento Globale

P0

P3

P2

P1

60

Giovanni Erbacci


16

Indirizzamento Locale

P0

P3

P2

P1

??

Giovanni Erbacci


17

Filosofia Master Slave e SPMD

main (int argc, char **argv){

if (process is to become a controller process){

Controller (/* Arguments /*);}else{

Worker (/* Arguments /*);}

}

PROGRAM

IF (process is to become a controller process)

THEN

CALL Controller (/* Arguments /*)

ELSE

CALL Worker (/* Arguments /*)

ENDIF

END

61

Giovanni Erbacci


18

Paradigmi di Programmazione Paralela

Linguaggi Procedurali sequenziali (Fortran 90,C,C++)

- Parallelism is not visible to the programmer

- Compiler responsible for parallelism

- Easy to do

- Small improvements in performance

Esplicito– Parallelism is visible to the programmer

– Difficult to do (right)

– Large improvements in performance

Giovanni Erbacci


19

Modelli di Parallelismo

Parallelismo sui Dati

62

Giovanni Erbacci


20

Modelli di Parallelismo

Giovanni Erbacci


21

Gestione del contorno

Parallelismo sui Dati

63

Giovanni Erbacci


22

Bilanciamento del carico

t

t

Giovanni Erbacci


23

64

Giovanni Erbacci


24

Functional or Data Parallelism?

Partition by task (functional parallelism)

o each process performs a different "function"

o identify functions, then data requirements

o commonly programmed with message-passing

Partition by data (data parallelism)

o each process does the same work on a unique piece of data

o data placement is critical

o more scalable than functional parallelism

Giovanni Erbacci


25

Concetto di Processo

Algoritmo

procedimento logico che occorre seguire per risolvere un determinatoproblema

Programma

descrizione dell'algoritmo, mediante un opportuno formalismo (illinguaggio di programmazione) in modo da poterlo eseguire su di un particolare elaboratore

Processo sequenziale

sequenza di eventi (esecuzione di operazioni) cui dà luogo l'elaboratorequando opera sotto il controllo di un particolare programma

entità astratta che identifica l'attività dell'elaboratore relativa all'esecuzione del programma

65

Giovanni Erbacci


26

Grafo di Precedenza

INIZIO

2 * 4 = 8

3 + 6 = 9

4 - 2 = 2

9*2 = 18

8+18=26

FINE

Giovanni Erbacci


27

Processi concorrenti

INIZIO

2 * 4 =8 3 + 6 = 9 4 - 2 = 2

9*2 = 18

8+18=26

FINE

66

Giovanni Erbacci


28

Processi indipendenti

e11

e12

e13

e1m

.

.

.

P1

ei1

ei2

e i3

eim

.

.

.

Pi

en1

en2

en3

enm

.

.

.

Pn

ej1

ej2

ej3

ejm

.

.

.

Pj

.. .... ..

Giovanni Erbacci


29

Processi interagenti

Se i processi sono indipendenti non esiste alcuna relazione tra un generico evento eik del processo Pi ed un evento ejl del processo Pj

(Algoritmi imbarazzantemente paralleli)

Le attivit rappresentate dai processi comunque non sono sempre traloro completamente indipendenti, ma si influenzano a vicenda

Spesso i processi durante la loro evoluzione cooperano e interagisconoscambiandosi informazioni

Fra eventi di processi diversi esistono quindi dei vincoli di precedenzache occorre rispettare

Nel grafo un vincolo di precedenza viene rappresentato attraverso un arco che collega un nodo di un processo con un nodo di un processo diverso

67

Giovanni Erbacci


30

Processi Interagenti

Un arco dal nodo eij al nodo ekl

significa che il task eij deve

esses completato prima che

inizi il task ekl. Si dice che il task

ekl dipende dal task eij

I vincoli di precedenza sono detti vincoli di sincronizzazione

poich indicano che i processi, quando arrivano ad un punto di interazione devono

sincronizzarsi cio ordinare i loro eventi come specificato dal grafo di precedenza e quindi

dalla logica dell'algoritmo

e11

e12

e13

e1m

.

.

.

P1

ei1

ei2

e i3

eim

.

.

.

Pi

en1

en2

en3

enm

.

.

.

Pn

ej1

ej2

ej3

ejm

.

.

.

Pj

.. .... ..

Giovanni Erbacci


31

L’accesso concorrente in lettura a una stessalocazione di memoria non causa problemi. Tale operazione è ben definita: concettualmente ogni processore fa una copiadel contenuto della locazione di memoria e la memorizza in un proprio registro.

I problemi si possono manifestare quando siverifica un accesso concorrente in scritturacioè quando più processi scrivonosimultaneamente sulla stessa locazione dimemoria.

P 1 P 2

X := X + 1

Qu

al'è

ilva

lore

fin

ale

dix ?

68

Giovanni Erbacci


32

Il non-determinismo è causato dalle race conditions.

Una race condition avviene quando due istruzioni in tasks concorrenti

accedono la stessa locazione di memoria, almeno una delle quali in

scrittura. Non c’è un un ordine di esecuzione garantito tra gli accessi.

Il problema del non determinismo può essere risolto sincronizzando

l’utilizzo dei dati condivisi.

– Infatti se x=x+1 e x=x+2 sono mutuamente esclusivi allora il valore finale della variabile x sarà sempre 3.

Le porzini di un programma paralello che richiedono sincronizzazione per

evitare il non determinismo sono chiamate sezioni critiche.

Giovanni Erbacci


33

Nella programmazione a memoria condivisa occorrono

costrutti per accedere in modo mutualmente esclusivo a

sezioni critiche.

Processor 1:

LOCK (X)

X = X + 1

UNLOCK (X)

Processor 2:

LOCK (X)

X = X + 2

UNLOCK (X)

69

Giovanni Erbacci


34

Deadlock

Situazione in cui uno o pi processi rimangono indefinitamente bloccatiperch non possono verificarsi le condizioni necessarie per il loroproseguimento

Un gruppo di processi entra in deadlock quando tutti i processi del gruppo attendono un evento (acquisizione o rilascio di risorse) che può essere causato solo da un altro dei processi in attesa

Processo P0 Processo P1

receive (x1, P1 )

…….

send (x2, P1)

receive (x2, P0)

…….

send(x1,P0)

Giovanni Erbacci


35

Costrutti per dichiarare entità parallele: moduli di programma chedevono essere eseguiti come processi sequenziali distinti

più processi possono svolgere lo stesso modulo di programma, operando su dati differenti

Costrutti per esprimere la concorrenza

strumenti per specificare l'attivazione di un processo (quando deveiniziare l'esecuzione del modulo di programma che corrisponde a quelprocesso)

strumenti per specificare la terminazione di un processo

Costrutti per specificere le interazioni dinamiche fra processi

- costrutti linguistici per specificare la sincronizzazione e la comunicazione fra i processi che devono cooperare

- costrutti linguistici per garantire la mutua esclusione fraprocessi che competono (per il modello a memoria condivisa)

70

Giovanni Erbacci


36

Obiettivi (ideali) Assicurare lo speed-up e la Scalabilità:

• Assegnare a ciascun processo una quantità unica di lavoro

• Assegnare a ogni processo i dati necessari per il lavoro dasvolgere

• Minimizzare la replica dei dati e della computazione

• Minimizzare la comunicazione tra i processi

• Bilanciare il work load

Tenere ben in mente che:

- Per un problema esistono diverse soluzioni parallele

- La miglior soluzione parallela non sempre deriva dalla miglior

soluzione scalare

71

Principi Di Parallelismo

Technology

Transcript of Principi Di Parallelismo