Parallel Programming Parallel Programming Patterns Patterns

Parallel Programming Parallel Programming

Patterns Patterns

Moreno Marzolla

Dip. di Informatica—Scienza e Ingegneria (DISI) Università di Bologna

http://www.moreno.marzolla.name/

Parallel Programming Patterns

●

Embarassingly Parallel

●

Partition

●

Stencil

●

Reduce

●

Scan

Embarassingly Parallel

●

La computazione puo' essere decomposta in task che possono essere eseguiti in modo totalmente

indipendente, senza necessità di comunicazioni

●

Esempi

–

Somma di due vettori

–

Insieme di Mandelbrot (vedremo fra poco)

–

Rendering 3D

–

Individuare una password “a forza bruta”

–

...

Partition

●

Lo spazio dei parametri di input è diviso in regioni

disgiunte (partizioni); ogni regione viene processata in modo indipendente dalle altre (embarassingly parallel)

●

Ogni core puo' leggere/scrivere dati nella propria partizione senza causare conflitti, in quanto le

partizioni sono disgiunte

●

Questo pattern consente di esprimere le

caratteristiche di località e isolamento nell'accesso ai

dati che certe applicazioni esibiscono

Partition

●

Tipi di partizionamento

–

Regular: lo spazio dei dati di input viene distribuito

uniformemente tra i processori. Es: prodotto matrice-vettore

–

Irregular: le partizioni non hanno necessariamente le stesse dimensioni. Es: modelli climatici planetari

●

Dimensione delle partizioni

–

Fine-Grained: il partizionamento produce un numero elevato di partizioni piccole

–

Coarse-Grained: il partizionamento produce un basso

numero di partizioni di grandi dimensioni

Regular partitioning:

Prodotto matrice-vettore

Core 0

Core 1 Core 2 Core 3

x =

●

Dati P processori, si partiziona la matrice in P blocchi orizzontali

●

Ogni CPU riceve un blocco e una copia del vettore v

●

Ogni processore

calcola un frammento

del vettore risultato

1-D Partitioning

●

Block

●

Cyclic

Core 0 Core 1 Core 2 Core 3

2-D Block Partitioning

Core 0

Core 2 Core 3 Core 1

Block, * *, Block Block, Block

2-D Cyclic Partitioning

Cyclic, * *, Cyclic

2-D Cyclic Partitioning

Cyclic-cyclic

Irregular partitioning

●

Per certi problemi è necessario effettuare una decomposizione irregolare

●

Esempio

–

La superficie di un lago viene partizionata tramite una griglia triangolare

–

I colori indicano la

mappatura della griglia sui processori

Fonte: http://www.cdac.in/HTmL/events/beta-test/archives/promcore-2008/mpi-1x-promcore-2008/partial-diff-eqns-solvers-mpi.html

Fine grained vs

Coarse grained parallelism

●

Fine grained Parallelism

–

Poca computazione tra gli eventi di comunicazione (basso rapporto computazione / comunicazione)

–

Facilita il bilanciamento del carico

–

Puo' causare overhead significativo per

comunicazione o distribuzione del carico: se la

granularità è troppo fine, il tempo di comunicazione potrebbe dominare sul tempo di calcolo

●

Coarse-grain Parallelism:

–

Molta computazione tra gli eventi di comunicazione (alto rapporto computazione / comunicazione)

–

Puo' causare sbilanciamento del carico

●

Spesso la scelta è dettata dal problema; in altri casi l'utente puo' decidere quale livello di

parallelismo adottare

Computazione Comunicazione

TempoTempo

Insieme di Mandelbrot

●

Definito come l'insieme dei punti c sul piano

complesso tali che la sequenza z

, definita come

resta limitata (non

diverge) per n → infinito

z

= { ^z

^{0 +} c altrimenti ^{se n=0}

Insieme di Mandelbrot

●

Spesso l'insieme viene visualizzato a colori

–

Ciascun pixel assume un colore che dipende dal

numero minimo di iterazioni necessarie perché la

sequenza z

abbia modulo maggiore di 2

–

Se z

rimane limitata per

nmax iterazioni, il pixel è

nero

Insieme di Mandelbrot Pseudocodice

For each pixel (x0, y0) do {

x = 0;

y = 0;

it = 0;

maxit = 1000;

while ( x*x + y*y < 2*2 AND it < maxit ) {

xtemp = x*x - y*y + x0 y = 2*x*y + y0

x = xtemp it = it + 1 }

plot(x,y,it);

}

Il colore di ogni pixel può essere calcolato

indipendentemente dagli altri

Fonte:http://en.wikipedia.org/wiki/Mandelbrot_set#For_programmers

Insieme di Mandelbrot

●

Applicare un

partizionamento

regolare porta ad uno sbilanciamento del

carico

–

Il tempo di calcolo di ciascun pixel non è costante

I pixel neri richiedono maxit iterazioni

Gli altri pixel richiedono

<< maxit iterazioni

Algoritmi Avanzati--modulo 2 18

(S)bilanciamento del carico

●

Load balancing = distribuire approssimativamente la stessa quantità di “lavoro” tra i task

●

Il bilanciamento del carico è importante per garantire buone prestazioni.

–

Es., se i task si sincronizzano periodicamente tramite

barriere, le prestazioni complessive saranno determinate dal task più lento

Task 1 Task 2

Task 3 Task 0

barrier

busy

idle

Come bilanciare il carico

●

Partizionare l'input in modo da assegnare ai task approssimativamente la stessa quantità di lavoro

–

Risulta facile per le operazioni di algebra lineare che coinvolgono matrici e vettori

●

Usare parallelismo “a grana fine”

–

Attenzione che questo potrebbe aumentare l'overhead dovuto alla comunicazione tra i task

●

Distribuire il lavoro in modo dinamico

–

Paradigma master-worker

Paradigma master-worker

(process farm, work pool)

●

Si applica un partizionamento a grana fine (numero di task >> numero di core)

●

Il master distribuisce il lavoro ad una serie di worker

●

Quando un worker termina, il master gli attribuisce un nuovo task

Master

Worker 0 Worker

1

Worker P-1 Task di durata non uniforme

Stencil

●

Molti problemi richiedono di aggiornare il contenuto di una matrice o di un vettore utilizzando uno schema uguale per ogni elemento

●

Esempio: smoothing gaussiano di una immagine

4 1

16 4

4 5

16 28

28 7

16 4

28 16 28

4

1 7 4

1 4 7 4 1

Il colore del pixel centrale si ottiene moltiplicando il colore dei pixel di tutta l'area colorata (incluso il centro) per i pesi

indicati, e dividendo la somma per 271

41

Stencil

●

Esempio: automi cellulari in una dimensione

Tempo

Il colore di questo pixel al tempo t+1 dipende dal colore dei pixel rossi al tempo t

Rule 30 cellular automata

Stencil

●

I problemi le cui soluzioni esibiscono una struttura a stencil offrono spesso possibilità di parallelizzazione, ma richiedono attenzione nel partizionamento

–

Esempio: per calcolare il valore dei pixel sul bordo delle

regioni assegnate ai core sono necessari i valori precedenti dei pixel che si trova nella regione assegnata al core vicino

Core 0 Core 1 Core 2

Reduce

●

L'operazione di riduzione consiste nell'applicare un operatore associativo (somma, prodotto, minimo,

massimo...) agli elementi di un vettore [x

, x

, … x

]

–

sum-reduce( [x

, x

, … x

] ) = x

+ x

+ … + x

–

min-reduce( [x

, x

, … x

] ) = min { x

, x

, … x

}

–

…

●

L'operazione di riduzione puo' essere implementata in

O(log

n) fasi

+ + + + + + + +

+ + +

+ +

+ +

Reduce

Scan (Prefix Sum)

●

La primitiva scan calcola la somma prefissa di un array [x

, x

, … x

]

–

La primitiva puo' essere estesa ad un qualsiasi operatore associativo)

[y

, y

, … y

] = excl-scan( [x

, x

, … x

] )

con

y

= 0 y

= x

y

= x

+ x

…

y = x + x + … + x

Nel caso si usi un altro operatore associativo, sostituire questo valore con il

valore neutro dell'operatore

Scan (Prefix Sum)

●

La primitiva scan calcola la somma prefissa di un array [x

, x

, … x

]

–

La primitiva puo' essere estesa ad un qualsiasi operatore associativo)

[y

, y

, … y

] = incl-scan( [x

, x

, … x

] )

con

y

= x

y

= x

+ x

y

= x

+ x

+ x

…

y = x + x + … + x

+ + + + + + + +

+ + +

+ +

+ +

+

+ +

+

+ +

+ +

+ +

+

incl-scan()

Applicazioni della primitiva scan Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

●

n montagne di altezze h[0], … h[n-1]; le vette sono equispaziate a distanza unitaria

●

Calcolare l'indice delle montagne le cui vette sono visibili dalla vetta della montagna 0

visibile non visibile

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Linea di visuale

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

Visibili

Schema parallelo

●

Si calcolano gli angoli a[i] tra la vetta della montagna 0 alla vetta della montagna i

–

a[i] := arctan( ( h[i] – h[0] ) / i );

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]

Schema parallelo

●

Si calcola un vettore amax ← max-excl-scan(a)

–

amax[i] ← max{a[0], … a[i-1]}

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]

Schema parallelo

●

Si verifica in parallelo se a[i] > amax[i]

–

In caso affermativo la vetta della montagna i-esima e' visibile dalla vetta della montagna 0

h[2] h[3]

h[4] h[5] h[6] h[7]

h[0] h[1]

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]

Conclusioni

●

Esistono strutture ricorrenti di computazioni parallele che possono essere codificate in una serie di pattern

●

Un pattern definisce:

–

una particolare struttura dei task

–

una particolare tecnica di partizionamento/allocazione dei dati

–

una particolare struttura delle comunicazioni tra task

●

La conoscenza dei pattern ricorrenti aiuta nello sviluppo di programmi paralleli efficienti

–

Molti problemi hanno una struttura tale da consentire l'uso di

uno o più pattern noti