Introduzione

Performance
●
Come si definisce il concetto di “performance”?
–
Tempo di esecuzione di un programma
●
Wall-clock time
–
●
CPU time
–
–
–
tiene conto solo del tempo in cui il programma usa la CPU
user time + system time
throughput
●
–
tiene conto anche di I/O e delle attese dovute alla condivisione
delle risorse con altri programmi
numero di task/transazioni eseguiti per unità di tempo
…
performance = 1 / CPU time
194
CPU time
CPU time = #istruzioni  CPI  Clock cycle
●
#istruzioni: numero di istruzioni nel programma
●
CPI: numero medio di cicli di clock per istruzione
●
Clock cycle: durata di un ciclo di clock
●
Per ridurre il tempo di CPU si può intervenire su ognuno
dei fattori
–
I fattori non sono indipendenti!
195
Cosa influenza il CPU time
●
Algoritmo e qualità di implementazione
●
Linguaggio di programmazione
●
Compilatore
●
Instruction Set Architecture
●
Processore
●
Memoria
196
Benchmark
●
Insieme di programmi scelti per la valutazione della
performance
SPECINT2006 for Intel Core i7 920
197
Pipeline
198
Pipelining
●
L'implementazione di un datapath basata su un singolo
ciclo di clock è inefficiente
–
il ciclo di clock deve essere sufficiente ad eseguire l'intera
istruzione più lenta
●
lw
Instruction memory → register file → ALU → data memory → register file
●
–
CPI = 1, ma ciclo di clock molto alto
–
può andare bene solo per instruction set molto semplici
Il pipelining è una tecnica implementativa in cui le
esecuzioni di più istruzioni sono sovrapposte nel tempo
199
Esempio
●
Basato su una lavanderia
–
lava, asciuga, piega, metti via
–
in un dato momento ogni carico usa una risorsa diversa
●
Speed-up
–
4 carichi
8 / 3.5 = 2.3
–
N carichi
2N / (0,5N + 1,5) → 4
= numero di passi (stadi)
●
Aumenta il numero di carichi
eseguiti per unità di tempo
(throughput), non la durata
di un singolo carico (latenza)
200
MIPS pipeline
●
Cinque stadi (stage):
–
IF: fetch dell'istruzione dalla memoria
–
ID: decodifica dell'istruzione e lettura dei registri
–
EX: esecuzione dell'operazione or calcolo dell'indirizzo
–
MEM: accesso alla memoria dati
–
WB: scrittura del risultato in un registro
Rappresentazione semplificata del datapath
Lettura dell'istruzione
Lettura di $t0 e $t1
Scrittura di $s0
201
Pipelined datapath
●
Il flusso è da sinistra a destra, con due eccezioni:
–
scrittura del prossimo PC
–
scrittura del risultato dell'istruzione in un registro
202
Rappresentazioni grafiche
203
Pipeline performance
●
●
●
Assumiamo i tempi seguenti per i diversi stadi:
–
100ps per la lettura o scrittura dei registri
–
200ps per gli altri stadi
Ciclo di clock = 200ps, corrispondente allo stadio più
lungo
Confronto tra implementazioni single-cycle e pipeline di
alcune istruzioni rappresentative
Instr
Instr fetch Register
read
ALU op
Memory
access
Register Single-cycle
write
time
lw
200ps
100 ps
200ps
200ps
100ps
sw
200ps
100 ps
200ps
200ps
R-format 200ps
100 ps
200ps
beq
100 ps
200ps
200ps
800ps
700ps
100ps
600ps
500ps
204
Pipeline performance (lw)
●
Lo speed-up (massimo) è 4 e non 5
–
●
I passi non sono perfettamente bilanciati
Notare che la latenza di una singola istruzione aumenta
–
e per alcune istruzioni alcuni stadi sono sprecati
205
Pipelining e ISA
●
L'ISA MIPS favorisce il pipelining
–
Tutte le istruzioni sono a 32 bit
●
–
Pochi formati per le istruzioni e regolari
●
–
L'indirizzo può essere calcolato nel terzo passo e l'accesso alla
memoria effettuato nel quarto
Allineamento degli accessi in memoria
●
–
Decode e lettura registri in un ciclo
Accesso alla memoria solo con istruzioni di load e store
●
–
Più facile implementare sia fetch che decode in un ciclo
L'accesso alla memoria avviene in un ciclo
Ogni istruzione MIPS scrive al più un risultato e lo fa
nell’ultimo stadio della pipeline
206
Criticità (hazard)
●
●
●
●
Situazioni che impediscono la partenza dell'istruzione
successiva nel ciclo successivo
Criticità strutturali: una risorsa necessaria all'esecuzione
di una istruzione è occupata
Criticità sui dati: un'istruzione dipende da un valore non
ancora disponibile
Criticità sul controllo: una decisione di controllo dipende
dal risultato di un'istruzione non ancora conclusa
207
Criticità strutturale
●
●
Dovuta a conflitti nell'uso di una risorsa
Esempio: la memoria contiene sia dati sia istruzioni, ma
può essere acceduta una sola volta per ciclo di clock
–
lw o sw in MEM confligge con una istruzione successiva in IF
–
in tal caso l'istruzione in IF dovrebbe essere bloccata (stall)
per un ciclo
●
–
●
inserimento di una “bolla” (bubble) nella pipeline
notare che non ci possono essere una lw e una sw
contemporaneamente in MEM
La criticità è risolvibile usando due memorie
–
o due cache
–
una per le istruzioni, una per i dati
208
Criticità sui dati
●
Una istruzione dipende dal risultato prodotto da una
istruzione precedente
209
Criticità sui dati
●
Si risolve inserendo bolle nella pipeline in attesa che il
risultato sia disponibile nel register file
–
●
l'inserimento può avvenire sia ad opera del processore
stesso che del compilatore (istruzione nulla nop)
Oppure...
210
Criticità sui dati
●
Oppure si usa il forwarding (o bypassing)
–
si creano ulteriori connessioni nel datapath così da rendere
un risultato disponibile non appena prodotto
–
senza aspettare che venga salvato nel registro di
destinazione
211
Criticità sui dati
●
●
Non sempre il forwarding evita tutti gli stalli
–
un risultato potrebbe non essere stato ancora calcolato
quando è richiesto
–
caso load-use
Uso contemporaneo di bolle e forwarding
212
Ordine delle istruzioni e stalli
●
Gli stalli possono essere in alcuni casi evitati con un
opportuno riordinamento delle istruzioni da eseguire
a = b + e;
c = b + f;
stallo
stallo
lw $t1,
lw $t2,
add $t3,
sw $t3,
lw $t4,
add $t5,
sw $t5,
0($t0)
4($t0)
$t1, $t2
12($t0)
8($t0)
$t1, $t4
16($t0)
13 cicli
lw $t1,
lw $t2,
lw $t4,
add $t3,
sw $t3,
add $t5,
sw $t5,
0($t0)
4($t0)
8($t0)
$t1, $t2
12($t0)
$t1, $t4
16($t0)
11 cicli
213
Ordine delle istruzioni e stalli
●
Il riordinamento può essere fatto
–
dal compilatore
●
–
dal processore
●
●
●
deve conoscere l'architettura per cui genera codice
out-of-order execution
in genere associato a tecniche predittive-speculative (vedi
oltre)
Il riordinamento (ovviamente) non deve modificare il
significato di un programma
–
as-if
214
Criticità sul controllo
●
Una decisione di controllo dipende dal risultato di
un'istruzione non ancora conclusa
215
Criticità sul controllo
add
beq
lw
...
40: or
●
$4,
$1,
$3,
$5, $6
$2, 40
300($0)
$7, $8, $9
La decisione se eseguire il salto o meno avviene nello
stadio MEM
–
bisogna aspettare 3 cicli di clock dopo l'inizio
dell'istruzione beq prima di decidere la prossima istruzione
da caricare
–
necessario inserire 3 bolle → 3 stalli
216
Criticità sul controllo
●
Prima soluzione:
–
aggiungendo ulteriore logica, si può anticipare il controllo
della condizione di due stadi, portandolo nello stadio ID
–
un solo stallo
caso branch taken
217
Criticità sul controllo
●
Seconda soluzione
–
tiriamo a indovinare → branch prediction
–
stallo solo se la predizione è sbagliata
prevediamo che il salto
non venga eseguito
predizione sbagliata
218
Branch prediction
●
●
Static branch prediction
–
Basato sul comportamento tipico dei salti
–
Esempio: il salto all'indietro (es: loop) è preso
–
Esempio: il salto in avanti (es: if) non è preso
Dynamic branch prediction
–
L'hardware misura il comportamento recente effettivo
●
●
es: può registrare la storia recente di ogni branch
–
Assume che il comportamento futuro sia simile
–
Se la predizione è sbagliata, la pipeline va pulita, si carica
l'istruzione corretta e si aggiorna la storia
As-if
219
2-bit branch predictor
●
Cambia decisione solo dopo due decisioni sbagliate
220
Criticità sul controllo
●
Terza soluzione
–
branch-delay slot
–
l'istruzione dopo l'istruzione di
branch viene sempre eseguita
–
si possono riordinare le istruzioni,
inserendo in quella posizione una
istruzione indipendente dal branch
stesso
●
se tale istruzione non esiste → nop
221
Registri della pipeline
●
L'output di ogni stadio viene salvato in registri e diventa
input per lo stadio successivo
–
viene salvato tutto quello che serve in uno stadio
successivo
222
IF per load e store
223
ID per load e store
224
EX per load
225
MEM per load
226
WB per load
227
WB per load
che registro viene scritto?
228
WB per load (corretto)
il registro di destinazione viene “portato avanti” e usato durante WB
229
MEM per store
230
WB per store
231
Esempio
stato della pipeline
al CC 5
232
Controllo della pipeline
●
Classifichiamo i segnali di controllo del datapath a
seconda dei vari stadi in cui sono utilizzati
233
Controllo della pipeline
234
Controllo della pipeline
●
●
Come nel caso del datapath a ciclo singolo, anche nel caso
della pipeline i segnali di controllo sono derivati
dall'istruzione
I segnali di controllo sono calcolati in ID ma portati avanti
fin dove necessario
235
Controllo della pipeline
236
Gestione del forwarding
●
I registri sono passati lungo la pipeline
–
●
I registri operandi per l'ALU, nello stadio EX, sono dati da
–
●
es.: ID/EX.RegisterRs è il registro per Rs salvato nel pipeline
register ID/EX
ID/EX.RegisterRs, ID/EX.RegisterRt
Si ha una criticità sui dati quando vale una delle seguenti
condizioni:
–
EX/MEM.RegisterRd = ID/EX.RegisterRs
–
EX/MEM.RegisterRd = ID/EX.RegisterRt
–
MEM/WB.RegisterRd = ID/EX.RegisterRs
–
MEM/WB.RegisterRd = ID/EX.RegisterRt
forward da
EX/MEM
pipeline reg
forward da
MEM/WB
pipeline reg
237
Gestione del forwarding
●
Inoltre l'istruzione più avanzata deve essere una
istruzione che scriverà in un registro
–
EX/MEM.RegWrite, MEM/WB.RegWrite
238

Download Report