Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 10/03/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Caricare n valori distinti
in un vettore
Si adoperano N processori
begin
for h = 0 to N-1 do
for i = 0 to h pardo
Pi:
if (i = 0) then
a0 = read(); b0 = a0
else
ai = ai-1; bi = ai
end
c
b
a
Poiché bisogna caricare N elementi il
tempo è pari a N
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Caricare n2 valori distinti
in una mesh
Si adoperano RxC processori
begin
for k = 1 to R do
for h = 0 to C-1 do
for j = 0 to h pardo
P0,j:
if (j = 0) then
a0,0 = read(); b0,0 = a0,0
else
a0,j = a0,j-1; b0,j = a0,j
if (k < R) then
for i = 1 to k pardo
for j = 0 to C-1 pardo
Pi,j:
ai,j = ai-1,j; bi,j = ai,j
end
Poiché bisogna caricare RC elementi il
tempo è pari a RC
Algoritmi Paralleli e Distribuiti a.a. 2008/09
c
b
a
f
e
d
i
h
g
a
l
k
j
g
f
e
d
a
3
Sistema Distribuito
Un Sistema Distribuito è un insieme interconnesso di computer, processi o
processori, ciascuno definito in modo autonomo. Un sistema
distribuito si può pensare semplicemente come un sistema fisico
(computer connessi da una rete) o più in generale come un sistema
logico: insieme di processi connessi da un meccanismo di scambio di
messaggi.
•
“... è un sistema in cui la caduta di un computer del quale ignoravi
persino l’esistenza, può rendere il tuo computer inutilizzabile”
Lensi Lamport
•
“... è un modo di organizzare e considerare una famiglia di risorse
indipendenti e possibilmente distanti (o debolmente connesse), come
se facessero parte di un unico grande pacchetto”
Andrew Tannenbaum
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Differenza fra sistema
distribuito e parallelo
Sistema distribuito
Sistema parallelo
sistema multiutente che si riferisce ad
ambienti di lavoro di tipo collaborativi
(e-commerce, applicazioni di businness,
ecc…)
è pensato per essere usato da un singolo
utente o processo per garantire la massima
velocizzazione
di
una
singola
applicazione; viene naturalmente associato
al mondo scientifico
computer, processi o processori non processori omogenei sincroni
omogenei e asincroni
computer, processi o processori fra loro processori usati insieme per un’unica
autonomi
computazione (nelle SIMD manca
l’autonomia)
problemi di sicurezza connessi alla rete in genere è considerato come un sistema
(perdita di messaggi, cadute di sitema, fisicamente e logicamente inaccessibile
condivisione dei dati, etc…)
no network, no problem
no network, no use
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Trasmissione dell’informazione
Nei sistemi distribuiti, la trasmissione dell’informazione
assume un ruolo fondamentale. A seconda del sistema
preso in considerazione, la rete di interconnessione può
consistere in connessioni punto a punto (in tal caso ogni
connessione gestisce il traffico esclusivamente fra due
processori) o in canali di trasmissione (broadcast channels)
che distribuiscono l’informazione a tutti i processori
appartenenti ad un agglomerato (cluster) predefinito. I
processori non condividono fisicamente alcuna memoria e
quindi lo scambio di informazioni fra essi deve per forza
passare lungo la specifica rete di interconnessione.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Task
Definiamo task un frammento di codice sequenziale che deve
essere eseguito da un singolo processore. Quando due task
debbono comunicare fra loro durante l’esecuzione, ma i
processori che li stanno eseguendo non sono connessi
direttamente nella rete, non c’è modo di effettuare tale
comunicazione in modo diretto. Ogni processore nel sistema
deve pertanto, sia eseguire il task che gli è stato assegnato, sia
ridistribuire l’informazione secondo le necessità del caso.
Queste due operazioni, per quanto possibile, non devono
interferire fra di loro. In tal modo ogni processore viene visto
dal sistema come una coppia di entità logiche che lavorano in
modo indipendente: l’entità di processo che esegue il proprio
compito e l’entità di comunicazione che trasmette
l’informazione nella rete.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Algoritmo Distribuito
Un algoritmo distribuito D si può rappresentare come un
grafo G = (P, C), dove l’insieme dei nodi è l’insieme dei
processori e l’insieme degli spigoli orientati è un insieme
di canali di comunicazione (generalmente unidirezionali).
Tutti i processori, con l’eccezione di un sottoinsieme al quale
è permesso di mandare messaggi “spontaneamente”, sono
reattivi, ovvero eseguono un qualunque task come risposta
al ricevimento di un messaggio da un altro task. Un solo
blocco di processori Pinit può inizialmente eseguire un task
a scopo di inizializzazione.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Schema base di un
algoritmo distribuito
begin
Pinit: exec eventuali operazioni di inizializzazione;
send messaggio ai vicini
repeat
Pi:
receive messaggio M e BM è vero
exec qualche operazione
send messaggi ai vicini
until un segnale di terminazione globale arriva a D
end
La operazione di send invia un messaggio su uno o più canali di
comunicazione uscenti da Pi.
Ogni processore ha una coda di messaggi ricevuti.
La receive estrae un messaggio dalla coda di Pi.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
Broadcast in un sistema
distribuito ad anello
Le connessioni si assumono unidirezionali, da Pi a Pi+1
P0 ha l’informazione da distribuire nella variabile inf
begin
P0:send inf al successore
P0
Pn-1
P1
P2
repeat
Pi:
receive inf da predecessore
send inf al successore
until P0 riceve messaggio dal predecessore
end
P3
In una rete ad anello ad n nodi, vengono inviati n messaggi in n passi
Algoritmi Paralleli e Distribuiti a.a. 2008/09
10
Broadcast in una qualsiasi
rete a connessione fissa
Assumiamo connessioni unidirezionali e rete aciclica
begin
Pinit:
Ninit = { q : q è un vicino di Pinit }
send messaggio ad ogni q in Ninit
repeat
Pi: receive messaggio da un vicino p
Ni = { q : q è un vicino di Pi }
send messaggio ad ogni q in Ni
until …
end
Pinit
Si ricorda che Pi invia lo stesso messaggio a tutti i suoi vicini contemporaneamente però sia i
processori sia i canali di comunicazione sono eterogenei, quindi il tutto è asincrono.
In una rete di n nodi, vengono inviati O(m) messaggi in O(d) passi
m = numero archi
d = diametro della rete
Manca il segnale di terminazione globale
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11
Broadcast con eco in una qualsiasi
rete a connessione fissa
Per risolvere il problema della terminazione si usa l’eco
Servono connessioni bidirezionali
begin
Peco:
Neco= { q : q è un vicino di Peco }
send messaggio ad ogni q in Neco
conteco = 0
while conteco < | Neco |
receive messaggio da un vicino
incrementa conteco
termina
Pi≠ eco: receive messaggio da un vicino p che chiamo padre
Ni = { q  p : q è un vicino di Pi }
send messaggio ad ogni q in Ni
conti = 0
while conti < | Ni |
receive messaggio da un vicino
incrementa conti
send messaggio al padre p
end
In una rete di n nodi, vengono inviati O(m) messaggi in O(d) passi
Algoritmi Paralleli e Distribuiti a.a. 2008/09
12