Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1
FONDAMENTI DI INFORMATICA
Prof. PIER LUCA MONTESSORO
Facoltà di IngegneriaUniversità degli Studi di Udine
Calcolo parallelo e sistemimultiprocessore
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2
Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyrighte dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (iviinclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio,musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degliStudi di Udine.Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca,scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministerodell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine dilucro. In tal caso non è richiesta alcuna autorizzazione.Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni susupporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se nonesplicitamente autorizzata per iscritto, a priori, da parte degli autori.L’informazione contenuta in queste slide è ritenuta essere accurata alla data dellapubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata inprogetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senzapreavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (iviincluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamentodell’informazione).In ogni caso non può essere dichiarata conformità all’informazione contenuta in questeslide.In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devonomai essere rimossi e devono essere riportati anche in utilizzi parziali.
Nota di Copyright
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 3
Aumentodell'affidabilità(fault tolerance)
Aumento della velocità oltre i limitidella tecnologia corrente
Maggiorpotenza aminorcosto
Necessità di HWspeciale per algoritmie tecniche diprogrammazioneparticolari (AI)
Calcolo parallelo
• Aumenta la potenza di calcolo facendouso di più CPU
• Può derivare da esigenze diverse:
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 4
Programmi per calcolo parallelo• Esistono diverse strategie. In generale:
– i programmi vengono suddivisi in moduli che sonoeseguiti concorrentemente e/o sequenzialmentesu più processori
– i dati possono essere ripartiti tra i processori, e/oessere condivisi in una memoria comune(arbitraggio)
– i moduli in esecuzione sui diversi processoricomunicano mediante messaggi per scambio didati e sincronizzazione dell'attività
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 5
EfficiencyEp = Sp/p <= 1Rapporto tra lo
speed-up effettivoe il massimoteorico (p)
Speed-upSp = T1/Tp ≥ 1Aumento dellavelocità grazie
all'uso di pprocessori
Misure di efficienza
• Tp = numero di unità di temponecessarie per eseguire un dato calcolosu p ≥ 1 processori
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 6
Esempi di calcolo parallelo
• Analizzeremo due semplici casi comeesempio di applicazione delle formule dispeed-up ed efficienza:– calcolo di espressioni aritmetiche– soluzione di sistema di equazioni lineari
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 7
Espressioniaritmetiche
a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8
+
+
+
+
+
+
+ Esecuzione sequenziale(macchina di Von Neumann)
p = 1Tp = 7
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 8
Esecuzioneparallela
a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8
+ ++ +
+ +
+
esecuzionecontemporanea
esecuzionecontemporanea
p = 4Tp = 3
Sp = 7/3 = 2.3Ep = 2.3/4 = 0.58
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 9
j=i-m
i-1
Sistemi di equazioni• Definiamo uno schema di iterazione lineare di
ordine m di un sistema di n equazioni:xi = 0 per i ≤ 0xi = ci + Σaijxj per 1 ≤ i ≤ n
• In forma matriciale:x = c + Axdove– x = (x1,...,xn)t c = (c1,...,cn)t
– A matrice dei coefficienti (triangolare):– aij = 0 per i ≤ j e per i - j > m
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 10
Esempio
x1 = c1
x2 = c2 + a21x1
x3 = c3 + a32x2 + a31x1
n = 3m = n - 1 = 2
= +x1
x2
x3
x1
x2
x3
c1
c2
c3
0a21
a31
00
a32
00
0
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 11
Algoritmo parallelo• n - 1 processori per n equazioni• Ogni processore i inizializza il risultato
dell'equazione con il termine costante ci
• x1 è inizialmente noto (c1)0) j = 1 (contatore delle iterazioni)1) broadcast di xi da parte del processore che ha
terminato il calcolo2) moltiplicazione per aij
3) somma con il risultato parziale precedente4) j = j+15) ripetere da 1)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 12
Misure di speed-up ed efficienza• Ad ogni iterazione vengono effettuate due
operazioni: una somma ed una moltiplicazione
• Su singolo processore:T1 = 2(1+2+...+(n-1)) = n(n-1)
• Su p = n-1 processori:Tp = 2(n-1)
• PerciòSp = n(n-1) / 2(n-1) = n/2Ep = Sp/p = n / 2(n-1) > 1/2
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 13
Possibilità di parallelizzaregli algoritmi
• Normalmente gli algoritmi possono essereparallelizzati solo in parte, il resto va eseguitosequenzialmente (cfr. Amdahl)
• Tradeoff tra il numero di processori e il loroutilizzo effettivo a causa dei tempi dicomunicazione: al crescere del numero diprocessori cresce la quantità di dati dascambiare, e quindi il tempo in cui in mediaciascun processore è in attesa di dati. Questoriduce l'utilizzo dei processori stessi
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 14
Possibilità di parallelizzaregli algoritmi (segue)
• Il tipo di algoritmi è spesso radicalmentedifferente tra macchine con alcune decine opoche centinaia di processori e macchine aparallelismo massiccio (decine di migliaia)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 15
Legge di Amdahl
Speedup = (s + p) / (s + p/N) = 1 / (s + p/N)
dove:– s e p sono le percentuali di programma da
eseguire sequenzialmente oparallelizzabili, rispettivamente (s + p = 1)
– N è il numero di processori
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 16
Legge di Amdahl (N = 1024)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 17
Classificazione in base alparallelismo
• Si considerano il numero di processorie la loro potenza:– cluster– macchine a parallelismo ridotto (anche
macchine a parallelismo non strutturato,coarse-grain parallel computer)
– macchine a parallelismo massiccio (anchemacchine a parallelismo strutturato, fine-grain parallel computer)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 18
Classificazione dei calcolatori inbase al tipo di parallelismo
(Michael J. Flynn)• Considera le sequenze di istruzioni (instruction
stream) e le sequenze di dati (data stream):
SISD: Single Instruction Stream - Single Data StreamSIMD: Single Instruction Stream - Multiple Data StreamMISD: Multiple Instruction Stream - Single Data StreamMIMD: Multiple Instruction Stream - Multiple Data Stream
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 19
CU PU MM
IS
IS DS
CU: control unitPU: processor unitMM: memory moduleIS: instruction streamDS: data stream
SISD
• È il modello classico di computer• Le istruzioni sono eseguite sequenzialmente,
ma possono sovrapporsi grazie al pipeline• Possono essere presenti più unità funzionali,
tutte controllate da un'unica unità di controllo
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 20
SM: shared memory
PU1 MM1
IS
DS1
CU PU2IS
PUn
.
..MM2
MMn
.
..
DS2
DSn
SMSIMD
• A questa classe appartengono gli arrayprocessor
• L'unità di controllo (CU) invia in broadcast leistruzioni alle unità di calcolo (PU)
• Ogni unità di calcolo esegue le istruzioni suun differente insieme di dati
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 21
memoria
Control Unit
ALU
Registri
ALU
Registri
ALU
Registri
ALU
Registri
Computer parallelo sincrono
Array processor
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 22
Memoria
Instruction fetch unitInstruction decode unit
Scalar fetch unit Scalar fetch unit
Processore scalare Processore vettoriale
Registri scalari Registri vettoriali
Pipeline scalare Pipeline vettoriale
Calcolatore vettoriale
Pipeline della medesima istruzione su diversi dati
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 23
CU1 PU1
MM1
IS1
IS1 DS
CU2 PU2IS2
CUn PUnISn
.
.....
MM1 MM1. . .SM
IS2
ISn
MISD
• Diverse sequenze di istruzioni applicate almedesimo insieme di dati.
• Architettura puramente ipotetica, nonesistono macchine MISD nella realtà.
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 24
CU1 PU1
IS1
IS1
CU2 PU2IS2
CUn PUnISn
.
.....
IS2
ISn
MM1
MM2
MMn
.
..
SMDS1
DS2
DSn
MIMD
• A questa classe appartengono i sistemimultiprocessore.
• Ogni processore esegue una distinta sequenzadi istruzioni su un distinto insieme di dati.
• I processori devono poter interagire.
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 25
Memoria
control unit
multiply divide
CPU
compareshift
add
boolean
instruction decoder
CPU singola con più unitàaritmetiche
Pipeline di diverse istruzioni su diversi dati
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 26
main memory
controlunit
ALU
registri
controlunit
ALU
registri
CPU1 CPU2
Computer parallelo parzialmente asincrono
Multiprocessor (memoria comune)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 27
bus o rete di comunicazione
controlunit
ALU
registri
memorialocale
controlunit
ALU
registri
memorialocale
controlunit
ALU
registri
memorialocale
Computer parallelo asincrono
Multiprocessor (memoria locale)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 28
Classificazione in base allacomunicazione tra i processori
• Memoria comune• Bus• Rete a topologia fissa, es. ipercubo,
griglia, toro, ecc.• Rete a topologia variabile, es. crossbar
switch
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 29
Comunicazione mediante retea topologia fissa
P P
PP
P P Parray lineare
PP
P P
P
anello
PP
P P
P
stella
PP P
albero
PP P
P
P
P P PP P PP P P
griglia
P P
PPcubo
P P PP P PP P P
toro
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 30
Switch box 2x2 (2 ingressi, due uscite)
Switch boxSwitch box
straight exchange
upper broadcast lower broadcast
Comunicazione mediante retea topologia variabile
• Elemento base di commutazione:switch box
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 31
1
n x m
1
r x r1n
1
m x n
2 2n+12n
2
r m(r-1)n+1rn
r
Esempio di rete a 3 stadi
1nn+12n
(r-1)n+1rn
Comunicazione mediante retea topologia variabile
...
...
... ...
...
...
...
...
...
...
...
...
...
...
......
...
...
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 32
0 1n = 1
00 01
10 11n = 2 n = 4
Ipercubo
• Dimensione n:– 2n processori– n canali di comunicazione in ciascun
processore
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 33
Comunicazioni in un ipercubo
0000
0001
0010
0011
0101
0111
1000
1101
11111010
1100
1110
1011
1001
Destination: 1101Source: 0000Data: 00101101
Messaggio per 1101:
1101 EXOR 0000= 1101prima differenza:dimensione 0(primo bit da destra)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 34
Comunicazioni in un ipercubo
0000
0001
0010
0011
0101
0111
1000
1101
11111010
1100
1110
1011
1001
Ricevuto messaggio condestinatario 11011101 EXOR 0001 = 1100prima differenza:dimensione 2(terzo bit da destra)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 35
Comunicazioni in un ipercubo
0000
0001
0010
0011
0101
0111
1000
1101
11111010
1100
1110
1011
1001Ricevuto messaggio condestinatario 11011101 EXOR 0101 = 1000prima differenza:dimensione 3(quarto bit da destra)
Fondamenti di Informatica - Calcolo parallelo e sistemi multiprocessore
© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 36
0000
0001
0010
0011
0101
0111
1000
1101
11111010
1100
1110
1011
10010000
1101
bit: 3 2 1 0
dim. 0dim. 2
dim. 3
Comunicazioni in un ipercubo