3. Evoluzione delle architetture
indice
3
3.1
3.2
3.3
3.4
3.5
Evoluzione delle architetture
Evoluzione tecnologica
Pipeline
Gerarchia di memoria
Memoria virtuale
Architettura RISC
L’architettura x86
Architettura degli elaboratori 1 - A. Memo
100
3. Evoluzione delle architetture
evoluzione tecnologica

CPU
- densità di transistor: +30% per anno
- frequenza di clock: +20% per anno

Memoria - capacità: +60% per anno
- velocità di accesso: +10% per anno
- costo per bit: -25% per anno

Hard disk - capacità: +60% per anno
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
101
3. Evoluzione delle architetture
evoluzione strutturale



a breve gli sviluppi tecnologici si dovranno
limitare, in attesa di un cambiamento totale
l’aumento di prestazioni è legato sempre più
ad organizzazioni più efficienti
parallelismo: se un lavoro non può essere
fatto più velocemente da una sola persona,
allora bisogna farlo fare da più persone
contemporaneamente
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
102
3.1 Pipeline
generalità 1



per svolgere un lavoro si devono seguire tre
fasi distinte e sequenziali
L  [fase1] [fase2] [fase3]
se ogni fase richiede un tempo T, un unico
esecutore svolge un lavoro ogni 3T
per ridurre i tempi di produzione si possono
utilizzare più esecutori
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
103
3.1 Pipeline
generalità 2

soluzione totalmente parallela
Esec 1  [fase1] [fase2] [fase3] [fase1] [fase2] [fase3]
Esec 2  [fase1] [fase2] [fase3] [fase1] [fase2] [fase3]
Esec 3  [fase1] [fase2] [fase3] [fase1] [fase2] [fase3]
- N esecutori svolgono un lavoro ogni 3T/N
- purtroppo non va bene in informatica perché
i lavori (istruzioni) sono (spesso) sequenziali
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
104
3.1 Pipeline
generalità 3
soluzione pipeline ad esecutori generici
Esec 1  [fase1] [fase2] [fase3] [fase1] [fase2]
Esec 2  ............ [fase1] [fase2] [fase3] [fase1]
Esec 3  ......................... [fase1] [fase2] [fase3]
- N esecutori svolgono a regime un lavoro ogni
3T/N e la sequenza dei lavori viene rispettata

Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
105
3.1 Pipeline
generalità 4
soluzione pipeline ad esecutori specifici
Esec 1  [fase1] [fase1] [fase1] [fase1] [fase1]
Esec 2  ............ [fase2] [fase2] [fase2] [fase2]
Esec 3  ......................... [fase3] [fase3] [fase3]
- ogni esecutore svolge sempre e solo la stessa
fase di tutti i lavori
- soluzione più efficiente in termini di risorse

Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
106
3.1 Pipeline
scomposizione in fasi
L’esecuzione di una generica istruzione può
essere ad esempio suddivisa in
 fetch
lettura dell’istruzione
 decode
decodifica dell’istruzione
 read data
lettura degli operandi
 execute
esecuzione dell’istruzione
 write data scrittura del risultato
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
107
3.1 Pipeline
evoluzione teorica
clock
ciclo1
ciclo2
ciclo3 ciclo4
ciclo5 ciclo6
Fetch  istr 1
istr 2
istr 3
istr 4
istr 5
istr 6
Decode  ............ istr 1
Read M  .........................
istr 2
istr 3
istr 4
istr 5
istr 1 istr 2 istr 3
Execute  ........................................ istr 1 istr 2
Write M  ....................................................... istr 1
istr 4
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
istr 3
istr 2
108
3.1 Pipeline
i problemi
In pratica il pipeline non permette di raggiungere il parallelismo teorico per

sbilanciamento delle fasi

problemi strutturali
dipendenza dei dati
dipendenza dai controlli


Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
109
3.1 Pipeline
sbilanciamento delle fasi 1



la suddivisione in fasi va fatta in base
all’istruzione più onerosa
non tutte le istruzioni richiedono le stesse
fasi
non tutte le fasi richiedono lo stesso tempo
di esecuzione (si pensi alla lettura di un
operando tramite registro o mediante
indirizzamento indiretto)
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
110
3.1 Pipeline
sbilanciamento delle fasi 2
Fetch  1 2 3 4 5 6
1 2 3 4 5 6
Decode  ............
Read M  ....................
1
Execute  ....................... 1
2
3
X
Write M  ................................. 1
4
2
X
3
2
4
X
3 4
X : tempi di attesa dovuti allo sbilanciamento delle fasi
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
111
3.1 Pipeline
sbilanciamento delle fasi 3
Possibili soluzioni allo sbilanciamento:
 scomposizione in più sottofasi
– i tempi di overhead diventano consistenti

duplicare gli esecutori delle fasi più lunghe
e farli operare in parallelo
– le CPU più recenti hanno più ALU intere e
un’ALU Floating Point
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
112
3.1 Pipeline
problemi strutturali
Problemi:
– Se servono più risorse interne, prima o poi la
tecnologia ci permetterà di duplicarle
– il vero collo di bottiglia è l’accesso alle risorse
esterne (memoria): anche 3 accessi per ciclo
Possibili soluzioni:
– suddividere le memorie
– introdurre fasi non operative
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
113
3.1 Pipeline
dipendenza dei dati 1

può succedere che un dato modificato nella
fase di execute venga utilizzato dalla fase di
lettura dell’istruzione successiva
INC [0123]
CMP [0123],AL
F1
D1
F2
Evoluzione delle architetture
RM1
D2
E1
WM1
RM2
Architettura degli elaboratori 1 - A. Memo
E2
WM2
114
3.1 Pipeline
dipendenza dei dati 2
Soluzioni:
 introduzione di fasi non operative
 individuazione del richio di dipendenza dei
dati e prelievo del dato direttamente all’uscita
dell’ALU (data forwarding)
 risoluzione a livello di compilatore
 riordino delle istruzioni (pipeline scheduling)
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
115
3.1 Pipeline
dipendenza dai controlli 1
Tutte le istruzioni che modificano l’Instruction Pointer (salti condizionati e non,
chiamate a e ritorni da procedure, interrupt)
mettono in crisi il pipeline.
La fase di fetch successiva carica l’istruzione
seguente, che non è detto sia quella giusta.
Queste istruzioni purtroppo sono circa il 30%.
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
116
3.1 Pipeline
dipendenza dai controlli 2
Soluzioni:
 mettere in stallo il pipeline fino a quando non
si è calcolato l’indirizzo della prossima istruzione (pessima efficienza, massima semplicità)
 individuare
prima possibile le istruzioni
dannose e anticiparne l’esecuzione, eventualmente con apposita logica di controllo
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
117
3.1 Pipeline
dipendenza dai controlli 3
Soluzioni per salti condizionati:
 ipotizzare che non ci sia il salto: se va bene
siamo andati avanti, altrimenti facciamo
ripartire il pipeline con il nuovo indirizzo
– alcune istruzioni modificano lo stato della CPU
fin dalle prime fasi: in tal caso bisogna ripristinare tutto come era prima (squashing)

usare due pipeline, e proseguire parallelamente nelle due possibilità
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
118
3.1 Pipeline
dipendenza dai controlli 4
Prevedere l’esito del salto:
 staticamente
– il compilatore aggiusta i controlli, e li organizza in
modo che i salti siano meno probabili

dinamicamente
– costruire una tabella storica dei salti effettuati
(Branch Target Buffer) e utilizzarla statisticamente,
campi BranchAddress, TargetAddress ed History
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
119
3.1 Pipeline
superpipeline


Suddivisione delle singole fasi lunghe T in n
sottofasi distinte, e far partire fino ad n
istruzioni nella medesima fase, ad intervalli
regolari T/n
prevedere n pipeline che possano operare in
parallelo
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
120
3.1 Pipeline
pipeline superscalare



riuscire ad eseguire più di un’istruzione per
ciclo macchina duplicando gli esecutori più
onerosi e facendoli operare in parallelo
tipicamente più ALU intere ed una Floating
Point
richiede un control path notevole per
sfruttare al meglio queste risorse
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
121
3.1 Pipeline
dynamic scheduling



In run-time la CPU riordina le istruzioni al
fine di ottimizzare l’utilizzo del pipeline, e
poi riaggiusta l’ordine corretto dei risultati
maggiore è il blocco di istruzioni riordinate,
migliore è l’efficienza e aumenta la complessità del control path e del datapath
viene detta anche out-of-order execution
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
122
3.1 Pipeline
scoreboard
L’esecuzione simultanea di più istruzioni su più
unità esecutive si implementa con:
 scoreboard
– tabella centralizzata che tiene conto delle istruzioni da eseguire e delle risorse a disposizione

reservation station
– tecnica distribuita di inoltro delle singole istruzioni alle varie unità bufferizzate
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
123
3.2 Gerarchia di memoria
tecnologie di memorizzazione
L’ideale sarebbe avere una memoria molto
grande, molto veloce e molto economica.
tecnologia
registro
cache on-chip
SRAM
DRAM
disk
CD-ROM
tape
Evoluzione delle architetture
velocità
1 - 2 nS
3 - 10 nS
20 - 50 nS
60 - 250 nS
5 - 20 mS
100 - 500 mS
1 - molti S
dimensioni
16 - 256 B
1 - 32 KB
32 - 512 KB
1 - 1024 MB
1 - 512 GB
600 - 1200 MB
superiori
Architettura degli elaboratori 1 - A. Memo
124
3.2 Gerarchia di memoria
prestazioni CPU/memoria

1000
100
10

1
1980
Evoluzione delle architetture
1990
2000
le CPU hanno avuto
un notevole aumento
di prestazioni dovuto a
innovazioni tecnologiche e architetturali
(..., pipeline, cache, ...)
le
memorie
sono
migliorate solo grazie
alla tecnologia
Architettura degli elaboratori 1 - A. Memo
125
3.2 Gerarchia di memoria
proprietà dei programmi


proprietà statiche (dal file sorgente)
proprietà dinamiche (in esecuzione)
– linearità dei riferimenti
gli indirizzi sono molto spesso consecutivi
– località dei riferimenti
 località
spaziale
gli indirizzi vicini sono molto probabili
 località
temporale
gli indirizzi più recenti hanno mggiore probabilità
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
126
3.2 Gerarchia di memoria
legge del 90/10
Un programma utilizza mediamente il
90 % del suo tempo di esecuzione per
effettuare
un
numero
limitato
di
istruzioni, pari a circa il 10 % di tutte
quelle che lo compongono.
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
127
3.2 Gerarchia di memoria
dividi et impera
Conviene suddividere la memoria in due parti:
 livello 1: molto veloce e di dimensioni
contenute (per il costo), in cui mettere le
informazioni più probabili (cache)

livello 2: molto grande e più lenta (per il
costo), in cui mettere tutte le informazioni
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
128
3.2 Gerarchia di memoria
organizzazione gerarchica




suddivisione della memoria in livelli
il livello superiore (il primo) è utilizzato
direttamente dalla CPU
ogni livello è più veloce, di dimensioni
minori e di costo per byte superiore del
livello sottostante
ogni livello contiene anche tutte le
informazioni del livello sottostante
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
129
3.2 Gerarchia di memoria
schema concettuale
livello inferiore
memoria
CPU
cache
centrale
livello
superiore
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
130
3.2 Gerarchia di memoria
suddivisione in blocchi



per implementare l’organizzazione gerarchica
è necessario suddividere la memoria in blocchi
la dimensione di un blocco è la minima
quantità indivisibile di informazioni che
vengono ricopiate nel livello sovrastante
l’indirizzo di un’informazione sarà composto
dall’indirizzo del blocco e da quello del dato
all’interno del blocco
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
131
3.2 Gerarchia di memoria
hit e miss
Quando la CPU richiede un’informazione,
questa può essere presente o meno in cache:
 hit, o successo, deve avere una probabilità
molto elevata (90 - 95 %)
 miss, o fallimento
In caso di miss si deve avviare una procedura di
scambio (swap) dati con il livello sottostante.
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
132
3.2 Gerarchia di memoria
tempo medio di accesso
Il tempo medio di accesso ad un dato in memoria vale:
Ta = Th + Tm (1-Ph)
Ta = tempo medio di accesso (average memory-access time)
Th = tempo di accesso ad un dato presente in cache
Tm = tempo medio di accesso ad un dato non in cache
Ph = probabilità di hit
N.B.= Tm e Ph dipendono dalla dimensione del blocco
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
133
3.2 Gerarchia di memoria
tecnica generale
- suddivisione della memoria centrale in blocchi
- dimensionamento della cache in multiplo di blocchi
- la CPU emette un indirizzo:
hit 
- il dato viene fornito immediatamente alla CPU
miss 
- la cache richiede al dato al suo livello inferiore
- in cache viene memorizzato un intero blocco
- viene fornito il dato alla CPU
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
134
3.2 Gerarchia di memoria
problematiche

organizzazione della cache e tecniche di
allocazione

individuazione di hit o miss

rimpiazzo dei blocchi

congruenza dei blocchi
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
135
3.2 Gerarchia di memoria
direct mapping 1
Associazione diretta (direct mapping)

ogni blocco di un certo gruppo di blocchi del
livello inferiore può essere allocato solo in un ben
preciso blocco (line o slot) del livello superiore
gruppo 0 gruppo 1 gruppo 2 gruppo 3
N gruppi
da M line
ciascuno
livello
inferiore
livello
superiore
Evoluzione delle architetture
gruppo N-1
N line
ILI = Indirizzo Livello inferiore
ILS = Indirizzo Livello Superiore
Architettura degli elaboratori 1 - A. Memo
} ILS = ILI mod N
136
3.2 Gerarchia di memoria
direct mapping 2
Vantaggi
 semplicità di traduzione da indirizzo ILI
(memoria) a indirizzo ILS (cache)
 determinazione veloce di hit o miss
Svantaggi
 necessità di contraddistinguere il blocco
presente nella line (introduzione del Tag)
 swap continui per dati di blocchi adiacenti
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
137
3.2 Gerarchia di memoria
fully associative 1
Associazione completa (fully associative)

ogni blocco del livello inferiore può essere allocato in un qualsiasi blocco (line o slot) del livello
superiore
livello
inferiore
N blocchi
livello
superiore
Evoluzione delle architetture
M line
Architettura degli elaboratori 1 - A. Memo
138
3.2 Gerarchia di memoria
fully associative 2
Alla cache composta da M blocchi viene
affiancata una tabella di M elementi,
contenenti il numero di blocco (tag) posto
nella line corrispondente.
Vantaggi

massima efficienza di allocazione
Svantaggi

calcolo dell’indirizzo ILS e verifica hit/miss molto onerosi
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
139
3.2 Gerarchia di memoria
n-way set associative 1
Associazione a gruppi (n-way set associative)

ogni blocco di un certo insieme di blocchi del livello
inferiore può essere allocato liberamente in un ben preciso
gruppo di blocchi del livello superiore
insieme 0 inisieme 1 insieme 2 insieme 3
insieme N-1
M insiemi
da K line
ciascuno
livello
inferiore
livello
superiore
Evoluzione delle architetture
M gruppi
da N line
ciascuno
nell’esempio N=2
2-way set associative
Architettura degli elaboratori 1 - A. Memo
140
3.2 Gerarchia di memoria
n-way set associative 2
Alla cache composta da M gruppi di N line
ciascuno vengono affiancate M tabelle di N
elementi ciascuna, contenenti i tag che
contraddistinguono i blocchi posti nelle line
corrispondenti (tecnica più diffusa).
Si ottiene una adeguata efficienza di allocazione a
fronte di una sopportabile complessità di ricerca
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
141
3.2 Gerarchia di memoria
rimpiazzo dei blocchi
Quando la cache è piena, quale blocco mi
conviene sostituire ?


Random, occupazione omogenea dello spazio
Last recently Used, coerente con la località temporale
rimpiazzo casuale
% Pmiss
rimpiazzo LRU
N-way
2
4
8
2
4
8
16 KB
5,69
5,29
4,96
5,18
4,67
4,39
64 KB
2,01
1,66
1,53
1,88
1,54
1,39
256 KB
1,17
1,13
1,12
1,15
1,13
1,12
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
142
3.2 Gerarchia di memoria
il problema della scrittura 1
La scrittura dei dati determina incoerenza tra
il blocco in cache e quello nei livelli inferiori.
 write through
– scrittura contemporanea in cache e nel livello di
memoria inferiore: aumento di traffico per
frequenti scritture nel medesimo blocco, ma in
entrambi i livelli i dati sono sempre coerenti. Si
utilizzano buffer di scrittura asincroni verso la
memoria.
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
143
3.2 Gerarchia di memoria
il problema della scrittura 2

write back
– scrittura differenziata in memoria inferiore solo
quando il blocco di cache viene rimpiazzato:
necessità di riconoscere se ci sono state
operazioni di scrittura nel nlocco, ottimizzazione
del traffico ma periodi di non coerenza
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
144
3.2 Gerarchia di memoria
ridurre la probabilità di miss 1


miss di primo accesso, non riducibile
miss di capacità insufficiente, quando in cache
non trovano posto tutti i blocchi del programma
– cache più ampie e blocchi più estesi (*)

miss di interferenza, quando nell’n-associative
dobbiamo rimpiazzare un blocco e ci sono ancora
blocchi non occupati
– aumentare la dimensione di N
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
145
3.2 Gerarchia di memoria
ridurre la probabilità di miss 2



realizzare le tabelle con memorie associative,
per ridurre i tempi di ricerca
distinguere tra cache dati e cache istruzioni
ottimizzare tramite compilatori
– posizionamento accurato delle procedure ripetitive
– fusione di vettori in strutture
– loop interchange
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
146
3.2 Gerarchia di memoria
quantificazione
dimensione del blocco
4 - 128 Byte
durata hit
1 - 4 cicli machina
durata miss
8 - 32 cicli (ed anche di più)
(tempo di accesso)
(6-10 cicli)
(tempo di trasferimento) (2 - 22 cicli)
percentuale miss
1% - 20%
dimensione cache
1 - 256 KByte
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
147
3.2 Gerarchia di memoria
memoria DRAM 1



Dynamic Random Access Memory
memorizzazione assegnata a componenti
capacitivi
richiedono un ciclo di refresh ogni 8-10 mS
organizzazione interna 2D e indirizzo diviso
– Raw Access Strobe
– Column Access Strobe
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
148
3.2 Gerarchia di memoria
memoria DRAM 2
anno
1980
1983
capacità
64 Kb
256 Kb
ciclo di lettura
250 ns
220 ns
1986
1989
1992
1 Mb
4 Mb
16 Mb
190 ns
165 ns
145 ns
1995
64 Mb
120 ns
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
149
3.2 Gerarchia di memoria
memoria principale 1
CPU
Organizzazione diretta
cache
Il Bus tra CPU e cache ha
la stessa dimensione di
quello tra cache e memoria
principale
memoria
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
150
3.2 Gerarchia di memoria
memoria principale 2
CPU
32 bit
Organizzazione estesa
multiplexer
cache cache cache
128 bit
memoria
Evoluzione delle architetture
Multiplexer tra CPU
ed N cache e bus ampio
tra le N cache e
la memoria principale
Architettura degli elaboratori 1 - A. Memo
151
3.2 Gerarchia di memoria
memoria principale 3
CPU
Organizzazione
interleaving
Bus normale tra CPU
cache
e cache e collegamento
a memoria interlacciata
tra cache e moduli
modulo modulo modulo
di memoria DRAM
0
1
2
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
152
3.2 Gerarchia di memoria
evoluzione delle DRAM 1


tempo di accesso: tempo necessario alla
memoria per accedere alla cella indirizzata
tempo di lettura: tempo necessario alla CPU
per acquisire un dato dal DB, dal momento
in cui emette l’indirizzo in AB
tempo di lettura
tempo di accesso
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
153
3.2 Gerarchia di memoria
evoluzione delle DRAM 2

memorie interleaving: accesso continuato
alla memoria senza aspettare la conclusione
della lettura
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
154
3.2 Gerarchia di memoria
evoluzione delle DRAM 3

memorie page mode: accesso continuato
alla stessa colonna di memoria (multiple
RAW access) (ciclo di lettura=100ns,
column select=20ns)
Evoluzione delle architetture
Architettura degli elaboratori 1 - A. Memo
155