1°edizione 7 - 18 luglio 2008 2°edizione 8 – 19 settembre 2008
Architetture parallele
Giovanni Erbacci - [email protected]
Gruppo Supercalcolo - Dipartimento Sistemi e Tecnologie
Giovanni Erbacci
Architetture parallele
1
Argomenti
Il modello di von Neumann
I primordi del parallelismo
Verso il parallelismo effettivo
Pipelining
Classificazione di Flynn
Architetture vettoriali
Architetture Parallele
9
Giovanni Erbacci
Architetture parallele
2
Modello di von Neumann
Controllo
Input Memoria Output
Unità Aritm. Logica
Calcolatore Convenzionale
Le istruzioni vengono processate sequenzialmente:
1 un istruzione viene caricata dalla memoria (fetch) e decodificata2 vengono calcolati gli indirizzi degli operandi;3 vengono prelevati gli operandi dalla memoria;4 viene eseguita l'istruzione;5 il risultato viene scritto in memoria (store).
Giovanni Erbacci
Architetture parallele
3
Calcolatori più Veloci
Tempo
Perf
orm
an
ce
Processori
Memoria
Gap
10
Giovanni Erbacci
Architetture parallele
4
Velocità dei Componenti
Ciclo macchina
Si definisce ciclo macchina o clock period !!!! l'intervallo temporale che regola la sincronizzazione delle operazioni in un calcolatore
Unit temporale di base di un calcolatore (si misura in ns - 10-9 s)
Si calcola come l inverso della frequenza di clock (misurata in MHz)
Tutte le operazioni all interno del processore durano un multiplo di !!!!.
CDC 6600 100 ns
Cyber 76 27.5 ns
IBM ES 9000 9 ns
Cray Y-MP C90 4.1 ns
Intel i860 20 ns
PC Pentium < 1 ns
Giovanni Erbacci
Architetture parallele
5
Legge di Moore
Legge empirica che afferma che la complessità dei dispositivi (numero di transistor per sqare inch nei microprocessori) raddoppia ogni 18 mesi.
Gordon Moore, co-founder di Intel, 1965Si stima che la legge di Moore valga ancora almeno per questo decennio.
11
Giovanni Erbacci
Architetture parallele
6
Oltre alla potenza del processore, altri fattori influenzano le prestazioni degli elaboratori:
- dimensione della memoria
- larghezza di banda (bandwidth) fra memoria e processore
- larghezza di banda verso il sistema di I/O
- dimensione e larghezza di banda della cache
- latenza fra processore, memoria e sistema di I/O
Dati
Indirizzi
Arithmetic-Logical Unit
ALU
Control Unit
Memoria Centrale
Device
Giovanni Erbacci
Architetture parallele
7
Primordi del Parallelismo
Miglioramenti architetturaliMemoria bit-parallel e Aritmetica bit-parallel
Processori indipendenti per l’attività di I/O
Memoria interleaved
Gerarchie di memoria
Unità funzionali multiple
Unità funzionali segmentate
Pipelining
Miglioramenti softwareMultiprogrammazione e
Look-ahead e scheduling delle istruzioni
12
Giovanni Erbacci
Architetture parallele
8
Verso il Parallelismo effettivo
Sistemi vettoriali
Array processors
Architetture sistoliche
Very Long Instruction Word (VLIW)
Sistemi Multiprocessore
Sistemi Multicomputer
Giovanni Erbacci
Architetture parallele
9
Memoria e Aritmetica Bit-parallel
Nei primi calcolatori elettronici, i bit di una word venivano letti singolarmente dalla memoria
L'aritmetica bit-parallel divenne possibile con l'introduzione delle memorie bit parallel(IBM 701, 1953)
L'IBM 704 (1955) fu il primo calcolatore commerciale ad usare memoria a nuclei di ferrite.Consentiva:
– accesso bit-parallel alla memoria
– non volatilità– velocità a costi ragionevoli.
13
Giovanni Erbacci
Architetture parallele
10
Processori di I/O (Canali)
Nei calcolatori della prima generazione, le istruzioni di I/O venivano eseguite dalla CPU
Questa inefficienza fu risolta introducendo processori separati per gestire le operazioni di I/O
I processori di I/O (canali) ricevono le istruzioni di I/O dalla CPU poi operano in modo indipendente, liberando la CPU
Input Output
I/O Processor
Memory Control Unit
(Multiplexer)CPU Memory
Giovanni Erbacci
Architetture parallele
11
Memoria InterleavedUnità di memoria suddivisa in moduli o banchi che possono essere acceduti simultaneamente
Ogni banco ha la propria circuiteria di indirizzamento
Gli indirizzi delle istruzioni e dei dati sono interleaved così si ha la possibilità di fetch in parallelo
L'IBM STRETCH (1961) è stato il primo calcolatore ad avere una memoria interleaved (2 banchi).
Il CDC 6600 (1964) aveva una memoria suddivisa in 32 banchi indipendenti
0000
0100
1000
0001
1001
0101
0010
0110
1010
1011
0111
1011
0 21 3Banchi dimemoria
indirizzo
contenuto
14
Giovanni Erbacci
Architetture parallele
12
Gerarchie di Memoria
Tempo di accesso alla memoria: indica la velocitàcon la quale si può referenziare una locazione di memoria
Tempo di ciclo della memoria: indica il tempo che deve trascorrere prima di un nuovo accesso a una stessa locazione di memoria
Negli ultimi anni questi tempi sono molto migliorati rendendo possibili sistemi di memoria più veloci ma al tempo stesso è diminuito anche il tempo di clock del processore:
– IBM PC XT (1980) 4.77 MHz => 210 nsCommodity DRAM T. acc. " 200 ns
– Pentium II (1998) 300 MHz => 3.3 nsCommodity DRAM T. acc. " 50 ns
La performance dei processori raddoppia ogni 18 mesi mentre quella della memoria raddoppia circa ogni 6 anni.
RegistriRegistri
Cache Memory
Cache Memory
MemoriaSecondaria
MemoriaSecondaria
Memoria
Primaria
Memoria
Primaria
Mag
gior
vel
ocità
Mag
gior
Cap
acità
Min
or c
osto
Giovanni Erbacci
Architetture parallele
13
Gerarchie di Memoria / 1
La capacità dei dispositivi di memoria secondaria è dell’ordine dei Gbyte(capacità di circa 10-100 Gbyte per singolo disco).
La capacità della memoria centrale è dell’ordine delle Mword-Gwordmentre la capacità della cache memory è dell’ordine dei KByte-MByte.
Il tempo di accesso fra memoria primaria e memoria secondaria (ad es.dischi) è dell’ordine dei µsecondi (se si sfruttano meccanismi dicaching su disco o su memoria primaria) o addirittura dei msecondiquando si accede direttamente all’informazione localizzata sul disco.
Il tempo di accesso dalla cache memory alla memoria centrale èdell’ordine dei nanosecondi (1 ns = 10-9 s).
15
Giovanni Erbacci
Architetture parallele
14
Cache Memory
Unità di memoria di dimensioni ridotte usata come buffer per i dati chevengono scambiati fra la memoria centrale e il processore.
L'instruction buffer del CDC 6600 era costituito da 8 registri di 60 bit ciascuno(istruzioni di 15 o 30 bit).
Il Cray Y-MP aveva 4 instruction buffer di 128 parcel (16 bit) per CPU (istruzioni di 1, 2, o 4 parcel).
Ogni processsore del Cray T3E ha una cache per le istruzioni di 8 KByte, una per i dati di 8KByte e di una disecondo livello di 96KByte.
– località temporale: una istruzione o un dato possono esserereferenziati più volte
– località spaziale: quando si referenzia una locazione dimemoria, è molto probabile che venganoreferenziate anche le locazioni adiacenti.
l'istruzione viene prelevata dalla cache anzich dalla memoria.un'istruzione può essere eseguita ripetutamente senza ulterioririferimenti alla memoria principale.
Giovanni Erbacci
Architetture parallele
15
Cache Memory / 1
E' demandato all'abilità del sistema far rientrare le istruzioni che compongonoun kernel computazionale pesante (es. un loop) all’interno della cache, se queste possono esservi contenute per intero.
Lo stesso vale per i dati, ma in questocaso l’opera di ottimizzazione coinvolgeanche il programmatore 220 nsMemoria
30 nsL3 Off-Chip
5 nsL2 On-Chip
4 nsL1 On-chip
2 nsRegistri
16
Giovanni Erbacci
Architetture parallele
16
Organizzazione della Cache
La cache è divisa in slot della stessa dimensione (linee)Ogni linea contiene k locazioni di memoria consecutive (es. 4 word).Quando è richiesto un dato dalla memoria, se questo non è già in cache,
viene caricata dalla memoria l’intera linea di cache che lo contiene, sovrascrivendo così il contenuto precedente della linea.
Memoria
Cache
Giovanni Erbacci
Architetture parallele
17
Organizzazione della Cache / 1
Quando si modifica un dato memorizzando un nuovo valore in cache, occorre aggiornare ildato anche in memoria principale:– Cache write-back - i dati scritti nella cache vi
rimangono finché la linea di cache non èrichiesta per memorizzare altri dati quando sideve rimpiazzare la cache il dato vienescritto in memoria; comune nei sistemimono-processore.
– Cache write-through – i dati vengono scrittiimmediatamente nella cache e nella memoriaprincipale.
Nei sistemi con più processori occorre gestire la coerenza della cache: per accedere a datiaggiornati i processori devono essere a conoscenza dell’attività delle cache locali
P1 P2
Cache P1 Cache P2
M
17
Giovanni Erbacci
Architetture parallele
18
Mapping
Poiché in ogni istante temporale la cache può contiene solo un sotto-insieme della memoria, occorre sapere quale: si tratta di associare un insieme di locazioni di memoria ad una linea di cache(mapping).
In base al mapping la cache può essereorganizzata in uno dei seguenti modi:
– - Direct mapped
- Fully associative
- Set associative
Memoria
CacheIl modo con cui le locazioni di memoria vengonomappate nelle linee di cache può incidere sulleprestazioni dei programmi (due locazioni dimemoria pesantemente usate possono esseremappate oppure no sulla stessa linea).
Giovanni Erbacci
Architetture parallele
19
Cache Direct Mapping
Con questo schema, se ad
es. la dimensione della
cache è di 8 Kbyte e la
memoria centrale ha word
di 8 Byte, la prima
locazione di memoria (word
1) viene mappata sulla
linea 1, così come la
locazione d+1, 2d+1, 3d+1
ecc. (dove d = N° linee *
N° word per linea).
……
-25.3
1.7
-18.5
51.9
725
1.9
2050
2049
2048
….
1030
1029
1028
1027
1026
1025
1024
…
6
5
4
3
2
1
Memoria
……
1.7
1.9
Linea 256
…..…
Linea 5
Linea 4
Linea 3
Linea 2
Linea 1
-25.3
725 51.9 -18.5
Cache
18
Giovanni Erbacci
Architetture parallele
20
Cache Direct Mapping / 1
Linea 6
1.7
1.9
Linea 7
Linea 5
Linea 4
Linea 3
Linea 2
Linea 1
Linea 0
-25.3
725
……..……...
……..……...
000
000
111
111
000
000
111
111
111
011
010
010
…
001
001
000
000
000
000
01
00
11
10
01
00
11
10
01
00
11
10
..
01
00
11
10
01
00
0010
0010
0001
0001
0001
0001
0000
0000
0000
0000
0000
0000
….
0000
0000
0000
0000
0000
0000
……
-25.3
1.7
-18.5
51.9
725
1.9
65
64
63
62
33
32
31
30
29
12
11
10
..
5
4
3
2
1
0
51.9 -18.5
Cache8 linee 4 word per linea
Indirizzo
Contenuto
Indica la linea
Indica la parola all’interno della linea
Mem
ori
a
Giovanni Erbacci
Architetture parallele
21
Cache Direct Mapping / 2
Quando si hanno riferimenti di memoria che alternativamente puntano alla stessa
linea di cache (es. word 1, word 1025, word 1, word 1025, ripetutamente), ogni
riferimento causa un cache miss e si deve rimpiazzare la linea appena inserita.
Si genera parecchio lavoro aggiuntivo (overhead); questo fenomeno è detto
thrashing.
19
Giovanni Erbacci
Architetture parallele
22
Cache Fully Associative
Con questo schema, ogni locazione di memoria può essere mappata in qualsiasi linea di cache, senza tener conto dell’indirizzo di memoria.
Il nome deriva dal tipo di memoria usata per costruire questo tipo di cache (memoria associativa).
Quando il processore richiede un dato questo viene richiesto a tutte le linee di cache contemporaneamente.
Se una linea contiene il dato, questo viene fornito, diversamente si ha un cache miss.
In genere la linea usata meno recentemente (politica LRU) è destinata ad essere sovrascritta con il nuovo dato.
Le cache fully associative sono costose ma garantiscono un utilizzosuperiore se confrontate con le cache direct mapped.
Giovanni Erbacci
Architetture parallele
23
Cache Set Associative
Si tratta praticamente di una cache direct mapped replicata in più copie(banchi).
In genere si hanno 2 o 4 banchi separati di cache (two-way, four-way set
associative).
Con questo schema, se una locazione di memoria viene mappata sullalinea k, un successivo riferimento a una locazione di memoria sempremappato sulla stessa linea, verrà allocato sulla linea K di un diversobanco.
Una cache set associative è meno predisposta a cache thrashing rispettoa una cache direct mapped della stessa grandezza. Infatti unalocazione di memoria verrà mappata in una linea che può essere sceltasu banchi differenti.
20
Giovanni Erbacci
Architetture parallele
24
Cache Set Associative
17
100
33
71
66
……
-25.3
1.7
-18.5
51.9
725
1.9
2050
2049
2048
….
1030
1029
1028
1027
1026
1025
1024
…
6
5
4
3
2
1
Mem
oria
Cac
he
17
66
Linea 2
Linea 1 71 10033
-25.3
725 -18.551.9
……
1.7
1.9
Linea 256
…..…
Linea 5
Linea 4
Linea 3
Linea 2
Linea 1
Banco 1
Banco 2
2 way set associative
2048 word, linee di 4 word
Giovanni Erbacci
Architetture parallele
25
Quesito
E’ più efficiente una cache set associative a k vie oppure una chache direct mapping con la stessa capienza e con lo stesso numero di word per linea?
Dare una dimostrazione della risposta data.
21
Giovanni Erbacci
Architetture parallele
26
Multiprogrammazione e Time Sharing
Giovanni Erbacci
Architetture parallele
27
Look ahead delle Istruzioni
Il concetto di look ahead consiste nel rendere disponibili diverse istruzionidecodificate e pronte per l'esecuzione, prima che vengano effettivamenterichieste.
– L'IBM STRETCH è stato il primo sistema ad introdurre questa possibilità: era possibileprelevare le istruzioni, decodificarle, calcolare gli indirizzi degli operandi, fare il fetch degli operandi, diverse istruzioni in anticipo rispetto alla loro esecuzione effettiva.
– L'IBM 360/91 inoltre ammetteva il prefetch di un'istruzione condizionale e di alcunedelle istruzioni successive, in modo da mantenere l'unità di esecuzione piena dopoogni salto condizionale.
Il look ahead delle istruzioni è necessario per migliorare le prestazioni nei sistemicon più unità funzionali.
22
Giovanni Erbacci
Architetture parallele
28
Compilatori e Look-aheadPer migliorare le prestazioni i compilatori riorganizzano la sequenza delle istruzioni
affinchè in esecuzione sfruttino il look ahead.
STORE D, R3
ADD R3, R4
FETCH R4, F
FETCH R3, E
STORE A, R1
ADD R1, R2
FETCH R2, C
FETCH R1, B
STORE D, R3
STORE A, R1
ADD R3, R4
ADD R1, R2
FETCH R4, F
FETCH R3, E
FETCH R2, C
FETCH R1, B
A #### B + C
D #### E + F
Giovanni Erbacci
Architetture parallele
29
Unità Funzionali Multiple
Nei calcolatori tradizionali, la CPU è costituita da un insieme diregistri generali, da alcuni registri speciali (es. il program
counter) e dall'unità aritmetico logica (ALU) che, una per volta, calcola le operazioni.
Un primo passo verso il parallelismo consiste nel suddividere le funzioni dell'ALU e progettare unità indipendenti capaci dioperare in parallelo (unità funzionali indipendenti).
E' compito del compilatore esaminare le istruzioni e stabilire qualioperazioni possono essere fatte in parallelo, senza alterare la semantica del programma.
23
Giovanni Erbacci
Architetture parallele
30
Unità Funzionali Multiple / 1
PP 0PP 1PP 2PP 3PP 4PP 5PP 6PP 7PP 8PP 9
12PeripheralChannels
Peripheral Processors
24Registers
10 Functional Units
I/O Subsystem Memory Central Processor
AddMultiplyMultiplyDivideFixed AddIncrementIncrementBooleanShiftBranch
InstructionStack Scoreboard
Central
Storage
Giovanni Erbacci
Architetture parallele
31
Pipelining
Il concetto di pipelining è analogo a quello di catena di montaggiodove in una linea di flusso (pipe) di stazioni di assemblaggio glielementi vengono assemblati a flusso continuo.
Idealmente tutte le stazioni di assemblaggio devono avere la stessa velocità di elaborazione altrimenti la stazione più lentadiventa il bottleneck dell'intera pipe.
24
Giovanni Erbacci
Architetture parallele
32
0 1 2 3 4 5 6 7 8 9 10
Tempo(cicli)
Spazio
T1
T1
T1
T4
T3
T2
T1
T1
T2
T2
T2
T2
T3
T3
T3
T3
T4
T4
T4
1 2
1
1
1
2
2
2 3
3
3
3
T4
4
4
4
4 5
5
5
5 ....
....
....
....
Tj
ij subtask del task imo mo
S1
S2
S4
S3
Pipelining / 1
Un task T viene scomposto in un insieme di sotto task {T1,T2,...Tk}
legati da una relazione di dipendenza: il task Tj non può partire
finchè tutti i sotto task precedenti {Ti ,$ i<j} non sono terminati
Giovanni Erbacci
Architetture parallele
33
Struttura di un Processore a Pipeline
Un processore a pipeline consiste di una cascata di stages di elaborazione.Gli stages sono circuiti che eseguono le operazioni aritmetiche o logiche sulla
corrente di dati che fluisce attraverso la pipe.Gli stages sono separati da interfacce (latches) cioè da registri veloci che
contengono i risultati intermedi fra gli stages.Le informazioni fluiscono fra stages adiacenti sotto il controllo di un clock
comune applicato a tutti i latches simultaneamente
OUTPUT
C
INPUT
L L L L L
S1
S2
Sk
....
latch
clock
stage
C :
L : i moS :i
25
Giovanni Erbacci
Architetture parallele
34
Prestazione della Pipeline
Sia !!!!i il delay temporale relativo all'insieme dei circuiti logici checompongono ciascun stage Si e sia !!!!l il delay temporale di ciascunlatch di interfaccia.
Il clock period (ciclo macchina) di una pipeline è definito da:!!!! = max{!!!!i, i = 1, k} + !!!!l
Si definisce frequenza di una pipeline il reciproco del clock period:f = 1 / !!!!
La pipe, una volta riempita, produce un risultato per clock period, indipendentemente dal numero di stages che la compongono
Idealmente, una pipe con k stages processa n tasks in tk = k + (n-1)
clock periods; di questi, k servono a riempire la pipe cioè a completare l'esecuzione del primo task (tempo di start up).
Giovanni Erbacci
Architetture parallele
35
Pipeline di Istruzioni
Fetchistruzioni operandi
Decodifica Fetch Esecuzione Storerisultato
S 1 S 2 S 3 S 4 S 5
0 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 2725 26 28 29 30
TimeI1
I2
I3
I4
I5
I6
I7
I8
........
0 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 2725 26 28 29 30
TimeI1
I2
I3
I4
I5
I6
I7
I8
........
26
Giovanni Erbacci
Architetture parallele
36
Esempio
Il CDC 6600 aveva unit funzionali segmentate.Riordinando il codice si poteva sfruttare il pipelining (pipelining delle
istruzioni scalari) in maniera efficiente.
A = B*C+D*E
K = W*X-Y*Z
(W*X)-(Y*Z)
Y*Z
W*X
(B*C)+(D*E)
D*E
B*C S1####-S1+S2
S3####-S3*S4
S1####-S1+S3
S5####-S5*S6
S5####-S5-S7
S7####-S7*S8
Tempo
Giovanni Erbacci
Architetture parallele
37
Esempio / 1
(W*X)-(Y*Z)
(B*C)+(D*E)
Y*Z
W*X
D*E
B*C S1####-S1*S2
S3####-S3*S4
S5####-S5*S6
S7####-S7*S8
S1####-S1+S3
S5####-S5-S7
Tempo
27
Giovanni Erbacci
Architetture parallele
38
Modelli di Elaborazione
Somma di due vettori A e BElementi floating point
Ci = Ai + Bi per i = 1, …., n
L’operazione di somma comporta lo svolgimento di 4 azioni in sequenza:
Ai = fi x 2pi
Bi = gi X 2ri
confronto degli esponenti (ri - pi)
allineamento delle mantisse
addizione delle mantisse
normalizzazione del risultato
Supponiamo che ogni azione duri esattamente 1 ciclo macchina
Giovanni Erbacci
Architetture parallele
39
Elaborazione Sequenziale
Elaborazione sequenziale: un risultato ogni 4 cicli
B3A3
C3
B1A1
C1
B2A2
C2
………
Tem
po
28
Giovanni Erbacci
Architetture parallele
40
Elaborazione Pipelining
Unità funzionale in pipelining
Dopo la fase di start-up si ha un risultato per ciclo
B5A5
C5
B4A4
C4
B3A3
C3
B1A1
C1
B2A2
C2
………
! = 1
! = 2! = 3
! = 4! = 5
! = 6! = 7
! = 8
Tem
po
Giovanni Erbacci
Architetture parallele
41
Elaborazione Parallela
Sincrona
B5A5
C5
B4A4
C4
B3A3
C3
B1A1
C1
B2A2
C2
………
! = 1
! = 2! = 3
! = 4
Tem
po
Sincronizzazione ad ogni passo
Con P processori si producono P risultati ogni 4 cicli
Clock
29
Giovanni Erbacci
Architetture parallele
42
Elaborazione Parallela
Asincrona
B5A5
C5
B4A4
C4
B3A3
C3
B1A1
C1
B2A2
C2
………
! = 4
Sincronizzazione finale
Con P processori si producono P risultati ogni 4 cicli
Tem
po
Giovanni Erbacci
Architetture parallele
43
Classificazione di FlynnM. J. Flynn
Very high speed computing systems, proceedings of the IEEE (1966).
Some computer organizations and their effectiveness, IEEE Transaction on Computers.(1972)."The moltiplicity is taken as the maximum possible number of simultaneous operations (instructions) or operands (data) being in the same phase of execution at the most constrained component of the organization"
SISD, SIMD, MISD, MIMD
30
Giovanni Erbacci
Architetture parallele
44
Sistemi SISD
Sistemi Sequenziali- Corrisponde alla classica architettura di von Neumann.
- Sistemi scalari monoprocessore.
- L'esecuzione delle istruzioni può essere pipelined (Cyber 76).
- Ciascuna istruzione aritmetica inizia un'operazione aritmetica
CU PU MMIS DS
CU Control UnitPU Processing UnitMM Memory ModuleDS Data streamIS Instruction Stream
Giovanni Erbacci
Architetture parallele
45
Sistemi SIMD
CU Control UnitPU Processing UnitMM Memory ModuleDS Data streamIS Instruction Stream
DS2
DS1
MM2
MM1
MMn
.
.
.
CU
IS
PU2
PU1
PUn
DSn
.
.
.
31
Giovanni Erbacci
Architetture parallele
46
Sistemi MIMD
.
.
.
.
.
.
.
.
.
IS2
CU2
IS2
PU2 MM2
DS2
PU1 MM1
DS1
PUn MMn
DSn
CU1
CUn
ISn
IS1
IS1
ISn
CU Control UnitPU Processing UnitMM Memory ModuleDS Data streamIS Instruction Stream
Giovanni Erbacci
Architetture parallele
47
Calcolatori Vettoriali
Dispongono di un set di istruzioni vettoriali che siaggiunge al set di istruzioni di istruzioniscalari.
Le istruzioni vettoriali specificano una particolareoperazione che deve essere eseguita su un determinato insieme di operandi detto vettore.
In questo contesto un vettore è una lista ordinatadi valori scalari.
Le unità funzionali che eseguono istruzioni vettoriali sfruttano il pipelining per esegure la stessa operazione su tutte le coppie di operandi.
32
Giovanni Erbacci
Architetture parallele
48
Calcolatori Vettoriali / 1
Organizzazione da memoria a memoria
Le unità funzionali floating point possono comunicaredirettamente con la memoria principale per ricevere o trasferiredati.
I sistemi Cyber 205 e ETA10 adottavano questa soluzione.
Organizzazione da registro a registro
Le unità funzionali interfacciano i registri; occorre un set di registrivettoriali, ciascuno dei quali è in grado di contenere più di un elemento.
Il path con la memoria viene attivato attraverso i registri.
Giovanni Erbacci
Architetture parallele
49
Registri Vettoriali
Un registro vettoriale è un particolare registro in grado di contenere più dati di uno stesso tipo.
si tratta di un insieme fisso di locazioni di memoria, che fa parte di una specialememoria sotto il controllo utente.
Il numero di elementi che può contenere un registro vettoriale è detto vector length.– Cray Y-MP: 8 registri vettoriali di 64 elementi a 64 bit
– Cray C90: 8 registri vettoriali di 128 elementi a 64 bit
– IBM ES 9000: 16 registri vettoriali di 256 elementi a 32 bit opure 8 a 64 bit.
81024
16512
32256
64128
12864
256 32
ElementiRegistri
Registri vettoriali configurabili
33
Giovanni Erbacci
Architetture parallele
50
Esempio
do i = 1, N
A(i) = B(i)+C(i)
end doB(2)
C(2)
B(1)
C(1)
B(3)
C(3)
B(1)
C(1)
B(2)
C(2)
B(4)
C(4)
B(1)
C(1)
B(2)
C(2)
B(3)
C(3)
B(5)
C(5)
B(1)
C(1)
B(2)
C(2)
B(3)
C(3)
B(4)
C(4)
B(6)
C(6)
B(1)
C(1)
B(2)
C(2)
B(3)
C(3)
B(4)
C(4)
B(5)
C(5)
B(7)
C(7)B(1) C(1)+
B(2)C(2)
B(3)
C(3)
B(4)C(4)
B(5)
C(5)
B(6)
C(6)
B(1)
C(1)
.... B(3) B(2) B(1)
.... C(3) C(2) C(1)
.... C(4) C(3) C(2)
.... C(8) C(7) C(6)
.... C(5) C(4) C(3)
.... C(6) C(5) C(4)
.... C(7) C(6) C(5)
.... C(9) C(8) C(7)
.... C(10) C(9) C(8)
.... B(4) B(3) B(2)
.... B(5) B(4) B(3)
.... B(6) B(5) B(4)
.... B(7) B(6) B(5)
.... B(8) B(7) B(6)
.... B(9) B(8) B(7)
.... B(10) B(9) B(8)
CP 0
CP 1
CP 2
CP 3
CP 4
CP 5
CP 7
CP 6
V0 # V1 + V2
Unità Funzionale Add Floating Point
Giovanni Erbacci
Architetture parallele
51
Supercalcolatori Vettoriali
.
34
Giovanni Erbacci
Architetture parallele
52
Chaining nei Calcolatori Vettoriali
do i = 1, n
A(i) = B(i) + C(i) * 0.5
end do15
16
128
1
15
128
1
2
14
128
1
29
30
128
1
16
23 21 19 17
24 22 20 18
11 9 7 5 3
4681012
S0
V0
V1
V2
V3
SOMMA
MOLTIPLICAZIONE
...
...
...
...
...
...
...
...
MEMORIA
13
14
27 25
28 26
Giovanni Erbacci
Architetture parallele
53
Array Processors
Un array processor è costituito da un set di processing element (PE) identici, che operano in modo sincrono, capaci di eseguiresimultaneamente la stessa operazione su dati differenti.
Gli array processor costituiscono un altro modo classico di realizzaresistemi di elaborazione in grado di operare su array.
Sono sistemi ormai fuori commercio ma che negli anni ’70-’80 hannoavuto un loro successo.
Con questa soluzione, ogni elemento vettoriale viene elaborato da un differente PE.
Alcuni array processor sono concepiti come sistemi indipendenti, altri, chiamati attached array processor, richiedono un sistema ospite.
35
Giovanni Erbacci
Architetture parallele
54
EsempiIlliac IV
progettato nella seconda met degli anni '60, Universit dell'Illinois256 processori elementari, ciascuno con una propria memoria locale di 2K word, suddivisi in 4 quadranti ciascun quadrante prevedeva un'unit di controlloche supervisionava l'array di 8 x 8 processori di quel quadrante solo nel 1972 la Burroughs ne realizzò una versione a un solo quadrante.
Altri esempi
Staran e MPP goodyear (1975),PEPE (1976), realizzato da Burroughs come attached per il Cyber 76 BSP Burroughs (1978),attached per il Burroughs B7800 ICL DAP (Inghilterra, 1979) attached per i sistemi della serie ICL 2900.Gli attached processor pi noti sono i sistemi prodotti dalla Floating Point System Inc, come ad es. AP-120 (1976) e FPS-164 (1980). Gli attached processor FPS non sono strutturati come array di PE, ma sfruttanoil pipelining.
Giovanni Erbacci
Architetture parallele
55
Progetto APEAPE: computer SIMD a parallelismo massiccio
Il progetto APE nasce verso la metà degli anni 80 ad opera di un gruppo
di fisici italiani dell`INFN. Potenza di calcolo di 1 Gflops.
Intorno al 1988 nasce il progetto di APE100, evoluzione di APE,
determinato da una più forte richiesta di potenza di calcolo (primi prototipi
realizzati nel 1990).
APE100, commercializzato da QSW (ALENIA) con il nome di Quadrics, è
scalabile da 8 a 2048 nodi
Ogni nodo di elaborazione è composto da:– processore floating point a 32 bit (MAD),
– banco di memoria RAM da 4 a 16 Mbytes,
– logica di comunicazione node-to-node
e può raggiungere una potenza di calcolo pari a 50 Mflops.
La configurazione completa di APE100 era costituita da 2048 nodi
(potenza di picco di 100 Gflops)
36
Giovanni Erbacci
Architetture parallele
56
Progetto APE / 1
Nel 1994 nasce il progetto APEmille: come APE100 è una macchinaparallela scalabile, tridimensionale di tipo SIMDArchitettura tridimensionale basata su una griglia cubica di nodi dielaborazione.
Ogni nodo è connesso direttamente con i 6 nodi più vicini attraverso deicanali di comunicazione dati sincroni.
I nodi sono ottimizzati per eseguire aritmetica in floating point a singolaprecisione, ma sono supportate anche operazioni intere e in floating point a doppia precisione (non presenti su APE100).
APE NEXT
Giovanni Erbacci
Architetture parallele
57
CM 2
Sistema SIMD prodotto da Connection Machine Corporation nel 1987
Prevede fino a 64k processori (bit procesor)
Architecture
The machines consist of an array of simple proprietary bit-serial
processors directly connected to local memory. Groups of 32
processors may optionally share a floating point accelerator unit. The memory uses commercially
available dynamic RAM. The machine is driven by a Sun, Vax
or Symbolics 3600-series machine.
37
Giovanni Erbacci
Architetture parallele
58
Array Sistolici
Il concetto di architettura sistolica è stato sviluppato da H. Kung allaCarnegie Mellon University, all'inizio degli anni '80.
Un array sistolico consiste di un insieme di celle identiche, interconnesse, ciascuna capace di eseguire un set di operazioni elementari.
Il flusso dei dati scorre fra le celle in una sorta di pipeline e la comunicazionecol mondo esterno avviene solo nelle celle di frontiera.
Ad intervalli regolari, ogni cella riceve da più direzioni dati che combina e poi ripropaga alle altre celle.
I dati dalla memoria vengono spinti attraverso l'array di celle, in modoanalogo a come opera la contrazione cardiaca, da cui deriva il nomesistolico.
Giovanni Erbacci
Architetture parallele
59
Esempio
A ha una banda lungo la diagonale principale di (3+2)-1=4
B ha una banda lungo la diagonale principale di (2+3)-1=4
C avrà una banda lungo la diagonale principale di (4+4)-1=7
=%
.....................
...00
...0
...
...
...0
...00
.....................
...0000
...000
...00
...00
...00
...00013
.....................
...000
...00
...00
...00
...000
...0000
66656463
5655545352
464544434241
363534333231
2524232221
14131211
6665
565554
46454443
35343332
24232221
1211
666564
56555453
45444342
34333231
232221
1211
cccc
ccccc
cccccc
cccccc
ccccc
cccc
bb
bbb
bbbb
bbbb
bbbb
bbb
aaa
aaaa
aaaa
aaaa
aaa
aa
Moltiplicazione di una matrice a bande
A %%%% B ====C
Cijout = Cij
in + aik %%%% bkj
38
Giovanni Erbacci
Architetture parallele
60
Esempio
È richiesta una griglia di 4 x 4 celle ditipo esagonale, ogni cella ha 3 input e 3 output.
Gli elementi di A = (aij) e B = (bij) entrano nelle celle lungo le due diagonali. Entrano anche glielementi C = (cij) che inizialmentehanno valore cij = 0.
I dati fluiscono attraverso l'array in modalità pipeline e dall'alto escono i risultati.
Se il delay temporale per ogni cella èunitario, l'array sistolico puòterminare la computazione in un tempo T = 3n + min(4, 4),linearmente proporzionale alladimensione della matrice (n).
Cijout = Cij
in + aik %%%% bkj
Giovanni Erbacci
Architetture parallele
61
VLIWJoseph-Fisher Yale University
Very Long Instruction Word architectures,
Multiflow Computer (1984)
Architetture RISC con un numero elevato di unità funzionalipipeline per sovrapporre l'esecuzione di operazioniindipendenti
Il controllo è centralizzato
Le risorse sono completamente controllate dal compilatore.
39
Giovanni Erbacci
Architetture parallele
62
VLIW / 1
Giovanni Erbacci
Architetture parallele
63
Sistemi Paralleli di classe MIMDMainframes multiprocessor
A metà degli anni '70 si diffondono i primi mainframes multiprocessore: Univac 1100/80(1976), Burroughs B-7800 (1978), Cyber 170/720 (1979), IBM 3081 (1980).
Solo il gestore del sistema beneficia del miglioramento del throughput (numero dilavori completati per unità di tempo).
Rimane il von Neumann bottelneck.
Sistemi multiprocessor ed elaborazione parallela
E' interessante invece disporre di sistemi multiprocessore in cui le diverse CPU possono essere attive in modo concorrente nella soluzione di un singolo problema(elaborazione parallela).
Multicomputer
Un sistema multicomputer consiste di più calcolatori autonomi che possono comunicareo meno l'uno con l'altro (distributed memory system).
Multiprocessor
In un sistema multiprocessor le diverse CPU che compongono il sistema condividonouna memoria centrale unica (shared memory system).
40
Giovanni Erbacci
Architetture parallele
64
Esempi di Sistemi MIMD
Cray Y MP/8, Cray C90/16, Cray T90/32 Cray T3D, Cray T3EIBM ES900-530-VFIBM SP1, SP2, SP3, SP4Ipercubi N-CubeIpercubi Intel Paragon IntelKSR1MeikoParsytec GC-2Thinking Machine Corp. CM5Fujitsu AP 100 e VPP500NEC SX4, SX5SGI Origin 3800
Giovanni Erbacci
Architetture parallele
65
Classificazione in Base alla Memoria
P
M
P
M
P
M
P
M
P
M
P
M
N
Sistema a Memoria Distribuita
Sistema a Memoria Condivisa
M
P P
PP
41
Giovanni Erbacci
Architetture parallele
66
Sistemi a Memoria CondivisaI processori coordinano la loro attività, accedendo ai dati e alle istruzioni in una memoria globale (shared memory), condivisa da tutti i processoriUniform Memory Access (UMA)model <=> SMP: Symmetric Multi ProcessorsL’accesso alla memoria è uniforme: i processori presentano lo stesso tempo di accesso per tutte le parole di memorial’interconnessione processore-memoria avviene tramite common bus, crossbar switch, o multistage network. ogni processore può disporre di una cache locale, le periferche sonocondivise.Alcuni esempi: ETA10, Cray 2, Cray C90, IBM 3090/600 VF, NEC SX-5 I sistemi a memoria condivisa presentano un numero limitato di processori(da 2 a 32) molto potenti (possoo presentare anche un’architettura vettoriale)Questi multiprocessori sono chiamati tightly coupled systems per l’alto gradodi condivisione delle risorse
Giovanni Erbacci
Architetture parallele
67
Sistemi a Memoria Distribuita
La memoria è distribuita fisicamente tra i processori (local memory).
tutte le memorie locali sono private e può accedervi solo il processorelocale
La comunicazione tra i processori avviene tramite un protocollo di comunicazione a scambio di messaggi (message passing).
I messaggi che vengono instradati sulla rete di interconnessioneIn genere si tratta di sistemi che presentano un numero elevato di
processori (da poche decine ad alcune migliaia), ma di potenza non troppo elevata, chiamati nodi di elaborazione.
42
Giovanni Erbacci
Architetture parallele
68
Sistemi NUMA
Non Uniform Memory Access (NUMA) model
La memoria è fisicamemte distribuita fra tutti i processori (ogniprocessore ha una propria memoria locale)
L’insieme delle memorie locali forma uno spazio di indirizzi globale, accessibile da tutti i processori
Supporto hw per far si che ogni processore possa indirizzare la memoria di tutti i processori
Il tempo di accesso dal processore alla memoria non è uniforme: – l’accesso è più veloce se il processore accede alla propria memoria
locale;
– quando si accede alla memoria dei processori remoti si ha un delaydovuto alla rete di interconnessione.
Giovanni Erbacci
Architetture parallele
69
Il concetto di Nodo
Nodo SMP
M
P P
PP
43
Giovanni Erbacci
Architetture parallele
70
Condivisione Fisica e Logica
Condivisione fisica della memoriale CPU hanno lo stesso spazio di indirizzamentoi valori scritti in una parola da una CPU possono essere letti da
un'altra.
Condivisione logica della memoriadeterminata da come il sw, in opposizione all'hw, vede ilsistema.
Quando due processi (programmi in esecuzione) condividono la stessa memoria logica, le informazioni scritte in una strutturadati da uno di questi, possono essere lette dall'altro.
Quando non c' condivisione logica i processi devonocomunicare con forme di I/O (read e write di buffer) o tramitemessage passing.
Giovanni Erbacci
Architetture parallele
71
Condivisione Fisica e Logica / 1
In sistemi a memoria fisica condivisa il software può usare il message passing.Simulazione di memoria condivisa logicamente su macchine che possono
comunicare solo tramite message passing.Linda è un modello di programmazione basato su uno spazio astratto di tuple.
Ogni tupla contiene uno o più elementi dati, come un record Pascal. Tutti i processi condividono logicamente lo stesso spazio delle tuple, non importadove risiede.
multiprocessori a memoria condivisacondivisacondivisa
message passing simulato da buffer condivisinon condivisacondivisa
memoria virtuale distribuita (Linda)condivisanon condivisa
Message passing tra processori disgiuntinon condivisanon condivisa
EsempiMemoria logica(Sw)
Memoria fisica(Hw)
44
Giovanni Erbacci
Architetture parallele
72
Rete di Interconnessione: definizioni
Grafo aciclico:
un grafo che non contiene cicli
grado:
il grado è il numero di linee connesse a un nodo in una data topologia. E’ equivalente al numero di primi vicini del nodo. E’ un indice della connettività
Un grado grande è un benefico perché identifica una molteplicità di paths.
Diametro:
il diametro di una rete è la distanza tra i due nodi più lontani (percorso più lungo tra due nodi)
Un diametro piccolo corrisponde a una latenza bassa.
Neighbor:Due nodi si dicono vicini se c un link che li connette.
Giovanni Erbacci
Architetture parallele
73
Rete di InterconnessioneCos una rete di interconnessione?È l’insieme dei cavi che definiscono come i diversi processori di un calcolatore parallelo sono connessi
tra loro e con le unità di memoria.
Il tempo richiesto per trasferire i dati dipende dal tipo di interconnessione.
Il tempo di trasferimento è detto communication time.
La massima distanza che devono percorrere i dati scambiati tra due processori che comunicano
incide sulle prestazioni della rete.
Caratteristiche di una rete di interconnessioneBandwidth: identifica la quantità di dati che possono essere inviati per unità di tempo sulla rete. Occorre
massimizzare la bandwidth
Latenza: identifica il tempo necessario per instradare un messaggio tra due processori. Si definisce
anche come il tempo necessario per trasferire un messaggio di lunghezza nulla.
Occorre minimizzare la latenza
Altri aspetti da considerare- Costo
- Scalabilità
- Affidabilità
- Diametro
- Degree
45
Giovanni Erbacci
Architetture parallele
74
Connettività
Interconnessione completa (ideale)– Ogni nodo può comunicare direttamente con tutti
gli altri nodi (in parallelo)
– con n nodi si ha un'ampiezza di bandaproporzionale a n2.
– il costo cresce proporzionalmente a n2.
Giovanni Erbacci
Architetture parallele
75
Bus Network
La topologia Bus è costituita daun cavo coassiale (bus) al quale vengono connessi tutti I dispositivi
I benefici di una rete basata suBus sono la semplicità dicostruzione e il costo moltobasso.
Gli aspetti negativi sono il rate ditrasmissione dati limitato e diconseguenza la non scalabilità in termini diperformance.
46
Giovanni Erbacci
Architetture parallele
76
Cross-bar Switch Network
Un cross-bar switch è una network che opera secondo un meccanismodi switching per connettere dispositivi ad altri dispositivi (processori, memoria).
Meccanismo analogo a quello adottato dai sistemi telefonici. Scalameglio del bus ma ha costi maggiori
Giovanni Erbacci
Architetture parallele
77
Multi-Stage Switching Network
In questa topologia diversi layers di switches connettono N nodi di un tipo a N nodi di un altro tipo.
Il Multi-Stage Switching una Network configurabile dinamicamente. Ciòsignifica che gli switches che connettono i vari processori possonoesssere cambiati dinamicamente, a seconda di dove va inviato ilmessaggio.
47
Giovanni Erbacci
Architetture parallele
78
Topologia Mesh
In una network a griglia, i nodi sono disposti secondo un reticolo a k dimensioni (k dimensional lattice) di ampiezza w, per un totale di wk
nodi.– k=1 (array lineare)
– k=2 (2D array) es. ICL DAP, Intel Paragon,
La comunicazione diretta è consentita solo tra i nodi vicini.
I nodi interni comunicano direttamente con altri 2k nodi.
Giovanni Erbacci
Architetture parallele
79
Topologia Toroidale
Alcune varianti del
modello a mesh
presentano connessioni
di tipo wrap-around fra i
nodi ai bordi della mesh
(topologia toroidale).
Il Cray T3E adotta una
topologia toroidale 3D.
48
Giovanni Erbacci
Architetture parallele
80
Topologia Ipercubo
Una topologia ipercubo (cube-connected) formata da n =2k nodi connessi secondo i vertici di un cubo a k dimensioni.
Ogni nodo connesso direttamente a k altri nodi.
Il degree di una topologia ipercubo log n ed anche il diametro log n.
Esempi di calcolatori con questo tipo di network sono la CM2, NCUBE-2, Intel iPSC860, SGI Origin.
Giovanni Erbacci
Architetture parallele
81
Topologia Ipercubo / 1
49
Giovanni Erbacci
Architetture parallele
82
Gray Coding
In un ipercubo a k dimensioni, ciascuno dei 2k vertici etichettatocon un numero intero binario di k bit.
Coordinate cartesiane nello spazio k-dimensionale.Gli identificatori di due nodi adiacenti differiscono di un solo bit.La distanza tra due nodi qualsiasi uguale al numero di bit
differenti nei loro identificatori.Fra coppie di nodi non adiacenti sono possibili pi percorsi.Occorre un algoritmo di instradamento (routing).Esempio: XOR(Natt., Ndest)
I bit a 1 indicano gli assi su cui i nodi si diversificanoIl messaggio va inviato lungo uno di questi assi
XOR(100,001) = 101lungo il 1° asseoppure lungo il 3°
Giovanni Erbacci
Architetture parallele
83
Topologia TreeI processori sono I nodi terminali (foglie) di un
albero
Il degree di una network con topologia ad albero con N nodi è log2N e il diametro è
2 log 2(N) - 2
Fat treela bandwidh della network aumenta all aumentare del livello della rete.Esempi: CM-5, Network Myrinet e QSNet
Piramide
Una network piramidale di ampiezza p un albero 4-rio completo con livelli, dove i nodi di ciascun livello sono collegati in unamesh bi-dimensionale.
50
Giovanni Erbacci
Architetture parallele
84
Architetture RISC
RISC : Reduced Instruction Set Computer contrapposto aCISC: Complex Instruction Set Computers
Reg-RegReg-Reg4StackReg - Reg
Reg - Mem
Mem - Mem
Reg– Reg
Reg - Mem
Mem - Mem
Dimensione Istruzioni
440132 - 572 - 6DimensioneMicrocodice
0012017 K61 K54 K
55391980270303208Istruzioni
19831981801197819781973Anno di completamento
Stanford MIPS
Berkeley RISC I
IBMXEROX Dorado
VAX 11/780IBM 370/168
RISCCISC
Giovanni Erbacci
Architetture parallele
85
Architetture RISC / 1
RISCCISC
Istruzioni semplici che richiedono un ciclo
Istruzioni complesse che richiedonopiù cicli
Solo le istruzioni di load e storepossono far riferimento allamemoria
Ogni istruzione può far riferimentoalla memoria
Insieme di registri multipliInsieme di registri singoli
La complessità è nel compilatoreLa complessità è nelmicroprogramma
Poche istruzioni e modalitàMolte istruzioni e modalità
Istruzioni a formato fissoIstruzioni a formato variabile
Istruzioni eseguite dall’hardwareIstruzioni interpretate dalmicroprogramma
Molto pipeliningNessun o poco pipelining
51
Giovanni Erbacci
Architetture parallele
86
Architetture RISC / 2
Superscalari
Un processore superscalare ha più unità funzionali (pipeline multiple).
Più istruzioni per volta vengono caricate, decodificate, eseguite.
In genere: operazione Integer / operazione Floating Point / Load
Pipelining delle istruzioni.
Esempi di sistemi RISC superscalari: – DEC Alpha, HP PA-RISC, IBM RS/6000, (Intel Pentium), SGI Origin,
IBM Power IV e Power V
52