III corso avanzato di calcolo e grid computing Catania 29 settembre 2009 Architettura e modelli di...

III corso avanzato di calcolo e grid computing

Catania 29 settembre 2009

www.cineca.it

Architettura e modelli di programmazione parallelaArchitettura e modelli di programmazione parallela

Giovanni ErbacciGruppo Supercalcolo – CINECA

[email protected]

© CINECA 2006 Giovanni Erbacci 2

Parallel Computing

Cosa si intende per parallel computing? Parallel computing è una tecnica di programmazione che

coinvolge l’utilizzo di più processori che operano insieme su un singolo problema

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

Programma Parallelo programma composto di tasks (processi) che comunicano tra loro per realizzare un

obiettivo computazionale complessivo.

L'esecuzione di processi di calcolo non sequenziali richiede:- un calcolatore non sequenziale (in grado di eseguire un

numero arbitrario di operazioni contemporaneamente) - un linguaggio di programmazione che consenta di descrivere formalmente algoritmi non sequenziali


Calcolatori Paralleli

Un calcolatore parallelo è un sistema costituito da una collezione di processori in grado di comunicare e cooperare per risolvere grandi problemi computazionali in modo veloce.

Progettati anche per evitare il von Neumann bottleneck:“The instruction stream is inherently sequential – there is one processing site and all instructions, operands and results must flow through a bottleneck between processors and memory.”

P M


Calcolatori Paralleli / 1

P

M

P

MP

M

P

M

P

M

P

M

N

Sstema a Memoria Distribuita

Sistema a Memoria Condivisa

MP P

PP

NetworkM

P P

PPNodo 1

Nodo 5

Nodo 6

Nodo 4

Nodo 2

Nodo 3

Sstema ibrido


Paradigmi di Programmazione Parallela

Un modello di programmazione è una collezione di astrazioni di programma chefornisce 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)


Paradigma Message Passing

Nel paradigma message passing i processi comunicano scambiandosi messaggi

Primitive message passing di base:

–Send (parameter list)

–Receive (parameter list)

A B


Paradigma Shared Memory

Nel paradigma shared memory i processi comunicano accedendo a variabili e strutture dati condivise.

Primitive shared memory di base:

–Read da una variabile condivisa

–Write su una variabile condivisa

Sistema di Interconnessione…Processori Moduli di

Memoria

…


Esempio: Sort di n numeri

/* Bubble sort for integers */ #define SWAP(a,b) { int t; t=a; a=b; b=t; }

void SORT( int a[], int n ) /* Pre-condition: a contains n items to be sorted */ { int i, j; /* Make n passes through the array */ for(i=0;i<n;i++) { /* From the first element to the end of the unsorted section */ for(j=1;j<(n-i);j++) { /* If adjacent items are out of order, swap them */ 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

Bubble Sort


Sort di n numeri / 1

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

- ordinare 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])


Sort su k ProcessoriP0 P1 P2 …….. Pk-1

Step 0

Step 2

Step 1

Step log2K


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

Nella programmazione parallela occorre affrontare problematiche che non si presentano con la programmazione sequenziale. Occorrono decidere: · quali parti di codice costituiscono le sezioni parallele · quando iniziare l’esecuzione delle diverse sezioni parallele· quando terminare l’esecuzione delle sezioni parallele· quando e come effettuare la comunicazione fra le entità parallele

. quando effettuare la sincronizzazione fra le entità parallele

Poi occorrono gli strumenti per implementare questi aspetti


Indirizzamento Locale o Globale

Con il modello di programmazione Shared Memory, si fa affidamento sull’indirizzamento globale della memoria

Con il modello a memoria distribuita è possibile solo la gestione locale della memoria, e quindi si può gestire solo uno spazio di indirizzamento locale.

Esempio: calcolare la somma degli elementi di una matrice M[n, n]

s = i j mij


Indirizzamento Globale

Si alloca la matrice M[n, n] nella memoria comune e tutti i processori che intervengono nella computazione possono indirizzare tutti gli elementi di M.

P0

P3

P2

P1

M

s3

s2

s1

s0

S

Memoria

M(i,j) i = 1, n, j = 1,m

Temp = M(857,760) + M(321, 251)


Indirizzamento LocaleOgni processore vede solo la sua memoria locale e vi alloca una fetta della matrice M[n, n]

P0

P3

P2

P1

s1

s0

M(i,j) i = 1, n/k, j = 1,m

s3

s2

??S

Temp = M(857,760) + M(321, 251)

Temp = M(107,760)P3 + M(71, 251) P1

(N = 1000, 4 proc)


Filosofia Master Slave e SPMD Master / Slave

Un singolo processo (il Master) controlla il lavoro svolto dagli altri processi (slaves, Workers). Questi possono eseguire lo stesso programma o

programmi differenti

Single Program Multiple DataOgni processore esegue la stessa copia del programmail flusso di esecuzione su ogni processore varia in funzione dell’ambiente locale (dati, numero di processore ecc.) Si può emulare la filosofia master /slave tipica di alcuni ambienti message passing. C main (int argc, char **argv){ if (process is to become a controller process) { Controller (/* Arguments /*); } else { Worker (/* Arguments /*); }}

FortranPROGRAMIF (process is to become a controller process) THEN

CALL Controller (/* Arguments /*)ELSE CALL Worker (/* Arguments /*)ENDIFEND


Paradigmi di Programmazione Paralela

- Paradigma a memoria condivisa (Open-MP)- Paradigma Message Passing (PVM, MPI, …)- Paradigma Data Passing (Shmem, One Side Communication)- Paradigma Data Parallel (HPF, HPF-Craft) Linguaggi Procedurali sequenziali (Fortran 90,C,C++) + API (Direttive al Compilatore)Si tende a favorire un Parallelismo implicito

- Parallelism is not visible to the programmer- Compiler responsible for parallelism- Easy to do- Small improvements in performance

Linguaggi Procedurali sequenziali (Fortran 90, C, C++) + API (Chiamate a Librerie)Parallelismo Esplicito Parallelism is visible to the programmer Difficult to do (right) Large improvements in performance

Schema SPMD oppure Fork/Join


Modelli di Parallelismo

Parallelismo sui Dati

Partizionamento dei dati (data parallelism) Ogni processo esegue lo stesso lavoro su un sottoinsieme dei dati - Il poizionamento dei dati (“data placement”) è critico - Più scalabile del parallelismo funczionale - Programmazione in message-passing o HPF

- Problema della gestione del contorno- Bilanciamento del carico (in alcuni casi)


Modelli di Parallelismo

Parallelismo sul Controllo

(Parallelismo Funzionale) vengono distribuite le funzioni Partizionamento by task

Ogni processo esegue una diversa "funzione“: Identificare le funzioni, e poi i data requirements

Bilanciamento del carico


Gestione del contorno

Parallelismo sui Dati


Bilanciamento del carico

t

P1 P0

P2

t

P1 P2

P0 P4 P3


Bilanciamento del carico / 1

t

P0 P1 P2 P3 P4 P5 P6 P7

t

P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14

P15


Note sul modello Shared Memory:Accesso a variabili condivise

L’accesso concorrente in lettura a una stessa locazione di memoria non causa problemi.

Tale operazione è ben definita: concettualmente ogni processore fa una copia del contenuto della locazione di memoria e la memorizza in un proprio registro.

I problemi si possono manifestare quando si verifica un accesso concorrente in scrittura cioè quando più processi scrivono simultaneamente sulla stessa locazione di memoria.

P1 P2

X := X + 1

Due processi P1 e P2 condividono una variabile x che entrambi devono incrementare

Qua

l'è il

val

ore

final

e di

x ?

P1 legge il valore corrente di x

P2 legge il valore corrente di x

P1 incrementa di 1 il valore letto

P2 incrementa di 1 il valore letto

P1 memorizza il nuovo valore

P2 memorizza il nuovo valore

Il programmatore, il linguaggio di programmazione e/o l’architettura devono fornire strumenti per risolvere i conflitti


Note sul modello Shared Memory:Deadlock

Situazione in cui uno o più processi rimangono indefinitamente bloccati perchè non possono verificarsi le condizioni necessarie per il loro proseguimento

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)

Il deadlock è detto anche blocco critico o stallo


Linguaggi per la programmazione parallela: requisiti

Costrutti per dichiarare entità parallele: moduli di programma che devono 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

deve iniziare l'esecuzione del modulo di programma che corrisponde a quel processo)

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 fra

processi che competono (per il modello a memoria condivisa)


Parallelizzazione: Obiettivi e decisioni

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 da svolgere 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

III corso avanzato di calcolo e grid computing Catania 29 settembre 2009 Architettura e modelli di...

Documents

Transcript of III corso avanzato di calcolo e grid computing Catania 29 settembre 2009 Architettura e modelli di...